Paridad de una permutación

Compartir Imprimir Citar
Permutaciones de 4 elementos

Las permutaciones extrañas tienen un fondo verde o naranja. Los números en la columna 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 X (i.e. the bijective functions from X a X) caer en dos clases de igual tamaño: el incluso permutaciones y el permutaciones extrañas. Si algún pedido total X está arreglado, paridad ()rareza o Incluso) 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,Sí. de X tales que x. Sí. y σ()x) σ()Sí.).

El signo, firma o signo de una permutación σ se denomina sgn(σ ) y se define como +1 si σ es par y −1 si σ es impar. La firma define el carácter alternativo del grupo simétrico Sn. 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 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 σ 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.

Ejemplo

Considere la permutación σ del conjunto {1, 2, 3, 4, 5} definido por σ σ ()1)=3,{displaystyle sigma (1)=3,} σ σ ()2)=4,{displaystyle sigma (2)=4,} σ σ ()3)=5,{displaystyle sigma (3)=5,} σ σ ()4)=2,{displaystyle sigma (4)=2,} y σ σ ()5)=1.{displaystyle sigma (5)=1.} En la notación de una línea, esta permutación se denota 34521. Se puede obtener de la permutación de identidad 12345 por tres transposiciones: primero cambiar los números 2 y 4, luego cambiar 3 y 5, y finalmente cambiar 1 y 3. Esto demuestra que la permutación dada σ Es extraño. Siguiendo el método del artículo de notación del ciclo, esto podría ser escrito, componiendo de izquierda a derecha, como

σ σ =()1234534521)=()135)()24)=()13)()35)()24).{displaystyle sigma {beginpmatrix}={}{beginpmatrix}{} {pmatrix}} {begin}} {begin}{}{} {begin} {pmatrix}} {begin}{pmatrix} {} {beginpmatrix} {} {begin} {}trix}{}{p}trix}trix} {} {p}trix} {begin}{}trix}{p}trix}{p]

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 uniforme. 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 (solo) con un número impar de transposiciones.

Las siguientes reglas se derivan directamente de las reglas correspondientes sobre la suma de números enteros:

De estos se sigue que

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

Sgn: Sn → {−1, 1}

que asigna a cada permutación su firma es un homomorfismo de grupo.

Además, vemos que las permutaciones pares forman un subgrupo de Sn. Este es el grupo alterno en n letras, indicado por An. Es el núcleo del homomorfismo sgn. 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 Sn ).

Si n > 1, entonces hay tantas permutaciones pares en Sn como impares; 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 estos dos mapas son inversos entre sí).

Un ciclo es par si y solo si su duración es impar. Esto se sigue de fórmulas como

()abcde)=()de)()ce)()be)()ae)o()ab)()bc)()cd)()de).{fnMicrosoft Sans Serif}(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 determinada 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 igual a la paridad de la permutación.

Cada permutación de orden impar debe ser par. La permutación (1 2)(3 4) en A4 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:

Prueba 1

Vamos σ ser una permutación en un dominio clasificado S. Cada permutación puede ser producida por una secuencia de transposiciones (2 intercambios de elementos). Que la siguiente sea una de tales descomposición

σ = T1 T2... Tk

Queremos mostrar 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 extraño 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 (ii+dEn el set {1,...i,...i+dComo composición de 2d−1 transposiciones adyacentes por recursión a d:

  • El caso base d=1 es trivial.
  • En el caso recurrente, primero reescribir (i, i+dComo...i, i+1) (i+1, i+d)i, i+1). Entonces reescribir repetidamente (i+1, i+d) como transposiciones adyacentes.

Si nos descomponemos de esta manera cada una de las transposiciones T1...Tk arriba, tenemos la nueva descomposición:

σ = A1 A2... Am

donde todo el A1...Am están adyacentes. Además, la paridad de m es lo mismo que el 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 se cambia cuando se compone con una transposición adyacente.

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

Así podemos definir la paridad de σ ser el de su número de transposiciones constituyentes en cualquier descomposición. Y esto debe estar de acuerdo con la paridad del número de inversiones bajo cualquier orden, como se ha visto anteriormente. Por lo tanto, las definiciones son de hecho bien definidas y equivalentes.
Prueba 2

Una prueba alternativa utiliza el polinomio Vandermonde

<math alttext="{displaystyle P(x_{1},ldotsx_{n})=prod _{iP()x1,...... ,xn)=∏ ∏ i.j()xi− − xj).{displaystyle P(x_{1},ldotsx_{n}=prod _{i obtenidosj}(x_{i}-x_{j}).}<img alt="{displaystyle P(x_{1},ldotsx_{n})=prod _{i

Así que, por ejemplo, en el caso n = 3, tenemos

P()x1,x2,x3)=()x1− − x2)()x2− − x3)()x1− − x3).{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

Sgn⁡ ⁡ ()σ σ )=P()xσ σ ()1),...... ,xσ σ ()n))P()x1,...... ,xn).{displaystyle operatorname {sgn}(sigma)={frac {P(x_{sigma (1)},ldotsx_{sigma (n)}}{P(x_{1},ldotsx_{n}}}}}}}}}}

