Paritat d'una permutació

En matemàtiques, les permutacions (és a dir, les bijeccions en els conjunts finits) es poden descompondre en un producte de transposicions, és a dir en una successió d'intercanvis d'elements dos a dos.

  • Una permutació parella és una permutació que es pot expressar com el producte d'un nombre parell de transposicions;
  • Una permutació senar és una permutació es pot expressar com el producte d'un nombre senar de transposicions.

El signe d'una permutació val 1 si és parella i -1 si és senar. L'aplicació signe constitueix un morfisme de grups. Intervé en àlgebra multilineal, sobretot per al càlcul de determinants.

Definició de la paritat

Sigui una permutació σ {\displaystyle \sigma } . La definició tradicional de la paritat de σ {\displaystyle \sigma } es fa pel recompte de les inversions.

Definició

Siguin i<j dos elements diferents compresos entre 1 i n. Es diu que la parella {i,j} queda 'invertida per σ {\displaystyle \sigma } quan σ ( i ) > σ ( j ) {\displaystyle \sigma (i)>\sigma (j)} .

Una permutació s'anomena parella quan presenta un nombre parell d'inversions, senar si no.

Exemple
Sigui la permutació
( 1 2 3 4 5 1 3 5 4 2 ) {\displaystyle {\begin{pmatrix}1&2&3&4&5\\1&3&5&4&2\end{pmatrix}}}
La parella {1,2} no està en inversió ja que les imatges de 1 i 2 estan conserven el mateix ordre. Tampoc ho estan 1 i 3. La llista de les parelles en inversió és {2,5}, {3,4}, {3,5}, {4,5}. N'hi ha quatre, per tant la permutació és parella.

Per definició, el signe d'una permutació parella és 1, la d'una permutació senar és -1.

Una transposició és senar

Tota transposició és una permutació senar. En efecte notant i i j, i<j, els termes intercanviats per la transposició, aquesta s'escriu

( 1 … i − 1 i i + 1 … j − 1 j j + 1 … n 1 … i − 1 j i + 1 … j − 1 i j + 1 … n ) {\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}}}

Els parells en inversió són els parells de la forma {i,k} amb k comprès entre i+1 i j i les de la forma {k,j} amb k comprès entre i+1 i j-1. En total, hi ha un nombre senar d'inversions, i d'aquí se'n desprèn que la permutació és senar.

Una fórmula per a calcular el signe

Es nota P {\displaystyle {\mathcal {P}}} el conjunt dels parells d'elements compresos entre 1 i n (n'hi ha n(n-1)/2). Una permutació σ té per signe

ε ( σ ) = ∏ i < j σ ( i ) − σ ( j ) i − j = ∏ { i , j } ∈ P σ ( i ) − σ ( j ) i − j {\displaystyle \varepsilon (\sigma )=\prod \limits _{i<j}{\frac {\sigma (i)-\sigma (j)}{i-j}}=\prod \limits _{\{i,j\}\in {\mathcal {P}}}{\frac {\sigma (i)-\sigma (j)}{i-j}}}
Demostració
Dient P aquest producte. Examinar totes les parelles (i,j) amb i<j porta a examinar tots els parells {i,j}. Per a cadascuna d'elles, el terme que es troba al producte té un signe negatiu si el parell és en inversió, positiu si no. Això mostra que el signe de P és el de la permutació. Finalment, per bijectivitat de σ, els termes σ(i)-σ(j) del numerador són, tret del signe, els mateixos que els i-j del denominador. Això mostra que el valor absolut de P és 1 i permet concloure.

Aquesta fórmula té un cert interès algebraic però no permet un càlcul eficaç del signe a la pràctica. En efecte, respecte al senzill recompte de les inversions s'afegeix la multiplicació i la divisió per un cert nombre d'enters.

Signe d'un producte

Les permutacions verifiquen una regla dels signes per al producte: el producte de dues permutacions parelles és parell, de dues permutacions senars és parell, el producte d'una permutació parella i d'una senar és senar. Utilitzant el signe, això es resumeix per la fórmula

ε ( σ ∘ τ ) = ε ( σ ) . ε ( τ ) {\displaystyle \varepsilon (\sigma \circ \tau )=\varepsilon (\sigma ).\varepsilon (\tau )}
Demostració
ε ( σ ∘ τ ) = ∏ { i , j } ∈ P σ ( τ ( i ) ) − σ ( τ ( j ) ) τ ( i ) − τ ( j ) ∏ { i , j } ∈ P τ ( i ) − τ ( j ) i − j {\displaystyle \varepsilon (\sigma \circ \tau )=\prod \limits _{\{i,j\}\in {\mathcal {P}}}{\frac {\sigma (\tau (i))-\sigma (\tau (j))}{\tau (i)-\tau (j)}}\prod \limits _{\{i,j\}\in {\mathcal {P}}}{\frac {\tau (i)-\tau (j)}{i-j}}}
En el segon factor del segon membre, es reconeix directament un signe. Per al primer, cal prèviament reindexar posant {i',j'}={τ(i),τ(j)}, on es reconeix llavors igualment un signe.

En termes algebraics: el signe és un morfisme de grups del grup simètric ( S n , ∘ ) {\displaystyle ({\mathfrak {S}}_{n},\circ )} en ( { − 1 , 1 } , × ) {\displaystyle \left(\{-1,1\},\times \right)} . El conjunt de les permutacions parelles forma el grup alternat, nucli d'aquest morfisme. Finalment la permutació inversa de σ té el mateix signe que σ.

Càlcul del signe

Com a corol·lari dels resultats precedents,

  • una permutació és parella si i només si es pot expressar com el producte d'un nombre parell de transposicions;
  • una permutació és senar si i només si es pot expressar com el producte d'un nombre senar de transposicions

i aquests dos casos s'exclouen mútuament.

El càlcul del signe per la descomposició en producte de transposicions és molt més eficaç que l'aplicació de la definició inicial; en efecte per a una permutació de S n {\displaystyle {\mathfrak {S}}_{n}} aquesta descomposició demanda com a màxim n-1 operacions, contra n(n-1)/2 per a la definició.

Exemples
la identitat és una permutació parella;
una transposició és una permutació senar;
una permutació circular és parella si el nombre d'elements és senar; és senar si el nombre d'elements és parell.

Vegeu també