Prueba de que la paridad de la permutación es bien definida ¿alternativa?

Question

Aprendí el siguiente teorema acerca de las propiedades de permutación de Gallian del Contemporáneo Álgebra Abstracta.

Cuando traté de reconstruir la prueba de mí, he encontrado que esto es suficiente para demostrar el siguiente lema:

Si $\epsilon=\beta_1\beta_2\cdots\beta_r$ donde $\beta$'s $2$-ciclos, a continuación, $r$ es incluso.

El original de la prueba de este lema, se utiliza la siguiente propiedad de clave de producto de $\beta_1\beta_2$:

El producto siempre puede ser expresado en uno de los siguientes formularios en la parte izquierda: $$\begin{align}(ab)(ab)&=\epsilon\\ (ab)(ac)&=(bc)(ab)\\ (ab)(cd)&=(cd)(ab)\\ (ab)(bc)&=(bc)(ac)\end{align}$$

La prueba del lema se basa en la propiedad y la inducción matemática. Me pareció muy duro para recordarle de la propiedad, así que me puse como un ejercicio para dar otra prueba. Sin embargo, no tengo idea de cómo hacerlo.

Así que aquí está mi pregunta:

¿Alguien conoce una alternativa a la prueba de los lexema o el teorema?

Answer 1

He aquí una bonita prueba que utiliza el grupo de acciones.

Deje $x_1,\ldots,x_n$ $n$ incógnitas, y considerar la posibilidad de $$\Delta= \prod_{1\leq i\lt j\leq n} (x_j-x_i).$$

Por ejemplo, para $n=4$, tendríamos $$\Delta = (x_2-x_1)(x_3-x_1)(x_4-x_1)(x_3-x_2)(x_4-x_2)(x_4-x_3).$$

Dada una permutación $\sigma\in S_n$, definir una función $f_{\sigma}\colon\{\Delta,-\Delta\}$ dejando $$f_{\sigma}(\Delta) = \prod_{1\leq i\lt j\leq n} (x_{\sigma(j)}-x_{\sigma(i)}),$$ y $f_{\sigma}(-\Delta)=-f_{\sigma}\Delta$.

Tenga en cuenta que desde $\sigma$ es una permutación, $f_{\sigma}(\Delta)=\Delta$ o $f_{\sigma}(\Delta) = -\Delta$. También, si $\sigma,\rho$ son dos permutaciones, a continuación,$f_{\sigma}\circ f_{\rho} = f_{\sigma\rho}$, como es fácil de comprobar.

Ahora, vamos a considerar lo que una transposición $\tau=(a,b)$,$\Delta$. Sin pérdida de generalidad, decir $a\lt b$.

Los factores de $(x_j-x_i)$ ni $i$ ni $j$ igual a $a$ ni $b$ son invariables.

Para las parejas con exactamente un índice en $\{a,b\}$, tenemos dos clases: aquellos en los que el otro índice es de entre $a$$b$, y aquellos en los que el otro índice es que no se entre $a$$b$.

Si el otro índice es de entre $a$$b$, $x_j-x_a$ es enviado a $-(x_b-x_j)$ $x_b-x_j$ es enviado a $-(x_j-x_a)$; los dos cambios de signo se cancelan uno al otro.

Si el otro índice es mayor que $b$, $x_j-x_a$ $x_j-x_b$ son intercambiados, con ninguna señal de los cambios.

Si el otro índice es menor que $a$, $x_a-x_i$ $x_b-x_i$ son intercambiados, con ninguna señal de los cambios.

Por último, el factor de $x_b-x_a$ es enviado a $-(x_b-x_a)$.

En resumen, si $\tau$ es una transposición, a continuación,$f_{\tau}(\Delta)=-\Delta$, $f_{\tau}(-\Delta)=\Delta$.

Ahora tome una permutación arbitraria $\sigma$, y se expresa como un producto de transposiciones en dos formas diferentes: $$\sigma = \tau_1\cdots \tau_r = \rho_1\cdots\rho_s.$$ Entonces $$f_{\sigma}(\Delta) = f_{\tau_1\cdots\tau_r}(\Delta) = f_{\tau_1}\circ\cdots\circ f_{\tau_r}(\Delta) = (-1)^r\Delta$$ y $$f_{\sigma}(\Delta) = f_{\rho_1\cdots\rho_s}(\Delta) = f_{\rho_1}\circ\cdots\circ f_{\rho_s}(\Delta) = (-1)^s\Delta.$$ Por lo tanto, $(-1)^r\Delta = (-1)^s\Delta$, lo $r$ $s$ tienen la misma paridad: tanto extraño, o ambos inclusive.

