Grup de permutacions

En matemàtiques, un grup de permutacions és un grup G els elements del qual són permutacions d'un conjunt M donat, juntament amb l'operació de grup definida com la composició de permutacions de G (vistes com a funcions bijectives del conjunt M en ell mateix). El grup de totes les permutacions d'un conjunt M és el grup simètric de M, sovint denotat per Sim(M). El terme grup de permutacions és un subgrup del grup simètric. Si M = {1,2,...,n}, llavors Sim(M), el grup simètric de n elements, s'acostuma a simbolitzar S_n.

La forma en la qual els elements d'un grup de permutacions permuten els elements del conjunt s'anomena acció de grup. Les accions de grup tenen aplicacions en l'estudi de simetries, combinatòria i altres branques de les matemàtiques, la física i la química.

El popular trencaclosques cub de Rubik inventat l'any 1974 per Ernő Rubik s'ha emprat com a il·lustració dels grups de permutacions. Cada rotació d'una cara del cub produeix una permutació de les peces acolorides.

Propietats bàsiques i terminologia

En ser un subgrup d'un grup simètric, per tal que un conjunt de permutacions satisfaci els axiomes de grup i esdevingui un grup de permutacions, només cal:

1. que contingui la permutació identitat,
2. que contingui la permutació inversa per a cada permutació del conjunt, i
3. que sigui tancat per composició de les seves permutacions.

Una propietat general dels grups finits és que un subconjunt finit no buit d'un grup simètric és un grup si i només si el subconjunt és tancat per l'operació de grup.

El grau d'un grup de permutacions d'un conjunt finit és el nombre d'elements del conjunt. L'ordre d'un grup (de qualsevol tipus) és el nombre d'elements (la cardinalitat) del grup. Pel teorema de Lagrange, l'ordre de qualsevol grup de permutaciins finit de grau n ha de dividir n! (factorial de n, l'ordre del grup simètric S_n).

Notació

Article principal: Permutació § En teoria de grups

Com que les permutacions són bijeccions d'un conjunt, es poden representar mitjançant la notació en dues files de Cauchy. Aquesta notació llista els elements de M en la primera fila i, per a cada element, a sota, la seva imatge per la permutació, en la segona fila. Si $\sigma$ és una permutació del conjunt $M=\{x_{1},x_{2},\ldots ,x_{n}\}$, llavors

$\sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\sigma (x_{1})&\sigma (x_{2})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}$.

Per exemple, una permutació particular del conjunt {1,2,3,4,5} es pot escriure com:

$\sigma ={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}$;

això significa que σ satisfà σ(1)=2, σ(2)=5, σ(3)=4, σ(4)=3 i σ(5)=1. No cal que els elements de M apareguin en cap ordre especial a la primera fila: aquesta permutació també es pot escriure com

$\sigma ={\begin{pmatrix}3&2&5&1&4\\4&5&1&2&3\end{pmatrix}}$.

Les permutacions també s'acostumen a escriure en notació de cicles de tal manera que, dinat el conjunt M = {1, 2, 3, 4}, una permutació g de M amb g(1) = 2, g(2) = 4, g(4) = 1 i g(3) = 3 es pot escriure com (1, 2, 4)(3), o més comunament, (1, 2, 4), ja que 3 roman sense canvis; si els objectes es deniten per dígits o lletres individuals, es poden suprimir els espais i les comes, i llavors es pot escriure (124). La permutació del primer exemple es podria escriure en notació de cicles com $\sigma =(125)(34)$.

Composició de permutacions: el grup producte

Article principal: Permutació § En teoria de grups

El producte de dues permutacions es defineix com la seva composició, pensades com a funcions. En altres paraules, σ·π és la funció que envia qualsevol element x del conjunt a σ(π(x)). Notem que primer s'aplica la permutació de la dreta, a causa de la forma com s'escriu l'aplicació de la funció. Alguns autors prefereixen interpretar que primer actua la funció de l'esquerra, però, per això, cal escriure les permutacions a la dreta de l'argument, sovint com a exponent, de tal manera que la permutació σ que actua sobre l'element x produeix la imatge x^σ. Amb aquesta convenció, el producte ve donat per x^σ·π = (x^σ)^π. Tanmateix, això proporciona una regla diferent per a la multiplicació de permutacions.

