Grupo de permutacións

En matemáticas, un grupo de permutacións é un grupo G cuxos elementos son permutacións dun conxunto M dado e cuxa operación de grupo é a composición de permutacións en G (que se consideran funcións bixectivas do conxunto M en si mesmo). O grupo de todas as permutacións dun conxunto M é o grupo simétrico de M, a miúdo escrito como Sym(M).^[1] O termo grupo de permutacións significa así un subgrupo do grupo simétrico. Se M = {1, 2, ..., n} entón Sym(M) adoita denotarse por S_n, e pódese chamar o grupo simétrico en n letras.

Segundo o teorema de Cayley, todo grupo é isomorfo a algún grupo de permutacións.

A forma en que os elementos dun grupo de permutacións permutan os elementos do conxunto chámase acción de grupo. As accións de grupo teñen aplicacións no estudo das simetrías, a combinatoria e moitas outras ramas das matemáticas, a física e a química.

Propiedades básicas e terminoloxía

Un grupo de permutacións é un subgrupo dun grupo simétrico; é dicir, os seus elementos son permutacións dun conxunto dado. É polo tanto un subconxunto dun grupo simétrico que está pechado baixo composición de permutacións, contén a permutación identidade e contén a permutació inversa de cada un dos seus elementos.^[2] Unha propiedade xeral dos grupos finitos implica que un subconxunto finito non baleiro dun grupo simétrico é un grupo de permutacións se e só se está pechado baixo a composición de permutacións.^[3]

O grao dun grupo de permutacións dun conxunto finito é o número de elementos do conxunto (os elementos que permutan). A orde dun grupo (de calquera tipo) é o número de elementos (cardinalidade) do grupo. Segundo o teorema de Lagrange, a orde de calquera grupo finito de permutacións de grao n (que serían un conxunto finito das permutacións deses n elementos) debe dividir n! xa que n factorial é a orde do grupo simétrico S_n.

Notación

Dado que as permutacións son bixeccións dun conxunto, pódense representar mediante a notación de dúas liñas de Cauchy. Esta notación enumera cada un dos elementos de M na primeira fila e, para cada elemento, a súa imaxe mediante a permutación debaixo dela na segunda fila. Se $\sigma$ é unha permutación do conxunto $M=\{x_{1},x_{2},\ldots ,x_{n}\}$ entón,

\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}}.

Por exemplo, unha permutación particular do conxunto {1, 2, 3, 4, 5} pódese escribir como

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

isto significa que σ satisfai σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3 e σ(5) = 1. Os elementos de M non necesitan aparecer nunha orde especial na primeira fila, polo que a mesma permutación tamén se pode escribir como

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

As permutacións tamén se escriben a miúdo en notación cíclica^[4] de xeito que dado o conxunto M = {1, 2, 3, 4}, unha permutación g de M con g(1) = 2, g(2) = 4, g(4) = 1 e g(3) = 3 escribiranse como (1, 2, 4)(3), ou máis comunmente, (1, 2, 4) xa que 3 fica sen mudar; se os obxectos se denotan con letras ou díxitos simples, tamén se pode prescindir das comas e dos espazos, e temos unha notación do tipo (124). A permutación escrita arriba en notación de 2 liñas escribiríase en notación de ciclo como $\sigma =(125)(34).$

Composición das permutacións (o produto do grupo)

O produto de dúas permutacións defínese como a súa composición como funcións, polo tanto, dadas dúas permutacións, sigma e pi, $\sigma \cdot \pi$ é a función que mapea calquera elemento x do conxunto con $\sigma (\pi (x))$ . Teña en conta que a permutación máis á dereita aplícase primeiro ao argumento, debido á forma en que se escribe a composición da función.^[5]

Algúns autores prefiren outra convención,^[6] ^[7] ^[8] este artigo usa a convención onde se aplica primeiro a permutación máis na dereita.

Por exemplo, dadas as permutacións,

P={\begin{pmatrix}1&2&3&4&5\\2&4&1&3&5\end{pmatrix}}\quad {\text{ e }}\quad Q={\begin{pmatrix}1&2&3&4&5\\5&4&3&2&1\end{pmatrix}},

o produto QP é:

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}}.

Digamos que:

