Archivo del Autor: Cecilia del Carmen Villatoro Ramos

Álgebra Moderna I: Paridad de una permutación

Introducción

En la entrada anterior descubrimos que toda permutación se puede factorizar en producto de transposiciones. Mas aún, el polinomio de Vandermonde nos permite saber que, aunque hayan varias factorizaciones, en realidad, todas siempre tienen una cantidad par (o un cantidad impar) de transposiciones. Con esto, podemos definir el signo de una permutación.

Ya teniendo una noción de la paridad de una permutación podemos jugar con las consecuencias: podemos deducir qué pasa si multiplicamos dos permutación con la misma paridad, qué sucede cuando tienen distinta paridad y además, como es raro en los cursos de matemáticas… ¡podemos agrupar por paridad! En esta entrada, descubrimos que el conjunto de transposiciones con signo par, es en realidad un grupo con $\frac{n!}{2}$ elementos. Este conjunto es llamado el grupo alternante.

¿Pares o impares?

Definición. Sea $\alpha \in S_n$, $\alpha$ es par si $\alpha = \text{id}$ o si $\alpha$ es un producto de un número par de transposiciones. Por otro lado, $\alpha$ es impar si es un producto de un número impar de transposiciones.

La función signo es $sgn: S_n \to \{+1, -1\}$ definida como
\begin{align*}
sgn \; \alpha = \begin{cases} +1 & \text{si } \alpha \text{ es par} \\
-1 & \text{si } \alpha \text{ es impar}
\end{cases}
\end{align*}

Observación. Sean $\alpha = \tau_{1} \cdots \tau_r \in S_n$, con $\tau_{1}, \cdots, \tau_r$ transposiciones. Entonces $sgn\;\alpha = (-1)^r$.

Demostración.
La definición nos asegura que $sgn\;\alpha = +1$ si y sólo si $r$ es par.

$\square$

Proposición. Sean $\alpha, \beta \in S_n$. Entonces $$sgn \;(\alpha \, \beta) = sgn\, \alpha \; sgn \, \beta.$$

Esto nos dice que la función signo ($sgn$) es multiplicativa. Esto lo hace más sencilla de trabajar.

Demostración.

Esto es bastante fácil de demostrar, para usar lo que vimos tenemos que expresar a estas permutaciones como producto de transposiciones.

Sean $\alpha, \beta \in S_n$, con $\alpha = \tau_{1} \cdots \tau_r$, $\beta = \rho_1 \cdots \rho_t$. Donde, $\tau_1, \cdots, \tau_r, \rho_{1}, \cdots, \rho_t$ son transposiciones.

Si calculamos el signo del producto $\alpha\,\beta$ y usando la observación anterior, obtenemos lo siguiente:
\begin{align*}
sgn(\alpha \, \beta) &= sgn(\tau_1 \cdots \tau_r \, \rho_1 \cdots \rho_t) \\
& = (-1)^{r+t} & \text{Observación anterior}\\
& = (-1)^r \, (-1)^t & \text{Propiedades de las potencias}\\
& = sgn\, \alpha \; sgn\, \beta &\text{Observación anterior}
\end{align*}

Esto es precisamente lo que queríamos probar.

$\square$

Podemos concluir que para calcular el signo de un producto, basta entender el signo de cada uno de los factores.

Calculando el signo de una transposición

Seguiremos puliendo la idea que nos dio la proposición anterior hasta llegar a una fórmula para sacar el signo de una permutación. Pero por ahora, veamos qué sucede con los $r$-ciclos

Lema. Sea $\sigma = (i_1 \cdots i_r) \in S_n$ un $r$-ciclo. Entonces $sgn\, \sigma = (-1)^{r-1}$.

Demostración.
Recordemos que en la entrada anterior vimos que podemos ver a $\sigma$ como producto de transposiciones:
\begin{align*}
\sigma &= (i_1 \cdots i_r) = (i_1\,i_r) \cdots (i_1 \, i_2).
\end{align*}
Ituitivamente, estamos intercambiando a $i_1$ con los elementos que le siguen, esto nos da $r-1$ transposiciones. Por lo tanto, $\sigma$ es un producto de $r-1$ transposiciones. De acuerdo con la observación, podemos concluir que $sgn \, \sigma = (-1)^{r-1}$.

$\square$

Teorema. Sea $\alpha \in S_n$, $\alpha = \beta_1 \cdots \beta_t$ una factorización completa de $\alpha$. Entonces $sgn\,\alpha = (-1)^{n-t}$, donde $n$ es la cantidad de elementos que estoy permutando y $t$ es la cantidad de factores que tiene la factorización completa de $\alpha$.

Demostración.
Como el signo es multiplicativo,
\begin{align*}
sgn\,\alpha = \prod_{i=1}^t sgn\,\beta_i.
\end{align*}
Estamos tomando una factorización completa de $\alpha$, entonces todos los $\beta_i$ son ciclos disjuntos. Así que su signo está dado por la longitud del ciclo (de acuerdo al lema dado):
\begin{align*}
sgn\,\beta_i = (-1)^{\text{long}\,\beta_i-1} \qquad \forall i\in\{1,\dots,t\}.
\end{align*}
Juntando ambas ecuaciones y sumando los $t$ exponentes obtenemos las siguientes igualdades
\begin{align*}
sgn\,\alpha &= \prod_{i = 1}^{t} sgn \,\beta_i & \text{Proposición}
\\&= \prod_{i = 1}^t (-1)^{\text{long}\,\beta_i – 1} &\text{Lema}\\
& = (-1)^{\left(\sum_{i = 1}^t \text{long}\,\beta_i \right) – t} = (-1)^{n-t}. &\text{Leyes de exponentes}
\end{align*}

Como la factorización es completa, la siguiente igualdad se cumple: $$\sum_{i = 1}^t \text{long}\,\beta_i = n.$$

Por lo tanto $sgn\,\alpha = (-1)^{n-t}$.

$\square$

Esta forma resulta útil porque ya no necesito descomponer una permutación en producto de transposiciones, nos basta con encontrar una factorización completa. Veamos esto con un ejemplo.

Ejemplo.
Consideremos $\alpha \in S_{10}$ como
\begin{align*}
\alpha = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
2 & 4 & 7 & 5 & 1 & 8 & 3 & 9 & 6 & 10
\end{pmatrix}.
\end{align*}

También podemos escribirla como $\alpha = (1\;2\;4\;5)(3\;7)(6\;8\;9)(10)$. Esto nos muestra que $\alpha$ es una factorización completa con 4 factores.

Entonces, de acuerdo con el teorema que acabamos de probar, $sgn\,\alpha = (-1)^{10-4} = (-1)^6 = +1$.

Por otro lado podemos sacar una factorización de $\alpha$ en transposiciones: $\alpha = (1 \; 5)(1 \; 4)(1 \; 2)(3 \; 7)(6 \; 9)(6 \; 8)$ que tiene 6 transposiciones. Entonces, efectivamente $\alpha$ es un producto de un número par de transposiciones.

Hora de Agrupar

Hemos visto que la función $sgn$ es una función mutliplicativa. Esto nos da como consecuencia que al multiplicar dos permutaciones con la misma paridad, te da como resultado una permutación par. En caso contrario, el resultado es impar. Ahora nos fijaremos solamente en las permutaciones pares.

Definición. El grupo alternante para $n$ elementos está definido como

$$A_n = \{\alpha \in S_n | sgn \, \alpha = +1\}.$$

Observación. $A_n$ efectivamente es un subgrupo de $S_n$.

