Permutări: operații, inversiuni și semn

O permutare a mulțimii $\{1;2;\dots ;n\}$ este o funcție bijectivă de la această mulțime la ea însăși: fiecare element are exact o imagine, iar imaginile nu se repetă. Se scrie pe două rânduri, de exemplu $\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$: $1$ merge în $2$, $2$ în $3$, $3$ în $1$. Mulțimea celor $n!$ permutări se notează $S_n$ și formează un grup la compunere, cu permutarea identică $e$ ca element neutru. În $\sigma \circ \tau$ aplici întâi $\tau$, apoi $\sigma$; inversa ${\sigma }^{-1}$ readuce fiecare imagine la elementul de pornire. Semnul unei permutări, $+1$ sau $-1$, spune dacă numărul inversiunilor ei este par sau impar.

Compunerea permutărilor este asociativă, $e\circ \sigma =\sigma \circ e=\sigma$, iar orice permutare are o inversă în $S_n$; de aceea $(S_n;\circ )$ este grup. Pentru $n\ge 3$ grupul nu este comutativ. Puterile se definesc ca la funcții: ${\sigma }^0=e$, ${\sigma }^{k+1}={\sigma }^k\circ \sigma$. Inversa unei compuneri schimbă ordinea factorilor: $(\sigma \circ \tau {)}^{-1}={\tau }^{-1}\circ {\sigma }^{-1}$.

O inversiune a lui $\sigma \in S_n$ este o pereche de poziții $i<j$ pentru care $\sigma (i)>\sigma (j)$, adică imaginile apar în ordine descrescătoare. Numărul lor se notează $m(\sigma )$, iar semnul (signatura) este $\epsilon (\sigma )=(-1{)}^{m(\sigma )}$. O permutare este pară dacă $\epsilon (\sigma )=+1$ și impară dacă $\epsilon (\sigma )=-1$. O transpoziție, adică permutarea care schimbă între ele două elemente și le lasă pe celelalte pe loc, este impară. Au loc relațiile $\epsilon (\sigma \circ \tau )=\epsilon (\sigma )\epsilon (\tau )$ și $\epsilon ({\sigma }^{-1})=\epsilon (\sigma )$. Pentru $n\ge 2$, exact jumătate dintre cele $n!$ permutări sunt pare: în $S_3$ sunt $3$ (adică $e$ și permutările $(2;3;1)$, $(3;1;2)$, scrise prin șirul imaginilor), în $S_4$ sunt $12$.

O transpoziție care schimbă elementele de pe pozițiile $i<j$ are $2(j-i)-1$ inversiuni, număr impar. Cel mai mare număr de inversiuni din $S_n$ este $\frac{n(n-1)}{2}$, atins de permutarea $(n;n-1;\dots ;1)$, al cărei semn este $(-1{)}^{n(n-1)/2}$: în $S_3$ aceasta are $3$ inversiuni (semn $-1$), iar în $S_4$ are $6$ (semn $+1$).

Inversiunile se numără ordonat: pentru fiecare element se numără elementele mai mici aflate la dreapta lui. Șirul de imagini $(3;5;1;4;2)$ dă $2+3+0+1=6$ inversiuni, deci permutarea este pară. Semnul apare în definiția determinantului: la ordinul $3$, cei șase termeni ai regulii lui Sarrus corespund celor șase permutări din $S_3$, iar termenii cu plus, $aei$, $bfg$ și $cdh$, sunt cei ai permutărilor pare.

Exemplu rezolvat. Fie $\sigma =\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$ și $\tau =\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$.

1. Compunerea: $(\sigma \circ \tau )(1)=\sigma (2)=3$, $(\sigma \circ \tau )(2)=\sigma (1)=2$, $(\sigma \circ \tau )(3)=\sigma (3)=1$; deci $\sigma \circ \tau =\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$. În ordine inversă, $\tau \circ \sigma =\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)\ne \sigma \circ \tau$.
2. Inversa: preimaginile lui $1;2;3$ prin $\sigma$ sunt $3;1;2$, deci ${\sigma }^{-1}=\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$.
3. Semnele: șirul imaginilor lui $\sigma$ este $(2;3;1)$ și are inversiunile $(2;1)$ și $(3;1)$, deci $\epsilon (\sigma )=+1$. Permutarea $\tau$ are o singură inversiune, $(2;1)$, deci $\epsilon (\tau )=-1$. Compunerea, $(3;2;1)$, are trei, deci $-1=(+1)\cdot (-1)$.