Com que la composició de dues bijeccions és una altra bijecció, el producte de dues permutacions és una altra permutació. En notació de dues files, el producte de dues permutacions s'obté reordenant les columnes de la segona permutació (la de l'esquerra) de tal manera que la seva primera fila sigui idèntica a la segona fila de la primera permutació (la de la dreta). Llavors, el producte es pot escriure com la primera fila de la primera permutació sobre la segona fila de la segona permutació modificada. Per exemple, si considerem les permutacions

$P={\begin{pmatrix}1&2&3&4&5\\2&4&1&3&5\end{pmatrix}}$ i $Q={\begin{pmatrix}1&2&3&4&5\\5&4&3&2&1\end{pmatrix}}$,

el producte QP és:

${\begin{aligned}QP&={\begin{pmatrix}1&2&3&4&5\\5&4&3&2&1\end{pmatrix}}{\begin{pmatrix}1&2&3&4&5\\2&4&1&3&5\end{pmatrix}}\\&={\begin{pmatrix}2&4&1&3&5\\4&2&5&3&1\end{pmatrix}}{\begin{pmatrix}1&2&3&4&5\\2&4&1&3&5\end{pmatrix}}\\&={\begin{pmatrix}1&2&3&4&5\\4&2&5&3&1\end{pmatrix}}.\end{aligned}}$

