Paritat d'una permutació

En matemàtiques, les permutació poden descompondre's en un producte de transposició, és dir, en una successió d'intercanvis d'elements dos a dos.

• Una permutació parell és una permutació que pot ser representada per un número parell de transposició.
• Una permutació impar és una permutació que pot ser representada per un número impar de transposició.

La paritat o signatura d'una permutació val 1 si esta és parell i -1 si és impar. L'aplicació corresponent a la paritat constituïx un homomorfisme de grups. És important en àlgebra multilineal, sobretot en el càlcul de determinants.

Definició de la paritat

Siga una permutació σ. La definició de la signatura de σ es fa contant les inversions.

Definició

Siguen i < j dos elements distints compresos entre 1 i n. Es diu que es té una inversió del parell {i, j} per a σ quan σ(i) > σ(j).

Es diu que una permutació és parell quan presenta un número par d'inversions. Es diu impar en el cas contrari.

La paritat (o signe) d'una permutació parell és 1 ; la d'una permutació impar és –1.

Eixemple

Siga la permutació

$\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 1& 3& 5& 4& 2\end{array}\right),$

que deixa fixos 1 i 4 i envia el 2 al 3, el 3 al 5 i el 5 al 2. Cap parell que continga 1 pot ser una inversió posat que para tot j > 1, σ(j) és distint de σ(1) = 1, per lo que σ(j) > σ(1). L'únic parell en inversió que conté 2 és {2, 5} (σ(2) = 3 > 2 = σ(5)). La llista de parells en inversió és {2, 5}, {3, 4}, {3, 5}, {4, 5}. Hi ha quatre, aixina que la permutació és parell.

Les transposició són impars

Tota transposició és una permutació impar. En efecte notant i i j, i < j, els térmens que la transposició intercanvia, està transposició s'escriurà:

$\left(\begin{array}{cccccccccc}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{array}\right).$

Els parells en inversió són els parells de la forma {i, k} en k comprés entre i + 1 i j i els de la forma {k, j} en k comprés entre i + 1 et j – 1. En total, hi ha un número impar d'inversions, de lo que es deduïx que la permutació és impar.

Una fòrmula per a la paritat

Note's $𝒫$ al conjunt de parells d'elements compresos entre 1 i n (en total hi ha n(n + 1)/2 elements). La signatura d'una permutació σ és:

$\epsilon (\sigma )=\prod _{i<j}\frac{\sigma (j)-\sigma (i)}{j-i}=\prod _{\{i,j\}\in 𝒫}\frac{\sigma (j)-\sigma (i)}{j-i}.$

Esta fòrmula té un cert interés algebraic pero en la pràctica no permet un càlcul eficaç de la paritat. En efecte, en comparació a un simple conteo d'inversions, la multiplicació i la divisió per un cert número de sancers són més costoses.

Paritat d'un producte

Les permutació verifiquen una regla de signe per al producte: el producte de dos permutació pares és parell, el de dos permutació impars és parell i el d'una permutació parell i una permutació impar és impar. Utilisant la paritat, açò es resumix en la fòrmula

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

En térmens algebraics : la signatura és un morfismo de grups del grup simètric $({𝔖}_n,\circ )$ en el grup de dos elements ({–1, 1}, ×). El subgrup format pel núcleu d'este morfismo forma el grup alternat de permutació pares. Finalment, la permutació inversa de $\sigma ,{\sigma }^{-1},$ té la mateixa paritat que $\sigma$.

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

Càlcul de la paritat

Com corolaris dels resultats precedents es té que

• una permutació és parell si i solament si pot ser expressada com el producte d'un número par de transposició;
• una permutació és impar si i solament si pot ser expressada com el producte d'un número impar de transposició.

El càlcul de la paritat a través de la descomposició en producte de transposició és molt més eficaç que l'aplicació de la definició inicial; en efecte, per a una permutació de ${𝔖}_n$, esta descomposició requerix com a màxim n – 1 operacions, en lloc de les n(n – 1)/2 operacions que es requerixen per la definició. D'estos dos corolaris i de la descomposició d'un cicle en trasposiciones es deduïx que els cicles de llongitut parell són permutació de paritat impar, i viceversa.

Eixemples

• l'identitat és una permutació parell.
• Una transposició és una permutació impar.
• Una permutació circular és parell si el número d'elements no fixos és impar i és impar si este número d'elements és parell.