Saltar a contenido principal

Sección 5.1 Definiciones y Notación

En general, las permutaciones de un conjunto \(X\) forman el grupo \(S_X\text{.}\) Si \(X\) es un conjunto finito, podemos suponer que \(X=\{ 1, 2, \ldots, n\}\text{.}\) En este caso escribiremos \(S_n\) en lugar de \(S_X\text{.}\) El siguiente teorema dice que \(S_n\) es un grupo. A este grupo lo llamaremos grupo simétrico en \(n\) símbolos.

La identidad de \(S_n\) es simplemente la función identidad que envía 1 en 1, 2 en 2, \(\ldots\text{,}\) \(n\) en \(n\text{.}\) Si \(f : S_n \rightarrow S_n\) es una permutación, entonces \(f^{-1}\) existe, pues \(f\) es biyectiva; luego, toda permutación tiene una inversa. La composición de funciones es asociativa, lo que hace que la operación del grupo sea asociativa. Dejamos como ejercicio la demostración de que \(|S_n|= n!\text{.}\)

Un subgrupo de \(S_n\) se llama grupo de permutaciones.

Considere el subgrupo \(G\) de \(S_5\) que consiste de la permutación \(\identity\) y las permutaciones

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

La siguiente tabla nos indica como multiplicar elementos en el grupo de permutaciones \(G\text{.}\)

\begin{equation*} \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} \end{equation*}
Nota 5.1.3.

Si bien es natural multiplicar los elementos en un grupo de izquierda a derecha, las funciones se componen de derecha a izquierda. Sean \(\sigma\) y \(\tau\) permutaciones en un conjunto \(X\text{.}\) Para componer \(\sigma\) y \(\tau\) como funciones, calculamos \((\sigma \circ \tau)(x) = \sigma( \tau(x))\text{.}\) Es decir, aplicamos primero \(\tau\text{,}\) luego \(\sigma\text{.}\) Hay diversas formas de resolver esta inconsistencia. Nosotros adoptaremos la convención de multiplicar permutaciones de derecha a izquierda. Para calcular \(\sigma \tau\text{,}\) haga \(\tau\) primero y luego \(\sigma\text{.}\) Es decir, por \(\sigma \tau (x)\) queremos decir \(\sigma( \tau( x))\text{.}\) (Otra manera de resolver este problema sería escribir las funciones a la derecha; es decir, en lugar de escribir \(\sigma(x)\text{,}\) podríamos escribir \((x)\sigma\text{.}\) También podríamos multiplicar las permutaciones de izquierda a derecha para coincidir con la forma usual de multiplicar elementos en un grupo. Cada una de estas soluciones ha sido usada.)

La multiplicación de permutaciones no es conmutativa en general. Sean

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

Entonces

\begin{equation*} \sigma \tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \end{pmatrix}, \end{equation*}

pero

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

Subsección 5.1.1 Notación cíclica

La notación que hemos usado hasta ahora para representar las permutaciones es engorrosa, para decir lo menos. Para trabajar efectivamente con grupos de permutaciones, necesitaremos un método más expedito de escribir y manipular permutaciones.

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

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

y \(\sigma( x) =x\) para todos los demás elementos \(x \in X\text{.}\) Escribiremos \((a_1, a_2, \ldots, a_k )\) para denotar al ciclo \(\sigma\text{.}\) Los ciclos son los bloques básicos para construir todas las permutaciones.

La permutación

\begin{equation*} \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 ) \end{equation*}

es un ciclo de largo 6, mientras

\begin{equation*} \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 4 & 2 & 3 & 5 & 6 \end{pmatrix} = (2 4 3) \end{equation*}

es un ciclo de largo 3.

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

\begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 1 & 3 & 6 & 5 \end{pmatrix} = (1 2 4 3)(5 6). \end{equation*}

Esta permutación de hecho contiene un ciclo de largo 2 y un ciclo de largo 4.

Es muy simple calcular el producto de ciclos. Supongamos que

\begin{equation*} \sigma = (1 3 5 2 ) \quad \text{y} \quad \tau = (2 5 6). \end{equation*}

Si pensamos en \(\sigma\) como

\begin{equation*} 1 \mapsto 3, \qquad 3 \mapsto 5, \qquad 5 \mapsto 2, \qquad 2 \mapsto 1, \end{equation*}

y \(\tau\) como

\begin{equation*} 2 \mapsto 5, \qquad 5 \mapsto 6, \qquad 6 \mapsto 2, \end{equation*}

entonces para \(\sigma \tau\) recordando que primero debemos aplicar \(\tau\) y luego \(\sigma\text{,}\) debe ser el caso que

\begin{equation*} 1 \mapsto 3, \qquad 3 \mapsto 5, \qquad 5 \mapsto 6, \qquad 6 \mapsto 2 \mapsto 1, \end{equation*}

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 todo \(i\) y para todo \(j\text{.}\)