La composició de permutacions, quan s'escriuen en notació de cicles, s'obté per juxtaposició de les dues permutacions (amb la segona escrita a l'esquerra) i llavors simplificant, si es vol, fins a obtenir una forma en cicles disjunts. Així, en notació de cicles, el producte anterior s'escriu com:

$Q\cdot P=(15)(24)\cdot (1243)=(1435).$

Com que la composició de funcions és associativa, també ho és el producte de permutacions: (σ·π)·ρ = σ·(π·ρ). Per tant, els productes de dues o més permutacions s'acostumen a escriure sense necessitat d'afegir parèntesis per expressar els agrupaments.

Element neutre i element invers

La permutació identitat, que envia cada element a ell mateix, és l'element neutre per aquest producte. En notació de dues files, la identitat és

${\begin{pmatrix}1&2&3&\cdots &n\\1&2&3&\cdots &n\end{pmatrix}}$.

En notació de cicles, e = (1)(2)(3)...(n), que per convenció també es denota per (1) o fins i tot per ().

Com que les bijeccions admeten inverses, també n'admeten les permutacions, i la inversa σ⁻¹ de σ també és una permutació. Explícitament, sempre que σ(x)=y es té també que σ⁻¹(y)=x. En notació de dues files, hom pot obtenir la inversa si s'intercamvien les dues files (i ordenant les columnes si hom prefereix que la primera fila estigui en un ordre determinat). Per exemple,

${\begin{aligned}{\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}^{-1}&={\begin{pmatrix}2&5&4&3&1\\1&2&3&4&5\end{pmatrix}}\\&={\begin{pmatrix}1&2&3&4&5\\5&1&4&3&2\end{pmatrix}}.\end{aligned}}$

Per obtenir l'invers d'un cicle, s'ha d'invertir l'ordre dels seus elements. Així,

${\begin{aligned}(125)^{-1}&=(521)\\&=(152).\end{aligned}}$

Per obtenir l'invers d'un producte de cicles, primer cal invertir l'ordre dels cicles, i després cal prendre l'invers de cada cicle, com s'ha vist abans. Així,

${\begin{aligned}\left[(125)(34)\right]^{-1}&=(34)^{-1}(125)^{-1}\\&=(43)(521)\\&=(34)(152).\end{aligned}}$

Com que té un producte associatiu, un element neutre, i invers per a cada element, això fa que el conjunt de totes les permutacions de M sigui un grup, simbolitzat per Sim(M).

Exemples

Considerem el següent conjunt G₁ de permutacions sobre el conjunt M = {1,2,3,4}:

• e = (1)(2)(3)(4)= (1)

Aquest és l'element neutre: la permutació trivial que fixa cada element.

• a = (1 2)(3)(4) = (1 2)

Aquesta permutació invercanvia 1 i 2, i deixa fixos 3 i 4.

• b = (1)(2)(3 4) = (3 4)

Aquesta permutació intercanvia 3 i 4, i deixa fixos 1 i 2.

• ab = (1 2)(3 4)

Aquesta permutació, que és la composició de les dues permutacions anteriors, intercanvia simultàniament 1 i 2, i per altra banda 3 i 4.

G₁ forma un grup, ja que aa = bb = e, ba = ab, i abab = e. Aquest grup de permutacions és isomorf, com a grup abstracte, al grup de Klein V₄.

Un altre exemple és el grup de simetria d'un quadrat. Numerem els vèrtexs del quadrat com 1, 2, 3 i 4 (on 1 representa el vèrtex superior esquerre, i continuem numerant en sentit antihorari). Les simetries estan determinades per les imatges dels vèrtexs, que, al seu torn, es poden descriure mitjançant permutacions. La rotació de 90° (antihorària) al voltant del centre del quadrat ve descrita per la permutació (1234). Les rotacions de 180° i 270° venen donades per (13)(24) i (1432), respectivament. La reflexió respecte a l'eix horitzontal que passa pel centre ve donada per (12)(34), i la corresponent reflexió respecte l'eix vertical és (14)(23). La reflexió respecte l'eix diagonal 1,3 és (24), i la reflexió respecte l'eix diagonal 2,4 és (13). L'única simetria que manca és la identitat (1)(2)(3)(4). Aquest grup de permutacions es coneix com a grup diedral d'ordre 8.

Accions de grup

Article principal: Acció de grup

En l'exemple anterior sobre el grup de simetria d'un quadrat, les permutacions "descriuen" el moviment dels vèrtexs del quadrat induïts pel grup de simetria. És habitual dir que aquests elements del grup "actuen" sobre el conjunt de vèrtexs del quadrat. Aquesta idea es pot formalitzar definint una acció de grup.

Sigui G un grup i sigui M un conjunt no buit. Una acció de G sobre M és una funció f: G × M → M tal que

• f(1, x) = x, per a tot x de M (1 és l'element neutre del grup G, i
• f(g, f(h, x)) = f(gh, x), per a qualssevol g,h de G i x de M.

Aquesta darrera condició es pot reformular dient que l'acció indueix un homomorfisme de grups de G en Sim(M). Un tal homomorfisme s'anomena representació (de permutacions) de G sobre M.

Per a qualsevol grup de permutacions, hom diu que l'acció que envia (g, x) ↦ g(x) és l'acció natural de G sobre M. Hom assumeix aquesta acció llevat que es digui el contrari. En l'exemple del grup de simetria del quadrat, l'acció del grup sobre el conjunt de vèrtexs és l'acció natural. Tot iaixò, aquest grup també indueix una acció sobre el conjunt dels quatre triangles del quadrat, que són: t₁ = 234, t₂ = 134, t₃ = 124 i t₄ = 123. També actua sobre les dues diagonals: d₁ = 13 i d₂ = 24.

Element del grup	Acció sobre els triangles	Acció sobre les diagonals
(1)	(1)	(1)
(1234)	(t1 t₂ t₃ t₄)	(d1 d₂)
(13)(24)	(t1 t₃)(t₂ t₄)	(1)
(1432)	(t1 t₄ t₃ t₂)	(d1 d₂)
(12)(34)	(t1 t₂)(t₃ t₄)	(d1 d₂)
(14)(23)	(t1 t₄)(t₂ t₃)	(d1 d₂)
(13)	(t1 t₃)	(1)
(24)	(t₂ t₄)	(1)

Teorema de Cayley

Tot grup G pot actuar sobre ell mateix (hom interpreta els elements del grup com a elements del conjunt M) de diverses maneres. En particular, existeix una acció regular donada per la multiplicació (per l'esquerra) del grup. És a dir, f(g, x) = gx per a qualssevol g i x de G. Fixat un element g, la funció f_g(x) = gx és una bijecció sobre Gi, per tant, una permutació del "conjunt" G. Cada element de G es pot pensar com una permutació en aquest sentit, de tal manera que G és isomorf a un grup de permutacions; aquest és el contingut del teorema de Cayley.

Considerem el grup G₁ actuant sobre el conjunt {1,2,3,4} anterior. Denotem els elements del grup per e, a, b i c = ab = ba. L'acció de G₁ sobre ell mateix descrita pel teorema de Cayley proporciona la següent representació de permutacions:

f_e ↦ (e)(a)(b)(c)

f_a ↦ (ea)(bc)

f_b ↦ (eb)(ac)

f_c ↦ (ec)(ab).

Grups de permutació isomorfs

Si G i H són dos grups de permutacions sobre els conjunts X i Y amb accions f₁ i f₂ respectivament, hom diu que G i H són isomorfs (com a grups de permutacions) si existeixen una funció bijectiva λ : X → Y i un isomorfisme de grups ψ : G → H tals que:

λ(f₁(g, x)) = f₂(ψ(g), λ(x)) per a qualssevol g de G i x de X.

Si X = Y, això és equivalent al fet que G i H siguin conjugats com a subgrups de Sim(X). El cas especial en què G = H i ψ és la funció identitat dona lloc al concepte d'accions equivalents d'un grup.

En l'exemple anterior sobre les simetries d'un quadrat, l'acció natural sobre el conjunt {1,2,3,4} és equivalent a l'acció sobre els triangles. La bijecció λ entre els conjunts ve donada per i ↦ t_i. L'acció natural del grup G₁ i la seva acció sobre ell mateix (via multiplicació per l'esquerra) no són equivalents, ja que l'acció natural té punts fixos i la segona no en té.

Història

L'estudi dels grups va sorgir com a forma de comprendre el funcionament dels grups de permutacions. Ja l'any 1770 Lagrange estudià intensament les permutacions en la seva obra sobre les soluciins algebraiques de les equacions polinòmiques. Aquesta branca de les matemàtiques patí un notable desenvolupament, i a mitjans del segle xix ja existia una teoria dels grups de permutacions ben desenvolupada, recollida per Camille Jordan en el seu llibre Traité des Substitutions et des Équations Algébriques de 1870. Aquesta obra de Jordan estava basada, al seu torn, en les investigacions realitzades per Évariste Galois l'any 1832.

Quan Cayley va introduir el concepte de grup abstracte, encara no estava clar si es tractava o no d'una col·lecció d'objectes més gran que els ja coneguts grups de permutacions (que per l'època tenien una definició diferent a l'actual). Cayley va establir, mitjançant la demostració del teorema de Cayley, que tots dos conceptes eren equivalents.

Un altre text clàssic que conté diversos capítols sobre l'estudi dels grups de permutacions és l'obra de William Burnside Theory of Groups of Finite Order de 1911. La primera meitat del segle xx fou un període improductiu en l'estudi de la teoria de grups en general, però l'interès va revifar entorn de la dècada de 1950, quan es van reimprimir les obres en alemany de Helmut Wielandt sota el títol de Finite Permutation Groups l'any 1964.

Bibliografia

• Cameron, Peter J. Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, 1994. ISBN 0-521-45761-0. 
• Dixon, John D.; Mortimer, Brian. Permutation Groups. 163. Springer-Verlag, 1996 (Graduate Texts in Mathematics). ISBN 0-387-94599-7. 
• Rotman, Joseph J. A First Course in Abstract Algebra with Applications. 3a edició. Pearson Prentice-Hall, 2006. ISBN 0-13-186267-7. 

Bibliografia addicional

• Seress, Ákos. Permutation group algorithms. 152. Cambridge University Press, 2003 (Cambridge Tracts in Mathematics). ISBN 978-0521661034. 
• Bhattacharjee, Meenaxi; Macpherson, Dugald; Möller, Rögnvaldur G.; Neumann, Peter M. Notes on Infinite Permutation Groups. 1698. Springer-Verlag, 1998 (Lecture Notes in Mathematics). ISBN 9783540649656. 
• Cameron, Peter J. Permutation Groups. 45. Cambridge University Press, 1999 (LMS Student Text). ISBN 9780521653787. 
• Cameron, Peter J. Oligomorphic Permutation Groups. Cambridge University Press, 1990. ISBN 978-0521388368. 

Enllaços externs

• Michiel Hazewinkel (ed.). Permutation group. Encyclopedia of Mathematics (en anglès). Springer, 2001. ISBN 978-1-55608-010-4. 
• Alexander Hulpke. GAP Data Library "Transitive Permutation Groups".