Answer 2

Aquí está mi favorito de la prueba. Representan una permutación de $n$ letras de la siguiente manera. Escribir los números de $1$ $n$en una fila y, a continuación, escribir en otra fila un poco por debajo de la primera fila. Ahora conecte los números en la parte superior de los números en la parte inferior por las curvas que representan la permutación. Por lo tanto, si $\sigma$ es la permutación, conecte $i$ $\sigma(i)$por una curva. Para mayor comodidad, dibujar las curvas de modo que se entrecruzan con las otras en la transversal de el doble de puntos. (Es decir, los vectores tangente a cada curva cuando se cruzan no son paralelas, y en ningún momento tiene más de dos curvas que pasen a través de él.) Ahora me reclaman que la paridad de la permutación de los partidos de la paridad en el número de intersecciones. Hay dos pasos para mostrar esto. La primera es demostrar que la intersección número está bien definido modulo 2. La segunda es mostrar que coincide con el número de transposiciones. Para ver que está bien definido módulo 2, tenga en cuenta que sólo tenemos que demostrar que la intersección entre dos curvas bien definidas modulo 2. De hecho, si la permutación de los swaps de los extremos de los arcos, luego de que intersecta un número impar de veces y si la permutación no invertir el orden de las estaciones, a continuación, los arcos se cruzan un número par de veces. (Esto es debido a que un arco local desconecta el avión, así que para ir de un lado al otro, tengo que cruzar el arco, y si lo hago dos veces, estoy de vuelta en el lado empecé con.) Así que tenemos una buena definición de intersección número modulo 2. Ahora escribo $\sigma$ como producto de transposiciones $\tau_j$, y, en consecuencia, de la pila de las imágenes para cada una de las $\tau_j$ para obtener una imagen de $\sigma$. A continuación, sólo tenemos que verificar que el número de cruces en algunos de imagen estándar de $\tau_j$ es impar, que es fácil. Todos los arcos son rectas, excepto dos, que forman una X-forma. La forma X tiene un punto de intersección en el centro y cruza todas las de la otra recta arcos en pares. Por lo que es una extraña intersección número.

Si estás familiarizado con la trenza de grupo, te darás cuenta de que esto es como la trenza de grupo, sólo el cruce de información se ha caído. Quizás por eso me atrae como un topologist. En cualquier caso, he encontrado que esta es una manera rápida de calcular la paridad de la permutación en la práctica.

Estrechamente relacionados con la prueba, pero sin buenas fotos, es decir que la paridad de la permutación es el número de inversiones modulo 2, donde con una inversión de un par de $i<j$ donde $\sigma (i)>\sigma(j)$.

Answer 3

Personalmente, me gusta la siguiente prueba que arrastra algunos de los molestos tecnicismos para algunos bastante elementales de álgebra lineal.

Considere la posibilidad de la acción de la $S_n$ $\mathbb R^n$ donde $\sigma$ hechos por permuting la base de los elementos, es decir, si $v=\sum a_ie_i$ donde $\{e_i\}$ es el estándar de base para $\mathbb R^n$, entonces cada $\sigma\in S_n$ determina una transformación lineal $M_\sigma(v)=\sum a_i e_{\sigma(i)}$. Por lo tanto, tenemos un mapa de $\rho\colon S_n\to GL_n(\mathbb R)$, el grupo de los invertible $n\times n$ valor real de las matrices.

Esta $\rho$ es en realidad un grupo de homomorphism desde $M_\sigma M_\tau=M_{\sigma\tau}$ , por definición, de las transformaciones lineales $M_\sigma$.

Ahora, el factor determinante a su vez es un grupo de homomorphism $GL_n(\mathbb R)\to\{-1,1\}$, siendo este último un grupo bajo la multiplicación, así que lo componen con $\rho$ tenemos un grupo de homomorphism $\det\circ\rho\colon S_n\to\{-1,1\}$.