Desde el polinomio P()xσ σ ()1),...... ,xσ σ ()n)){displaystyle P(x_{sigma (1)},dotsx_{sigma (n)}} tiene los mismos factores P()x1,...... ,xn){displaystyle P(x_{1},dotsx_{n}} excepto por sus signos, sigue ese sgn(σ) es +1 o −1. Además, si σ y τ son dos permutaciones, vemos que

Sgn⁡ ⁡ ()σ σ τ τ )=P()xσ σ ()τ τ ()1)),...... ,xσ σ ()τ τ ()n)))P()x1,...... ,xn)=P()xσ σ ()1),...... ,xσ σ ()n))P()x1,...... ,xn)⋅ ⋅ P()xσ σ ()τ τ ()1)),...... ,xσ σ ()τ τ ()n)))P()xσ σ ()1),...... ,xσ σ ()n))=Sgn⁡ ⁡ ()σ σ )⋅ ⋅ Sgn⁡ ⁡ ()τ τ ).{fnMicrosoft Sans Serif}
Puesto que con esta definición es más claro que cualquier transposición de dos elementos tiene firma −1, realmente recuperamos la firma como se define anteriormente.
Prueba 3

Un tercer enfoque utiliza la presentación del grupo Sn en términos de generadores τ1,... τn−1 y relaciones

  • τ τ i2=1{displaystyle tau _{i}{2}=1}para todos i
  • τ τ iτ τ i+1τ τ i=τ τ i+1τ τ iτ τ i+1{displaystyle tau _{i} {tau} - ¿Qué? ¿Qué? - ¿Qué? ¿Qué? ¿Qué? para todos i. n− 1
  • τ τ iτ τ j=τ τ jτ τ i{displaystyle tau _{i} {tau} ¿Qué? si Silencioi− − jSilencio≥ ≥ 2.{displaystyle Silencio. 2.}
[Aquí el generador τ τ i{displaystyle tau _{i} 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 duración uniforme siempre resultará en una palabra de duración incluso después de usar las relaciones, y de forma similar para palabras de fuerza extraña. Por lo tanto, es inequívoco llamar a los elementos de Sn representado por palabras "even" de longitud, y los elementos representados por palabras "odd".
Prueba 4

Recuerda que un par x, Sí. tales que x. Sí. y σ()x) σ()Sí.) se llama inversión. Queremos demostrar que el conteo de las inversiones tiene la misma paridad que el conteo de los swaps de 2 elementos. Para ello, podemos demostrar que cada cambio cambia la paridad del conteo de las inversiones, sin importar qué dos elementos se están intercambiando y qué permutación ya se ha aplicado. Supongamos que queremos cambiar el iy el jelemento. Claramente, las inversiones formadas por i o j con un elemento fuera de [i, j] no se verá afectado. Para el n = j − i − 1 elementos dentro del intervalo ()i, j), asumir vi de ellos forma inversiones con i y vj de ellos forma inversiones con j. Si i y j son intercambiados, esos vi inversiones con i se han ido, pero n − vi se forman inversiones. El conteo de inversiones i Así pues, n − 2vi, que tiene la misma paridad n.

Del mismo modo, el conteo de las inversiones j ganado también tiene la misma paridad que n. Por lo tanto, el conteo de las inversiones obtenidas por ambos combinados tiene la misma paridad que 2n o 0. Ahora si contamos las inversiones obtenidas (o perdidas) intercambiando el iy el jt elemento, podemos ver que este intercambio cambia la paridad del conteo de las inversiones, ya que también agregamos (o restar) 1 al número de inversiones obtenidas (o perdidas) para el par (i,j).

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

Considere los elementos que son emparedados por los dos elementos de una transposición. Cada uno se encuentra completamente por encima, completamente por debajo, o entre los dos elementos de transposición.

Un elemento que está completamente por encima o completamente por debajo no contribuye al recuento de inversión cuando se aplica la transposición. Elementos entre contribuyentes 2{displaystyle 2}.

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

Otras definiciones y pruebas

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

Sea σ = (i1 i2... ir+1)(j1 j 2... js+1)...(ℓ1 ℓ2... ℓu+1) sea la descomposición única de σ en ciclos disjuntos, que pueden estar compuestos en cualquier orden porque conmutan. Un ciclo (a b c... x y z) con k + 1 puntos siempre se pueden obtener componiendo k transposiciones (2-ciclos):

()abc...... xSí.z)=()ab)()bc)...... ()xSí.)()Sí.z),{displaystyle (a b c dots x y z)=(a b) c)dots (x y)(y z),}

