cada permutación es par o impar, pero no ambas

Question

Cómo podemos demostrar que cada permutación es par o impar, pero no ambas ...... No puedo llegar a una prueba para este ..... Puede alguien darme la prueba...

Gracias de antemano...

Answer 1

Una forma es definir el signo de una permutación $\sigma$ utilizando el polinomio $\Delta = \Pi (x_i-x_j)$ con $1\le i < j \le n$ .

Es fácil ver que $\sigma(\Delta) = \Pi (x_{\sigma(i)}-x_{\sigma(j)})$ satisface $\sigma(\Delta)=\pm\Delta$ . Ahora define el signo por $sign(\sigma)=\frac{\Delta}{\sigma(\Delta)}$

Con un poco más de trabajo se puede demostrar que esta función es un homomorfismo de grupos, y que en las transposiciones devuelve -1. Por lo tanto, si $\sigma=\tau_1\cdots\tau_k$ es una forma de escribir $\sigma$ como producto de transposiciones, tenemos $sign(\sigma)=(-1)^k$ y así para las permutaciones pares (permutaciones cuyo signo es 1) k debe ser siempre par, y para las permutaciones Impares (cuyo signo es -1) debe ser siempre impar.

Answer 2

Aquí se ofrece una prueba: Una nota histórica sobre la paridad de las permutaciones T. L. Bartlow, American Mathematical Monthly Vol. 79, No. 7 (Ago. - Sep., 1972), pp. 766-769.

Aquí hay un esquema de la prueba de Bartlow (coincide con la prueba dada en la respuesta de Ted).

• Dividir $S_n$ (el grupo simétrico en $n$ letras) en dos clases según la paridad del número de ciclos (los puntos fijos se cuentan como 1-ciclos) en su única descomposición en ciclos disjuntos. [Por ejemplo, en $S_5$ la permutación $(1,2,3)(4)(5)$ tiene 3 ciclos disjuntos].

• Estas clases están por tanto bien definidas y son disjuntas, y la permutación de identidad pertenece exactamente a una clase (ya que se descompone en $n$ ciclos disjuntos, y $n$ es par o impar).

• Demostró que al multiplicar una permutación en una clase por una transposición, resultará una permutación en la otra clase.

• Concluye que las dos clases son, de hecho, los conjuntos de permutaciones pares e Impares en $S_n$ .

(Nota: En versiones anteriores de esta respuesta, califiqué erróneamente esta prueba como defectuosa. De hecho, es una prueba excelente, y no se basa en ninguna función auxiliar ni en conceptos no relacionados).

---

Reclamo las tres "pruebas" de este resultado (actualmente) en wikipedia son incompletos. Comencemos con la observación de que, suponiendo que la permutación de identidad no es una permutación impar, entonces el resultado se sigue con bastante facilidad.

Teorema : Suponiendo que la permutación de identidad no es una permutación impar, entonces todas las permutaciones son pares x o impar.

Prueba : Dejemos que $\sigma$ sea una permutación par y otra impar. Entonces existen transposiciones $t_i$ y $s_j$ tal que \N[\Nsigma=t_1 \\Ncirc t_2 \Ncirc \Ncdots \Nk=s_1 \Ncirc s_2 \Ncirc \Ncdots s_m\] donde $k$ es par y $m$ es impar. Obsérvese que \N[\Nsigma^{-1}=s_m \\Ncirc s_{m-1} \Ncirc \Ndots \Ncirc s_1.\N-]

Entonces la permutación de identidad $\sigma \circ \sigma^{-1}$ es la permutación impar \\Nde que [t_1 \\Ncirc t_2 \Ncirc t_k \Ncirc s_m \Ncirc s_{m-1} \Ncirc \Ncirc s_1,\N] da una contradicción. Así se completa la demostración del teorema.

El problema es que no podemos suponer sin más que la permutación identidad no es una permutación impar (sí, es una permutación par, pero ¿qué impide que sea también una permutación impar?), no se deduce de la definición y es el caso base de la "inducción". Para demostrarlo, hay que demostrar que la permutación identidad no puede descomponerse en un número impar de transposiciones (sin utilizar el propio teorema).

Sin embargo, podemos deducir del teorema anterior que o bien (a) todas las permutaciones son a la vez pares e Impares o (b) todas las permutaciones son o bien pares x o Impares.

En la wikipedia: La prueba 1 dice que la permutación de identidad es una permutación par (que lo es) y luego asume que la permutación de identidad no es también una permutación impar (esto es análogo a asumir que un conjunto cerrado no es un conjunto abierto). La prueba 2 dice esencialmente que podemos cambiar de signo multiplicando por una transposición (lo que está bien, si sabes a priori que existe alguna permutación que no es par o no impar). La prueba 3 ignora la posibilidad de que una palabra de longitud par sea igual a una palabra de longitud impar.

