Grupo de permutaciones

El cubo de Rubik, inventado en 1974 por Ernő Rubik, se ha utilizado para como ejemplo de grupo de permutación. Cada rotación de una cara del cubo da como resultado una permutación de los colores de su superficie, y es un miembro del grupo del cubo de Rubik

En matemáticas, un grupo de permutaciones es un grupo G cuyos elementos son permutaciones de un conjunto M dado, y cuya operación de grupo es la composición de permutaciones en G (que son consideradas como biyecciones del conjunto M sobre sí mismo). El grupo de todas las permutaciones de un conjunto M es el grupo simétrico de M, a menudo escrito como Sim(M).​ El término "grupo de permutaciones" significa, por tanto, un subgrupo del grupo simétrico. Si M= {1, 2, ..., n}, entonces Sim(M) generalmente se denota por S_n y puede denominarse como grupo simétrico de n letras.

Por el teorema de Cayley, cada grupo es isomorfo con respecto a algún grupo de permutación.

La forma en que los elementos de un grupo de permutación permutan los elementos del conjunto se llama acción de grupo. Las acciones grupales tienen aplicaciones en el estudio de simetrías, combinatoria y muchas otras ramas de las matemáticas, la física y la química.

Propiedades básicas y terminología

Un grupo de permutación es un subgrupo de un grupo simétrico; es decir, sus elementos son permutaciones de un conjunto dado. Por lo tanto, es un subconjunto de un grupo simétrico que es cerrado bajo la composición de permutaciones, contiene la permutación identidad y contiene la permutación inversa de cada uno de sus elementos.​ Una propiedad general de los grupos finitos implica que un subconjunto finito no vacío de un grupo simétrico es un grupo de permutación si y solo si está cerrado bajo la composición de permutaciones.​

El grado de un grupo de permutaciones de un conjunto finito es el número de elementos del conjunto. El orden de un grupo (de cualquier tipo) es el número de elementos (cardinalidad) del grupo. Según el teorema de Lagrange, el orden de cualquier grupo de permutaciones finito de grado n debe dividir a n!, ya que n-factorial es el orden del grupo simétrico S_n.

Notación

Dado que las permutaciones son las biyecciones de un conjunto, se pueden representar mediante la "notación de dos líneas" de Cauchy.​ Esta notación enumera cada uno de los elementos de M en la primera fila, y para cada elemento, su imagen bajo la permutación debajo de él en la segunda fila. Si $\sigma$ es una permutación del conjunto $M=\{x_{1},x_{2},\ldots ,x_{n}\}$ entonces,

$\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 ejemplo, una permutación particular del conjunto {1, 2, 3, 4, 5} se puede escribir como

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

esto significa que σ satisface σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3, y σ(5) = 1. No es necesario que los elementos de M aparezcan en ningún orden especial en la primera fila, por lo que la misma permutación también podría escribirse como

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

Las permutaciones también suelen escribirse en notación cíclica (forma cíclica)​ de modo que dado el conjunto M = {1, 2, 3, 4}, una permutación g de M con g(1) = 2, g(2) = 4, g(4) = 1 y g(3) = 3 se escribirá como (1 , 2, 4)(3), o más comúnmente, (1, 2, 4), ya que 3 no se modifica; si los objetos se denotan con letras o dígitos, también se pueden prescindir de comas y espacios, y resulta una notación como (124). La permutación escrita arriba en notación de 2 líneas se escribiría en notación cíclica como $\sigma =(125)(34).$

Composición de permutaciones: el producto del grupo

El producto de dos permutaciones se define como su composición como funciones, por lo que $\sigma \cdot \pi$ es la función que asigna cualquier elemento x del conjunto a $\sigma (\pi (x))$. Téngase en cuenta que la permutación situada más a la derecha se aplica primero al argumento, debido a la forma en que se escribe la composición de las funciones.​​ Algunos autores prefieren que el factor más a la izquierda actúe primero, pero para ese fin las permutaciones deben escribirse a la "derecha" de su argumento, a menudo como superíndice, de modo que la permutación $\sigma$ que actúa sobre el elemento $x$ da como resultado la imagen $x^{\sigma }$. Con esta convención, el producto viene dado por $x^{\sigma \cdot \pi }=(x^{\sigma })^{\pi }$.​ ​ ​ Sin embargo, esto proporciona una regla "diferente" para multiplicar permutaciones. Esta convención se usa comúnmente en la literatura sobre grupos de permutaciones, pero este artículo usa la convención donde la permutación más a la derecha se aplica primero.