o 1 vai ao 2 e o 2 vai ao 4 por tanto o 1 vai ao 4.
o 2 vai ao 4 e o 4 vai ao 2 por tanto o 2 vai ao 2.
o 3 vai ao 1 e o 1 vai ao 5 por tanto o 3 vai ao 5.
o 4 vai ao 3 e o 3 vai ao 3 por tanto o 4 vai ao 3.
o 5 vai ao 5 e o 5 vai ao 1 por tanto o 5 vai ao 1.

A composición das permutacións, cando se escriben en notación de ciclo, obtense xustapoñendo as dúas permutacións (coa segunda escrita á esquerda) e simplificando despois a unha forma de ciclo disxunto se se desexa. Así, o produto anterior viría dado por:

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

En Q, o 1 vai ao 5 e o 5 vai ao 1, o 2 vai ao 4 e 4 vai ao 2 e o 3 vai para o 3.
En P, o 1 vai ao 2, o 2 vai ao 4, o 4 vai ao 3, o 3 vai ao 1 e o 4 vai para o 4.
En QP, o 1 vai para o 4, o 4 para o 3, o 3 para o 5, o 5 para o 1, e o 2 para o 2.

Dado que a composición da función é asociativa, tamén o é a operación do produto nas permutacións: $(\sigma \cdot \pi )\cdot \rho =\sigma \cdot (\pi \cdot \rho )$ . Polo tanto, os produtos de dúas ou máis permutacións adoitan escribirse sen engadir parénteses para expresar o agrupamento; tamén adoitan escribirse sen un punto ou outro signo para indicar a multiplicación (os puntos do exemplo anterior foron engadidos para destacar, polo que simplemente se escribirían como $\sigma \pi \rho$ ).

Elemento neutro e inversos

A permutación identidade, que asigna cada elemento do conxunto a si mesmo, é o elemento neutro para este produto. En notación de dúas liñas, a identidade é

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

En notación de ciclo, e = (1)(2)(3)... ( n ) que por convención tamén se denota con só (1) ou mesmo ().^[9]

Dado que as bixeccións teñen inversas, tamén as teñen as permutacións, e por tanto a inversa σ ⁻¹ de σ tamén é unha permutación. Explicitamente, sempre que σ (x)= y tamén se ten σ ⁻¹(y)=x. Na notación de dúas liñas pódese obter a inversa trocando as dúas liñas (e ordenando as columnas se se desexa que a primeira liña estea nunha orde determinada). Por exemplo

{\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}}.

Para obter a inversa dun único ciclo, invertimos a orde dos seus elementos. Así,

(125)^{-1}=(521)=(152).

Para obter a inversa dun produto de ciclos, primeiro invertemos a orde dos ciclos e despois tomamos a inversa de cada un como se indica arriba. Así,

[(125)(34)]^{-1}=(34)^{-1}(125)^{-1}=(43)(521)=(34)(152).

Tendo un produto asociativo, un elemento de identidade e inversas para todos os seus elementos, fai que o conxunto de todas as permutacións de M se converta nun grupo, Sym(M), grupo simétrico dos elementos de M, que é tamén un grupo de permutacións.

Exemplos

Considere o seguinte conxunto G₁ de permutacións do conxunto M = {1, 2, 3, 4}:

e = (1)(2)(3)(4) = (1)
- Esta é a identidade, a permutación que fixa cada elemento.
a = (12)(3)(4) = (12)
- Esta permutación troca 1 e 2, e mantén 3 e 4.
b = (1)(2)(34) = (34)
- Troca 3 e 4, e mantén 1 e 2.
ab = (12)(34)
- Esta permutación, que é a composición das dúas anteriores, troca 1 con 2 e 3 con 4.

G₁ forma un grupo, xa que aa = bb = e, ba = ab, e abab = e. Este grupo de permutacións é, como grupo abstracto, o grupo de Klein V₄.

