Grupo de permutaciones

En matemáticas , un grupo de permutaciones es un grupo G cuyos elementos son permutaciones de un conjunto dado M y cuya operación de grupo es la composición de permutaciones en G (que se consideran funciones biyectivas 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 Sym( M ). ^{[ 1 ]} El término grupo de permutaciones significa, por lo tanto, un subgrupo del grupo simétrico . Si M = {1, 2, ..., n }, entonces Sym( M ) se suele denotar por S _n , y puede llamarse el grupo simétrico de n letras .

Según el teorema de Cayley , todo grupo es isomorfo a algún grupo de permutaciones.

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

Un grupo de permutaciones 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. ^{[ 2 ]} Una propiedad general de los grupos finitos implica que un subconjunto finito no vacío de un grupo simétrico es un grupo de permutaciones si y solo si es cerrado bajo la composición de permutaciones. ^{[ 3 ]}

El grado de un grupo de permutaciones de un conjunto finito es el número de elementos en el conjunto. El orden de un grupo (de cualquier tipo) es el número de elementos (cardinalidad) en el grupo. Por 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 .

Dado que las permutaciones son biyecciones de un conjunto, pueden representarse mediante la notación de dos líneas de Cauchy . ^{[ 4 ]} 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 que se encuentra debajo en la segunda fila. Si${\displaystyle \sigma }$es una permutación del conjunto${\displaystyle M=\{x_{1},x_{2},\ldots ,x_{n}\}}$entonces,

${\displaystyle \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

${\displaystyle \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. Los elementos de M no necesitan aparecer en ningún orden especial en la primera fila, por lo que la misma permutación también podría escribirse como

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

Las permutaciones también se suelen escribir en notación cíclica ( forma cíclica ) ^{[ 5 ]} , 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 el 3 permanece sin cambios; si los objetos se denotan con letras o dígitos individuales, también se pueden omitir las comas y los espacios, y obtenemos una notación como (124). La permutación escrita arriba en notación de dos líneas se escribiría en notación cíclica como${\displaystyle \sigma =(125)(34).}$

El producto de dos permutaciones se define como su composición como funciones, por lo tanto${\displaystyle \sigma \cdot \pi }$es la función que asigna cualquier elemento x del conjunto a${\displaystyle \sigma (\pi (x))}$. Nótese que la permutación más a la derecha se aplica primero al argumento, debido a la forma en que se escribe la composición de funciones. ^{[ 6 ] [ 7 ]} Algunos autores prefieren que el factor más a la izquierda actúe primero, pero para ello las permutaciones deben escribirse a la derecha de su argumento, a menudo como un superíndice , por lo que la permutación${\displaystyle \sigma }$actuando sobre el elemento${\displaystyle x}$resultados en la imagen${\displaystyle x^{\sigma }}$Con esta convención, el producto se da por${\displaystyle x^{\sigma \cdot \pi }=(x^{\sigma })^{\pi }}$. ^{[ 8 ] [ 9 ] [ 10 ]} Sin embargo, esto da 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 reordenando las columnas de la segunda permutación (la de 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). El producto se puede escribir entonces como la primera fila de la primera permutación sobre la segunda fila de la segunda permutación modificada. Por ejemplo, dadas las permutaciones,

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

El producto QP es:

${\displaystyle 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 permutaciones, cuando se escriben en notación cíclica, se obtiene yuxtaponiendo las dos permutaciones (con la segunda escrita a la izquierda) y luego simplificando a una forma cíclica disjunta si se desea. Así, el producto anterior quedaría dado por:

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

Dado que la composición de funciones es asociativa , también lo es la operación de producto sobre permutaciones:${\displaystyle (\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 la agrupación; también generalmente se escriben sin un punto u otro signo para indicar la multiplicación (los puntos del ejemplo anterior se agregaron para enfatizar, por lo que simplemente se escribiría como${\displaystyle \sigma \pi \rho }$).

La permutación identidad, que asigna a cada elemento del conjunto su propio elemento, es el elemento neutro para este producto. En notación de dos líneas, la identidad es

${\displaystyle {\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 (). ^{[ 11 ]}

Dado que las biyecciones tienen inversas , también las tienen las permutaciones, y la inversa σ ⁻¹ de σ es nuevamente una permutación. Explícitamente, siempre que σ ( x )= y también se tiene σ ⁻¹ ( y )= x . En 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

${\displaystyle {\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 el inverso de un ciclo simple, invertimos el orden de sus elementos. Por lo tanto,

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

Para obtener el inverso de un producto de ciclos, primero invertimos el orden de los ciclos y luego tomamos el inverso de cada uno como se indicó anteriormente. Por lo tanto,

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

Tener un producto asociativo, un elemento identidad e inversos para todos sus elementos, hace que el conjunto de todas las permutaciones de M sea un grupo , Sym( M ); un grupo de permutaciones.

Consideremos 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 fija 3 y 4.
• b = (1)(2)(3 4) = (3 4)
  • Igual que el anterior, pero intercambiando el 3 y el 4, y corrigiendo los demás.
• ab = (1 2)(3 4)
  • Esta permutación, que es la composición de las dos anteriores, intercambia simultáneamente 1 con 2 y 3 con 4.

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

Como otro ejemplo, consideremos el grupo de simetrías de un cuadrado . Sean los vértices del cuadrado 1, 2, 3 y 4 (en sentido antihorario 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 sentido antihorario) 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 respecto a la línea horizontal que pasa por el centro está dada por (12)(34) y la reflexión correspondiente respecto a la línea vertical es (14)(23). La reflexión respecto a la diagonal 1,3 es (24) y la reflexión respecto a la diagonal 2,4 es (13). La única simetría restante es la identidad (1)(2)(3)(4). Este grupo de permutaciones se conoce, como grupo abstracto, como el grupo diedral de orden 8.

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 "actúan" sobre el conjunto de vértices del cuadrado. Esta idea se puede precisar definiendo formalmente una acción de grupo . ^{[ 12 ]}

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 (neutral) del grupo G ), y
• f ( g , f ( h , x )) = f ( gh , x ), para todo g , h en G y todo x en M .

Este par de condiciones también puede expresarse diciendo que la acción induce un homomorfismo de grupo de G en Sym ( M ). ^{[ 12 ]} Cualquier homomorfismo de este tipo se llama representación (de permutación) de G en M .

Para cualquier grupo de permutaciones, la acción que envía ( g , x ) → g ( x ) se llama acción natural de G sobre M. Esta es la acción que se asume a menos que se indique lo contrario. ^{[ 12 ]} _{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 en el cuadrado, que son: t1 = 234, t2 ₌ 134, t3 _{= 124} y t4 = _123. También actúa sobre las dos diagonales: d1 = 13 y d2 = 24 _.

Se dice que la acción de un grupo G sobre un conjunto M es transitiva si, para cada par de elementos s , t de M , existe algún elemento del grupo g tal que g ( s ) = t . Equivalentemente, el conjunto M forma una única órbita bajo la acción de G. ^{[ 13 ]} De los ejemplos anteriores , 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 toma 1 a 3), pero el grupo de simetrías de un cuadrado es transitivo en los vértices.

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 (por la izquierda) en el grupo. Es decir, f ( g , x ) = gx para todo g y x en G . Para cada g fijo , la función f _g ( x ) = gx es una biyección en 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, consideremos el grupo G ₁ que actúa sobre el conjunto {1, 2, 3, 4} dado anteriormente. Sean los elementos de este grupo 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 permutación:

f _e ↦ ( e )( a )( b )( c )

f _a ↦ ( ea )( bc )

f _b ↦ ( eb )( ac )

f _c ↦ ( ec )( ab ).

Si G y H son dos grupos de permutaciones sobre conjuntos X e Y con acciones f ₁ y f ₂ respectivamente, entonces decimos que G y H son isomorfos de permutación (o isomorfos como grupos de permutaciones ) 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 . ^{[ 14 ]}

Si X = Y, esto es equivalente a que G y H sean conjugados como subgrupos de Sym( X ). ^{[ 15 ]} El caso especial donde G = H y ψ es la aplicación identidad da lugar al concepto de acciones equivalentes de un grupo. ^{[ 16 ]}

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 multiplicación por la izquierda) no son equivalentes, ya que la acción natural tiene puntos fijos y la segunda acción no.

Cuando un grupo G actúa sobre un conjunto S , la acción puede extenderse naturalmente al producto cartesiano S ⁿ de S , que consiste en 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 . ^{[ 17 ] [ 18 ]} (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 , por ejemplo, al considerar automorfismos en teorías categóricas numerables . ^{[ 19 ]}

El estudio de los grupos surgió originalmente de la comprensión de los grupos de permutaciones. ^{[ 20 ]} Las permutaciones habían sido estudiadas intensamente por 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 permutaciones, 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 documentos que Évariste Galois dejó en 1832.

Cuando Cayley introdujo el concepto de grupo abstracto , no quedó claro de inmediato si se trataba de una colección de objetos mayor que los grupos de permutación conocidos (cuya definición era diferente a la moderna). Cayley demostró posteriormente que ambos conceptos eran equivalentes en su teorema. ^{[ 21 ]}

Otro texto clásico que contiene varios capítulos sobre grupos de permutaciones es la obra de Burnside , * Theory of Groups of Finite Order* , de 1911. ^{[ 22 ]} La primera mitad del siglo XX fue un período de estancamiento en el estudio de la teoría de grupos en general, pero el interés por los grupos de permutaciones se reavivó en la década de 1950 gracias a H. Wielandt, cuyas notas de clase en alemán se reimprimieron como *Finite Permutation Groups* en 1964. ^{[ 23 ]}

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

• Artin, Michael (1991), Álgebra , Prentice-Hall, ISBN 0-13-004763-5
• Cameron, Peter J. (1994), Combinatoria: Temas, técnicas, algoritmos , Cambridge University Press, ISBN 0-521-45761-0
• Dixon, John D.; Mortimer, Brian (1996), Grupos de permutación , Textos de posgrado en matemáticas 163), Springer-Verlag, ISBN 0-387-94599-7
• Rotman, Joseph J. (2006), Un primer curso de álgebra abstracta con aplicaciones (3.ª  ed.), Pearson Prentice-Hall, ISBN 0-13-186267-7

• Akos Seress. Algoritmos de grupos de permutación . Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003.
• Meenaxi Bhattacharjee, Dugald Macpherson, Rögnvaldur G. Möller y Peter M. Neumann. Notas sobre grupos de permutaciones infinitos . Número 1698 de Lecture Notes in Mathematics. Springer-Verlag, 1998.
• Peter J. Cameron . Grupos de permutación . LMS Student Text 45. Cambridge University Press, Cambridge, 1999.
• Peter J. Cameron. Grupos de permutaciones oligomórficas . Cambridge University Press, Cambridge, 1990.

• "Grupo de permutaciones" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Alexander Hulpke. Biblioteca de datos GAP "Grupos de permutación transitivos" Archivado el 19/01/2021 en Wayback Machine .