Cicle (permutació)

En matemàtiques, i en particular en teoria de grups, una permutació cíclica és una permutació dels elements d'un conjunt X que transforma els elements d'un subconjunt S de X els uns en els altres de manera cíclica, mentre que manté fixos (és a dir, transforma en ells mateixos) la resta d'elements de X. Per exemple, la permutació de {1, 2, 3, 4} que envia 1 a 2, 2 a 3, 3 a 4 i 4 a 1 és un cicle, mentre que la permutació que envia 1 a 3, 3 a 1, 2 a 4 i 4 a 2 no ho és (permuta de manera separada els parells {1, 3} i {2, 4}).

Un cicle d'una permutació és un subconjunt dels elements que s'intercanvien de forma cíclica. El conjunt S s'anomena òrbita del cicle. Tota permutació d'un nombre finit d'elements es pot descompondre en un nombre finit de cicles amb òrbites disjuntes. En alguns contextos, hom anomena cicle a una permutació cíclica.

Definició

Esquema de la permutació (1)

Hom diu que una permutació és una permutació cíclica si i només si consisteix d'un sol cicle no trivial (un cicle de longitud > 1).

Exemple:

${\begin{aligned}&{\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&1&2&5\end{pmatrix}}&=\\=&(146837)(2)(5)\end{aligned}}$

(1)