Demostración.
Si $\alpha = \text{id}$, por definición del signo, $sgn\,\text{id} = +1$. Así, $\text{id}\in A_n$.

Sean $\alpha, \beta \in A_n$.
Como la función signo es multiplicativa:
\begin{align*}
sgn\,\alpha\beta = sgn \, \alpha \; sgn \, \beta = (+1)(+1) = +1.
\end{align*}
Así, $\alpha\beta \in A_n$. Es decir, $A_n$ es cerrada bajo el producto.

Por último, sea $\alpha \in A_n$.

Por un lado, usando la propiedad multiplicativa del signo obtenemos:
\begin{align*}
sgn\,(\alpha\alpha^{-1}) = sgn \, \alpha \; sgn \, \alpha^{-1} = (+1)\, sgn\, \alpha^{-1}.
\end{align*}

Por otro lado, como $\alpha \,\alpha^{-1} = \text{id}$, tenemos:
\begin{align*}
sgn\,(\alpha\,\alpha^{-1}) = sgn\, \text{id} = +1.
\end{align*}

Por lo tanto $sgn\,(\alpha\, \alpha^{-1}) = +1$, así $\alpha^{-1} \in A_n$. Es decir, $A_n$ es cerrada bajo inversos.

Por lo tanto $A_n$ es un subgrupo de $S_n$.

$\square$

El siguiente resultado nos muestra que el grupo alternante $A_n$ «parte en dos» a las permutaciones, es decir, la mitad de permutaciones son pares.

Proposición. Sea $n>1$, entonces $|A_n| = \frac{n!}{2}$.

Demostración. Podemos ver a $S_n$ como la unión de las permutaciones pares e impares, esto se expresa así $$S_n = A_n \cup (S_n\setminus A_n).$$
Pero, podemos dar una biyección definida como $\phi: A_n \to S_n\setminus A_n$, definida como $\phi \, \alpha = (1\;2)\alpha$.

Entonces, $|A_n| = \# S_n \setminus A_n$.

Así, como dijimos que

$n! = |S_n| = |A_n| + \# S_n\setminus A_n = 2 |A_n|$.

Por lo tanto $|A_n| = \frac{n!}{2}$.

Notación. Para denotar la cardinalidad u orden de un conjunto $A$, usamos dos notaciones:
\begin{align*}
|A| \to & \;\text{Si $A$ es un grupo.}\\
\# A \to & \;\text{Si $A$ no es un grupo (o si no sabemos si $A$ es un grupo o no).}
\end{align*}

Tarea moral

  1. Considera el elemento $\alpha \in S_{12}$ como
    \begin{align*}
    \alpha = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &10&11&12\\
    2 & 11&4& 1 & 8 &12& 3 & 6 & 9 & 5 & 7 & 10
    \end{pmatrix}
    \end{align*}
    1. Encuentra $\alpha^{-1}$, el signo de $\alpha$ y el de $\alpha^{-1}$.
    2. En general, ¿qué pasará con el signo de una permutación y de su inversa?
  2. Sea $\alpha$ un $r$ ciclo en $S_n$. ¿Podemos determinar el signo de $\alpha$ a partir de la paridad de $r$?
  3. Dada $\alpha \in S_n$ decimos que los números $i,j \in \{1,2,\dots,n\}$ forman una inversión si $i<j$ pero $\alpha(i) > \alpha(j)$. ¿Qué relación existe entre la paridad y el número de inversiones de $\alpha$?
  4. Encuentra todos los elementos de $A_4$.

Más adelante…

Esta entrada nos sirvió para construir los cimientos, es importante que lo tengamos claro antes de avanzar. En la siguiente entrada definiremos el producto de $S$ con $T$, veremos en qué situaciones el producto de los subconjuntos conmuta, cuándo se cumple que $ST$ es un subgrupo de $G$. Esto nos ayudará para definir las clases laterales. Más adelante, estas clases nos ayudarán a definir una nueva relación de equivalencia.

Entradas relacionadas

Álgebra Moderna I: Misma Estructura Cíclica, Permutación Conjugada y Polinomio de Vandermonde.

Introducción

Anteriormente en nuestro curso, definimos una caracterización única para las permutaciones, aprendimos que la factorización completa es única salvo por el orden de los factores. Ahora, podemos analizar a los ciclos que aparecen en dicha factorización completa.

La unicidad de la factorización completa nos asegura que la cantidad de ciclos que la conforman y la longitud de éstos no van a cambiar sin importar la factorización que escojamos. Estudiar estas propiedades de la factorización completa motiva la definición de estructura cíclica y de permutación conjugada, dos definiciones centrales de esta entrada.

Además de la factorización completa, existen otras maneras de descomponer a las permutaciones. Intuitivamente, podemos pensar a las permutaciones como reacomodos, entonces es posible llegar a cualquier acomodo intercambiando elementos de dos en dos, es decir podemos reacomodar los números de $1$ a $n$ como queramos mediante intercambios dos a dos.

Misma Estructura Cíclica

Recordemos que toda permutación se puede factorizar en una factorización completa y que toda factorización completa es única salvo por el orden de sus productos. Entonces la cantidad de ciclos y su longitud no va a cambiar, independientemente de la factorizacoón completa que escojamos. Esto motiva la siguiente definición.

Definición. Sean $\alpha, \beta \in S_n$. Decimos que $\alpha$ y $\beta$ tienen la misma estructura cíclica si su factorización completa tiene el mismo número de $r-$ciclos para toda $r \in \z^+$.

Ejemplo.

En $S_9$, tomemos $\alpha$ y $\beta$ como sigue

\begin{align*}
\alpha &= (2 \; 4 \; 7 \; 9)(1 \; 3)(5 \; 6)(8)\\
\beta &= (2 \; 4)(1 \; 5 \; 8 \; 9)(3 \; 7)(6).
\end{align*}

Claramente, $\alpha$ y $\beta$ tienen la misma estructura cíclica, ya que ambas están formadas por un $4-$ciclo, dos transposiciones y un uno ciclo.

Permutación Conjugada

Definición. Sean $\alpha, \beta \in S_n$. Decimos que $\beta$ es conjugada de $\alpha$ si existe $\gamma \in S_n$ tal que $\beta = \gamma \alpha \gamma^{-1}$.

Ejemplo.

Tomemos $\gamma = (1 \; 2 \; 3)$, entonces $\gamma = (1\;2\;4)$ y $\alpha = (3 \; 5 \; 6 \; 8)$. Entonces podemos calcular a $\beta$ como sigue,

\begin{align*}
\gamma\alpha\gamma^{-1} &= (1 \; 2 \; 3)(3 \; 5 \; 6 \; 8)(1 \; 3 \; 2) \\
& = (1 \; 5 \; 6 \; 8) = \beta
\end{align*}

Así, $\beta = (1 \; 5 \; 6 \; 8)$ es conjugada de $(1 \; 5 \; 6 \; 8) = \alpha$.

Teorema.

La siguiente igualdad de conjuntos se cumple,

$S_n = \left< \{\tau \in S_n | \tau \text{ es una transposición} \} \right>$.

Demostración.

Como toda permutación es un producto de ciclos, basta ver que todo ciclo es un producto de transposiciones. Así,

\begin{align*}
(i_1 \; \cdots \; i_r) = (i_1 \; i_r) \cdots (i_1\; i_3)(i_1 \; i_2).
\end{align*}

Por lo tanto $S_n = \left< \{ \tau \in S_n | \tau \text{ es una transposición} \}\right>$.

