Cicle (permutació)

De la Viquipèdia, l'enciclopèdia lliure

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ó[modifica]

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).[1]

Exemple:

 

 

 

 

(1)

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

Esquema de la permutació (2)

Exemple:

 

 

 

 

(2)

Més formalment, hom diu que una permutació d'un conjunt X, que és una funció bijectiva , és un cicle si l'acció sobre X del subgrup generat per té com a màxim una òrbita amb més d'un element.[3] 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 un element qualsevol de S, i escrivim per a qualsevol . Si S és finit, llavors existeix un nombre mínim tal que . Aleshores , i és la permutació definida per

i per a qualsevol element de . Els elements que no queden fixats per es poden visualitzar com

.

Hom pot escriure un cicle emprant la notació de cicles compacta (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.[4] Quan s'utilitza la notació de cicles, hom acostuma a suprimir els 1-cicles, si no hi ha confusió.[5]

Propietats bàsiques[modifica]

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 en la seva òrbita).[6] 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.[7]

El nombre de k-cicles del grup simètric Sn ve donat, per , per les següents fórmules equivalents:

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

Transposicions[modifica]

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[modifica]

Qualsevol permutació es pot expressar com a composició (producte) de transposicions; formalment, les transposicions són generadores del grup.[8] De fet, si hom pren , , ..., , llavors qualsevol permutació es pot expressar com a producte de transposicions adjacents, és a dir, com a transposicions de la forma ; en aquest cas, , , i . 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ó on 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:

.

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:

Això significa que l'objectiu inicial és moure cap a , cap a , cap a i finalment cap a . En comptes d'això, es poden desplaçar els elements mantenint 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 a la posició de , de tal manera que, després de la primera permutació, els elements i encara no estan a les seves posicions finals. La transposició , executada a continuació, identifica l'element mitjançant l'índex de , per tal d'intercanviar el que inicialment eren i .

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.[9] 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).

Referències[modifica]

  1. Bogart, Kenneth P. Introductory Combinatorics. 2a edició. Harcourt, Brace, Jovanovich, 1990, p. 486. ISBN 0-15-541576-X. 
  2. Gross, Jonathan L. Combinatorial Methods with Computer Applications. Chapman & Hall/CRC, 2008, p. 29. ISBN 978-1-58488-743-0. 
  3. Fraleigh 1993, p. 103
  4. Rotman 2006, p. 108
  5. Sagan 1991, p. 2
  6. Per tal de ser tècnicament correcte, una factorització hauria de contenir un 1-cicle per a cada punt fix de la permutació (vegeu Rotman 2006, pàg. 113-114).
  7. Rotman 2006, pàg. 117, 121
  8. Rotman 2006, Prop. 2.35
  9. Rotman 2006, p. 122

Bibliografia[modifica]

  • 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[modifica]

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