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.
- 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$. - 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.
- 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$.
- 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.
- 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$. - 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$.
$\blacksquare$
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.
$\blacksquare$
Tarea moral
- 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$. - 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$.
- 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
- Ir a Álgebra Moderna I.
- Entrada anterior del curso: Permutaciones disjuntas.
- Siguiente entrada del curso: Misma Estructura Cíclica, Permutación Conjugada y Polinomio de Vandermonde.
- Resto de cursos: Cursos.