Como outro exemplo considere o grupo de simetrías dun cadrado. Sexan os vértices dun cadrado rotulados 1, 2, 3 e 4 (en sentido antihorario ao redor do cadrado comezando por 1 na esquina superior esquerda). As simetrías están determinadas polas imaxes dos vértices, que á súa vez poden ser descritas por permutacións. A rotación de 90° (en sentido antihorario) arredor do centro do cadrado descríbese mediante a permutación (1234). As rotacións de 180° e 270° veñen dadas por (13)(24) e (1432), respectivamente. A reflexión sobre a liña horizontal polo centro vén dada por (12)(34) e a reflexión da liña vertical correspondente é (14)(23). A reflexión sobre a recta 1,3−diagonal é (24) e a reflexión sobre a diagonal 2,4−é (13). A única simetría restante é a identidade (1)(2)(3)(4). Este grupo de permutación coñécese, como grupo abstracto, como o grupo diédrico de orde 8.

Accións de grupo

No exemplo anterior do grupo de simetría dun cadrado, as permutacións "describen" o movemento dos vértices do cadrado inducido polo grupo de simetrías. É habitual dicir que estes elementos de grupo están "actuando" sobre o conxunto de vértices do cadrado. Esta idea pódese concretar definindo formalmente unha acción de grupo.^[10]

Sexa G un grupo e M un conxunto non baleiro. Unha acción de G sobre M é unha función f : G × M → M tal que

f (1, x) = x, para todo x en M (1 é o elemento de identidade (neutro) do grupo G), e
f (g, f(h, x)) = f (gh, x), para todo os g, h en G e todo x en M .

Este par de condicións tamén se pode expresar dicindo que a acción induce un homomorfismo de grupos de G a Sym (M).^[10] Calquera homomorfismo deste tipo chámase representación (permutación) de G en M.

Para calquera grupo de permutacións, a acción que envía (g, x) → g (x) chámase acción natural de G sobre M. Esta é a acción que se asume a non ser que se indique o contrario.^[10] No exemplo do grupo de simetría do cadrado, a acción do grupo sobre o conxunto de vértices é a acción natural. Non obstante, este grupo tamén induce unha acción sobre o conxunto de catro triángulos do cadrado, que son: t₁ = 234, t₂ = 134, t₃ = 124 e t₄ = 123. Tamén actúa sobre as dúas diagonais: d₁ = 13 e d₂ = 24.

Elemento de grupo	Acción sobre triángulos	Acción sobre diagonais
(1)	(1)	(1)
(1234)	(t₁ t₂ t₃ t₄)	(d₁ d₂)
(13)(24)	(t₁ t₃)(t₂ t₄)	(1)
(1432)	(t₁ t₄ t₃ t₂)	(d₁ d₂)
(12)(34)	(t₁ t₂)(t₃ t₄ )	(d₁ d₂)
(14)(23)	(t₁ t₄)(t₂ t₃)	(d₁ d₂)
(13)	(t₁ t₃)	(1)
(24)	(t₂ t₄)	(1)

Accións transitivas

A acción dun grupo G sobre un conxunto M dise que é transitiva se, por cada dous elementos s, t de M, hai algún elemento do grupo g tal que g(s) = t. De forma equivalente, o conxunto M forma unha única órbita baixo a acción de G. ^[11] Dos exemplos anteriores, o grupo {e, (12), (34), (12)(34)} de permutacións de {1, 2, 3, 4} non é transitivo (ningún elemento do grupo leva 1 a 3) mais o grupo de simetrías dun cadrado é transitivo nos vértices.

Accións primitivas

Un grupo de permutacións G que actúa transitivamente sobre un conxunto finito M non baleiro é non primitivo se hai algunha partición do conxunto non trivial de M que se conserva pola acción de G, onde "non trivial" significa que a partición non é a partición en conxuntos unitarios nin a partición cunha soa parte. En caso contrario, se G é transitivo mais non conserva ningunha partición non trivial de M, o grupo G é primitivo.

Por exemplo, o grupo de simetrías dun cadrado é non primitivo nos vértices: se están numerados 1, 2, 3, 4 en orde cíclica, entón a partición {{1, 3}, {2, 4}} en pares opostos é preservado por cada elemento do grupo. Por outra banda, o grupo simétrico completo nun conxunto M é sempre primitivo.

Teorema de Cayley

