5.1: Definiciones y Notación

En general, las permutaciones de un conjunto\(X\) forman un grupo\(S_X\text{.}\) Si\(X\) es un conjunto finito, podemos asumir\(X=\{ 1, 2, \ldots, n\}\text{.}\) En este caso escribimos en\(S_n\) lugar de\(S_X\text{.}\) El siguiente teorema dice que\(S_n\) es un grupo. Llamamos a este grupo el grupo simétrico de\(n\) letras.

Teorema\(5.1\)

El grupo simétrico sobre\(n\) letras,\(S_n\text{,}\) es un grupo con\(n!\) elementos, donde la operación binaria es la composición de mapas.

Prueba

La identidad de\(S_n\) es solo el mapa de identidad que envía\(1\) a\(1\text{,}\)\(2\)\(2\text{,}\)\(\ldots\text{,}\)\(n\) a\(n\text{.}\) Si\(f : S_n \rightarrow S_n\) es una permutación, entonces\(f^{-1}\) existe, ya que\(f\) es uno a uno y sobre; de ahí, cada permutación tiene una inversa. La composición de los mapas es asociativa, lo que hace que la operación de grupo sea asociativa. Dejamos la prueba de que\(|S_n|= n!\) como ejercicio.

Un subgrupo de\(S_n\) se llama grupo de permutación.

Ejemplo\(5.2\)

Considerar el subgrupo\(G\)\(S_5\) consistente en la permutación de identidad\(\identity\) y las permutaciones

