Paridad de una permutación

En matemáticas, las permutaciones pueden descomponerse en un producto de transposiciones, es decir, en una sucesión de intercambios de elementos dos a dos.

• Una permutación par es una permutación que puede ser representada por un número par de transposiciones.
• Una permutación impar es una permutación que puede ser representada por un número impar de transposiciones.

La paridad o signatura de una permutación vale 1 si esta es par y -1 si es impar. La aplicación correspondiente a la paridad constituye un homomorfismo de grupos. Es importante en álgebra multilineal, sobre todo en el cálculo de determinantes.

Definición de la paridad

Sea una permutación σ. La definición de la signatura de σ se hace contando las inversiones.

Definición

• Sean i < j dos elementos distintos comprendidos entre 1 y n. Se dice que se tiene una inversión del par {i, j} para σ cuando σ(i) > σ(j).
• Se dice que una permutación es par cuando presenta un número par de inversiones. Se dice impar en el caso contrario.
• La paridad (o signo) de una permutación par es 1 ; la de una permutación impar es –1.

Ejemplo

Sea la permutación

${\begin{pmatrix}1&2&3&4&5\\1&3&5&4&2\end{pmatrix}},$

que deja fijos 1 y 4 y envía el 2 al 3, el 3 al 5 y el 5 al 2. Ningún par que contenga 1 puede ser una inversión puesto que para todo j > 1, σ(j) es distinto de σ(1) = 1, por lo que σ(j) > σ(1). El único par en inversión que contiene 2 es {2, 5} (σ(2) = 3 > 2 = σ(5)). La lista de pares en inversión es {2, 5}, {3, 4}, {3, 5}, {4, 5}. Hay cuatro, así que la permutación es par.

Las transposiciones son impares

Toda transposición es una permutación impar. En efecto notando i y j, i < j, los términos que la transposición intercambia, está transposición se escribirá:

${\begin{pmatrix}1&\dots &i-1&i&i+1&\dots &j-1&j&j+1&\dots \;n\\1&\dots &i-1&j&i+1&\dots &j-1&i&j+1&\dots \;n\end{pmatrix}}.$

Los pares en inversión son los pares de la forma {i, k} con k comprendido entre i + 1 y j y los de la forma {k, j} con k comprendido entre i + 1 et j – 1. En total, hay un número impar de inversiones, de lo que se deduce que la permutación es impar.

Una fórmula para la paridad

Nótese ${\mathcal {P}}$ al conjunto de pares de elementos comprendidos entre 1 y n (en total hay n(n + 1)/2 elementos). La signatura de una permutación σ es:

$\varepsilon (\sigma )=\prod \limits _{i<j}{\frac {\sigma (j)-\sigma (i)}{j-i}}=\prod \limits _{\{i,j\}\in {\mathcal {P}}}{\frac {\sigma (j)-\sigma (i)}{j-i}}.$

Demostración

Denotemos P a este producto. Examinar todas las parejas (i, j) con i < j es lo mismo que examinar todos los pares {i, j}. Para cada uno de ellos, el término que se encuentra en el producto tienes signo negativo si el par está en inversión y positivo en el caso contrario. Esto demuestra que el signo de P es el mismo que el de la paridad. Finalmente, por la biyectividad de σ, los términos σ(j) – σ(i) del numerador son, salvo cambio de signo, los mismos que los j – i del denominador. Esto demuestra que el valor absoluto de P vale 1, lo cual termina la prueba.

Esta fórmula tiene un cierto interés algebraico pero en la práctica no permite un cálculo eficaz de la paridad. En efecto, en comparación con un simple conteo de inversiones, la multiplicación y la división por un cierto número de enteros son más costosas.

Paridad de un producto

Las permutaciones verifican una regla de signo para el producto: el producto de dos permutaciones pares es par, el de dos permutaciones impares es par y el de una permutación par y una permutación impar es impar. Utilizando la paridad, esto se resume en la fórmula

$\varepsilon (\sigma \circ \tau )=\varepsilon (\sigma )\varepsilon (\tau ).$

Demostración

${\begin{aligned}\varepsilon (\sigma \circ \tau )&=\prod _{\{i,j\}\in {\mathcal {P}}}{\frac {(\sigma \circ \tau )(j)-(\sigma \circ \tau )(i)}{j-i}}\\&=\prod _{\{i,j\}\in {\mathcal {P}}}\left({\frac {\sigma (\tau (j))-\sigma (\tau (i))}{\tau (j)-\tau (i)}}\right)\left({\frac {\tau (j)-\tau (i)}{j-i}}\right)\\&=\prod _{\{i,j\}\in {\mathcal {P}}}{\frac {\sigma (j)-\sigma (i)}{j-i}}\prod _{\{i,j\}\in {\mathcal {P}}}{\frac {\tau (j)-\tau (i)}{j-i}}\\&=\varepsilon (\sigma )\varepsilon (\tau ).\end{aligned}}$ En el segundo factor del segundo miembro, se reconoce directamente una signatura. En el primero, es necesario establecer {i', j'} = {τ(i), τ(j)} ; donde se reconoce igualmente una signatura.

En términos algebraicos : la signatura es un morfismo de grupos del grupo simétrico $({\mathfrak {S}}_{n},\circ )$ en el grupo de dos elementos ({–1, 1}, ×). El subgrupo formado por el núcleo de este morfismo forma el grupo alternado de permutaciones pares. Finalmente, la permutación inversa de $\sigma ,\,\,\sigma ^{-1},$ tiene la misma paridad que $\sigma$.

$\varepsilon (\sigma ^{-1})=\varepsilon (\sigma )$

Demostración

$1=\varepsilon (1_{{\mathfrak {S}}_{n}})=\varepsilon (\sigma \circ \sigma ^{-1})=\varepsilon (\sigma )\,\varepsilon (\sigma ^{-1})\Rightarrow \varepsilon (\sigma ^{-1})={\frac {1}{\varepsilon (\sigma )}}=\varepsilon (\sigma )$

Cálculo de la paridad

Como corolarios de los resultados precedentes se tiene que

• una permutación es par si y solo si puede ser expresada como el producto de un número par de transposiciones;
• una permutación es impar si y solo si puede ser expresada como el producto de un número impar de transposiciones.

El cálculo de la paridad a través de la descomposición en producto de transposiciones es mucho más eficaz que la aplicación de la definición inicial; en efecto, para una permutación de ${\mathfrak {S}}_{n}$, esta descomposición requiere como máximo n – 1 operaciones, en lugar de las n(n – 1)/2 operaciones que se requieren por la definición. De estos dos corolarios y de la descomposición de un ciclo en trasposiciones se deduce que los ciclos de longitud par son permutaciones de paridad impar, y viceversa.

Ejemplos

• La identidad es una permutación par.
• Una transposición es una permutación impar.
• Una permutación circular es par si el número de elementos no fijos es impar y es impar si este número de elementos es par.

• Datos: Q1064405