$\square$

Podemos observar que si consideramos la relación en $S_n$ dada por $\alpha \sim \beta$ si y sólo si $\alpha$ es conjugada de $\beta$, es una relación de equivalencia. Aquí no lo demostraremos, pero queda como tarea moral.

¿A qué nos referimos con reacomodos?

Vimos que toda permutación se puede descomponer en ciclos disjuntos y, bajo condiciones específicas, esta descomposición es única salvo por orden de factores. Sin embargo, hay otras maneras de descomponer a una permutación, las podemos pensar a las permutaciones como reacomodos. Es claro que podemos llegar a cualquier reacomodo intercambiando los elementos de 2 en 2.

A continuación, ilustramos esto con un ejemplo.

Tomemos $\sigma = (1 \; 2 \; 3 \; 4 \; 5)$, en esta permutación los números $1,2,3,4$ y $5$ cambian ya que el $1$ va a dar a $2$, el $2$ al $3$, etc., así que si reacomodamos los números $1,2,3,4,5$ de acuerdo a lo que nos indica $\sigma,$ en vez la lista $1\;2\;3\;4\;5$ tendremos ahora la lista $2\;3\;4,5\;1.$ Entonces nos preguntamos, ¿cómo podemos llegar de la lista $1\;2\;3\;4\;5$ a la lista $2\;3\;4\;5\;1$ sólo mediante intercambios dos a dos?

Primero, observemos que lo único que tenemos que hacer es pasar el 1 hasta el final. Luego, tomemos en cuenta que nuestra propuesta es intercambiar los elementos de dos en dos. Así, el proceso es el siguiente:

Referencia visual del reacomodo.
  1. Intercambiamos 1 y 2, así nuestra lista quedaría $2 \; 1 \; 3 \; 4 \; 5.$ Observemos que el 2 ya queda en la posición deseada.
  2. Sobre el resultado anterior, intercambiamos 1 y 3. Hasta el momento tenemos el reacomodo $2 \; 3 \; 1 \; 4 \; 5$.
  3. Ahora, nos toca intercambiar 1 y 4. Así obtenemos $2 \; 3 \; 4 \; 1 \;5$
  4. Por último, nos queda acomodar el último número, así que intercambiamos 1 y 5.

Al final, llegamos al reacomodo buscado. Esto nos indica que para permutar los números $1,2,3,4$ y $5$ de acuerdo a $\sigma$ basta con intercambiar el uno con el dos, luego el uno con el tres, después el uno con el cuatro y finalmente el uno con el cinco. En otras palabras, la permutación sigma se obtiene de aplicar sucesivamente las transposiciones $(1 \; 2)$, $(1 \; 3)$, $(1 \; 4)$ y $(1 \; 5)$. Debido a que escribimos la composición de permutaciones de derecha a izquierda, nuestra sigma quedaría de la siguiente manera:

$\sigma = (1 \; 2 \; 3 \; 4 \; 5) = (1 \; 5) (1 \; 4) (1 \; 3) (1 \; 2).$

Este ejemplo nos ilustra cómo podemos descomponer un ciclo como producto de transposiciones. Probaremos esto en el caso general, y dado que toda permutación es un producto de ciclos y cada ciclo se puede descomponer en producto de transposiciones, entonces podremos concluir que toda permutación es un producto de transposiciones.

El polinomio de Vandermonde

Hemos probado que toda permutación se puede expresar como un producto de transposiciones, esto es importante porque las transposiciones son permutaciones muy sencillas, sin embargo estas descomposiciones no son únicas, pueden cambiar los factores que aparecen, su orden e incluso en el número de factores que presentan. A pesar de ello siempre tienen un número par o siempre un número impar de transposiciones. Para probar este resultado introduciremos un polinomio con distintas indeterminadas que permutaremos usando permutaciones.

Definición. El polinomio de Vandermonde en los indeterminadas $x_1, \dots, x_n$ con coeficientes enteros es

\begin{align*}
V(x_1,\dots,x_n) = \prod_{1 \leq i < j \leq n}(x_i – x_j).
\end{align*}

Dado $\alpha \in S_n$, el $\alpha-$polinomio de Vandermonde es

\begin{align*}
\alpha \; V(x_1, \dots, x_n) = \prod_{1 \leq i < j \leq n}(x_{\alpha(i)} – x_{\alpha(j)}).
\end{align*}

Ejemplo.

\begin{align*}
V(x_1,x_2,x_3,x_4) = & (x_1 – x_2)(x_1 – x_3)(x_1 – x_4) \\
& (x_2 – x_3) (x_2 – x_4)(x_3-x_4)
\end{align*}

Calculemos ahora $(2 \; 4) \, V(x_1,x_2,x_3,x_4)$. Observemos que los únicos factores de $V$ que cambian son aquellos donde aparece el subíndice $2$ o el $4$, y éstos se intercambian, por ejemplo el factor $ (x_1 – x_2)$ cambiará al factor $ (x_1 – x_4)$. Así

\begin{align*}
(2 \; 4) \, V(x_1,x_2,x_3,x_4) = &(x_1 – x_4)(x_1 – x_3)(x_1-x_2)\\
&(x_4-x_3)(x_4 – x_2)(x_3-x_2) \\
= & \,- V(x_1,x_2,x_3,x_4).
\end{align*}

Observación. Sólo pueden suceder dos cosas, $\alpha V = V$ ó $\alpha V = – V$ para todo $\alpha \in S_n$.

Vandermonde y las Transposiciones

A continuación veremos qué efecto tienen las transposiciones en el polinomio de Vandermonde.

Lema 1. Sea $\tau \in S_n$ una transposición. Entonces $\tau V = -V$.

Demostración.

Sea $\tau = (k \; l) \in S_n$ con $k < l$.
Al aplicar $\tau$ a $V$, los factores donde no aparecen ni $k$ ni $l$ quedan igual, los factores $x_i-x_k$ con $i<k$ cambian a $x_i-x_k$ con $i<k<l$ por lo que no provocan cambio de signo. Mediante argumentos análogos podemos ver que tampoco los factores

\begin{align*}
x_k – x_i \quad &\text{ con } \quad i > l \\
x_i – x_l \quad &\text{ con } \quad i < k \\
x_l – x_i \quad &\text{ con } \quad i > l
\end{align*}

cambian de signo. Sólo cambian de signo los factores
\begin{align*}
x_k – x_{k + 1} && x_{k+1} – x_l \\
x_k – x_{k+2} && x_{k+2} – x_l \\
\vdots && \vdots \\
x_k – x_{l-1} && x_{l-1} – x_l \\
x_k – x_l
\end{align*}

Debido a que en esta última lista hay una cantidad impar de factores, entonces hay una cantidad impar de cambios de signo. Por lo tanto $\tau\, V = -V$.

$\square$

Lema 2. Sean $\tau, \beta \in S_n$, $\tau$ una transposición. $( \tau \beta )V = – \beta V$.

Demostración. Basta hacer
\begin{align*}
(\tau \beta) V = \tau (\beta V) = \tau (\pm V) = – (\pm V) = – \beta V.
\end{align*}

$\square$

Teoremas importantes

Teorema. Sea $\alpha = \tau_1 \cdots \tau_r \in S_n$, $\tau_1, \dots, \tau_r$ transposiciones. Entonces

$\alpha V = (-1)^r \,V$.

Demostración. Por inducción sobre $r$.

