Permutarea ciclică

În teoria grupurilor, o permutare ciclică este o permutare a elementelor unei mulțimi X care rearanjează elementele unei submulțimi S a mulțimii X într-un mod ciclic, menținând elementele rămase ale lui X la locul lor (adică, maparea lor în sine) . De exemplu, permutarea {1, 2, 3, 4} care ia 1 la 3, 3 la 2, 2 la 4 și 4 la 1 este ciclică, în timp ce permutarea care ia 1 la 3, 3 la 1, 2 la 4 și 4 în 2 nu este ciclic.

Un ciclu într-o permutare este un subset de elemente care sunt permutate într-o manieră ciclică. Mulțimea S se numește orbita ciclului. Fiecare permutare a unui set finit de elemente poate fi descompusă într-o uniune de cicluri cu orbite care nu se intersectează. În unele contexte, o permutare ciclică este ea însăși numită ciclu.

Definiție

O permutare se numește ciclică dacă și numai dacă constă dintr-un singur ciclu non-trivial (adică, un ciclu de lungime mai mare de 1) [1] .

Exemplu:

{\displaystyle {\begin{pmatrix}1&2&3&4&5&6&7&8\\4&2&7&6&5&8&1&3\end{pmatrix}}={\begin{pmatrix}}1&4&6&8&3&7&2&5\\4&6&8&3&7&7&1&5(1&5)(1&3&7&1&5)

Unii autori limitează definiția doar la acele permutări care au exact un ciclu (adică, permutările care au puncte fixe nu sunt permise [2] .

Exemplu:

{\begin{pmatrix}1&2&3&4&5&6&7&8\\4&5&7&6&8&2&1&3\end{pmatrix}}={\begin{pmatrix}1&4&6&2&5&8&3&7\\4&6&2&2&5&8}2&5&8}2&pmatrix}(pmatrix)&4&6&2&5&8&3&7\\4&6&2&5&8&8}2&5&8

Mai formal, o permutare a unei multimi X care este o functie bijectiva se numeste ciclica daca actiunea asupra X a unui subgrup cu un generator are cel mult o orbita a mai mult de un element [3] . Acest concept este folosit cel mai des atunci când X este o mulțime finită. Atunci, desigur, cea mai mare orbită S este, de asemenea, finită. Fie orice element al lui S , stabilit pentru orice . Dacă mulțimea S este finită, atunci există un număr minim , pentru care . Atunci și este o permutare definită de formulă $\sigma:X\la X$ $\sigma$ $s_{0)$ $s_{i}=\sigma ^{i}(s_{0})$ $i\in \mathbf {Z}$ $k\geqslant 1$ $s_{k}=s_{0)$ ${\displaystyle S=\{s_{0},s_{1},\ldots,s_{k-1}\))$ $\sigma$

\sigma (s_{i})=s_{i+1}\quad

pentru

0\leq i<k

si pentru orice element . Elementele care nu sunt capturate de afișaj pot fi reprezentate ca $\sigma (x)=x$ $X\setminus S$ $\sigma$

s_{0}\mapsto s_{1}\mapsto s_{2}\mapsto \cdots \mapsto s_{k-1}\mapsto s_{k}=s_{0)

O buclă poate fi scrisă folosind notația buclă compactă (nu există virgulă între elemente într-o astfel de notație pentru a evita confuzia cu tuplurile ). Lungimea unui ciclu este numărul de elemente de pe orbita sa cea mai mare. În notația buclă, buclele de lungime 1 sunt adesea omise dacă acest lucru nu provoacă confuzie [4] . $\sigma =(s_{0}~s_{1}~\dots ~s_{k-1})$

Proprietăți de bază

Conform uneia dintre principalele proprietăți ale grupurilor simetrice , orice permutare poate fi reprezentată ca un produs al ciclurilor care nu se intersectează (mai precis, ciclurile cu orbite care nu se intersectează). Astfel de cicluri pot fi permutate între ele, iar expresia de permutare este unică în ordinea ciclurilor (rețineți că notația ciclică nu este unică - orice k -ciclu în sine poate fi scris în k moduri diferite, în funcție de alegerea în orbita sa). Setul multiplu de lungimi de ciclu (tip de ciclu) este determinat în mod unic de o permutare. $s_{0)$