Pensando en el determinante como una alternancia de forma multilineal (función en $n$ vectores, lineal en cada variable, que voltea signo cuando dos de sus entradas se activan), podemos ver que $\det\circ\rho(\sigma)=\det(M_\sigma)=\det(e_{\sigma(1)}, e_{\sigma(2)},\dots, e_{\sigma(n)})$. Ahora bien, el hecho de que los relatos de los vectores de la base invierte el signo del determinante nos dice que los relatos son enviados por nuestro mapa a $-1$, mientras que el mapa de identidad se envía a $1$. Desde el determinante es multiplicativo, entonces $\sigma=\tau_1\dots\tau_m$ donde $\tau_i$ son transposiciones se envía a $(-1)^m$ que sólo depende de la paridad de $m$, por lo tanto $m$ es siempre o siempre impar.

Answer 4

Hay un montón de posibles pruebas, he aquí uno basado en el ciclo de descomposición de la permutación. Nos muestran que si multiplicamos una permutación por una transposición de la derecha (es decir, la primera aplicación de la transposición), entonces la paridad en el número de ciclos que siempre cambia.

El número de ciclos en la identidad de permutación es el mismo que el número de puntos de $n$ (ya que hay que $n$ de los ciclos). Así, por $n$, incluso, si se multiplica un número par de transposiciones, que siempre se obtiene una permutación con un número de ciclos; si se multiplica un número impar de transposiciones, que siempre se obtiene una permutación con un número impar de ciclos. Para $n$ impares de la asociación es inversa.

Supongamos que la transposición es $(12)$. Hay dos casos: o $1,2$ pertenecen al mismo ciclo o no.

Caso 1: $1,2$ pertenecen al mismo ciclo de $(1\alpha2\beta)$. A continuación, en la nueva permutación el ciclo se divide a $(1\beta)(2\alpha)$.

Caso 2: $1,2$ pertenecen a dos diferentes ciclos de $(1\alpha)(2\beta)$. A continuación, en la nueva permutación de los dos ciclos de unirse a $(1\beta2\alpha)$.

En el primer caso obtenemos un ciclo, en el segundo que perdemos un ciclo. Así que en ambos casos, la paridad de los cambios.

---

Aquí es de otro, de Herstein del libro. Para $i<j$ y una permutación $\pi$, vamos a $\psi(\pi,i,j)$ $1$ si $\pi(i)>\pi(j)$, e $0$ lo contrario. Deje $\Psi(\pi) = \sum_{i<j} \psi(\pi,i,j)$. Por lo $\Psi(\pi)$ el número de índices de $i<j$ tal que $\pi(i) > \pi(j)$. Para la identidad que tenemos $\Psi(e) = 0$.

Deje $k < l$$\tau = \pi (k l)$, por lo que el $\tau(t) = \pi(t)$ $t \neq k,l$, $\tau(k) = \pi(l)$ y $\tau(l) = \pi(k)$. Desde $k,l$ son sólo cambió las entradas, a fin de considerar el cambio en $\Psi$ sólo tenemos que considerar pares de $i,j$ en el que uno de los índices (por lo menos) es $k$ o $l$.

Caso 1: Pares de $i<k$$i<l$. Es fácil ver que $\psi(\pi,i,k) = \psi(\tau,i,l)$$\psi(\pi,i,l) = \psi(\tau,i,k)$. Por lo que la contribución a $\Psi$ es el mismo.

Caso 2: Pares de $k<i$$l<i$. Similar a la del Caso 1.

Caso 3: Pares de $k<i$$i<l$. Esta vez $\psi(\pi,k,i) = 1 - \psi(\tau,i,l)$$\psi(\pi,i,l) = 1 - \psi(\tau,k,i)$. En total, $$ \psi(\pi,k,i) + \psi(\pi,i,l) = 2 - (\psi(\tau,k,i) + \psi(\tau,i,l)). $$

Caso 4: El par $k<l$. Claramente $\psi(\pi,k,l) = 1 - \psi(\tau,k,l)$.

Sólo Caso 4 cambios en la paridad de $\Psi$, y podemos deducir que la multiplicación por una transposición cambios en la paridad de $\Psi$. Por lo $\pi$ es un producto de un número par de transposiciones iff $\Psi(\pi)$ es incluso.