Algebră - Grupuri de Permutări

[Admin]

Deoarece PERMUTĂRILE reprezintă un subiect mai complex şi mai larg inclusiv la nivel universitar (sau mai bine zis mai ales la nivel universitar) am decis să creez acest Topic de Algebră separat de Algebră - Anul 1 - Grupuri .

Prin Sn vom nota în general grupul simetric de permutări.
Acest grup este de fapt grupul bijecţiilor de la {1,2,...,n} la {1,2,...,n}.

Pentru simplificare şi uşurinţa în notare şi scriere vom nota cu (i₁,i₂,...,i_n) acea permutare ce se identifică cu bijecţia :

i₁ -> i₂ -> i₃ -> ... -> i_n -> i₁

(adică o permutare ciclică de ordin n , sau un ciclu de ordin n .. sau un ciclu de lungime n)

... aceasta şi pentru a nu mai face apel la notaţia mai greoaie pe Forum :

$$\begin{pmatrix}
i_1 & i_2 & i_3 & . & . & . & i_{n-1} & i_n & \\
i_2 & i_3 & i_4 & . & . & . & i_n & i_1 &
\end{pmatrix}$$

(Aici am făcut apel la scrierea în Latex, care deşi nu este greu, mai ales că Latex Editor este prezent în Edit Box, adică în căsuţa de editare. Eventual scrierea folosind Latex durează un pic mai mult, dar e mai greu pentru începători. -> DETALII )

Acelaşi lucru în cazul CICLURILOR de orice ordin (nu neapărat de ordin maxim, cazul transpoziţiilor fiind cicluri de ordin 2 ).
Această lejeritate în scriere este recomandată aici pe Forum de câte ori va fi posibil (deci cazul ciclurilor).

Iar în cazul în care avem (a,b) aceasta va denota o transpoziţie, adică : a -> b , b - > a iar i -> i pentru a ≠ i ≠ b ,
chiar dacă permutarea este de ordin mai mare decât 2.

[Admin]

a) Orice permutare din Sn se poate scrie ca un produs format din transpoziţiile : (1,2), (1,3), ... ,(1,n)
b) Orice permutare din Sn se poate scrie ca un produs format din transpoziţiile : (1,2), (2,3), ... , ((n-1),n)

Rezolvare :

Este binecunoscută simpla afirmaţie că orice permutare se poate scrie ca un produs de transpoziţii
(scrierea nefiind unică ... putem înmulţi oriunde cu pătratul unei transpoziţii care înseamnă permutarea identică)

Atunci e suficient să demonstrăm afirmaţiile pentru transpoziţii.

a) Dacă a = 1 sau b = 1 atunci permutarea se găseşte deja în listă.
Altfel se observă uşor că (a,b) = (1,a)(1,b)(1,a)

b) Folosim rezultatul obţinut la punctul a)
Este suficient să se arate că o transpoziţie de forma (1,k) se scrie ca produs de permutări din lista b) .. şi avem :

(1,k) = ((k-1),k)*...*(2,3)*(1,2)*(2,3)*... *((k-1),k)

(Am pus semnul * la înmulţire/compunere pentru o mai bună observare ...)

DEMONSTRĂM aceasta simplu prin inducţie după k . Pentru k=2 este un lucru evident.
Pentru k > 2 presupunem că afirmaţia este adevărată pentru k şi să arătăm pentru k+1.

(1,(k + 1)) = (k,(k+1))*(1,k)*(k,(k+1)) = (k,(k+1))*((k-1),k)*...*(2,3)*(1,2)*(2,3)*((k-1),k)*(k,(k+1))

am evidenţiat cu roşu pasul de inducţie ... QED.

[Admin]

Problemă
Dacă un subgrup G de permutări al lui Sn conţine o permutare de ordin n şi o transpoziţie atunci G = Sn .

Rezolvare :

O permutare de ordin/grad n este evident un ciclu de lungime n .

Cu rezultatul de la punctul b) din postarea anterioară şi notaţiile explicate în prima postare este suficient să arătăm că dacă G conţine permutarea (1,2,3,...,n) şi transpoziţia (1,2) atunci orice transpoziţie de forma (k,(k+1))

Reamintim că am notat cu (1,2,3,...,n) permutarea ciclu care înseamnă funcţia bijectivă : 1 -> 2 -> 3 -> ... -> n -> 1
(... altfel spus bijecţia f dată de f(1)=2, f(2)=3, f(3)=4, ... , f(n-1)=n, f(n)=1 ...)
Permutarea aceasta are evident gradul n .

Putem folosi aceasta deoarece putem renumerota elementele permutării date .. şi ajungem la această situaţie.

---

Observaţie. Fiind vorba de o dublă renumerotare e nevoie totuşi de o precizare, pentru "conservarea ipotezei" :
mai întâi renumerotăm elementele pentru ca transpoziţia să devină (1,2) şi apoi renumerotăm restul elementelor. Adică, privite ca funcţii avem egalitatea evidentă :

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

deci prima parte a renumerotării ar fi a -> 1 şi b -> 2.
Asta are importanţă că în permutarea de ordin n vom avea pe 1 pe prima poziţie.
Apoi, dacă e necesar (daca în permutare 2 nu este pe a 2-a poziţie), deci dacă avem permutarea de genul
(1 ->... 2 -> ... -> 1) atunci, presupunând că 2 se află pe poziţia k , atunci o anume putere a permutării date,
mai exact (1 ->... 2 -> ... -> 1)^(k-1) (1) = 2 (vezi şi observaţiile de mai jos) deci va fi de genul (1 ->2 -> ... -> 1) şi putem lucra cu aceasta (ea făcând parte din G, evident)

---

Demonstraţia "DETALIATĂ" : Notăm s = (1,2,3,...,n) , adică bijecţia 1-> 2 -> 3 -> ... -> n -> 1
Evident s^-1 este bijecţia 1 <- 2 <- 3 <- ... <- n <- 1 . Atunci vom avea :

s(1,2)s^-1 = (2,3)

E suficientă verificarea pentru 1, 2, 3 , la restul fiind evident. În membrul drept e evident.
Deci, în membrul stâng, verificăm compunerea celor 3 funcţii (şi trebuie să obţinem ca în membrul drept) :
1 -> n -> n -> 1 (ca şi în membrul drept) /// 2 -> 1 -> 2 -> 3 /// 3 -> 2 -> 1 -> 2 ///... Analog :

s(2,3)s^-1 = (3,4)
s(3,4)s^-1 = (4,5)
....................
s(n-2),(n-1))s^-1 = ((n-1),n)

---

Demonstraţia "CONDENSATĂ" :
Tot ce mai rămâne de observat este că (1,2,3,...,n)^k-1 (1,2) (1,2,3,...,n)^-(k-1) = (k,(k+1)) care înseamnă, scris altfel, prin înmulţire la dreapta :

(1,2,3,...,n)^k-1 * (1,2) = (k,(k+1)) * (1,2,3,...,n)^k-1

Lucrul acesta se verifică uşor, dacă notând s = (1,2,3,...,n)^k-1 atunci :

s(1)= 1+(k-1), s(2)= 2+(k-1), ... adică s(i) = i+(k-1)

(... în general (1,2,3,...,n)^r(i)=i+r ...)

evident numerele de forma i+(k-1) > n fiind înlocuite cu i+(k-1)-n ...
... şi ţinând cont de ceea ce este evidenţiat cu albastru atunci ce este cu roşu este o simplă verificare.

[Admin]

Finite group - A Cayley graph of the symmetric group S4 - see on Wikipedia

[Admin]