Numărul de cicluri diferite de lungime k din grupul simetric S n este dat de următoarea formulă $1\leqslant k\leqslant n$

{\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n !}{(nk)!k}}

Un ciclu de lungime k are paritatea (−1) k − 1 .

Transpoziții

Un ciclu format din două elemente se numește transpunere . De exemplu, permutarea {1, 4, 3, 2} care ia 1 la 1, 2 la 4, 3 la 3 și 4 la 2 este o transpunere (și anume, o transpunere care schimbă 2 și 4).

Orice permutare poate fi reprezentată ca o compoziție (produs) a transpozițiilor - formal, sunt generatoare de grupe [5] . Mai mult, orice permutare a mulțimii ordonate X = {1, 2, …, n } poate fi exprimată ca un produs al transpozițiilor adiacente , adică transpoziții de formă Într-adevăr, orice transpoziție poate fi reprezentată ca un produs al transpozițiilor adiacente. $(k~~k+1).$

Descompunerea unei permutări într-un produs de transpoziții poate fi obținută, de exemplu, prin scrierea unei permutări ca produs al diferitelor cicluri și apoi descompunerea iterativă a ciclurilor de lungime 3 sau mai mare într-un produs al unei transpoziții și al unui ciclu unul mai scurt. :

(a~b~c~d~\ldots ~y~z)=(a~b)\cdot (b~c~d~\ldots ~y~z)

Grupul simetric este un grup Coxeter , în sensul că este generat de elemente de ordinul 2 (transpoziții adiacente) și toate relațiile au o formă definită.

Unul dintre principalele rezultate ale teoriei elementare a grupurilor simetrice afirmă că fie toate descompunerea unei anumite permutări în transpoziții au un număr par de transpoziții, fie toate descompunerea au un număr impar de transpoziții [6] . Acest lucru permite ca paritatea permutării să fie o funcție bine definită.

Vezi și

Loop sort este un algoritm de sortare bazat pe ideea că o matrice poate fi descompusă în bucle care pot fi parcurse individual pentru a obține o matrice sortată
Cicluri și puncte fixe
Permutări ciclice ale numerelor întregi
Permutări ciclice în proteine

Notă

↑ Bogart, 1990 , p. 486.
↑ Brut, 2008 , p. 29.
↑ Fraleigh, 1993 , p. 103.
↑ Sagan, 1991 , p. 2.
↑ Rotman, 2006 , p. 118, prop. 2.35.
↑ Rotman, 2006 , p. 122.

Literatură

Anderson M., Feil T. . Un prim curs de algebră abstractă. editia a 2-a. — Boca Raton: Chapman & Hall/CRC, 2005. — 696 p. — ISBN 1-58488-515-7 .
Fraleigh J. Un prim curs de algebră abstractă. editia a 5-a. - Lectură: Addison-Wesley, 1993. - 576 p. - ISBN 978-0-201-53467-2 .
Rotman J.J. Un prim curs de algebră abstractă cu aplicații. a 3-a editie. - Upper Saddle River: Prentice Hall, 2006. - 581 p. — ISBN 978-0-13-186267-8 .
Sagan B.E. Grupul simetric: reprezentări, algoritmi combinatori și funcții simetrice . - Belmont: Wadsworth, 1991. - 197 p. — ISBN 978-0-534-15540-7 .
Bogart K.P. Combinatorică introductivă. editia a 2-a. - San Diego: Harcourt, Brace, Jovanovich, 1990. - 622 p. — ISBN 0-15-541576-X .
Brut J.L. Metode combinatorii cu aplicații computerizate. - Boca Raton: Chapman & Hall/CRC, 2008. - xvii + 644 p. — ISBN 978-1-58488-743-0 .

Link -uri

Permutările ca produs al transpozițiilor