Este artículo o sección necesita referencias que aparezcan en una publicación acreditada. Busca fuentes: «Paridad de una permutación» – noticias · libros · académico · imágenes Este aviso fue puesto el 13 de octubre de 2014.

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.

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

${\displaystyle {\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.

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á:

${\displaystyle {\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.

Nótese ${\displaystyle {\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:

${\displaystyle \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}}.}$

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.

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

${\displaystyle \varepsilon (\sigma \circ \tau )=\varepsilon (\sigma )\varepsilon (\tau ).}$

Demostración

${\displaystyle {\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 ${\displaystyle ({\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 ${\displaystyle \sigma ,\,\,\sigma ^{-1},}$ tiene la misma paridad que ${\displaystyle \sigma }$.

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

Demostración

${\displaystyle 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 )}$

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 ${\displaystyle {\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.