Los ciclos \((1 3 5)\) y \((2 7 )\) son disjuntos; mientras los ciclos \((1 3 5)\) y \((3 4 7 )\) no lo son. Calculando sus productos, descubrimos que

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

El producto de dos ciclos que no son disjuntos a veces se puede reducir a algo menos complicado; el producto de dos ciclos disjuntos no puede ser simplificado.

Sea \(\sigma = (a_1, a_2, \ldots, a_k )\) y \(\tau = (b_1, b_2, \ldots, b_l )\text{.}\) Debemos mostrar que \(\sigma \tau(x) = \tau \sigma(x)\) para todo \(x \in X\text{.}\) Si \(x\) no está en \(\{ a_1, a_2, \ldots, a_k \}\) ni en \(\{b_1, b_2, \ldots, b_l \}\text{,}\) entonces tanto \(\sigma\) como \(\tau\) fijan \(x\text{.}\) Es decir, \(\sigma(x)=x\) y \(\tau(x)=x\text{.}\) Luego,

\begin{equation*} \sigma \tau(x) = \sigma( \tau(x)) = \sigma(x) = x = \tau(x) = \tau( \sigma(x)) = \tau \sigma(x). \end{equation*}

No debemos olvidar que estamos multiplicando las permutaciones de derecha a izquierda,. Ahora supongamos que \(x \in \{ a_1, a_2, \ldots, a_k \}\text{.}\) Entonces \(\sigma( a_i ) = a_{(i \bmod k) + 1}\text{;}\) 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. \end{align*}

Pero, \(\tau(a_i) = a_i\) pues \(\sigma\) y \(\tau\) son disjuntos. Por lo tanto,

\begin{align*} \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). \end{align*}

Similarmente, si \(x \in \{b_1, b_2, \ldots, b_l \}\text{,}\) entonces \(\sigma\) y \(\tau\) también conmutan.

Podemos suponer que \(X = \{ 1, 2, \ldots, n \}\text{.}\) Si \(\sigma \in S_n\) y definimos \(X_1\) como \(\{ \sigma(1), \sigma^2(1), \ldots \}\text{,}\) entonces el conjunto \(X_1\) es finito pues \(X\) es finito. Ahora sea \(i\) el primer entero en \(X\) que no está en \(X_1\) y definamos \(X_2\) como \(\{ \sigma(i), \sigma^2(i), \ldots \}\text{.}\) Nuevamente, \(X_2\) es un conjunto finito. Continuando de esta manera, podemos definir conjuntos finitos disjuntos \(X_3, X_4, \ldots\text{.}\) Como \(X\) es un conjunto finito, estamos seguros que este proceso terminará y que habrá un número finito de estos conjuntos, digamos \(r\text{.}\) Si \(\sigma_i\) es el ciclo definido por

