Paridad de una permutación

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

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 $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 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 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 ${displaystyle sigma (1)=3,}$ ${displaystyle sigma (2)=4,}$ ${displaystyle sigma (3)=5,}$ ${displaystyle sigma (4)=2,}$ y ${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

{displaystyle sigma ={begin{pmatrix}1&2&3&4&5\3&4&5&2&1end{pmatrix}}={begin{pmatrix}1&3&5end{pmatrix}}{begin{pmatrix}2&4end{pmatrix}}={begin{pmatrix}1&3end{pmatrix}}{begin{pmatrix}3&5end{pmatrix}}{begin{pmatrix}2&4end{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 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:

la composición de dos permutaciones es incluso
la composición de dos permutaciones extrañas es incluso
la composición de una extraña y una permutación uniforme es extraño

De estos se sigue que

el inverso de cada permutación es incluso
el inverso de cada permutación extraña es extraño

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

Sgn: S n \to {-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 S_n. Este es el grupo alterno en n letras, indicado por A_n. 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 A_n (en S_n).

Si n > 1, entonces hay tantas permutaciones pares en S_n como impares; 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 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

{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 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 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 que σ se puede descomponer a (cuando elijamos descomponerlo).

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

σ = T₁ T₂... T_k

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 T₁...T_k arriba, tenemos la nueva descomposición:

σ = A₁ A₂... A_m

donde todo el A₁...A_m 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

{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)},ldotsx_{sigma (n)})}{P(x_{1},ldotsx_{n})}}.}

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

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

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 S_n en términos de generadores τ₁,... τ_n−1 y relaciones

$tau_i^2 = 1$ para todos i
$tau_i^{}tau_{i+1}tau_i = tau_{i+1}tau_itau_{i+1}$ para todos i. n− 1
$tau_i^{}tau_j = tau_jtau_i$ si ${displaystyle |i-j|geq 2.}$

[Aquí el generador

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 S_n 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 v_i de ellos forma inversiones con i y v_j de ellos forma inversiones con j. Si i y j son intercambiados, esos v_i inversiones con i se han ido, pero n − v_i se forman inversiones. El conteo de inversiones i Así pues, n − 2v_i, 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$ .

Como la transposición misma suministra

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$ puntos también está codificado en su estructura de ciclo.

Sea σ = (i₁ i₂... i_r+1)(j₁ j ₂... j_s+1)...(ℓ₁ ℓ₂... ℓ_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):

{displaystyle (a b cdots 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, 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 el 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 $t_{1}$ después t₂ después... después t_r 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

Un examen cuidadoso del argumento anterior muestra que r ≥ N()σ), y desde cualquier descomposición de σ en ciclos cuyos tamaños suman r puede expresarse como una composición 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 que todos los ciclos son transposiciones.
Esta prueba no introduce un orden (posiblemente arbitrario) en el conjunto de puntos sobre los cuales σ actos.

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.

Contenido relacionado

Más resultados...