Dado que la composición de dos biyecciones siempre da otra biyección, el producto de dos permutaciones es nuevamente una permutación. En notación de dos líneas, el producto de dos permutaciones se obtiene reorganizando las columnas de la segunda permutación (la más a la izquierda) de modo que su primera fila sea idéntica a la segunda fila de la primera permutación (la de más a la derecha). En consecuencia, el producto se puede escribir como la primera fila de la primera permutación sobre la segunda fila de la segunda permutación modificada. Por ejemplo, dadas las permutaciones,

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

el producto QP es:

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

La composición de las permutaciones, cuando están escritas en notación cíclica, se obtiene yuxtaponiendo las dos permutaciones (con la segunda escrita a la izquierda) y luego simplificando a una forma de ciclo disjunta si se desea. Así, el producto anterior estaría dado por:

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

Dado que la composición de funciones es asociativa, también lo es la operación del producto de permutaciones: $(\sigma \cdot \pi )\cdot \rho =\sigma \cdot (\pi \cdot \rho )$. Por lo tanto, los productos de dos o más permutaciones generalmente se escriben sin agregar paréntesis para expresar agrupaciones. También suelen escribirse sin punto u otro signo para indicar la multiplicación (los puntos del ejemplo anterior se agregaron para dar énfasis a su expresión, por lo que simplemente se escribirían como $\sigma \pi \rho$).

Elemento neutro e inversos

La permutación identidad, que aplica cada elemento del conjunto sobre sí mismo, es el elemento neutro de este producto. En notación de dos líneas, la identidad es

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

En notación cíclica, e = (1)(2)(3)...(n), que por convención también se denota simplemente por (1) o incluso ().​

Dado que cada biyección tiene su inversa, también lo tienen las permutaciones, y la inversa σ⁻¹ de σ es nuevamente una permutación. Explícitamente, siempre que σ(x)=y también se tiene que σ⁻¹(y)=x. En la notación de dos líneas, la inversa se puede obtener intercambiando las dos líneas (y ordenando las columnas si se desea que la primera línea esté en un orden determinado). Por ejemplo