Alguns autors restringeixen la definició a aquelles permutacions que tenen exactament un cicle (és a dir, no s'hi permeten punts fixos).

Esquema de la permutació (2)

Exemple:

${\begin{aligned}&{\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&5&8&3&7&1\end{pmatrix}}&=\\=&(14625837)\end{aligned}}$

(2)

Més formalment, hom diu que una permutació d'un conjunt X, que és una funció bijectiva $\sigma :X\to X$, és un cicle si l'acció sobre X del subgrup generat per $\sigma$ té com a màxim una òrbita amb més d'un element. Aquest concepte s'usa sobretot si X és un conjunt finit; en aquest cas, és evident que l'òrbita més gran, S, també és finita. Sigui $s_{0}$ un element qualsevol de S, i escrivim $s_{i}=\sigma ^{i}(s_{0})\,$ per a qualsevol $i\in \mathbf {Z}$. Si S és finit, llavors existeix un nombre mínim $k\geq 1$ tal que $s_{k}=s_{0}$. Aleshores $S=\{s_{0},s_{1},\ldots ,s_{k-1}\}$, i $\sigma$ és la permutació definida per

$\sigma (s_{i})=s_{i+1}\quad {\mbox{per }}0\leq i<k$

i $\sigma (x)=x$ per a qualsevol element de $X\setminus S$. Els elements que no queden fixats per $\sigma$ es poden visualitzar com

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

Hom pot escriure un cicle emprant la notació de cicles compacta $\sigma =(s_{0}~s_{1}~\dots ~s_{k-1})$ (notem que no hi ha comes entre els elements, per evitar confusions amb una k-tupla). La longitud d'un cicle és el nombre d'elements de la seva òrbita més gran. Un cicle de longitud k també es diu k-cicle.

Hom diu que l'òrbita d'un 1-cicle és un punt fix de la permutació, però pensat com a permutació, tot 1-cicle és la permutació identitat. Quan s'utilitza la notació de cicles, hom acostuma a suprimir els 1-cicles, si no hi ha confusió.

Propietats bàsiques

Un dels resultats bàsics dels grups simètrics estableix que tota permutació es pot expressar com a producte de cicles disjunts (més precisament: cicles amb òrbites disjuntes); aquests cicles disjunts commuten els uns amb els altres, i l'expressió de la permutació és única llevat de l'ordre dels cicles (observem, però, que la notació de cicles no és única: cada k-cicle es pot escriure de k maneres diferents, depenent de l'elecció de $s_{0}$ en la seva òrbita). Per tant, el multiconjunt de les longituds dels cicles expressats d'aquesta forma (l'indicador de cicles) està unívocament determinat per la permutació, i també determina tant la signatura com la classe de conjugació de la permutació del grup simètric.

El nombre de k-cicles del grup simètric S_n ve donat, per $1\leq k\leq n$, per les següents fórmules equivalents:

${\begin{aligned}{\binom {n}{k}}(k-1)!&={\frac {n(n-1)\cdots (n-k+1)}{k}}\\&={\frac {n!}{(n-k)!k}}\end{aligned}}$

Un k-cicle té signatura (−1)^{k − 1}.

Transposicions

Matriu de transposicions

Una transposició és un cicle amb dos elements. Per exemple, la permutació de {1, 2, 3, 4} que envia 1 a 1, 2 a 4, 3 a 3 i 4 a 2 és una transposició (la transposició que intercanvia 2 i 4).

Propietats

Qualsevol permutació es pot expressar com a composició (producte) de transposicions; formalment, les transposicions són generadores del grup. De fet, si hom pren $a=1$, $b=2$, ..., $e=5$, llavors qualsevol permutació es pot expressar com a producte de transposicions adjacents, és a dir, com a transposicions de la forma $(k~~k+1)$; en aquest cas, $(1~2)$, $(2~3)$, $(3~4)$ i $(4~5)$. Això és una conseqüència del fet que qualsevol transposició es pot expressar com a producte de transposicions adjacents. Concretament, hom pot expressar la transposició $(k~~l)$ on $k<l$ movent k a la posició de l un pas a cada iteració, i llavors movent l a la posició original de k, la qual cosa intercanvia aquests dos elements i no realitza cap més canvi:

$(k~~l)=(k~~k+1)\cdot (k+1~~k+2)\cdots (l-1~~l)\cdot (l-2~~l-1)\cdots (k~~k+1)$.

La descomposició d'una permutació en producte de transposicions s'obté, per exemple, escrivint la permutació com a producte de cicles disjunts, i després separant iterativament cadascun dels cicles de longitud ≥3 en producte d'una transposició i un cicle de longitud igual a la longitud del cicle original menys 1:

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

Això significa que l'objectiu inicial és moure $a$ cap a $b$, $b$ cap a $c$, $y$ cap a $z$ i finalment $z$ cap a $a$. En comptes d'això, es poden desplaçar els elements mantenint $a$ al seu lloc, primer executant el factor dret (de la manera habitual en la notació d'operadors, i seguint la convenció de l'article Permutació). Amb aquesta operació hem aconseguit moure $z$ a la posició de $b$, de tal manera que, després de la primera permutació, els elements $a$ i $z$ encara no estan a les seves posicions finals. La transposició $(a~b)$, executada a continuació, identifica l'element $z$ mitjançant l'índex de $b$, per tal d'intercanviar el que inicialment eren $a$ i $z$.

Un dels resultats principals sobre grups simètrics afirma que o bé totes les descomposicions d'una permutació donada tenen un nombre parell de transposicions, o bé tenen totes un nombre senar de transposicions. Això permet que la paritat d'una permutació sigui un concepte ben definit (és a dir, no hi ha ambigüitat possible, perquè davant de dues descomposicions diferents, són ambdues o bé parelles o bé senars).

Bibliografia

• Anderson, Marlow; Feil, Todd. A First Course in Abstract Algebra. 2a edició. Chapman & Hall/CRC, 2005). ISBN 1-58488-515-7. 
• Fraleigh, John. A first course in abstract algebra. 5a edició. Addison Wesley, 1993. ISBN 978-0-201-53467-2. 
• Rotman, Joseph J. A First Course in Abstract Algebra with Applications. 3a edició. Prentice-Hall, 2006. ISBN 978-0-13-186267-8. 
• Sagan, Bruce E. The Symmetric Group / Representations, Combinatorial Algorithms & Symmetric Functions. Wadsworth & Brooks/Cole, 1991. ISBN 978-0-534-15540-7. 

Enllaços externs

• Permutations as a Product of Transpositions

Aquest article conté material de la pàgina cycle a PlanetMath, llicenciat sota la Llicència de Creative Commons Reconeixement i Compartir-Igual.

Viccionari