Paridad de una permutación

Propiedad en teoría de grupos

Permutaciones de 4 elementos

Las permutaciones impares tienen un fondo verde o naranja. Los números de la columna de la derecha son los números de inversión (secuencia A034968 en el OEIS ), que tienen la misma paridad que la 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 ( impar 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 ) . ${\displaystyle \sigma }$

El signo , firma o signum de una permutación  σ se denota como sgn( σ ) y se define como +1 si σ es par y −1 si σ es impar. La firma define el carácter alterno 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 todos los mapas de X a X , y tiene valor cero para mapas no biyectivos .

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

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

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

sgn( σ ) = (−1) ^m

donde m es el número de transposiciones en la descomposición. Aunque tal 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]

Ejemplo

Considere la permutación σ del conjunto {1, 2, 3, 4, 5} definido 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 intercambie los números 2 y 4, luego intercambie 3 y 5, y finalmente intercambie 1 y 3. Esto muestra que la permutación dada σ es impar. Siguiendo el método del artículo de notación cíclica , esto podría escribirse, 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.

Propiedades

La permutación de identidad es una permutación par. ^[1] Una permutación par se puede obtener como la composición de un número par (y sólo un número par) de intercambios (llamados transposiciones ) de dos elementos, mientras que una permutación impar se puede obtener mediante (sólo) 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 estos se deduce que

• el inverso de toda permutación par es par
• el inverso de toda 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

signo: S _norte → {−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 el compuesto de dos permutaciones impares es par, pero forman una clase lateral de An ₍ en S _n ). ^[5]

Si n > 1 , entonces hay tantas permutaciones pares en S _n como impares; ^[3] en consecuencia, _An 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 duración es impar. Esto se desprende de fórmulas como