Base de inducción: Supongamos que $r = 1$.
Entonces, desarrollando $\alpha V$ y usando el lema 1 obtenemos

\begin{align*}
\alpha V &= \tau_1 V\\
&= -V = (-1)^1 V & \text{Lema 1}
\end{align*}

Así, se cumple la proposición para al caso base.

Ahora, sea $r > 1$.
Hipótesis de Inducción: Supongamos que el resultado se cumple para el producto de $r-1$ transposiciones.

P.D. $\alpha V = (-1)^r V$.

Desarrollando $\alpha V$ y usando el Lema 2, obtenemos:

\begin{align*}
\alpha V &= (\tau_1 \, \tau_2 \cdots \tau_r) V\\
&= (\tau_1 \, (\tau_2 \cdots \tau_r)) V & \text{Agrupamos}\\
&= -(\tau_2 \cdots \tau_r) V &\text{Lema 2}
\end{align*}

Ahora, como $(\tau_2 \cdots \tau_r)$ tiene $r-1$ factores, podemos aplicar la hipótesis de inducción y continuar con las igualdades.

\begin{align*}
-(\tau_2 \cdots \tau_r) V = -(-1)^{r-1} V = (-1)^r \,V
\end{align*}

Así, demostramos lo deseado.

$\square$

Teorema. Sea $\alpha = \tau_1 \cdots \tau_r = \rho_1 \cdots \rho_t \in S_n$, con $\tau_1, \cdots, \tau_r$, $\rho_1, \cdots, \rho_t$ transposiciones. Entonces $r$ y $t$ tienen la misma paridad.

Demostración.
Por el teorema anterior, obtenemos:

\begin{align*} \alpha V = (\rho_1 \cdots \rho_t) V = (-1)^t \,V \end{align*}

Por otro lado, por el teorema anterior también obtenemos:

\begin{align*} \alpha V = (\tau_1 \cdots \tau_r) V = (-1)^r \,V \end{align*}

Entonces $(-1)^t V = (-1)^r V$. Por lo tanto $t$ y $r$ tienen la misma paridad.

$\square$

Tarea moral

  1. Prueba que la relación en $S_n$ dada por $\alpha \sim \beta$ si y sólo si $\beta$ es conjugada de $\alpha$, es una relación de equivalencia.
  2. Encuentra $\sigma\alpha\sigma^{-1}$ en cada inciso:
    1. $\alpha = ( 2 \; 3 \; 5), \; \sigma = (1\; 3 \; 5 \; 6)$.
    2. $\alpha = (5 \; 4 \; 3 \; 1), \; \sigma = (2 \; 4 \; 5 \; 7 \; 8)$.
    3. $\alpha = (1 \; 7 \; 5 \; 4 \; 2 \; 3), \; \sigma = (1 \; 2 \; 4 \; 6 \; 7)$.
  3. Sean $\alpha,\sigma \in S_n$ con $\sigma = (i_1\; i_2 \; \cdots \; i_r) \in S_n$ un $r-$cíclo.
    1. ¿Qué forma cíclica tiene $\alpha\sigma\alpha^{-1}$?
    2. ¿Cómo podemos describir a la permutación $\alpha\sigma\alpha^{-1}$ a partir de cómo son $\alpha$ y $\sigma$ sin necesidad de hacer paso a paso la composición? ¿puedes encontrar una fórmula que lo describa?
  4. Considera $\alpha = (1 \; 9 \; 4)(10 \; 2 \; 8 \; 5 \; 3)(3 \; 5 \; 6 \; 8)(7 \; 2) \in S_{10}$.
    1. Escribe a $\alpha$ como un producto de transposiciones de al menos tres formas distintas y compara la cantidad de transposiciones que se usan en cada caso.
    2. Con lo anterior, determina quién es $\alpha V$.

Más adelante…

Todavía nos quedan propiedades del polinomio de Vandermonde que estudiar. En la siguiente entrada profundizaremos en ellas. Por ejemplo, ¿existe una manera de determinar el signo que tendrá el $\alpha-$polinomio de Vandermonde? ¿Cómo se relaciona con la descomposición de la permutación $\alpha$? ¿Hay manera de relacionar las permutaciones que dan lugar a polinomios con el mismo signo? Éstas y otras preguntas las responderemos a continuación.

Entradas relacionadas

Álgebra Moderna I: Factorización Completa

Introducción

Consideremos $\alpha \in S_7$ como $\alpha = (1\,3\,2)(6\,4)$, esta permutación fija a $5$ y a $7$. Entonces también podemos escribirla como $\alpha = (1\,3\,2)(6\,4)(5)(7)$. Notamos que una de las cosas en las que difieren es que en la segunda descomposición estamos agregando uno ciclos, pero también $\alpha = (1 \, 3 \, 2) (7) (6 \, 4)(5)$ es otra forma diferente de expresar a la permutación escribiendo a los uno ciclos. En esta entrada nos planteamos la posibilidad de escribir a $\alpha$ como un producto de ciclos distintos incluyendo a todos los uno ciclos y analizamos en qué difieren todas las distintas maneras de hacerlo.

Antes de empezar, podrías intentar escribir todas las maneras posibles de describir a $\alpha$ escribiendo a los uno ciclos. ¿Notas algo en común entre todas? Al final de esta entrada, tendremos la respuesta más clara.

Definición de una factorización completa

Para empezar, necesitamos definir un nuevo concepto.

Definición. Sea $\alpha \in S_n$. Una factorización completa de $\alpha$ es una descomposición de $\alpha$ en ciclos disjuntos con un $1-$ciclo por cada elemento fijado por $\alpha$.

Ejemplos.

  1. Sea $\alpha \in S_8$ como
    \begin{align*}
    \alpha = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\
    3 & 2 & 1 & 5 & 7 & 6 & 4 & 8
    \end{pmatrix}
    \end{align*}

    Entonces $\alpha = (1 \; 3)\,(4 \; 5 \; 7)$ es una factorización de $\alpha$ en ciclos distintos pero no es una factorización completa de $\alpha$. Por otro lado $\alpha = (1 \; 3)\,(4 \; 5 \; 7)\,(2) \,(6) \,(8)$ sí es una factorización completa de $\alpha$.
  2. Sea $\beta$ dada por \begin{align*}
    \beta = (2 \; 4 \; 6 \; 8) \, (1 \; 3 \; 5)\,(7).
    \end{align*}

    Esa es una factorización completa de $\beta \in S_8$, pero no en $S_{10}$, en $S_{10}$ una factorización completa de de $\beta$ sería
    \begin{align*}
    \beta = (2 \; 4 \; 6 \; 8) \, (1 \; 3 \; 5)\,(7)\, (9) \, (10).
    \end{align*}

Una herramienta misteriosa que nos ayudará más tarde

El siguiente resultado es un lema técnico que nos ayudará a resolver el problema planteado al inicio de esta entrada. De manera informal el lema nos dice que si tenemos una factorización de una permutación en factores distintos, el factor que mueve a un elemento de su soporte, moverá a ese elemento de la misma forma que la permutación misma. También nos dice que si dos ciclos y cada una de sus potencias mueven a un elemento de su soporte de la misma forma, entonces los ciclos son iguales.

Lema.

  1. Sea $\alpha \in S_n$, $\alpha = \beta_1 \cdots \beta_t$ una factorización en permutaciones disjuntas e $i \in \{1,\dots,n\}$. Si $\beta_1(i) \neq i$ entonces $\alpha^k(i) = \beta_1^k(i)$ para toda $k \in \z$.
  2. Sean $\beta,\gamma \in S_n$ ciclos. Si existe $i \in \{1, \dots, n\}$ tal que $\beta(i) \neq i \neq \gamma (i)$ y $\beta^k(i) = \gamma^k(i)$ para toda $k \geq 1$, entonces $\beta = \gamma$.