Exemplu rezolvat. Fie $\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 3& 1& 4& 2\end{array}\right)\in S_4$.

1. Inversiunile sunt $(3;1)$, $(3;2)$ și $(4;2)$, deci $m(\sigma )=3$ și $\epsilon (\sigma )=-1$.
2. ${\sigma }^2$ trimite $1\to \sigma (3)=4$, $2\to \sigma (1)=3$, $3\to \sigma (4)=2$, $4\to \sigma (2)=1$, deci ${\sigma }^2=\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 3& 2& 1\end{array}\right)$, care are $6$ inversiuni și semnul $+1=\epsilon (\sigma {)}^2$.
3. Cum $({\sigma }^2{)}^2=e$, avem ${\sigma }^4=e$. Pentru $2025=4\cdot 506+1$ rezultă ${\sigma }^{2025}=\sigma$.

Exemplu rezolvat. Rezolvăm în $S_3$ ecuația $\sigma \circ x=\tau$, cu $\sigma$ și $\tau$ de mai sus. Compunând la stânga cu ${\sigma }^{-1}$ obținem $x={\sigma }^{-1}\circ \tau$. Avem $x(1)={\sigma }^{-1}(2)=1$, $x(2)={\sigma }^{-1}(1)=3$, $x(3)={\sigma }^{-1}(3)=2$, deci $x=\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$. Verificare: $\sigma (x(1))=2$, $\sigma (x(2))=\sigma (3)=1$, $\sigma (x(3))=\sigma (2)=3$, adică imaginile $(2;1;3)$ ale lui $\tau$. Dacă ecuația ar fi $x\circ \sigma =\tau$, soluția ar fi $x=\tau \circ {\sigma }^{-1}$, adică $x(1)=\tau (3)=3$, $x(2)=\tau (1)=2$, $x(3)=\tau (2)=1$, deci $x=\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$: partea pe care stă $\sigma$ hotărăște de ce parte se compune cu ${\sigma }^{-1}$.

Greșeli frecvente

• Greșit: în $\sigma \circ \tau$ aplici întâi $\sigma$.
  Corect: în convenția compunerii funcțiilor se aplică întâi $\tau$.
• Greșit: semnul depinde de mărimea numerelor mutate.
  Corect: depinde de paritatea lui $m(\sigma )$, numărul inversiunilor.
• Greșit: inversa lui $\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$ se obține citind rândul de jos invers, deci este $\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$.
  Corect: se caută preimaginile lui $1;2;3$, iar inversa este $\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$.
• Greșit: inversiunile se numără doar între elemente vecine; la $(3;1;4;2)$ ar fi $2$.
  Corect: se numără toate perechile $i<j$ cu $\sigma (i)>\sigma (j)$, adică $3$.
• Greșit: $\epsilon (\sigma \circ \tau )=\epsilon (\sigma )+\epsilon (\tau )$.
  Corect: semnele se înmulțesc; pentru două permutări impare, compunerea este pară, fiindcă $(-1)\cdot (-1)=+1$.
• Greșit: $(\sigma \circ \tau {)}^{-1}={\sigma }^{-1}\circ {\tau }^{-1}$.
  Corect: $(\sigma \circ \tau {)}^{-1}={\tau }^{-1}\circ {\sigma }^{-1}$; pentru $\sigma$ și $\tau$ din primul exemplu rezolvat, ${\tau }^{-1}\circ {\sigma }^{-1}$ dă șirul de imagini $(3;2;1)$, adică chiar $(\sigma \circ \tau {)}^{-1}$, iar ${\sigma }^{-1}\circ {\tau }^{-1}$ dă $(1;3;2)$.

Înainte și după