${\displaystyle (a\ b\ c\ d\ e)=(d\ e)(c\ e)(b\ e)(a\ e){\text{ or }}(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 la permutación como un producto de ciclos disjuntos. La permutación es impar si y sólo 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 lo contrario no es cierto en general.

Equivalencia de las dos definiciones

Esta sección presenta pruebas de que la paridad de una permutación σ se puede definir de dos formas 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 (sin importar cómo decidamos descomponerlo).

Prueba 1

Sea σ una permutación en un dominio clasificado S. Cada permutación puede producirse mediante una secuencia de transposiciones (intercambios de 2 elementos). Sea la siguiente una de esas descomposición

σ = T ₁ T ₂ ... T _k

Queremos demostrar que la paridad de k es igual a la paridad del número de inversiones de σ .

Cada transposición se puede escribir como producto de un número impar de transposiciones de elementos adyacentes, por ejemplo

(2 5) = (2 3) (3 4) (4 5) (4 3) (3 2).

Generalmente, podemos escribir la transposición ( i  i+d ) en el conjunto {1,..., i ,..., i+d ,...} como la composición de 2 d −1 transposiciones adyacentes por recursividad en d :

• El caso base d=1 es trivial.

• En el caso recursivo, primero reescribe ( i , i+d ) como ( i , i +1) ( i +1, i+d ) ( i , i +1). Luego reescribe recursivamente ( i +1, i+d ) como transposiciones adyacentes.

Si descomponemos de esta forma cada una de las transposiciones T ₁  ...  T _k anteriores, obtenemos la nueva descomposición:

σ = Un ₁ Un ₂ ... Un _metro

donde todos los A ₁ ... Am _son adyacentes. Además, la paridad de m es la misma que la de k .

Esto es un hecho: para toda permutación τ y transposición adyacente a, aτ tiene una inversión menos o una más que τ . En otras palabras, la paridad del número de inversiones de una permutación cambia cuando se compone con una transposición adyacente.

Por tanto, la paridad del número de inversiones de σ es precisamente la paridad de m , que también es la paridad de k . Esto es lo que nos propusimos demostrar.

Por tanto, podemos definir la paridad de σ como la de su número de transposiciones constituyentes en cualquier descomposición. Y esto debe coincidir con la paridad del número de inversiones bajo cualquier orden, como se vio arriba. Por lo tanto, las definiciones están bien definidas y son equivalentes.

Prueba 2

Una prueba alternativa utiliza el polinomio de Vandermonde.

${\displaystyle P(x_{1},\ldots ,x_{n})=\prod _{i<j}(x_{i}-x_{j}).}$

Entonces, por ejemplo, en el caso n = 3 , tenemos

${\displaystyle P(x_{1},x_{2},x_{3})=(x_{1}-x_{2})(x_{2}-x_{3})(x_{1}-x_{3}).}$

Ahora, para una permutación dada  σ de los números {1, ...,  n }, definimos

${\displaystyle \operatorname {sgn}(\sigma )={\frac {P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}{P(x_{1},\ldots ,x_{n})}}.}$

Dado que el polinomio tiene los mismos factores excepto por sus signos, se deduce que sgn( σ ) es +1 o −1. Además, si σ y τ son dos permutaciones, vemos que ${\displaystyle P(x_{\sigma (1)},\dots ,x_{\sigma (n)})}$ ${\displaystyle P(x_{1},\dots ,x_{n})}$

${\displaystyle {\begin{aligned}\operatorname {sgn}(\sigma \tau )&={\frac {P(x_{\sigma (\tau (1))},\ldots ,x_{\sigma (\tau (n))})}{P(x_{1},\ldots ,x_{n})}}\\[4pt]&={\frac {P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}{P(x_{1},\ldots ,x_{n})}}\cdot {\frac {P(x_{\sigma (\tau (1))},\ldots ,x_{\sigma (\tau (n))})}{P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}}\\[4pt]&=\operatorname {sgn}(\sigma )\cdot \operatorname {sgn}(\tau ).\end{aligned}}}$

Dado que con esta definición queda además claro que cualquier transposición de dos elementos tiene firma −1, de hecho recuperamos la firma como se definió anteriormente.

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 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. 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 lo tanto, no es ambiguo 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. ${\displaystyle \tau _{i}}$

Prueba 4

Recuerde que un par x , y tal que x < y y σ ( x ) > σ ( y ) se llama inversión. Queremos demostrar que el recuento de inversiones tiene la misma paridad que el recuento de swaps de 2 elementos. Para hacer eso, podemos demostrar que cada intercambio cambia la paridad del recuento de inversiones, sin importar qué dos elementos se intercambien y qué permutación ya se haya aplicado. Supongamos que queremos intercambiar el elemento i y j . Claramente, las inversiones formadas por i o j con un elemento fuera de [ i , j ] no se verán afectadas. Para los elementos n = j − i − 1 dentro del intervalo ( i , j ) , supongamos que v _i de ellos forman inversiones con i y v _j de ellos forman inversiones con j . Si se intercambian i y j , esas inversiones v _i con i desaparecen, pero se forman n − v _i inversiones. El recuento de inversiones i obtenidas es, por tanto, n − 2 vi _, que tiene la misma paridad que n .

De manera similar, el recuento de inversiones j obtenidas también tiene la misma paridad que n . Por lo tanto, el recuento de inversiones ganadas por ambos combinados tiene la misma paridad que 2 n o 0. Ahora, si contamos las inversiones ganadas (o perdidas) al intercambiar el elemento i y j , podemos ver que este intercambio cambia el paridad del recuento de inversiones, ya que también sumamos (o restamos) 1 al número de inversiones ganadas (o perdidas) para el par (i,j) .

Tenga en cuenta que inicialmente, cuando no se aplica ningún intercambio, el recuento de inversiones es 0. Ahora obtenemos la equivalencia de las dos definiciones de paridad de una permutación.

Prueba 5

Considere los elementos que están intercalados por 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 está completamente por encima o completamente por debajo 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í 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}$

Otras definiciones y pruebas

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} 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),}$

así que llame a k el tamaño del ciclo y observe que, según 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, aplicando las r transposiciones después de t ₂ después ... después de t _r después de la identidad (cuyo N es cero) observamos que N ( σ ) yr tienen la misma paridad. Al definir la paridad de σ como la paridad de N ( σ ), una permutación que tiene una descomposición en longitud par es una permutación par y una permutación que tiene una descomposición en 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 sumen 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 σ .

Generalizaciones

La paridad se puede generalizar a 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.

Ver también

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

Notas

1. Jacobson (2009), pág. 50.
2. Rotman (1995), pág. 9, Teorema 1.6.
3. Jacobson (2009), pág. 51.
4. Buen hombre, pág. 116, definición 2.4.21
5. Meijer y Bauer (2004), pág. 72

Referencias

• 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). Una 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 . Clásicos de Dover de ciencias y matemáticas. Publicaciones de Dover. ISBN 978-0-486-43798-9.