Inversiuni și semnul unei permutări: pe scurt

O pereche de poziții $(i,j)$ cu $i<j$ se numește inversiune a permutării $\sigma$ dacă valorile de pe ele stau invers, adică $\sigma (i)>\sigma (j)$. Numărul inversiunilor se notează $m(\sigma )$ și se numără fără greșeală așa: parcurgi linia a doua de la stânga la dreapta și, pentru fiecare valoare, numeri câte valori mai mici stau la dreapta ei; apoi aduni. Fiecare pereche este numărată exact o dată.

Se numără perechi de poziții, nu numere „mutate din loc". De aici și marginile: $0\le m(\sigma )\le \frac{n(n-1)}{2}$, minimul fiind atins de permutarea identică, iar maximul de cea răsturnată, cu linia a doua scrisă descrescător. Un rezultat în afara acestui interval este, sigur, o greșeală de numărare.

Din numărul de inversiuni păstrăm un singur bit: paritatea. Semnul, sau signatura, este $\epsilon (\sigma )=(-1{)}^{m(\sigma )}\in \{-1,+1\}$; permutarea se numește pară când $\epsilon (\sigma )=+1$ și impară când $\epsilon (\sigma )=-1$. Identitatea este mereu pară. Nu confunda $m$ cu $\epsilon$: al doilea este întotdeauna $\pm 1$.

Trei reguli de calcul îți scurtează munca la Bacalaureat M1: dacă schimbi între ele două valori, semnul se schimbă; $\epsilon (\sigma \circ \tau )=\epsilon (\sigma )\cdot \epsilon (\tau )$, deci afli semnul unei compuneri fără să o calculezi; și $\epsilon ({\sigma }^{-1})=\epsilon (\sigma )$, adică inversa are același semn, nu semnul opus.

Semnul este ultima piesă necesară determinantului de ordin $n$: fiecare dintre cele $n!$ produse intră în sumă cu semnul permutării care îl conduce.

Exerciții din această mini-lecție

1. Câte inversiuni are permutarea de grad $5$ cu linia a doua $3,5,1,4,2$?

   • a) $4$
   • b) $5$
   • c) $6$
   • d) $10$
   Vezi răspunsul

   Răspuns corect: c) $6$

   Numărăm, pentru fiecare valoare, câte valori mai mici stau la dreapta ei: $3$ are $1$ și $2$ (două), $5$ are $1$, $4$ și $2$ (trei), $1$ are zero, $4$ îl are pe $2$ (una), $2$ are zero. Deci $m(\sigma )=2+3+0+1+0=6$. Varianta d) este maximul posibil la gradul $5$, $\frac{5\cdot 4}{2}=10$, atins doar de permutarea răsturnată.

2. Se știe că $\sigma ,\tau \in S_5$ au $m(\sigma )=7$ și $m(\tau )=4$. Cât este $\epsilon (\sigma \circ \tau )$?

   • a) $-1$
   • b) $+1$
   • c) $28$
   • d) $11$
   Vezi răspunsul

   Răspuns corect: a) $-1$

   $\epsilon (\sigma )=(-1{)}^7=-1$ și $\epsilon (\tau )=(-1{)}^4=+1$, iar semnele se înmulțesc: $\epsilon (\sigma \circ \tau )=(-1)\cdot (+1)=-1$. Variantele c) și d) vin din confuzia dintre $m$ și $\epsilon$: signatura este întotdeauna $-1$ sau $+1$, niciodată alt număr.

3. Se consideră permutarea de grad $7$ cu linia a doua $7,6,5,4,3,2,1$. Care afirmație este adevărată?

   • a) $m(\sigma )=21$ și $\sigma$ este pară
   • b) $m(\sigma )=42$ și $\sigma$ este pară
   • c) $m(\sigma )=28$ și $\sigma$ este impară
   • d) $m(\sigma )=21$ și $\sigma$ este impară
   Vezi răspunsul

   Răspuns corect: d) $m(\sigma )=21$ și $\sigma$ este impară

   La permutarea răsturnată orice pereche de poziții este inversiune, deci $m(\sigma )=\frac{7\cdot 6}{2}=21$. Cum $21$ este impar, $\epsilon (\sigma )=(-1{)}^{21}=-1$, adică permutarea este impară. Varianta b) numără perechile ordonate, uitând împărțirea la $2$.