${\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 obtener la inversa de un solo ciclo, se invierte el orden de sus elementos. De este modo,

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

Para obtener el inverso de un producto de ciclos, primero se invierte el orden de los ciclos y luego se toma el inverso de cada uno como se indicó anteriormente. De este modo,

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

Tener un producto asociativo, un elemento identidad e inversas para todos sus elementos convierte al conjunto de todas las permutaciones de M en un grupo, Sim(M); un grupo de permutación.

Ejemplos

Considérese el siguiente conjunto G₁ de permutaciones del conjunto M = {1, 2, 3, 4}:

• e = (1)(2)(3)(4) = (1)
  • Esta es la identidad, la permutación trivial que fija cada elemento.
• a = (1 2)(3)(4) = (1 2)
  • Esta permutación intercambia 1 y 2, y deja fijos 3 y 4.
• b = (1)(2)(3 4) = (3 4)
  • Igual que la anterior, pero intercambiando 3 y 4, y fijando los demás.
• ab = (1 2)(3 4)
  • Esta permutación, que es la composición de las dos anteriores, intercambia simultáneamente 1 por 2 y 3 por 4.

G₁ forma un grupo, ya que aa = bb = e, ba = ab y abab = e. Este grupo de permutación es, como grupo abstracto, el grupo de Klein V₄.

Como otro ejemplo, considérese el grupo de simetrías de un cuadrado. Considerar que los vértices de un cuadrado estén etiquetados como 1, 2, 3 y 4 (en el sentido contrario a las agujas del reloj alrededor del cuadrado comenzando con 1 en la esquina superior izquierda). Las simetrías están determinadas por las imágenes de los vértices, que a su vez pueden describirse mediante permutaciones. La rotación de 90° (en el sentido contrario a las agujas del reloj) alrededor del centro del cuadrado se describe mediante la permutación (1234). Las rotaciones de 180° y 270° están dadas por (13)(24) y (1432), respectivamente. La reflexión sobre la línea horizontal que pasa por el centro está dada por (12)(34) y la reflexión de la línea vertical correspondiente es (14)(23). La reflexión sobre la recta de la diagonal 1,3 es (24), y la reflexión sobre la recta de la diagonal 2,4 es (13). La única simetría que queda es la identidad (1)(2)(3)(4). Este grupo de permutaciones se conoce, como grupo abstracto, como el grupo diédrico de orden 8.

Acciones grupales

En el ejemplo anterior del grupo de simetría de un cuadrado, las permutaciones "describen" el movimiento de los vértices del cuadrado inducido por el grupo de simetrías. Es común decir que estos elementos del grupo están "actuando" sobre el conjunto de vértices del cuadrado. Esta idea puede precisarse definiendo formalmente una acción grupal.​

Sea G un grupo y M un conjunto no vacío. Una acción de G sobre M es una función f: G × M → M tal que:

• f(1, x) = x, para todo x en M (1 es el elemento identidad (neutro) del grupo G ), y
• f(g, f(h, x)) = f(gh, x ), para todos los g, h en G y todos los x en M.

Este par de condiciones también se puede expresar diciendo que la acción induce un homomorfismo de grupo de G sobra Sim(M).​ Cualquier homomorfismo de este tipo se denomina representación (permutación) de G sobre M.

Para cualquier grupo de permutación, la acción que aplica (g, x) → g(x) se llama acción natural de G en M. Esta es la acción que se asume, a menos que se indique lo contrario.​ En el ejemplo del grupo de simetría del cuadrado, la acción del grupo sobre el conjunto de vértices es la acción natural. Sin embargo, este grupo también induce una acción sobre el conjunto de cuatro triángulos del cuadrado, que son: t₁ = 234, t₂ = 134, t₃ = 124 y t₄ = 123. También actúa sobre las dos diagonales: d₁ = 13 y d₂ = 24.

Elemento de grupo	Acción sobre triángulos	Acción sobre diagonales
(1)	(1)	(1)
(1234)	(t1 t2 t3 t4)	(d1 d2)
(13)(24)	(t1 t3)(t2 t4)	(1)
(1432)	(t1 t4 t3 t2)	(d1 d2)
(12)(34)	(t1 t2)(t3 t4)	(d1 d2)
(14)(23)	(t1 t4)(t2 t3)	(d1 d2)
(13)	(t1 t3)	(1)
(24)	(t2 t4)	(1)

Acciones transitivas

La acción de un grupo G sobre un conjunto M se dice transitiva si, por cada dos elementos s y t de M , hay algún elemento de grupo g tal que g(s) = t. De manera equivalente, el conjunto M forma una única órbita bajo la acción de G.​ En los ejemplos anteriores, se puede ver que el grupo {e, (1 2), (3 4), (1 2)(3 4)} de permutaciones de {1, 2, 3, 4} no es transitivo (ningún elemento del grupo aplica 1 a 3) pero el grupo de simetrías de un cuadrado es transitivo en los vértices.

Acciones primitivas

Un grupo de permutación G que actúa transitivamente sobre un conjunto finito no vacío M es imprimitivo si existe alguna partición no trivial del conjunto M que se conserva mediante la acción de G, donde "no trivial" significa que la partición no es la partición en conjuntos unitarios ni la partición en una sola parte. En caso contrario, si G es transitivo pero no conserva ninguna partición no trivial de M, el grupo G es primitivo.

Por ejemplo, el grupo de simetrías de un cuadrado no es primitivo en los vértices: si están numerados 1, 2, 3, 4 en orden cíclico, entonces cada elemento del grupo conserva la partición {{1, 3}, {2, 4}} en pares opuestos. Por otra parte, el grupo simétrico completo en un conjunto M es siempre primitivo.

Teorema de Cayley

Cualquier grupo G puede actuar sobre sí mismo (considerando los elementos del grupo como el conjunto M) de muchas maneras. En particular, existe una acción regular dada por la multiplicación (izquierda) en el grupo. Es decir, f(g, x) = gx para todo g y x en G. Para cada g fija, la función f_g(x) = gx es una biyección sobre G y por lo tanto una permutación del conjunto de elementos de G. Cada elemento de G puede considerarse como una permutación de esta manera, por lo que G es isomorfo a un grupo de permutaciones; este es el contenido del teorema de Cayley.

Por ejemplo, considérese el grupo G₁ actuando sobre el conjunto {1, 2, 3, 4} dado anteriormente. Denotar los elementos de este grupo por e, a, b y c = ab = ba. La acción de G₁ sobre sí mismo descrita en el teorema de Cayley da la siguiente representación de las permutaciones:

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

f_a ↦ (ea)(bc)

f_b ↦ (eb)(ac)

f_c ↦ (ec)(ab).

Isomorfismos de grupos de permutación

Si G y H son dos grupos de permutaciones en los conjuntos X e Y con acciones f₁ y f₂ respectivamente, entonces se dice que G y H son permutaciones isomórficas (o isomorfas como grupos de permutación) si existe una aplicación biyectiva λ : X → Y y un isomorfismo de grupos ψ : G → H tales que

λ(f₁(g, x)) = f₂(ψ(g), λ(x)) para todo g en G y x en X.​

Si X= Y, esto es equivalente a que G y H se conjuguen como subgrupos de Sym(X).​ El caso especial en el que G= H y ψ es la identidad da lugar al concepto de acciones equivalentes de un grupo.​

En el ejemplo de las simetrías de un cuadrado dado anteriormente, la acción natural sobre el conjunto {1,2,3,4} es equivalente a la acción sobre los triángulos. La biyección λ entre los conjuntos viene dada por i ↦ t_i. La acción natural del grupo G₁ anterior y su acción sobre sí mismo (mediante la multiplicación por la izquierda) no son equivalentes, ya que la acción natural tiene puntos fijos y la segunda acción no.

Grupos oligomorfos

Cuando un grupo G actúa sobre un conjunto S, la acción puede extenderse naturalmente al producto cartesiano Sⁿ de S, que consta de n-tuplas de elementos de S: la acción de un elemento g sobre la n-tupla (s₁, ..., s_n) viene dada por

g(s₁, ..., s_n) = (g(s₁), ..., g (s_n)).

Se dice que el grupo G es oligomórfico si la acción sobre Sⁿ tiene solo un número finito de órbitas para cada entero positivo n.​​ Esto es automático si S es finito, por lo que el término suele ser de interés cuando S es infinito.

El interés en los grupos oligomórficos se basa en parte en su aplicación a la teoría de modelos, como por ejemplo, cuando se consideran automorfismos en las teorías contablemente categóricas.​

Historia

El estudio de los grupos surgió originalmente de la comprensión de los grupos de permutación.​ Las propias permutaciones habían sido estudiados intensamente por Joseph-Louis Lagrange en 1770 en su trabajo sobre las soluciones algebraicas de ecuaciones polinómicas. Este tema floreció y, a mediados del siglo XIX, existía una teoría bien desarrollada de los grupos de permutación, codificada por Camille Jordan en su libro Traité des Substitutions et des Équations Algébriques de 1870. El libro de Jordan, a su vez, se basó en los artículos dejados por Évariste Galois en 1832.

Cuando Cayley introdujo el concepto de teoría de grupos, no quedó claro de inmediato si se trataba de una colección de objetos más grande que los grupos de permutaciones conocidos (que tenían una definición diferente a la moderna). Cayley pasó a demostrar que los dos conceptos eran equivalentes en el teorema de Cayley.​

Otro texto clásico que contiene varios capítulos sobre grupos de permutaciones es la teoría de grupos de orden finito de Burnside de 1911.​ La primera mitad del siglo XX fue un período inactivo en el estudio de la teoría de grupos en general, pero el interés por los grupos de permutaciones fue revivido en la década de 1950 por H. Wielandt, cuyas notas de conferencias en alemán se reimprimieron como Grupos de permutación finita en 1964.​

Véase también

• Grupo 2-transitivo
• Grupo de permutación de rango 3
• Grupo de Mathieu

Referencias

• 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 edición), Pearson Prentice-Hall, ISBN 0-13-186267-7 .

Lecturas adicionales

• Akos Seress. Permutation group algorithms. Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003.
• Meenaxi Bhattacharjee, Dugald Macpherson, Rögnvaldur G. Möller and Peter M. Neumann. Notes on Infinite Permutation Groups. Number 1698 in Lecture Notes in Mathematics. Springer-Verlag, 1998.
• Peter J. Cameron. Permutation Groups. LMS Student Text 45. Cambridge University Press, Cambridge, 1999.
• Peter J. Cameron. Oligomorphic Permutation Groups. Cambridge University Press, Cambridge, 1990.

Enlaces externos

• Hazewinkel, Michiel, ed. (2001), «Grupo de permutaciones», Encyclopaedia of Mathematics (en inglés), Springer, ISBN 978-1556080104 .
• Alexander Hülpke. Biblioteca de datos GAP "Grupos de permutación transitiva".

• Datos: Q1412905
• Multimedia: Permutation groups / Q1412905