\ begin {align*}\ sigma & =\ begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 3 & 5 & 5 & 4\ end {pmatrix}\\\ tau & =\ begin {pmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 2 & 1 & 4 & 5\ end {pmatrix}\\ mu & =\ begin {pmatrix} & 1 2 y 3 y 4 y 5\\ 3 & 2 & 1 & 5 & 4\ end {pmatrix}\ text {.} \ end {align*}

Solución

La siguiente tabla nos dice cómo multiplicar elementos en el grupo de permutación\(G\text{.}\)

\[ \begin{array}{c|cccc} \circ & \identity & \sigma & \tau & \mu \\ \hline \identity & \identity & \sigma & \tau & \mu \\ \sigma & \sigma & \identity & \mu & \tau \\ \tau & \tau & \mu & \identity & \sigma \\ \mu & \mu & \tau & \sigma & \identity \end{array} \nonumber \]

Observación\(5.3\)

Aunque es natural multiplicar elementos en un grupo de izquierda a derecha, las funciones se componen de derecha a izquierda. Dejar\(\sigma\) y\(\tau\) ser permutaciones en un conjunto\(X\text{.}\) Para componer\(\sigma\) y\(\tau\) como funciones, calculamos Es\((\sigma \circ \tau)(x) = \sigma( \tau(x))\text{.}\) decir, hacemos\(\tau\) primero, luego\(\sigma\text{.}\) Hay varias formas de abordar esta inconsistencia. Vamos a adoptar la convención de multiplicar permutaciones de derecha a izquierda. Para computar\(\sigma \tau\text{,}\) hacer\(\tau\) primero y después Es decir, por\(\sigma \tau (x)\) lo\(\sigma\text{.}\) que queremos decir\(\sigma( \tau( x))\text{.}\) (Otra forma de resolver este problema sería escribir funciones a la derecha; es decir, en lugar de escribir\(\sigma(x)\text{,}\) podríamos escribir También\((x)\sigma\text{.}\) podríamos multiplicar permutaciones dejadas a derecho a ponerse de acuerdo con la forma habitual de multiplicar elementos en un grupo. Ciertamente se han utilizado todos estos métodos.

Ejemplo\(5.4\)

La multiplicación por permutación no suele ser conmutativa. Let

\ begin {align*}\ sigma & =\ begin {pmatrix} 1 & 2 & 3 & 4\\ 4 & 1 & 2 & 3\ end {pmatrix}\\\ tau & =\ begin {pmatrix} 1 & 2 & 3 & 4\\ 2 & 4 & 1 & 4 & 3\ end {pmatrix}\ text {.} \ end {align*}

Solución

Entonces

\[ \sigma \tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \end{pmatrix}\text{,} \nonumber \]

pero

\[ \tau \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 \end{pmatrix}\text{.} \nonumber \]

Notación de ciclo

La notación que hemos utilizado para representar permutaciones hasta este punto es engorrosa, por decir lo menos. Para trabajar eficazmente con grupos de permutación, necesitamos un método más simplificado de escribir y manipular permutaciones.

Una permutación\(\sigma \in S_X\) es un ciclo de longitud\(k\) si existen elementos\(a_1, a_2, \ldots, a_k \in X\) tales que

\ begin {alinear*}\ sigma (a_1) & = a_2\\ sigma (a_2) & = a_3\\ &\ vdots\\\ sigma (a_k) & = a_1\ end {alinear*}

y\(\sigma( x) = x\) para todos los demás elementos\(x \in X\text{.}\) Escribiremos\((a_1, a_2, \ldots, a_k )\) para denotar el ciclo Los\(\sigma\text{.}\) ciclos son los bloques de construcción de todas las permutaciones.

Ejemplo\(5.5\)

La permutación

\[ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 6 & 3 & 5 & 1 & 4 & 2 & 7 \end{pmatrix} = (1 6 2 3 5 4 ) \nonumber \]

es un ciclo de duración,\(6\text{,}\) mientras que

\[ \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 4 & 2 & 3 & 5 & 6 \end{pmatrix} = (2 4 3) \nonumber \]

es un ciclo de duración\(3\text{.}\)

Solución

No toda permutación es un ciclo. Considerar la permutación

\[ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 1 & 3 & 6 & 5 \end{pmatrix} = (1 2 4 3)(5 6)\text{.} \nonumber \]

Esta permutación en realidad contiene un ciclo de longitud 2 y un ciclo de longitud\(4\text{.}\)

Ejemplo\(5.6\)

Es muy fácil calcular productos de ciclos. Supongamos que

\[ \sigma = (1 3 5 2 ) \quad \text{and} \quad \tau = (2 5 6)\text{.} \nonumber \]

Solución

Si pensamos\(\sigma\) en

\[ 1 \mapsto 3, \qquad 3 \mapsto 5, \qquad 5 \mapsto 2, \qquad 2 \mapsto 1\text{,} \nonumber \]

y\(\tau\) como

\[ 2 \mapsto 5, \qquad 5 \mapsto 6, \qquad 6 \mapsto 2\text{,} \nonumber \]

luego por\(\sigma \tau\) recordar que aplicamos\(\tau\) primero y luego debe\(\sigma\text{,}\) darse el caso que

\[ 1 \mapsto 3, \qquad 3 \mapsto 5, \qquad 5 \mapsto 6, \qquad 6 \mapsto 2 \mapsto 1\text{,} \nonumber \]

o\(\sigma \tau = (1 3 5 6 )\text{.}\) Si\(\mu = (1634)\text{,}\) entonces\(\sigma \mu = (1 6 5 2)(3 4)\text{.}\)

Dos ciclos en\(S_X\text{,}\)\(\sigma = (a_1, a_2, \ldots, a_k )\) y\(\tau = (b_1, b_2, \ldots, b_l )\text{,}\) son disjuntos si\(a_i \neq b_j\) para todos\(i\) y\(j\text{.}\)

Ejemplo\(5.7\)

Los ciclos\((1 3 5)\) y\((2 7 )\) son disjuntos; sin embargo, los ciclos\((1 3 5)\) y no lo\((3 4 7 )\) son.

Solución

Calculando sus productos, encontramos que

\ begin {align*} (1 3 5) (2 7) & = (1 3 5) (2 7)\\ (1 3 5) (3 4 7) & = (1 3 4 7 5)\ text {.} \ end {align*}

El producto de dos ciclos que no son disjuntos puede reducirse a algo menos complicado; el producto de ciclos disjuntos no puede simplificarse.

Proposición\(5.8\)

Dejar\(\sigma\) y\(\tau\) ser dos ciclos disjuntos en\(S_X\text{.}\) Entonces\(\sigma \tau = \tau \sigma\text{.}\)

Prueba

Vamos\(\sigma = (a_1, a_2, \ldots, a_k )\) y\(\tau = (b_1, b_2, \ldots, b_l )\text{.}\) Debemos demostrar que\(\sigma \tau(x) = \tau \sigma(x)\) para todos\(x \in X\text{.}\) Si no\(x\) está ni en\(\{ a_1, a_2, \ldots, a_k \}\) ni\(\{b_1, b_2, \ldots, b_l \}\text{,}\) entonces ambos\(\sigma\) y\(\tau\) arreglar\(x\text{.}\) Eso es,\(\sigma(x)=x\) y\(\tau(x)=x\text{.}\) por lo tanto,

\[ \sigma \tau(x) = \sigma( \tau(x)) = \sigma(x) = x = \tau(x) = \tau( \sigma(x)) = \tau \sigma(x)\text{.} \nonumber \]

No hay que olvidar que estamos multiplicando permutaciones de derecha a izquierda, que es lo opuesto al orden en el que solemos multiplicar elementos grupales. Ahora supongamos\(\sigma( a_i ) = a_{(i \bmod k) + 1}\text{;}\) que\(x \in \{ a_1, a_2, \ldots, a_k \}\text{.}\) Entonces es decir,

\ begin {align*} a_1 &\ mapsto a_2\\ a_2 &\ mapsto a_3\\ &\ vdots\\ a_ {k-1} &\ mapsto a_k\\ a_k &\ mapsto a_1\ texto {.} \ end {align*}

Sin embargo,\(\tau(a_i) = a_i\) ya que\(\sigma\) y\(\tau\) son disjuntas. Por lo tanto,

\ begin {alinear*}\ sigma\ tau (a_i) & =\ sigma (\ tau (a_i))\\ & =\ sigma (a_i)\\ & = a_ {(i\ bmod k) +1}\\ & =\ tau (a_ {(i\ bmod k) +1})\\ & =\ tau (\ sigma (a_i))\\ & =\ tau\ sigma (a_i)\ texto {.} \ end {align*}

Del mismo modo, si\(x \in \{b_1, b_2, \ldots, b_l \}\text{,}\) entonces\(\sigma\) y\(\tau\) también conmutar.

Teorema\(5.9\)

Cada permutación en\(S_n\) puede escribirse como producto de ciclos disjuntos.

Prueba

Podemos suponer que\(X = \{ 1, 2, \ldots, n \}\text{.}\) si\(\sigma \in S_n\) y definimos\(X_1\) ser\(\{ \sigma(1), \sigma^2(1), \ldots \}\text{,}\) entonces el conjunto\(X_1\) es finito ya que\(X\) es finito. Ahora vamos a\(i\) ser el primer entero en\(X\) que no está en\(X_1\) y definir\(X_2\) por\(\{ \sigma(i), \sigma^2(i), \ldots \}\text{.}\) De nuevo,\(X_2\) es un conjunto finito. Continuando de esta manera, podemos definir conjuntos disgregados finitos\(X_3, X_4, \ldots\text{.}\) Dado que\(X\) es un conjunto finito, se nos garantiza que este proceso terminará y solo habrá un número finito de estos conjuntos, digamos\(r\text{.}\) Si\(\sigma_i\) es el ciclo definido por

\[ \sigma_i( x ) = \begin{cases} \sigma( x ) & x \in X_i \\ x & x \notin X_i \end{cases}\text{,} \nonumber \]

entonces\(\sigma = \sigma_1 \sigma_2 \cdots \sigma_r\text{.}\) Dado que los conjuntos\(X_1, X_2, \ldots, X_r\) son disjuntos, los ciclos también\(\sigma_1, \sigma_2, \ldots, \sigma_r\) deben ser disjuntos.

Ejemplo\(5.10\)

Let

\ begin {align*}\ sigma & =\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 6 & 4 & 3 & 1 & 5 & 2\ end {pmatrix}\\\ tau & =\ begin {pmatrix} 1 & 2 & 3 & 4 & 5 & 6\ 3 & 2 & 1 & 5 & 6 & 4\ end {pmatrix}\ text {.} \ end {align*}

Solución

Usando la notación de ciclo, podemos escribir

\ begin {alinear*}\ sigma & = (1624)\\\ tau & = (13) (456)\\\ sigma\ tau & = (1 3 6) (2 4 5)\\ tau\ sigma & = (1 4 3) (2 5 6)\ text {.} \ end {align*}

Observación\(5.11\).

A partir de este punto en adelante nos resultará conveniente utilizar la notación de ciclo para representar permutaciones. Cuando se utiliza la notación de ciclo, a menudo denotamos la permutación de identidad por\((1)\text{.}\)

Transposiciones

La permutación más simple es un ciclo de longitud\(2\text{.}\) Tales ciclos se denominan transposiciones. Desde

\[ (a_1, a_2, \ldots, a_n ) = (a_1 a_n ) (a_1 a_{n-1} ) \cdots ( a_1 a_3 ) (a_1 a_2 )\text{,} \nonumber \]

cualquier ciclo puede ser escrito como producto de transposiciones, dando lugar a la siguiente proposición.

Proposición\(5.12\)

Cualquier permutación de un conjunto finito que contenga al menos dos elementos puede escribirse como producto de transposiciones

Ejemplo\(5.13\)

Considerar la permutación

\[ ( 1 6 ) (2 5 3) = (1 6 )( 2 3 )( 2 5 ) = (1 6 )( 4 5 )(2 3 )( 4 5 )(2 5 )\text{.} \nonumber \]

Solución

Como podemos ver, no existe una manera única de representar la permutación como producto de las transposiciones. Por ejemplo, podemos escribir la permutación de identidad\((1 2 )(1 2 )\text{,}\) como\((1 3 )(2 4 )(1 3 )( 2 4 )\text{,}\) y de muchas otras maneras. Sin embargo, resulta que ninguna permutación puede escribirse como producto tanto de un número par de transposiciones como de un número impar de transposiciones. Por ejemplo, podríamos representar la permutación\((1 6)\) por

\[ (2 3 )(1 6)( 2 3) \nonumber \]

o por

\[ (3 5) (1 6) (1 3) (1 6) (1 3) (3 5) (5 6)\text{,} \nonumber \]

pero siempre\((1 6)\) será producto de un número impar de transposiciones.

Lema\(5.14\)

Si la identidad se escribe como producto de\(r\) transposiciones,

\[ \identity = \tau_1 \tau_2 \cdots \tau_r\text{,} \nonumber \]

entonces\(r\) es un número par.

Prueba

Vamos a emplear inducción en\(r\text{.}\) una transposición no puede ser la identidad; de ahí,\(r \gt 1\text{.}\) si\(r=2\text{,}\) entonces hemos terminado. Supongamos que\(r \gt 2\text{.}\) en este caso el producto de las dos últimas transposiciones,\(\tau_{r-1} \tau_r\text{,}\) debe ser uno de los siguientes casos:

\ begin {align*} (a b) (a b) & =\ identidad\\ (b c) (a b) & = (a c) (b c)\\ (c d) (a b) & = (a b) (a b) (c d)\ (a c) (a b) & = (a b) (b c)\ text {,}\ end {align*}

donde\(a\text{,}\)\(b\text{,}\)\(c\text{,}\) y\(d\) son distintos.

La primera ecuación simplemente dice que una transposición es su propia inversa. Si ocurre este caso, eliminar\(\tau_{r-1} \tau_r\) del producto para obtener

\[ \identity = \tau_1 \tau_2 \cdots \tau_{r - 3} \tau_{r - 2}\text{.} \nonumber \]

Por inducción\(r - 2\) es parejo; de ahí,\(r\) debe ser parejo.

En cada uno de los otros tres casos, podemos\(\tau_{r - 1} \tau_r\) sustituir por el lado derecho de la ecuación correspondiente para obtener un nuevo producto de\(r\) transposiciones para la identidad. En este nuevo producto la última ocurrencia de\(a\) será en la próxima a la última transposición. Podemos continuar con este proceso\(\tau_{r - 2} \tau_{r - 1}\) para obtener ya sea un producto de\(r - 2\) transposiciones o un nuevo producto de\(r\) transposiciones donde la última ocurrencia de\(a\) está en\(\tau_{r - 2}\text{.}\) Si la identidad es producto de\(r - 2\) transposiciones, entonces nuevamente estamos hechos, por nuestra inducción hipótesis; de lo contrario, repetiremos el procedimiento con\(\tau_{r - 3} \tau_{r - 2}\text{.}\)

En algún momento o bien tendremos dos transposiciones adyacentes, idénticas que se cancelan entre sí o\(a\) se barajarán para que sólo aparezca en la primera transposición. No obstante, este último caso no puede ocurrir, porque la identidad no se fijaría\(a\) en esta instancia. Por lo tanto, la permutación de identidad debe ser producto de\(r-2\) transposiciones y, nuevamente por nuestra hipótesis de inducción, hemos terminado.

Teorema\(5.15\)

Si una permutación\(\sigma\) puede expresarse como el producto de un número par de transposiciones, entonces cualquier otro producto de transposiciones iguales también\(\sigma\) debe contener un número par de transposiciones. De igual manera, si se\(\sigma\) puede expresar como el producto de un número impar de transposiciones, entonces cualquier otro producto de transposiciones igualadas también\(\sigma\) debe contener un número impar de transposiciones.

Prueba

Supongamos que

\[ \sigma = \sigma_1 \sigma_2 \cdots \sigma_m = \tau_1 \tau_2 \cdots \tau_n\text{,} \nonumber \]

donde\(m\) es parejo. Debemos demostrar que también\(n\) es un número par. La inversa de\(\sigma\) es\(\sigma_m \cdots \sigma_1\text{.}\) Since

\[ \identity = \sigma \sigma_m \cdots \sigma_1 = \tau_1 \cdots \tau_n \sigma_m \cdots \sigma_1\text{,} \nonumber \]

\(n\)debe ser par por Lema 5.14. Se deja como ejercicio la prueba para el caso en el que se\(\sigma\) pueda expresar como un número impar de transposiciones.

A la luz del Teorema\(5.15\), definimos una permutación para que sea par si puede expresarse como un número par de transposiciones e impar si puede expresarse como un número impar de transposiciones.

Los grupos alternos

Uno de los subgrupos más importantes de\(S_n\) es el conjunto de todas las permutaciones pares,\(A_n\text{.}\) El grupo\(A_n\) se llama el grupo alterno en\(n\) letras.

Teorema\(5.16\)

El conjunto\(A_n\) es un subgrupo de\(S_n\text{.}\)

Prueba

Dado que el producto de dos permutaciones pares también debe ser una permutación par,\(A_n\) se cierra. La identidad es una permutación par y por lo tanto está en\(A_n\text{.}\) Si\(\sigma\) es una permutación par, entonces

\[ \sigma = \sigma_1 \sigma_2 \cdots \sigma_r\text{,} \nonumber \]

donde\(\sigma_i\) es una transposición y\(r\) es parejo. Dado que la inversa de cualquier transposición es en sí misma,

\[ \sigma^{-1} = \sigma_r \sigma_{r-1} \cdots \sigma_1 \nonumber \]

también se encuentra en\(A_n\text{.}\)

Proposición\(5.17\)

El número de permutaciones pares en\(S_n\text{,}\)\(n \geq 2\text{,}\) es igual al número de permutaciones impares; por lo tanto, el orden de\(A_n\) es\(n!/2\text{.}\)

Prueba

Dejar\(A_n\) ser el conjunto de permutaciones pares en\(S_n\) y\(B_n\) ser el conjunto de permutaciones impares. Si podemos demostrar que existe una bijección entre estos conjuntos, deben contener el mismo número de elementos. Arreglar una transposición\(\sigma\) en\(S_n\text{.}\) Dado que\(n \geq 2\text{,}\) tal\(\sigma\) existe. Definir

\[ \lambda_{\sigma} : A_n \rightarrow B_n \nonumber \]

por

\[ \lambda_{\sigma} ( \tau ) = \sigma \tau \text{.} \nonumber \]

Supongamos que\(\lambda_{\sigma} ( \tau ) = \lambda_{\sigma} ( \mu )\text{.}\) Entonces\(\sigma \tau = \sigma \mu\) y así

\[ \tau = \sigma^{-1} \sigma \tau = \sigma^{-1} \sigma \mu = \mu\text{.} \nonumber \]

Por lo tanto,\(\lambda_{\sigma}\) es uno a uno. Dejaremos al lector la prueba que\(\lambda_{\sigma}\) sea suryectiva.

Ejemplo\(5.18\)

El grupo\(A_4\) es el subgrupo\(S_4\) que consiste en incluso permutaciones. Hay doce elementos en\(A_4\text{:}\)

\ begin {align*} & (1) && (12) (34) && (13) (24) && (14) (23)\\ & (123) && (132) && (124) && (142)\\ & (134) && (143) && (234) && (243)\ text {.} \ end {align*}

Solución

Uno de los ejercicios de fin de capítulo será anotar todos los subgrupos de\(A_4\text{.}\) Encontrarás que no hay subgrupo de orden 6. ¿Te sorprende esto?

Nota Histórica

Lagrange pensó primero en las permutaciones como funciones de un conjunto a sí mismo, pero fue Cauchy quien desarrolló los teoremas básicos y la notación para las permutaciones. Fue el primero en utilizar la notación de ciclo. Augustin-Louis Cauchy (1789—1857) nació en París en el apogeo de la Revolución Francesa. Su familia pronto salió de París hacia el pueblo de Arcueil para escapar del Reino del Terror. Uno de los vecinos de la familia fue Pierre-Simon Laplace (1749—1827), quien lo animó a buscar una carrera en matemáticas. Cauchy comenzó su carrera como matemático resolviendo un problema en geometría que le dio Lagrange. Cauchy escribió más de 800 artículos sobre temas tan diversos como ecuaciones diferenciales, grupos finitos, matemáticas aplicadas y análisis complejos. Fue uno de los matemáticos encargados de hacer el cálculo riguroso. Quizás más teoremas y conceptos en matemáticas tienen el nombre Cauchy unido a ellos que el de cualquier otro matemático.