\begin{equation*} \sigma_i( x ) = \left\{\begin{array}{ll} \sigma( x ) & x \in X_i \\ x & x \notin X_i, \end{array}\right. \end{equation*}

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

Sean

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

Usando notación cíclica, podemos escribir

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

Desde ahora nos resultará conveniente usar la notación cíclica para representar las permutaciones. Cuando usemos la notación cíclica, frecuentemente representaremos la permutación identidad por \((1)\) o por \(()\text{.}\)

Subsección 5.1.2 Transposiciones

La permutación (no trivial) más simple es un ciclo de largo 2. Tales ciclos se llaman transposiciones. Como

\begin{equation*} (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 ), \end{equation*}

cualquier ciclo puede ser escrito como el producto de transposiciones, llevándonos a la siguiente proposición.

Considere la permutación

\begin{equation*} ( 1 6 ) (2 5 3) = (1 6 )( 2 3 )( 2 5 ) = (1 6 )( 4 5 )(2 3 )( 4 5 )(2 5 ). \end{equation*}

Como podemos ver, no hay una única forma de representar la permutación como producto de transposiciones. Por ejemplo, podemos escribir la identidad como \((1 2 )(1 2 )\text{,}\) como \((1 3 )(2 4 )(1 3 )( 2 4 )\text{,}\) y en muchas otras formas. Sin embargo, resulta ser, que ninguna permutación se puede escribir tanto como un producto de un número par como de un número impar de transposiciones. Por ejemplo, podemos representar la permutación \((1 6)\) por

\begin{equation*} (2 3 )(1 6)( 2 3) \end{equation*}

o por

\begin{equation*} (3 5) (1 6) (1 3) (1 6) (1 3) (3 5) (5 6), \end{equation*}

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

Procederemos por inducción en \(r\text{.}\) Una transposición no puede ser la identidad; luego, \(r \gt 1\text{.}\) Si \(r=2\text{,}\) estamos listos. Supongamos que \(r \gt 2\text{.}\) En este caso el producto de al menos dos de estas transposiciones, \(\tau_{r-1} \tau_r\text{,}\) debe estar en uno de los casos siguientes:

\begin{align*} (a b)(a b) & = \identity\\ (b c)(a b) & = (a c)(b c)\\ (c d)(a b) & = (a b)(c d)\\ (a c)(a b) & = (a b)(b c), \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, borre \(\tau_{r-1} \tau_r\) del producto para obtener

\begin{equation*} \identity = \tau_1 \tau_2 \cdots \tau_{r - 3} \tau_{r - 2}. \end{equation*}

Por inducción \(r - 2\) es par; luego, \(r\) debe ser par.

En cada uno de los otros tres casos, podemos reemplazar \(\tau_{r - 1} \tau_r\) con 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 aparición de \(a\) será en la penúltima transposición. Podemos continuar este proceso con \(\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 aparición de \(a\) es en \(\tau_{r - 2}\text{.}\) Si la identidad es el producto de \(r - 2\) transposiciones, entonces nuevamente estamos listos, por la hipótesis de inducción; de otro modo, repetiremos el procedimiento con \(\tau_{r - 3} \tau_{r - 2}\text{.}\)

En algún momento, tendremos dos transposiciones adyacentes iguales, que se cancelarán o \(a\) solamente estará presente en la primera transposición. Pero este último caso no puede ocurrir, pues la identidad no fijaría \(a\) en esta situación. Por lo tanto, la identidad debe ser el producto de \(r-2\) transposiciones y, nuevamente por la hipótesis de inducción, estamos listos.

Supongamos que

\begin{equation*} \sigma = \sigma_1 \sigma_2 \cdots \sigma_m = \tau_1 \tau_2 \cdots \tau_n, \end{equation*}

con \(m\) par. Debemos mostrar que \(n\) también es un número par. La inversa de \(\sigma\) es \(\sigma_m \cdots \sigma_1\text{.}\) Como

\begin{equation*} \identity = \sigma \sigma_m \cdots \sigma_1 = \tau_1 \cdots \tau_n \sigma_m \cdots \sigma_1, \end{equation*}

\(n\) debe ser par por el Lema 5.1.14. La demostración del caso en el que \(\sigma\) puede ser expresada como el producto de un número impar de transposiciones lo dejamos como ejercicio.

A la luz del Teorema 5.1.15, definimos que una permutación es par si puede ser expresada como el producto de un número par de transposiciones e impar si puede ser expresada como el producto de un número impar de transposiciones.

Subsección 5.1.3 Los Grupos Alternantes

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 grupo alternante en \(n\) símbolos.

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

\begin{equation*} \sigma = \sigma_1 \sigma_2 \cdots \sigma_r, \end{equation*}

donde \(\sigma_i\) son transposiciones y \(r\) es par. Como la inversa de una transposición es ella misma,

\begin{equation*} \sigma^{-1} = \sigma_r \sigma_{r-1} \cdots \sigma_1 \end{equation*}

también está en \(A_n\text{.}\)

Sea \(A_n\) el conjunto de permutaciones pares en \(S_n\) y \(B_n\) el conjunto de permutaciones impares. Si podemos mostrar que existe una biyección entre estos conjuntos, habremos demostrado que contienen el mismo número de elementos. Fijemos una transposición \(\sigma\) en \(S_n\text{.}\) Como \(n \geq 2\text{,}\) tal \(\sigma\) existe. Defina

\begin{equation*} \lambda_{\sigma} : A_n \rightarrow B_n \end{equation*}

como

\begin{equation*} \lambda_{\sigma} ( \tau ) = \sigma \tau . \end{equation*}

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

\begin{equation*} \tau = \sigma^{-1} \sigma \tau = \sigma^{-1} \sigma \mu = \mu. \end{equation*}

Por lo tanto, \(\lambda_{\sigma}\) es 1-1. Dejaremos la demostración de que \(\lambda_{\sigma}\) es sobreyectiva como ejercicio.

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

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

Uno de los ejercicios al final del capítulo será el de encontrar todos los subgrupos de \(A_4\text{.}\) Descubrirá que no hay ningún subgrupo de orden 6. ¿Le sorprende?

Subsección 5.1.4 Note Histórica

Lagrange fue el primero en pensar las permutaciones como funciones de un conjunto en sí mismo, pero fue Cauchy quién desarrolló los teoremas básicos y la notación para las permutaciones. Él fue el primero en usar la notación cíclica. Augustin-Louis Cauchy (1789–1857) nació en París durante en el apogeo de la Revolución Francesa. Su familia dejó París y se fue al pueblo de Arcueil para escapar del Reino del Terror. Uno de los vecinos de la familia allí, fue Pierre-Simon Laplace (1749–1827), quien lo motivó a iniciar una carrera en matemáticas. Cauchy comenzó su carrera como matemático resolviendo un problema de geometría que le planteó Lagrange. Cauchy escribió más de 800 trabajos en diversos tópicos, como ecuaciones diferenciales, grupos finitos, matemáticas aplicadas, y análisis complejo. Fue uno de los matemáticos responsables de hacer que el Cálculo Diferencial fuera riguroso. Es probable que haya más teoremas y conceptos en matemáticas asociados al nombre de Cauchy que al de cualquier otro matemático.