Archivo de la etiqueta: permutaciones disjuntas

Álgebra Moderna I: Permutaciones disjuntas

Por Cecilia del Carmen Villatoro Ramos

Deja un comentario

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 sí, 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)$ sí 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$.

$\blacksquare$

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.

$\blacksquare$

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 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*}

$\blacksquare$

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