Paridad de una permutación

En matemáticas , cuando X es un conjunto finito con al menos dos elementos, las permutaciones de X (es decir, las funciones biyectivas de X a X ) se dividen en dos clases de igual tamaño: las permutaciones pares y las permutaciones impares . Si se fija cualquier orden total de X , la paridad ( imparidad o paridad ) de una permutación${\displaystyle \sigma }$de X se puede definir como la paridad del número de inversiones para σ , es decir, de pares de elementos x , y de X tales que x < y y σ ( x ) > σ ( y ) . 

El signo , signatura o signum de una permutación σ se denota sgn( σ ) y se define como +1 si σ es par y −1 si σ es impar. La signatura define el carácter alternante del grupo simétrico S _n . Otra notación para el signo de una permutación viene dada por el símbolo de Levi-Civita _más general ( εσ ), que se define para todas las aplicaciones de X a X y tiene valor cero para aplicaciones no biyectivas . 

El signo de una permutación se puede expresar explícitamente como

sgn( σ ) = (−1) ^{N ( σ )}

donde N ( σ ) es el número de inversiones en σ . 

Alternativamente, el signo de una permutación σ puede definirse a partir de su descomposición en el producto de transposiciones como 

sgn( σ ) = (−1) ^m

donde m es el número de transposiciones en la descomposición. Aunque dicha descomposición no es única, la paridad del número de transposiciones en todas las descomposiciones es la misma, lo que implica que el signo de una permutación está bien definido . ^{[ 1 ]}

Consideremos la permutación σ del conjunto {1, 2, 3, 4, 5} definida por${\displaystyle \sigma (1)=3,}$${\displaystyle \sigma (2)=4,}$${\displaystyle \sigma (3)=5,}$${\displaystyle \sigma (4)=2,}$y${\displaystyle \sigma (5)=1.}$ En notación de una línea , esta permutación se denota como 34521. Se puede obtener a partir de la permutación identidad 12345 mediante tres transposiciones: primero se intercambian los números 2 y 4, luego el 3 y el 5, y finalmente el 1 y el 3. Esto demuestra que la permutación dada σ es impar. Siguiendo el método del artículo sobre notación cíclica , esto podría escribirse, componiendo de derecha a izquierda, como

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5\\3&4&5&2&1\end{pmatrix}}={\begin{pmatrix}1&3&5\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}={\begin{pmatrix}1&3\end{pmatrix}}{\begin{pmatrix}3&5\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}.}$

Hay muchas otras formas de escribir σ como una composición de transposiciones, por ejemplo

σ = (1 5)(3 4)(2 4)(1 2)(2 3) ,

pero es imposible escribirlo como producto de un número par de transposiciones.

La permutación identidad es una permutación par. ^{[ 1 ]} Una permutación par se puede obtener como la composición de un número par (y solo un número par) de intercambios (llamados transposiciones ) de dos elementos, mientras que una permutación impar se puede obtener mediante (solo) un número impar de transposiciones.

Las siguientes reglas se derivan directamente de las reglas correspondientes sobre la suma de enteros: ^{[ 1 ]}

• La composición de dos permutaciones pares es par.
• La composición de dos permutaciones impares es par.
• La composición de una permutación impar y una par es impar.

De esto se deduce que

• El inverso de toda permutación par es par.
• El inverso de cada permutación impar es impar.

Considerando el grupo simétrico S _n de todas las permutaciones del conjunto {1, ..., n }, podemos concluir que el mapa

sgn: S _n → {−1, 1}

que asigna a cada permutación su signatura es un homomorfismo de grupo . ^{[ 2 ]}

Además, vemos que las permutaciones pares forman un subgrupo de S _n . ^{[ 1 ]} Este es el grupo alternante de n letras, denotado por A _n . ^{[ 3 ]} Es el núcleo del homomorfismo sgn. ^{[ 4 ]} Las permutaciones impares no pueden formar un subgrupo, ya que la composición de dos permutaciones impares es par, pero forman una clase lateral de A _n (en S _n ). ^{[ 5 ]}

Si n > 1 , entonces hay tantas permutaciones pares en S _n como impares; ^{[ 3 ]} en consecuencia, A _n contiene n ! /2 permutaciones. (La razón es que si σ es par, entonces (1 2) σ es impar, y si σ es impar, entonces (1 2) σ es par, y estas dos aplicaciones son inversas entre sí.) ^{[ 3 ]}

Un ciclo es par si y solo si su longitud es impar. Esto se deduce de fórmulas como

${\displaystyle (a\ b\ c\ d\ e)=(d\ e)(c\ e)(b\ e)(a\ e){\text{ o }}(a\ b)(b\ c)(c\ d)(d\ e).}$

En la práctica, para determinar si una permutación dada es par o impar, se escribe como un producto de ciclos disjuntos. La permutación es impar si y solo si esta factorización contiene un número impar de ciclos de longitud par.

Otro método para determinar si una permutación dada es par o impar consiste en construir la matriz de permutación correspondiente y calcular su determinante . El valor del determinante es igual a la paridad de la permutación.

Toda permutación de orden impar debe ser par. La permutación (1 2)(3 4) en A ₄ muestra que lo contrario no es cierto en general.

Esta sección presenta pruebas de que la paridad de una permutación σ puede definirse de dos maneras equivalentes:

• como la paridad del número de inversiones en σ (bajo cualquier ordenamiento); o
• como la paridad del número de transposiciones en las que se puede descomponer σ (sin importar cómo elijamos descomponerlo).

Prueba 3

Un tercer enfoque utiliza la presentación del grupo S _n en términos de generadores τ ₁ , ..., τ _{n − 1} y relaciones