Demostración.

  1. Sea $\alpha = \beta_1 \cdots \beta_t \in S_n$ una factorización en permutaciones disjuntas. Sea $i \in \{1, \dots,n\}$ tal que $\beta_1(i) \neq i$.
    Entonces, $\alpha^k = (\beta_1(\beta_2 \cdots \beta_t))^k = \beta_1^k(\beta_2 \cdots\beta_t)^k$ para toda $k \in \z$ ya que como $\beta_1$ y $(\beta_2 \cdots\beta_t)$ son disjuntas, conmutan.
    Además, como $\beta_1(i)\neq i$, el hecho de que $\beta_1, \dots, \beta_t$ sean disjuntas implica que $\beta_2(i)=\dots \beta_t(i)=i$, entonces $\beta_2 \cdots \beta_t(i) = i$. Así $\alpha^k(i) = \beta_1^k (\beta_2\cdots \beta_t)^k(i) = \beta_1^k(i)$ para toda $k \in \z$.
  2. Sean $\beta, \gamma \in S_n$ ciclos, $i \in \{1, \dots, n\}$ tal que $\beta$ y $\gamma$ mueven a $i$ y $\beta^k(i) = \gamma^k(i)$ para todo $k \geq 1$.
    P.D. $\beta = \gamma$
    Como $\beta$ y $\gamma$ son ciclos que mueven a $i$, entonces los podemos escribir como $\beta = (i \; i_1 \; \cdots \; i_r)$ y $\gamma = (i \; j \; \cdots \; j_l)$.
    Si observamos cómo mueven a los elementos, tenemos que
    \begin{align*}
    \beta^k(i) = i_k, \; k\in \{1, \dots, r\}, \; \beta^{r+1}(i) = i \\
    \gamma^k(i) = j_k, \; k \in \{1, \dots, l\}, \; \beta^{l+1}(i) = i
    \end{align*}
    Supongamos que $r \neq l$, sin pérdida de generalidad, $r < l$.
    \begin{align*}
    i &= \beta^{r+1}(i) \\
    & = \gamma^{r+1}(i) & \text{porque }\beta^k(i) = \gamma^k(i) \;\; \forall k \geq 1 \\
    & = j_{r+1} \neq i & r+1 \leq l
    \end{align*}
    Esto es una contradicción.
    Así, $r = l$ y $i_k = \beta^k(i) = \gamma^k(i) = j_k$ para toda $k \in \{1,\dots,r\}$.
    Por lo tanto $\beta = \gamma$.

$\square$

No es UNA factorización completa, es LA factorización completa

Recortemos la pregunta de la introducción ¿qué tienen en común todas las formas de describir a $\alpha$ como un producto de ciclos distintos en el que se incluyen todos los uno ciclos? He aquí la respuesta.

Teorema. Una factorización completa es única salvo por el orden de los factores.

Demostración.

Dado que en una factorización completa los $1-$ciclos corresponden a los elementos que quedan fijos, basta probar que los ciclos de longitud mayor a $1$ que aparecen en toda factorización completa coinciden.

Haremos inducción sobre $k = \#$sop $\alpha$.

Caso base. Cuando $k = 0$, entonces $\alpha =$ id y por lo tanto no tiene ciclos de longitud mayor a 1.

Sea $k > 0$.
Hipótesis de Inducción. Supongamos que si $\beta \in S_n$ con $\#$sop $\beta < k$, cualesquiera dos factorizaciones completas de $\beta$ tienen exactamente los mismos ciclos de longitud mayor a 1.

Sean $\alpha = \beta_1 \cdots \beta_t = \gamma_1 \cdots \gamma_s$, con $t,s \in \n^+$ dos factorizaciones de $\alpha$ obtenidas de omitir los $1-$ciclos en dos factorizaciones completas de $\alpha$.

Como $k>0$, existe $i \in \{1,\dots,n\}$ tal que $\alpha(i) \neq i$ y entonces también deben existir algún $\beta_j$ y algún $\gamma_l$ que muevan a $i$. Sin pérdida de generalidad supongamos que $\beta_1(i) \neq i \neq \gamma_1(i)$.

Entonces, por el inciso 1 del lema anterior,
\begin{align*}
\beta_i^k(i) = \alpha^k(i) = \gamma_1(i)^k \qquad \forall k \in \z
\end{align*}

y, por el inciso 2 del mismo lema,
\begin{align*}
\beta_1 = \gamma_1 .
\end{align*}

Así, cancelando $\beta_1$ tenemos que

\begin{align*}
\beta_2 \cdots \beta_t = \gamma_2 \cdots \gamma_s.
\end{align*}

Pero $\beta_2 \cdots \beta_t = \gamma_{2} \cdots \gamma_s$ son dos factorizaciones de una permutación que mueve menos de $k$ elementos con ciclos disjuntos de longitud mayor a $1$.

Por la hipótesis de inducción, $t = s$ y $\beta_2, \dots, \beta_t$son los mismos que $\gamma_2, \dots, \gamma_t$ salvo por el orden.

Por lo tanto, $\beta_1,\dots,\beta_t$ son los mismos que $\gamma_1,\dots,\gamma_s$ salvo por el orden.

$\square$

Tarea moral

  1. Considera el siguiente elemento de $S_9$
    \begin{align*}
    \alpha = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
    9 & 8 & 1 & 4 & 3 & 7 & 6 & 2 & 5
    \end{pmatrix}
    \end{align*}
    Encuentra la factorización completa de $\alpha$.
  2. Sea $\alpha \in S_n$ y $\alpha = \beta_1 \dots \beta_t$ una factorización completa de $\alpha$. Analiza qué ocurre con $\displaystyle \sum_{i= 1}^t \text{long } \beta_i$.
  3. Considera el ejercicio 3 de la entrada de permutaciones:
    Sean $\alpha, \beta \in S_{10}$,
    \begin{align*}
    \alpha = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
    10 & 4 & 3 & 2 & 9 & 7 & 5 & 1 & 6 & 8
    \end{pmatrix} \\ \\
    \beta = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
    10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1
    \end{pmatrix}
    \end{align*}
    Encuentra las factorizaciones completas de $\alpha, \beta, \alpha\beta, \beta\alpha$ y $\beta^{-1}$.

Más adelante…

Entonces ya sabemos que existe una factorización única para cada permutación. La usaremos para definir el concepto de estructura cíclica en la siguiente entrada.

Entradas relacionadas

Álgebra Moderna I: Permutaciones disjuntas

Introducción

Repasemos un poco el último ejemplo de la entrada anterior. En $S_5$ teníamos la composición $(1 \; 2 \; 3 \; 4)(2 \; 4 \; 5)$ y fijándonos en qué ocurre con cada elemento, concluimos que esta composición es igual a $(1 \; 2)(3 \; 4 \; 5)$. Entonces obtuvimos dos composiciones distintas para escribir a esa permutación. En el dibujo, es más claro que en la primera los dos ciclos se están entrelazando entonces es más difícil entender qué es lo que hace la permutación. Pero cuando vemos la representación de $(1 \; 2)(3 \; 4 \; 5)$ es más fácil entender qué es lo que está haciendo nuestra permutación. Así, es más conveniente trabajar con la segunda notación.

