Paritatea unei permutări

În matematică, permutările unei mulțimi M finite cu cel puțin două elemente (bijecțiile de la M la M) se împart în două clase la fel de numeroase: permutările pare și permutările impare. Există mai multe metode de a defini paritatea (sau signatura) unei permutări, date în principal de modul de prezentare al permutărilor.

Paritatea unei permutări poate fi notată cu sgn(σ) sau cu ($\epsilon _{\sigma }$), având valorile de +1 în cazul în care σ este o permutare pară, și −1 dacă σ este impară.

Orice permutare poate fi scrisă ca un produs de transpoziții; însă paritatea numărului de transpoziții este aceeași pentru orice scriere posibilă a unei permutări. Cu alte cuvinte, nu se poate scrie o permutare ca un produs al unui număr par de transpoziții și, în același timp, ca un produs al unui număr impar de transpoziții.

Exemplu

Fie o permutare σ care rearanjează simbolurile 12345 în 34521. Această permutare poate fi obținută prin trei transpoziții: prima schimbă locurile lui 1 și 3, apoi a două schimbă locurile lui 2 și 4 iar în final o a treia transpoziție schimbă 1 și 5.

Folosind notațiile obișnuite,

$\sigma ={\begin{pmatrix}1&2&3&4&5\\3&4&5&2&1\end{pmatrix}}={\begin{pmatrix}1&3&5\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}={\begin{pmatrix}1&5\end{pmatrix}}{\begin{pmatrix}1&3\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}.$

iar permutarea σ este impară. Sunt multe alte moduri de a scrie pe σ ca o compunere de permutări, spre exemplu : $\sigma ={\begin{pmatrix}2&3\end{pmatrix}}{\begin{pmatrix}1&2\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}{\begin{pmatrix}3&5\end{pmatrix}}{\begin{pmatrix}4&5\end{pmatrix}},$

însă este imposibil de a o scrie ca un produs al unui număr par de transpoziții.

Definiție

Fie o permutare σ care rearanjează n simboluri, permutare formată din k cicluri, inclusiv ciclurile de lungime 1. Atunci numărul n+k este par sau impar. Paritatea acestui număr este, prin definiție, paritatea permutării σ.

• Asfel, permutarea identică $Id={\begin{pmatrix}1\end{pmatrix}}{\begin{pmatrix}2\end{pmatrix}}{\begin{pmatrix}3\end{pmatrix}}\cdots {\begin{pmatrix}8\end{pmatrix}}$ a unei mulțimi cu 8 simboluri este pară, deoarece n = k și n+k = 2.n = 8+8 (număr par)
• O permutare $\sigma ={\begin{pmatrix}1&2&3\end{pmatrix}}{\begin{pmatrix}4&5&6&7\end{pmatrix}}{\begin{pmatrix}8\end{pmatrix}}$ a unei mulțimi cu 8 simboluri este impară, deoarece 8 + 3 = 11 (11 este număr impar).

Observație : numărul n − k (care are aceeași paritate cu n + k) poate fi văzut ca număr minim de transpoziții în care se descompune permutarea dată. Fiecare ciclu contribuie la acest număr cu lungimea lui minus 1, deci în total avem lungimile însumate minus numărul de cicluri. De exemplu, permutarea de 8 simboluri de mai sus se descompune în transpoziții astfel :

$\sigma ={\begin{pmatrix}1&2\end{pmatrix}}{\begin{pmatrix}2&3\end{pmatrix}}\cdot {\begin{pmatrix}4&5\end{pmatrix}}{\begin{pmatrix}5&6\end{pmatrix}}{\begin{pmatrix}6&7\end{pmatrix}}$

Rămâne de arătat că orice altă scriere ca produs de transpoziții a unei permutări păstrează paritatea numărului de transpoziții.

Demonstrație riguroasă

În cazul în care o transpoziție „lovește” în două cicluri distincte, acestea se vor reuni într-unul singur

În celălalt caz, o transpoziție cade în același ciclu, producând două cicluri distincte

Să presupunem prin absurd că permutările ar putea fi scrise, în același timp, fie ca un produs par de transpoziții, fie ca un produs impar de transpoziții. Considerăm deci toate formulele de scriere ca produs de transpoziții ale unei permutări σ.

Să numim formulele de scriere (ca produs de transpoziții) ale unei permutări care au aceeași paritate cu cea definită mai sus (n+k) scrieri „normale”, iar celelalte formule „a-normale”.

Pentru fiecare permutare există o cea mai scurtă formulă a-normală. Între permutări, una va trebui să aibă o cea mai scurtă formulă a-normală dintre toate. Fie această permutare σ și o cea mai scurtă formulă a-normală:

$\sigma =\tau \cdot \tau _{1}\cdot \tau _{2}\cdot \tau _{3}\cdots \tau _{m}$ ( m+1 factori )

Fie acum permutarea

