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ó (Plantilla:EquationNote)

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:

Plantilla:NumBlk

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ó (Plantilla:EquationNote)

Exemple:

Plantilla:NumBlk

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 𝐙$. Si S és finit, llavors existeix un nombre mínim $k\ge 1$ tal que $s_k=s_0$. Aleshores $S=\{s_0,s_1,\dots ,s_{k-1}\}$, i $\sigma$ és la permutació definida per

$\sigma (s_i)=s_{i+1}\text{per }0\le 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\le k\le n$, per les següents fórmules equivalents:

$\begin{array}{cc}(\genfrac{}{}{0ex}{}{n}{k})(k-1)!& =\frac{n(n-1)\cdots (n-k+1)}{k}\\ & =\frac{n!}{(n-k)!k}\end{array}$

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 $(kk+1)$; en aquest cas, $(12)$, $(23)$, $(34)$ i $(45)$. 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ó $(kl)$ 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:

$(kl)=(kk+1)\cdot (k+1k+2)\cdots (l-1l)\cdot (l-2l-1)\cdots (kk+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:

$(abcd\dots yz)=(ab)\cdot (bcd\dots yz)$

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ó $(ab)$, 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

• Plantilla:Ref-llibre
• Plantilla:Ref-llibre
• Plantilla:Ref-llibre
• Plantilla:Ref-llibre

Enllaços externs

• Permutations as a Product of Transpositions

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