La representación de $(1 \; 2 \; 3 \; 4)(2 \; 4 \; 5) = (1 \; 2)(3 \; 4 \; 5)$

A simple vista podemos observar que $(1 \; 2 \; 3 \; 4)$ y $(2 \; 4 \; 5)$ comparten el 2, pero $(1 \; 2)$ y $(3 \; 4 \; 5)$ no comparten ningún elemento. En este caso, se dice que $(1 \; 2)$ y $(3 \; 4 \; 5)$ son ciclos disjuntos. Más aún, ¿será que cualquier permutación se puede descomponer en ciclos disjuntos? la respuesta es que , esto lo demostraremos también en esta entrada.

Definición de permutaciones disjuntas

Antes de definir lo que significa que dos permutaciones sean disjuntas, nos gustaría recordar la última observación de la entrada anterior.
Observación. Si $n \geq 3$, entonces $S_n$ no es abeliano.
Esto nos sirve para establecer que, en general, trabajaremos con grupos no abelianos.

Ahora sí definamos lo que son permutaciones disjuntas.
Definición. Sean $\alpha, \beta \in S_n$. Decimos que $\alpha$ y $\beta$ son disjuntas o ajenas si sop$\alpha \cap $sop$\beta = \emptyset$, es decir,

\begin{align*}
\text{Si }\alpha(i) \neq i &\Rightarrow \beta(i) = i \\
\text{Si }\beta(i) \neq i & \Rightarrow \alpha(i) = i
\end{align*}

Observación. Si $\alpha$ y $\beta$ son disjuntas, pueden fijar a un mismo elemento pero no mover a un mismo elemento.

En particular, si tenemos dos ciclos de longitud mayor a uno, podemos obtener la siguiente equivalencia.
Observación. Sean $\alpha = (i_1 \dots i_r)$ y $\beta = (j_1 \dots j_t)$ con $r,t > 1$. Entonces $\alpha$ y $\beta$ son disjuntas si y sólo si $\{i_1, \dots, i_r\} \cap \{j_1, \dots, j_t\} = \emptyset$

Ejemplos.

  • $(1 \; 2 \; 3 \; 4)$ y $(2 \; 4 \; 5)$ no son disjuntas.
  • $(1 \; 2)$ y $(3 \; 4 \; 5)$ son disjuntas.

Las permutaciones disjuntas conmutan

Lema. Sean $\alpha, \beta \in S_n$. Si $\alpha$ y $\beta$ son disjuntas, entonces conmutan.

P.D. $\alpha \beta = \beta \alpha$.
Sea $i \in \{1, \dots, n\}$.

Caso 1. Cuando $\alpha(i) = i$, $\beta(i) = i$. Ambas fijan al mismo elemento, esto es posible en permutaciones disjuntas. Entonces, al componer, no importará que permutación se aplique primero.
\begin{align*}
\alpha\beta(i) = \alpha(i) = i = \beta(i) = \beta\alpha(i).
\end{align*}

Caso 2. Cuando $\alpha(i) = i$, $\beta(i) \neq i$.
Si componemos, obtenemos $\beta\alpha(i) = \beta(i)$.
Como $\beta$ es inyectiva y $\beta(i) \neq i$, entonces $\beta(\beta(i)) \neq \beta(i)$. Así $\beta$ mueve a $\beta(i)$ y como $\alpha$ y $\beta$ son disjuntas $\alpha$ fija a $\beta(i)$. Entonces
\begin{align*}
\alpha\beta(i) = \alpha(\beta(i)) = \beta(i)
\end{align*}
Por lo tanto $\beta\alpha(i) = \alpha\beta(i)$.

Caso 3. Cuando $\alpha(i) \neq i$, $\beta(i) = i$.
Este es análogo al caso 2.

El caso $\alpha(i) \neq i$, $\beta(i) \neq i$ no se da pues $\alpha$ y $\beta$ son disjuntas.
Por lo tanto $\alpha\beta = \beta\alpha$.

$\square$

Toda permutación se puede descomponer en ciclos disjuntos

Comencemos como un ejemplo. Consideremos a la permutación $\alpha \in S_9$

\begin{align*}
\alpha = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
3 & 4 & 1 & 7 & 8 & 6 & 2 & 9 & 5
\end{pmatrix}.
\end{align*}

  • El 1 va al 3 y el 3 regresa al 1, entonces tenemos una transposición $(1 \; 3)$.
  • Luego, observemos que el 2 va al 4, el 4 al 7 y el 7 al 4. Así tenemos un $3-$ciclo, $(2 \; 4 \; 7)$.
  • De los números que no han aparecido hasta ahora, podemos tomar el 5, este va al 8, el 8 al 9 y el 9 regresa al 5. Entonces tenemos otro $3-$ciclo $(5 \; 8 \; 9)$.
  • Por último, el 6 queda fijo.

Esto se puede dibujar de la siguiente manera:

Representación gráfica de $\alpha$.

Pero también se puede escribir algebraicamente como:

\begin{align*}
\alpha = (1 \; 3)\,(2 \; 4 \; 7)\,(5 \; 8 \; 9)\,(6).
\end{align*}

Ahora veremos que cualquier permutación se puede descomponer en un producto de ciclos disjuntos.

Teorema. Toda permutación en $S_n$ es un ciclo o un producto de ciclos disjuntos.

Demostración.
Sea $\alpha \in S_n$. Lo demostraremos con inducción sobre sop$\alpha = k$.

Caso Base. Supongamos que $k = 0$, entonces sop$\alpha = \emptyset$. Entonces $\alpha = $id$= (1)$ que es un $1-$ciclo.

Supongamos ahora que $k > 0$.
Hipótesis de Inducción. Supongamos que si $\beta \in S_n$ y $\#$sop$\beta < k$, entonces $\beta$ es un ciclo o un producto de ciclos disjuntos.
Como $k = \#$sop$(\alpha) > 0$, existe $i \in $ sop$\alpha$. Consideremos
\begin{align*}
i , \alpha(i), \alpha^2(i), \dots
\end{align*}

Sabemos que esta lista tienen elementos repetidos ya que consiste de números en $\{1,2,\dots,n\}$. Sea
\begin{align*}
r = \text{mín}\{t \in \n | i, \alpha(i), \dots, \alpha^t(i) \text{ tiene repeticiones}\}.
\end{align*}

Por la elección de $r$
\begin{align*}
\alpha^r(i) &= \alpha^s(i) & \text{para algún } 0 \leq s < r \\
\Rightarrow \, \alpha^{r-s}(i) &= i & \text{con } 0 < r-s \leq r
\end{align*}

Por lo tanto, $i, \alpha(i), \dots, \alpha^{r-s}(i)$ tiene repeticiones con $r-s \leq r$.

Para no contradecir la elección de $r$ tenemos que $r-s = r$. Así $s = 0$ y $\alpha^r(i) = \alpha^0(i) = i$.

Obs. Observemos que $j \in \{i, \alpha(i), \alpha^{r-1}(i)\}$ si y sólo si $\alpha(j) \in \{i, \alpha(i), \alpha^{r-1}(i)\}$. Demostraremos esto.

$|\Rightarrow)$ Supongamos que existe $0 \leq t < r$ tal que $j = \alpha^{t}(i)$, entonces $\alpha(j) = \alpha^{t+1}(i)$ donde $0 < t+1 \leq r$.

Pero en el caso donde $t+1 = r$, $\alpha(j) = \alpha^r(i) = i$.
Así, $\alpha(j) \in \{i, \alpha(i), \dots, \alpha^{r-1}(i)\}$