Calquera grupo G pode actuar sobre si mesmo (considéranse os elementos do grupo como o conxunto M) de moitas maneiras. En particular, hai unha acción regular dada pola multiplicación (esquerda) no grupo. É dicir, f(g, x) = gx para todo g e x en G. Para cada g fixo, a función f_g (x) = gx é unha bixección sobre G e polo tanto unha permutación do conxunto de elementos de G. Cada elemento de G pódese pensar deste xeito como unha permutación, polo que G é isomorfo a un grupo de permutacións; este é o contido do teorema de Cayley.

Por exemplo, considere o grupo G₁ que actúa sobre o conxunto {1, 2, 3, 4} indicado anteriormente. Denotémos os elementos deste grupo por e, a, b e c = ab = ba. A acción de G₁ sobre si mesmo descrita no teorema de Cayley dá a seguinte representación de permutacións:

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

f_a ↦ (ea)(bc)

f_b ↦ (eb) (ac)

f_c ↦ (ec)(ab).

Isomorfismos de grupos de permutacións

Se G e H son dous grupos de permutacións en conxuntos X e Y con accións f₁ e f₂ respectivamente, entón dicimos que G e H son isomorfos de permutacións (ou isomorfos como grupos de permutacións) se existe un mapa bixectivo λ : X → Y e un isomorfismo de grupo ψ : G → H tal que

λ(f₁(g, x)) = f₂(ψ(g), λ(x)) para todo g en G e x en X.^[12]

Se X = Y isto equivale a que G e H se conxuguen como subgrupos de Sym(X).^[13] O caso especial onde G = H e ψ é o mapa identidade dá lugar ao concepto de accións equivalentes dun grupo.^[14]

No exemplo das simetrías dun cadrado dado anteriormente, a acción natural sobre o conxunto {1,2,3,4} é equivalente á acción sobre os triángulos. A bixección λ entre os conxuntos vén dada por i ↦ t_i. A acción natural do grupo G₁ anterior e a súa acción sobre si mesmo (mediante a multiplicación pola esquerda) non son equivalentes xa que a acción natural ten puntos fixos e a segunda acción non.

Notas

↑ The notations S_M and S^M are also used.
↑ Rotman 2006
↑ Rotman 2006
↑ para abreviar ou por facilidade alxébrica.
↑ Biggs, Norman L.; White, A. T. (1979). Permutation groups and combinatorial structures. Cambridge University Press. ISBN 0-521-22287-7.
↑ Dixon & Mortimer 1996, p. 3 Exemplo 1.2.2
↑ Cameron, Peter J. (1999). Permutation groups. Cambridge University Press. ISBN 0-521-65302-9.
↑ Jerrum, M. (1986). "A compact representation of permutation groups". J. Algorithms 7 (1): 60–78. doi:10.1016/0196-6774(86)90038-6.
↑ Rotman 2006
↑ ^10,0 ^10,1 ^10,2 Dixon & Mortimer 1996
↑ Artin 1991, p. 177
↑ Dixon & Mortimer 1996, p. 17
↑ Dixon & Mortimer 1996
↑ Cameron 1994

Véxase tamén

Bibliografía

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

Outros artigos

Ligazóns externas

"Permutation group". Encyclopedia of Mathematics. EMS Press. 2001 [1994].
Alexander Hulpke. GAP Data Library "Transitive Permutation Groups" Arquivado 19 de xaneiro de 2021 en Wayback Machine..

[1] The notations S_M and S^M are also used.

[2] Rotman 2006

[3] Rotman 2006

[4] ra abreviar ou por facilidade alxébrica.

[5] Biggs, Norman L.; White, A. T. (1979). Permutation groups and combinatorial structures. Cambridge University Press. ISBN 0-521-22287-7.

[6] Dixon & Mortimer 1996, p. 3 Exemplo 1.2.2

[7] Cameron, Peter J. (1999). Permutation groups. Cambridge University Press. ISBN 0-521-65302-9.

[8] Jerrum, M. (1986). "A compact representation of permutation groups". J. Algorithms 7 (1): 60–78. doi:10.1016/0196-6774(86)90038-6.

[9] Rotman 2006

[Dixon96-10] 10,0 ^10,1 ^10,2 Dixon & Mortimer 1996

[11] Artin 1991, p. 177

[12] Dixon & Mortimer 1996, p. 17

[13] Dixon & Mortimer 1996

[14] Cameron 1994

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]