• ${\displaystyle \tau _{i}^{2}=1}$ por todo lo que yo
• ${\displaystyle \tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}}$ para todo i < n − 1  
• ${\displaystyle \tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}}$ si${\displaystyle |i-j|\geq 2.}$

[Aquí el generador${\displaystyle \tau _{i}}$representa la transposición ( i , i + 1) . Todas las relaciones mantienen la longitud de una palabra igual o la modifican en dos. Por lo tanto, comenzar con una palabra de longitud par siempre dará como resultado una palabra de longitud par después de usar las relaciones, y lo mismo ocurre con las palabras de longitud impar. Por consiguiente, es inequívoco llamar "pares" a los elementos de S _n representados por palabras de longitud par, y "impares" a los elementos representados por palabras de longitud impar.

Prueba 5

Consideremos los elementos que se encuentran entre los dos elementos de una transposición. Cada uno se sitúa completamente por encima, completamente por debajo o entre los dos elementos de la transposición.

Un elemento que está completamente arriba o completamente abajo no contribuye en nada al recuento de inversión cuando se aplica la transposición. Los elementos intermedios contribuyen${\displaystyle \pm 2}$.

Como la transposición misma proporciona${\displaystyle \pm 1}$inversión, y todos los demás proporcionan 0 (mod 2) inversiones, una transposición cambia la paridad del número de inversiones.

La paridad de una permutación de${\displaystyle n}$Los puntos también están codificados en su estructura cíclica .

Sea σ = ( i ₁ i ₂ ... i _{r +1} )( j ₁ j ₂ ... j _{s +1} )...( ℓ ₁ ℓ ₂ ... ℓ _{u +1} ) la descomposición única de σ en ciclos disjuntos , que pueden componerse en cualquier orden porque conmutan. Un ciclo ( a b c ... x y z ) que involucra k + 1 puntos siempre se puede obtener componiendo k transposiciones (2-ciclos):

${\displaystyle (a\ b\ c\dots x\ y\ z)=(a\ b)(b\ c)\dots (x\ y)(y\ z),}$

Llamemos k al tamaño del ciclo y observemos que, bajo esta definición, las transposiciones son ciclos de tamaño 1. A partir de una descomposición en m ciclos disjuntos podemos obtener una descomposición de σ en k ₁ + k ₂ + ... + k _m transposiciones, donde k _i es el tamaño del i- ésimo ciclo. El número N ( σ ) = k ₁ + k ₂ + ... + k _m se llama discriminante de σ , y también se puede calcular como

${\displaystyle n{\text{ minus the number of disjoint cycles in the decomposition of }}\sigma }$

si tenemos cuidado de incluir los puntos fijos de σ como 1-ciclos.

Supongamos que se aplica una transposición ( a b ) después de una permutación σ . Cuando a y b están en ciclos diferentes de σ , entonces

${\displaystyle (a\ b)(a\ c_{1}\ c_{2}\dots c_{r})(b\ d_{1}\ d_{2}\dots d_{s})=(a\ c_{1}\ c_{2}\dots c_{r}\ b\ d_{1}\ d_{2}\dots d_{s})}$,

y si a y b están en el mismo ciclo de σ entonces

${\displaystyle (a\ b)(ac_{1}c_{2}\dots c_{r}\ b\ d_{1}\ d_{2}\dots d_{s})=(a\ c_{1}\ c_{2}\dots c_{r})(b\ d_{1}\ d_{2}\dots d_{s})}$.

En cualquier caso, se puede ver que N (( a b ) σ ) = N ( σ ) ± 1 , por lo que la paridad de N (( a b ) σ ) será diferente de la paridad de N ( σ ).

Si σ = t ₁ t ₂ ... t _r es una descomposición arbitraria de una permutación σ en transposiciones, aplicando las r transposiciones${\displaystyle t_{1}}$Después de t ₂ después de ... después de t _r después de la identidad (cuyo N es cero) observe que N ( σ ) y r tienen la misma paridad. Al definir la paridad de σ como la paridad de N ( σ ), una permutación que tiene una descomposición de longitud par es una permutación par y una permutación que tiene una descomposición de longitud impar es una permutación impar.

Observaciones

• Un examen cuidadoso del argumento anterior muestra que r ≥ N ( σ ) , y dado que cualquier descomposición de σ en ciclos cuyos tamaños suman r puede expresarse como una composición de r transposiciones, el número N ( σ ) es la suma mínima posible de los tamaños de los ciclos en una descomposición de σ , incluyendo los casos en los que todos los ciclos son transposiciones.
• Esta demostración no introduce un orden (posiblemente arbitrario) en el conjunto de puntos sobre los que actúa σ .

La paridad se puede generalizar a los grupos de Coxeter : se define una función de longitud ℓ( v ), que depende de una elección de generadores (para el grupo simétrico, transposiciones adyacentes ), y luego la función v ↦ ( − 1) ^{ℓ( v )} da un mapa de signos generalizado.

• El rompecabezas de quince es una aplicación clásica
• El lema de Zolotarev

• Weisstein, Eric W. "Permutación uniforme" . MundoMatemático .
• Jacobson, Nathan (2009). Álgebra básica . Vol.  1 (2.ª  ed.). Dover. ISBN 978-0-486-47189-1.
• Rotman, JJ (1995). Introducción a la teoría de grupos . Textos de posgrado en matemáticas. Springer-Verlag. ISBN 978-0-387-94285-8.
• Goodman, Frederick M. Álgebra: abstracta y concreta . ISBN 978-0-9799142-0-1.
• Meijer, Paul Herman Ernst; Bauer, Edmond (2004). Teoría de grupos: aplicación a la mecánica cuántica . Clásicos de la ciencia y las matemáticas de Dover. Dover Publications. ISBN 978-0-486-43798-9.