$\Leftarrow)$ Supongamos que existe $0\leq t < r$ tal que $\alpha(j) = \alpha^t(i)$.

Entonces $j = \alpha^{t-1}(i)$ para $-1 \leq t-1 < r$.

Pero en el caso cuado $-1 = t-1$, $j = \alpha^{-1} = \alpha^{-1}(i) = \alpha^{-1}(\alpha^r(i)) = \alpha^{r-1}(i)$.
Así $j \in \{i, \alpha(i), \dots, \alpha^{r-1}(i)\}$.

Ahora, sea $\sigma = (i \; \alpha(i) \; \dots \; \alpha^{r-1})$. Entonces $\sigma^{-1} = (\alpha^{r-1}(i) \; \dots \; \alpha(i) \; i)$.

Sea $\alpha’ = \sigma^{-1}\alpha$. Veamos la regla de correspondencia:
Si $j \in \{i, \alpha(i), \dots, \alpha^{r-1}(i)\}$ entonces existe $0 \leq t < r$ tal que $j = \alpha^t(i)$.
\begin{align*}
\alpha'(j) &= \sigma^{-1}\alpha(j) \\
&= \sigma^{-1}\alpha(\alpha^t(i)) \\
&= \sigma^{-1}(\alpha^{t+1}(i)) \\
&= \alpha^t(i) = j
\end{align*}

Si $j \not\in \{i, \alpha(i), \dots, \alpha^{r-1}(i)\}$, por la observación, $\alpha(j) \not\in \{i, \alpha(i), \dots, \alpha^{r-1}(i)\}$, entonces
\begin{align*}
\alpha'(j) = \sigma^{-1}\alpha(j) = \sigma^{-1}(\alpha(j)) = \alpha(j)
\end{align*}
Así sop$\alpha’ = $ sop$\alpha \setminus$ sop$\sigma$.

Entonces $\alpha’$ y $\sigma$ son disjuntos y $\#$sop$\alpha’ < \#$sop$\alpha = k$.
Por la H.I. $\alpha’$ es un ciclo o un producto de ciclos disjuntos.

Concluimos que $\alpha = \sigma\alpha’$ es un producto de ciclos disjuntos.

$\square$

Ejemplo.
Sea $\alpha \in S_{10}$ como sigue

\begin{align*}
\alpha = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
4 & 1 & 7 & 9 & 6 & 8 & 3 & 5 & 2 & 10
\end{pmatrix}
\end{align*}

Veamos qué sucede con el $1 \in $ sop$\alpha$. Le aplicamos $\alpha$ varias veces para formar el primer el ciclo.

\begin{align*}
1, \alpha(1) = 4, \alpha^2(1) = 9, \alpha^3(1) = 2, \alpha^4(1) = 1
\end{align*}

Entonces, nombremos $\sigma$ a ese $4-$ciclo, $\sigma = (1 \; 4 \; 9 \; 2)$.

Ahora, tomemos un elemento que no esté en $\sigma$, digamos $3$. De nuevo, aplicamos $\alpha$ varias veces para descubrir el ciclo al que pertenece.
\begin{align*}
3, \alpha(3) = 7, \alpha^2(3)=3
\end{align*}

Tenemos así una transposición $(3\; 7).$

Volvemos a tomar un número que no aparezca hasta ahora, digamos $5$. Aplicando $\alpha$ varias veces, podemos descubrir el ciclo,
\begin{align*}
5, \alpha(5) = 6, \alpha^2(5) = 8, \alpha^3(5) = 5.
\end{align*}

Ponemos ahora un $1$-ciclo por cada elemento que sea fijado por $\alpha$, en este caso sólo para el $10$.

Así, nuestra permutación quedaría como
\begin{align*}
\alpha = (1 \; 4 \; 9 \; 2 ) (3 \; 7)( 5 \; 6 \; 8)(10).
\end{align*}

$\square$

Tarea moral

  1. Demuestra la observación: Si $n \geq 3$, entonces $S_n$ no es abeliano.
  2. Encuentra dos permutaciones disjuntas $\alpha$ y $\beta$. Encuentra $\beta\alpha$ y $\alpha\beta$ ¿qué observas al comparar $\beta\alpha$? Intenta con otro ejemplo de dos permutaciones disjuntas $\alpha$ y $\beta$ y analiza lo que ocurre.
  3. Sean $\alpha$ y $\beta$ dos permutaciones que conmutan ¿podemos concluir entonces $\alpha$ y $\beta$ son disjuntas?
  4. Considera el siguiente elemento de $S_{11}$
    \begin{align*}
    \alpha = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\
    5 & 8 & 2 & 6 & 4 & 1 & 3 & 7 & 9 & 11 & 10
    \end{pmatrix}
    \end{align*}
    Encuentra una factorización en ciclos disjuntos de $\alpha$, y de $\alpha^{-1}$.

Más adelante…

Ya conocemos qué son las permutaciones disjuntas y que cualquier permutación se puede ver como multiplicación de ciclos disjuntos. También, puede que hayas notado que comenzamos a escribir los $1-$ciclos de los elementos que se quedan fijos en las permutaciones. Esto nos encamina al tema principal de la siguiente entrada, la factorización completa, que no es más que la descomposición de una permutación en ciclos disjuntos incluyendo los $1-$ciclos.

Entradas relacionadas

Álgebra Moderna I: Permutaciones y Grupo Simétrico

Introducción

La Unidad 2 empieza con algunas definiciones nuevas. Veremos un ejemplo específico de grupo, primero definiremos qué es una permutación y luego, el conjunto de todas las permutaciones, al que llamaremos grupo simétrico junto con la composición. Este grupo es importante porque más adelante descubriremos que los grupos se pueden visualizar como subgrupos de grupos de permutaciones.

Primeras definiciones

Definición. Una permutación de un conjunto $X$ es una función biyectiva de $X$ en $X$.

Notación. Denotaremos por $S_X$ al conjunto

\begin{align*}
S_X = \{\sigma: X \to X | \sigma \text{ es biyectiva}\}
\end{align*}

Si $X = \{1,…,n\}$, $S_X$ se denota por $S_n$. Si tomamos $\alpha, \beta \in S_X$ la composición de $\alpha$ seguida de $\beta$ se denota por $\beta\alpha$.

Observación 1. $S_X$ con la composición es un grupo, se llama el Grupo Simétrico.

Observación 2. $|S_n| = n!$

Definición. Sea $\alpha \in S_n$, $i \in \{1,2,…,n\}$.

Decimos que $\alpha$ mueve a $i$ si $\alpha(i) \neq i$, y que $\alpha$ fija a $i$ si $\alpha(i) = i$. El soporte de $\alpha$ es

\begin{align*}
\text{sop }\alpha = \{i \in \{1,\dots, n\}: \alpha(i) \neq i\}.
\end{align*}

Ejemplo

Sea $\alpha \in S_{10}$, definida como

\begin{align*}
\alpha = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\
8 & 3 & 1 & 7 & 2 & 6 & 4 & 5 & 9 & 10 \end{pmatrix}
\end{align*}

La matriz es una manera de representar una permutación, la fila de arriba son todos los elementos de $X= \{1,2,3,4,5,6,7,8,9,10\}$ y la fila de abajo está formada por las imágenes bajo $\alpha$ de cada elemento de la fila de arriba. Es decir, la matriz de $\alpha$ se puede leer como: «$\alpha$ manda al $1$ al $8$», «el $ 2 $ lo manda al $3$», etc. Entonces tenemos que, $\alpha$ mueve a $1,2,3,4,5,7,8$ y fija al $6,9,10$. Así