Keith Conrad también dio una prueba de que la permutación de identidad no es una permutación impar aquí . Tiene casi una página (y es la mayor parte de la prueba del resultado en cuestión).

Answer 3

Basta con demostrar que el producto de un número impar de transposiciones no puede ser la identidad.

Toda permutación de un conjunto finito $S$ es un producto único de ciclos disjuntos en el que cada elemento de $S$ ocurre exactamente una vez (donde incluimos los puntos fijos como 1-ciclos). Sea $p$ sea cualquier permutación de $S$ , dejemos que $(ij)$ sea una transposición ( $i,j \in S$ ), y que $q=p \cdot (ij)$ . Es fácil comprobar que si $i$ y $j$ están en el mismo ciclo en $p$ , entonces ese ciclo se divide en dos en $q$ ; si $i$ y $j$ están en diferentes ciclos en $p$ y luego esos ciclos se funden en uno solo en $q$ . Ciclos de $p$ que no contenga $i$ o $j$ siguen siendo los mismos en $q$ . Por lo tanto, $q$ tiene un ciclo más o uno menos que $p$ lo hace.

Ahora dejemos que $t$ sea cualquier producto de un número impar de transposiciones. Entonces por lo anterior, multiplicando cualquier permutación por $t$ cambia la paridad del número de ciclos en la permutación. Por lo tanto, $t$ no puede ser la identidad.

Answer 4

Esto es exagerado, pero se deduce de los hechos generales sobre los grupos de Coxeter, como se indica aquí . En particular, se deduce del hecho de que $S_n$ tiene presentación $s_i^2 = 1, (s_i s_{i+1})^3 = 1, s_i s_j = s_j s_i, |i - j| \ge 2$ (que se deduce de la fidelidad de la representación geométrica) que el homomorfismo $s_i \to -1$ está bien definida.

Answer 5

Para definir el signo de una permutación $\sigma$ utilizando el polinomio : $$\begin{gathered} A = \left( {{x_1} – {x_2}} \right)\left( {{x_1} – {x_3}} \right)\left( {{x_1} – {x_4}} \right) \cdots \left( {{x_1} – {x_n}} \right) \\ \,\,\,\,\,\,\,\,\,\,\left( {{x_2} – {x_3}} \right)\left( {{x_2} – {x_4}} \right)\left( {{x_2} – {x_5}} \right) \cdots \left( {{x_2} – {x_n}} \right) \\ \,\,\,\,\,\,\,\,\,\,\left( {{x_3} – {x_4}} \right) \cdots \left( {{x_3} – {x_n}} \right) \cdots \cdots \cdots \left( {{x_{n – 1}} – {x_n}} \right) \\ \end{gathered} $$ .

Ahora define el signo por $sign(\sigma)=\frac{A}{|A|}$

Por ejemplo, tomar $$n = 4$$ tenemos $$A = \left( {{x_1} – {x_2}} \right)\left( {{x_1} – {x_3}} \right)\left( {{x_1} – {x_4}} \right)\left( {{x_2} – {x_3}} \right)\left( {{x_2} – {x_4}} \right)\left( {{x_3} – {x_4}} \right)$$

tomando $$\sigma=1423$$ esto puede representar una entrada de $4 \times 4$ matriz $B$ , $b_{11}b_{24}b_{32}b_{43}$ es decir, hacer la permutación en los índices $i,j,k,l$ de las entradas $b_{1i}b_{2j}b_{3k}b_{4l}$

$$A=(1-4)(1-2)(1-3)(4-2)(4-3)(2-3)=12$$

$$sign(\sigma)=\frac{12}{12}=1$$

En general, una transposición $\left( {i,j} \right),\,\,i < j$ tiene los siguientes efectos sobre $A$ .

(i) Cualquier factor que no incluya el sufijo $i$ ni $j$ se mantiene sin cambios.

(ii)Hay n-1 factores de cualquier $x_k$ los términos que implican $i,j$ pueden agruparse en $(x_i-x_j)\times\prod_{m<i}(x_m-x_i)(x_m-x_j) \times \prod_{i<m< j}(x_m-x_j)(x_i-x_m)\times \prod_{j<m}(x_j-x_m)(x_i-x_m)$

(iii) El factor único $\left( {{x_i} – {x_j}} \right)$ cambia su signo.

(iv) Los restantes factores que implican el sufijo $i$ o $j$ pero no ambos pueden agruparse en pares de productos, $ \pm \left( {{x_m} – {x_i}} \right)\left( {{x_m} – {x_j}} \right)$ donde $m \ne i$ o $j$ y dicho producto permanece inalterable cuando ${x_i}$ y ${x_j}$ se intercambian.