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 cualquier ordenación total de X es fija, la paridad ( imparidad o paridad ) de una permutación 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 ) . ${\estilo de visualización \sigma}$

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 más general de Levi-Civita ( ε _σ ), que se define para todas las funciones de X a X , y tiene valor cero para funciones 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  σ se puede definir a partir de su descomposición en el producto de transposiciones como

signo( σ ) = (−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 y En notación unifilar , esta permutación se denota 34521. Se puede obtener a partir de la permutación identidad 12345 mediante tres transposiciones: primero intercambiemos los números 2 y 4, luego intercambiemos 3 y 5, y finalmente intercambiemos 1 y 3. Esto demuestra que la permutación dada σ es impar. Siguiendo el método del artículo de notación cíclica , esto se podría escribir, componiendo de derecha a izquierda, como ${\displaystyle \sigma (1)=3,}$ ${\displaystyle \sigma (2)=4,}$ ${\displaystyle \sigma (3)=5,}$ ${\displaystyle \sigma (4)=2,}$${\displaystyle \sigma (5)=1.}$

${\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 puede obtenerse 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 puede obtenerse mediante (solo) un número impar de transposiciones.

Las siguientes reglas se derivan directamente de las reglas correspondientes sobre la suma de números 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 par e impar es impar.

De esto se deduce que

• La inversa de cada permutación par es par.
• La inversa 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 la función

signo: S _n → {−1, 1} 

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

Además, vemos que las permutaciones pares forman un subgrupo de S _n . ^[1] Este es el grupo alterno 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 un coconjunto 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 funciones son inversas entre sí.) ^[3]

Un ciclo es par si y sólo 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 determinada permutación es par o impar, se escribe la permutación 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 es construir la matriz de permutación correspondiente y calcular su determinante. El valor del determinante es el mismo que 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 la recíproca no es cierta en general.

En esta sección se presentan 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 orden); o
• como la paridad del número de transposiciones en las que se puede descomponer σ (como sea que 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}$  Para 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 representa la transposición ( i , i + 1) .] Todas las relaciones mantienen la longitud de una palabra igual o la cambian por dos. 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 lo tanto, es inequívoco llamar a los elementos de S _n representados por palabras de longitud par "pares", y a los elementos representados por palabras de longitud impar "impares".${\displaystyle \tau _{i}}$

Prueba 5

Considere los elementos que están intercalados entre los dos elementos de una transposición. Cada uno se encuentra completamente encima, completamente debajo o entre los dos elementos de transposición.

Un elemento que se encuentra 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 2}$

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

La paridad de una permutación de puntos también está codificada en su estructura de ciclo . ${\displaystyle n}$

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

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

Así que 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 diferentes ciclos 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, al aplicar las r transposiciones 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. ${\displaystyle t_{1}}$

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 σ , incluidos los casos en los que todos los ciclos son transposiciones.
• Esta prueba 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 los 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: la aplicación a la mecánica cuántica . Dover Classics of Science and Mathematics. Dover Publications. ISBN 978-0-486-43798-9.