\begin{align*}
\text{sop } \alpha = \{1,2, 3, 4, 5, 7, 8\}.
\end{align*}

Definición de ciclo

Definición. Sea $\alpha \in S_n$, $r\in\z$, $r>1$. Decimos que $\alpha$ es un ciclo de longitud $r$ o un $r$-ciclo si existen $i_1, \dots, i_r \in \{1, \dots, n\}$ distintos tales que $\text{sop }\alpha = \{i_1, \dots, i_r\}$ y

\begin{align*}
\alpha(i_t) = \begin{cases}
i_{t+1} & \text{si } t \in \{1, \dots, r-1\} \\
i_1 & \text{si } t = r
\end{cases}
\end{align*}

Figura para ilustrar la definición de un ciclo.

Diremos que la permutación $\text{id}\in S_n$ es un ciclo de longitud $1$ o un $1$-ciclo. Los ciclos de longitud dos se llaman transposiciones.

Las transposiciones son muy importantes porque, como veremos más adelante, nos permitirán describir a las demás permutaciones.

Notación.

  • Un $r$-ciclo $\alpha$, tal que cada $i_j$ va a $i_{j+1}$ para cada $j \in \{1,…,r-1\}$ y $i_r$ regresa a $i_1$ se denota como $\alpha = (i_1\; i_2 \; \dots \; i_r)$.
  • Además, denotamos como $r = \text{long } \alpha$ a la longitud de $\alpha$.

Ejemplos

  1. $\alpha \in S_8$ con $\alpha = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 4 & 3 & 5 & 8 & 2 & 7 & 6 \end{pmatrix}$.

\begin{align*}
\alpha &= (2 \; 4 \; 5 \; 8 \; 6) = (4 \; 5 \; 8 \; 6 \; 2) \\
& = (5 \; 8 \; 6 \; 2 \; 4) = (8 \; 6 \; 2 \; 4 \; 5) \\
& = (6 \; 2 \; 4 \; 5 \; 8)
\end{align*}

Representación de $\alpha$.

En este caso, $\alpha$ es un $5-$ciclo y $\text{long }\alpha = 5$.
Observemos que el ciclo se puede comenzar a escribir con cualquier elemento de su soporte, siempre y cuando se cumpla la regla de correspondencia establecida.

2. Ahora, consideremos $\beta \in S_8$ como

Representación de $\beta$.

\begin{align*}
\beta =\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 2 & 5 & 4 & 3 & 6 & 7 & 8\end{pmatrix}
\end{align*}
entonces podemos decir que $\beta = (3 \; 5)$, porque a los otros elementos los deja fijos.

Si componemos $\beta$ con el $\alpha$ del ejemplo anterior obtenemos:

\begin{align*}
\alpha\beta &= (2 \; 4 \; 5 \; 8 \; 6) (3 \; 5) = (2 \; 4 \; 5 \; 3 \; 8 \; 6).
\end{align*}

Para verificar qué ésta es efectivamente la composición de $\beta$ seguida de $\alpha$, tenemos que observar a dónde manda a cada elemento:

  • Comenzamos con el $2$ (esto es arbitrario, se puede comenzar con el número que sea), observamos que $\beta$ lo deja fijo, entonces nos fijamos a dónde lo manda $\alpha$, en este caso, el $2$ es mandado al $4$. Así, $\alpha\beta$ manda al $2$ en el $4$.
  • Repetimos el proceso con el $4$, $\beta$ lo deja fijo y $\alpha$ lo manda al $5$. Así, $\alpha\beta$ manda al $4$ en el $5$.
  • Ahora con el $5$, $\beta$ manda al $5$ en $3$, entonces ahora vemos a dónde manda $\alpha$ al $3$, en este caso lo deja fijo. Así, $\alpha\beta$ manda al $5$ en el $3$.
  • Entonces ahora tenemos que observar a dónde es mandado el $3$ después de la composición. Primero, $\beta$ manda el $3$ al $5$ y $\alpha$ manda el $5$ al $8$, por lo tanto $\alpha\beta$ manda el $3$ al $8$.
  • Así continuamos con todos los elementos que aparezcan en la composición hasta terminar.

    Ahora, veamos qué sucede con $\beta\alpha$. El proceso es análogo:
    \begin{align*}
    \beta\alpha &= (3 \; 5) (2 \; 4 \; 5 \; 8 \; 6) = (3 \; 5 \; 8 \; 6 \; 2 \; 4)
    \end{align*}
    Por lo tanto $\alpha\beta \neq \beta\alpha$.

3. En $S_5$. Podemos considerar la siguiente permutación: $(1 \; 2 \; 3 \; 4)(2 \; 4 \; 5)$. A esta permutación la podemos simplificar usando el mismo procedimiento que en el ejemplo 2.

Observamos a dónde lleva cada uno de sus elementos:

  • Comencemos con el 2, la primera parte de la permutación, lleva el 2 al 4 y, la segunda parte lleva el 4 al 1.
  • Ahora veamos a dónde va el 1. La primera parte lo deja fijo y la segunda lo lleva al 2. Entonces obtenemos una permutación $(1\;2)$. Pero todavía falta ver el resto de elementos.
  • Ahora, veamos qué sucede con el 3. La primera parte lo deja fijo y la segunda lo manda al 4.
  • La primera parte de nuestra permutación manda el 4 al 5 y, el 5 se queda fijo.
  • Por último, el 5 es mandado al 2 por la primera parte de la permutación y, la segunda parte manda al 2 en el 3. Por lo tanto, el 5 regresa al 3. Esto se puede escribir como:

\begin{align*}
(1 \; 2 \; 3 \; 4)(2 \; 4 \; 5) = (1 \; 2) (3 \; 4 \; 5)
\end{align*}

Es decir:

Representación de $(1 \; 2 \; 3 \; 4)(2 \; 4 \; 5) = (1 \; 2) (3 \; 4 \; 5)$.

Este ejemplo nos permite intuir que en ocasiones las permutaciones se pueden simplificar.

Observación. Si $n \geq 3$, entonces $S_n$ no es abeliano.

Tarea moral

  1. Demostrar la observación 1: $S_X$ con la composición es un grupo, se llama el Grupo Simétrico.
  2. Sea $X$ un conjunto infinito, $H$ la colección de permutaciones de $S_X$ que mueven sólo un número finito de elementos y $K$ la colección de permutaciones que mueven a lo más $50$ elementos. ¿Son $H$ y $K$ subgrupos de $S_X$?
  3. Considera los siguientes elementos de $S_{10}$
    \begin{align*} \alpha &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
    10 & 4 & 3 & 2 & 9 & 7 & 5 & 1 & 6 & 8 \end{pmatrix} \\\\
    \beta &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
    10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{pmatrix} \end{align*}
    Encuentra $\alpha \beta, \beta \alpha, \alpha^{-1}$ y $\beta^{-1}$.
  4. Sea $a \in S_n, $ con $n > 2$. Si $\alpha$ conmuta con toda permutación de $S_n$ ¿puedes decir quién debe ser $\alpha$?

Más adelante…

Por el momento continuaremos hablando de las permutaciones. El último ejemplo visto nos da la noción de permutaciones disjuntas, este tema es el que profundizaremos en la siguiente entrada, pero por el momento ¿puedes imaginarte de qué se trata?

Entradas relacionadas