$\tau \cdot \sigma =\tau \cdot \tau \cdot \tau _{1}\cdot \tau _{2}\cdot \tau _{3}\cdots \tau _{m}=\tau _{1}\cdot \tau _{2}\cdot \tau _{3}\cdots \tau _{m}$ (m factori)

Transpoziția $\tau \,$ „pică” în permutarea $\sigma \,$ fie peste un singur ciclu, fie peste două cicluri. În ambele cazuri, paritatea (cum este definită mai sus) lui $\tau \cdot \sigma$ este cealaltă decât paritatea lui $\sigma \,$, deoarece numărul de cicluri este modificat cu 1, deci și numărul n+k își schimbă paritatea. Atunci, formula

$\tau _{1}\cdot \tau _{2}\cdot \tau _{3}\cdots \tau _{m}$

este o scriere a-normală pentru $\tau \cdot \sigma$

Contradicție, pentru că am presupus inițial că $\sigma \,$ are o cea mai scurtă scriere a-normală ca produs de transpoziții.

Proprietăți

• Produsul a două permutări pare este tot o permutare pară.
• Identitatea este o permutare pară.
• Inversa unei permutări pare este tot o permutare pară.
• Așadar, permutările pare formează un grup, subgrup al grupului de permutări.
• Permutările pot fi puse în corespondentă biunivocă cu cele impare - prin simpla înmulțire cu o aceeași transpoziție a fiecărei permutări pare, se obține o permutare corespondentă impară. Aceasta înseamnă că grupul (numit altern) are indice 2 în grupul simetric al tuturor permutărilor.
• Orice grup de permutări este alcătuit fie numai din permutări pare, fie, în cantitate egală, din permutări pare și permutări impare.
• Se poate face o speculație filozofică în jurul permutărilor pare. Întrucât două obiecte nu își pot schimba locul între ele, universul în care trăim este un univers „altern”. Pentru a schimba pozițiile a două obiecte între ele, avem nevoie de permutări pare.

loc liber <--------- A

în locul lui A <----B

în locul lui B <----A

Această idee, că trăim numai în jumătate dintr-un univers matematic posibil, se regăsește în simetriile spațiului 3D în care trăim, în care obiectele nu pot fi ”inversate în oglindă”.

Signatura

În cazul în care permutarea este văzută ca o reordonare a numerelor naturale cuprinse între 1 și n, o formulă pentru signatură este:

$\varepsilon (\sigma )=\prod \limits _{i<j}{\frac {\sigma (i)-\sigma (j)}{i-j}}$

unde rezultatul de −1 este asociat permutărilor cu număr impar de inversiuni iar +1 este asociat permutărilor cu număr par de inversiuni.

Această formulă contorizează numărul de inversiuni, adică de perechi (i, j), i < j, pentru care

$\sigma (i)>\sigma (j)\,$

Formula are avantajul de a putea scrie explicit morfismul de la grupul simetric la grupul multiplicativ {−1, +1}, de unde va rezulta că permutările cu număr par de inversiuni formează un subgrup de indice 2, care este exact nucleul morfismului dat de produs.

Mai rămâne de arătat că acest subgrup este identic cu subgrupul definit anterior cu ajutorul ciclurilor.

Echivalența dintre paritate și signatură

Fie $\alpha \,$ un simbol fixat. Atunci o transpoziție ${\begin{pmatrix}a&b\end{pmatrix}}$ se poate scrie:

${\begin{pmatrix}a&b\end{pmatrix}}={\begin{pmatrix}\alpha &a\end{pmatrix}}{\begin{pmatrix}\alpha &b\end{pmatrix}}{\begin{pmatrix}\alpha &a\end{pmatrix}}$

deci orice permutare pară poate fi scrisă ca un produs al unui număr tot par de transpoziții de tipul: ${\begin{pmatrix}\alpha &x\end{pmatrix}}$ .

O permutare pară va putea fi deci scrisă ca un produs de factori de tipul

$[{\begin{pmatrix}\alpha &x\end{pmatrix}}{\begin{pmatrix}\alpha &y\end{pmatrix}}]={\begin{pmatrix}y&x&\alpha \end{pmatrix}}$

și, în general, ca un produs de cicluri de lungime trei.

Deoarece un ciclu de lungime trei are signatură +1, signatura oricărei permutări pare, văzută ca produs de permutări de signatură +1, trebuie să fie +1.

Atunci cele ${\frac {n!}{2}}$ permutări pare sunt aceleași cu cele ${\frac {n!}{2}}$ permutări de signatură +1.

Vezi și

• Grup altern
• Permutare

Bibliografie

• Carmichael, Robert D. (1937), Introduction to the Theory of Groups of finite order, Boston, New York: Ginn & company 
• Jacobson, Nathan (1985), Basic algebra, 1 (ed. 2nd), New York: W.H.Freeman & Company