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*). O termo *grupo de permutacións* significa así un subgrupo do grupo simétrico. Se {{Nowrap|1=*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.
[miniatura| O popular crebacabezas [Cubo de Rubik|O cubo de Rubik inventado en 1974 por Ernő Rubik utilizouse como ilustración do grupo de permutacións. Cada rotación dunha capa do cubo produce unha permutación das cores da superficie e é un membro do grupo. O grupo de permutacións do cubo chámase grupo do cubo de Rubik.]]

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

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

Algúns autores prefiren outra convención,

 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 = (1 5)(2 4) \cdot (1 2 4 3) = (1 4 3 5).

* 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 ().

Dado que as bixeccións teñen inversas, tamén as teñen as permutacións, e por tanto a inversa *σ* −1 de *σ* tamén é unha permutación. Explicitamente, sempre que *σ* (*x*)= *y* tamén se ten *σ* −1(*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í,

:  (1 2 5)^{-1} = (5 2 1) = (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í,

:  [(1 2 5)(3 4)]^{-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*1 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*1 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*4.

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

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*). 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. 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*1 = 234, *t*2 = 134, *t*3 = 124 e *t*4 = 123. Tamén actúa sobre as dúas diagonais: *d*1 = 13 e *d*2 = 24.

## 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*.  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  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*1 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*1 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*1 e *f*2 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  e un isomorfismo de grupo  tal que

: *λ*(*f*1(*g*, *x*)) = *f*2(*ψ*(*g*), *λ*(*x*)) para todo *g* en *G* e *x* en *X*.

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

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 . A acción natural do grupo *G*1 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 
## Véxase tamén 
### Bibliografía 
*  
*  
* 
* 

### Outros artigos 
* Grupo 2-transitivo
* Grupo simétrico
* Grupo de Mathieu

### Ligazóns externas 
* 
* Alexander Hulpke. GAP Data Library "Transitive Permutation Groups" .