así que llame a k el tamaño del ciclo, y observe 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 k1 + k2 +... + km transposiciones, donde k i es el tamaño del iésimo ciclo. El número N(σ) = k1 + k 2 +... + km se llama el discriminante de σ, y también se puede calcular como

nmenos el número de ciclos disyuntivos en la descomposición deσ σ {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

()ab)()ac1c2...... cr)()bd1d2...... ds)=()ac1c2...... crbd1d2...... ds){fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {f} {fnMicros}}fnMicros}f}f}f}fnMicrosoft SanscfnMicrosoft SanscfnMicrosoft Sans}fnMicrosoft Sans}fnMicrosoft Sans}fnMicrosoft Sans}fnMis}fnMicrosoft Sans)}}fnMicrosoft Sans}fnMicrosoft Sans}fnMicrosoft Sans}fnMicrosoft Sanscf}fnMicrosoft Sans}fnMicrosoft Sans}fn,

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

()ab)()ac1c2...... crbd1d2...... ds)=()ac1c2...... cr)()bd1d2...... ds){fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans}fnMicrosoft Sans Serif}fnMicrosoft Sans Serif}fnMicrosoft Sans Serif}fnMicrosoft Sans Serif} {fnMicrosoft Sans}fnMicrosoft Sans Serif}fnMicrosoft Sans Serif}fnMicrosoft Sans Serif} {fnMicrosoft Sans}fnMicrosoft Sans Serif} {fnMicrosoft Sans {fnMicrosoft Sans Serif}fnMicrosoft Sans}fnMicrosoft Sans Serif}}.

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 σ = t1t2... tr es una descomposición arbitraria de una permutación σ en transposiciones, aplicando las r transposiciones t1{displaystyle T_{1} después t2 después... después tr después de la identidad (cuyo N es cero) observar que N()σ) y r tienen la misma paridad. Definiendo la paridad σ como la paridad N()σ), una permutación que tiene una descomposición de longitud uniforme es una permutación uniforme y una permutación que tiene una descomposición de longitud extraña es una permutación extraña.

Observaciones

Generalizaciones

La paridad se puede generalizar a los grupos de Coxeter: uno 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) proporciona un mapa de signos generalizado.