Paridad de una permutación

La propiedad en la 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 la 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 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 ) . ${\displaystyle \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]

Ejemplo

Consideremos la permutación σ del conjunto {1, 2, 3, 4, 5} definida por y En notación unifilar , esta permutación se denota 34521. Puede obtenerse 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 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 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{ or }}(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.

Equivalencia de las dos definiciones

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 1

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

σ = T1T2 ... _Tk​ ​​_​

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

Cada transposición puede escribirse 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).

En general, 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 recursión 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 manera cada una de las transposiciones T ₁  ...  T _k anteriores, obtenemos la nueva descomposición:

σ = A ₁ A ₂ ... A _m

donde todos los A ₁ ... A _m 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 más o una menos que τ . En otras palabras, la paridad del número de inversiones de una permutación se invierte cuando se compone con una transposición adyacente.

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

Podemos definir la paridad de σ como la del número de transposiciones que la constituyen en cualquier descomposición. Y esto debe coincidir con la paridad del número de inversiones bajo cualquier orden, como se vio anteriormente. 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}).}$

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

Como el polinomio tiene los mismos factores que 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, recuperamos efectivamente la firma tal 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}$  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 "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

Recordemos que un par x , y tal que x < y y σ ( x ) > σ ( y ) se llama inversión. Queremos mostrar que el conteo de inversiones tiene la misma paridad que el conteo de intercambios de 2 elementos. Para hacer eso, podemos mostrar que cada intercambio cambia la paridad del conteo de inversiones, sin importar qué dos elementos se estén intercambiando y qué permutación ya se haya aplicado. Supongamos que queremos intercambiar el i ésimo y el j ésimo elemento. Claramente, las inversiones formadas por i o j con un elemento fuera de [ i , j ] no se verán afectadas. Para los n = j − i − 1 elementos 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 i y j se intercambian, esas v _i inversiones con i desaparecen, pero se forman n − v _i inversiones. El recuento de inversiones i obtenidas es entonces n − 2 v _i , que tiene la misma paridad que n .

De manera similar, el conteo de inversiones j ganadas también tiene la misma paridad que n . Por lo tanto, el conteo 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 el j , podemos ver que este intercambio cambia la paridad del conteo de inversiones, ya que también sumamos (o restamos) 1 al número de inversiones ganadas (o perdidas) para el par (i,j) .

Nótese 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 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}$

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 ú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 σ .

Generalizaciones

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.

Véase también

• El rompecabezas de los quince es una aplicación clásica
• 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. Goodman, 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). 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.