permutacion archivos - El blog de Leo

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

Consideremos $α \in S_{7}$ como $α = (1 3 2) (6 4)$ , esta permutación fija a $5$ y a $7$ . Entonces también podemos escribirla como $α = (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 $α = (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 $α$ 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 $α$ 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 $α \in S_{n}$ . Una factorización completa de $α$ es una descomposición de $α$ en ciclos disjuntos con un $1 -$ ciclo por cada elemento fijado por $α$ .

Ejemplos.

Sea $α \in S_{8}$ como
$\begin{array}{r} α = (\begin{array}{c} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 2 & 1 & 5 & 7 & 6 & 4 & 8 \end{array}) \end{array}$

Entonces $α = (1 3) (4 5 7)$ es una factorización de $α$ en ciclos distintos pero no es una factorización completa de $α$ . Por otro lado $α = (1 3) (4 5 7) (2) (6) (8)$ sí es una factorización completa de $α$ .
Sea $β$ dada por $\begin{array}{r} β = (2 4 6 8) (1 3 5) (7) . \end{array}$

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

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

Recordemos la pregunta de la introducción ¿qué tienen en común todas las formas de describir a $α$ 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.

Supongamos por reducción al absurdo que existe $α \in S_{n}$ con dos factorizaciones completas distintas, no sólo por el orden de sus factores. Dado que en una factorización completa los $1 -$ ciclos corresponden a los elementos que quedan fijos, éstos coinciden en ambas factorizaciones. Igualando ambas factorizaciones y cancelando los $1 -$ ciclos y el resto de los factores comunes de ambas factorizaciones obtenemos $β_{1} \dots β_{r} = δ_{1} \dots δ_{s},$ con $r, s \in N^{+} .$ Notemos que $α = β_{1} \dots β_{r} = δ_{1} \dots δ_{s}$ .

Por la hipótesis de reducción al absurdo, alguno de los factores de la primera expresión de $α$ no aparece como factor en la segunda expresión de $α$ o viceversa. Sin pérdida de generalidad supongamos que $β_{1} \notin {γ_{1}, \dots, γ_{s}} .$

Sea $i \in {1, \dots, n}$ un elemento movido por $β_{1}$ , entonces, de acuerdo a lo que hemos estudiado, $β_{1}$ es de la forma $β_{1} = (i β_{1} (i) \dots β_{1}^{t - 1} (i)),$ con $t$ el menor natural positivo tal que $β_{1}^{t} (i) = i$ . Dado que $β_{1}, \dots, β_{r}$ son disjuntos, $α$ mueve a $i$ , y como $δ_{1}, \dots, δ_{s}$ también son disjuntos, exactamente un factor $δ_{1}, \dots, δ_{s}$ mueve a $i$ . Sin pérdida de generalidad supongamos que $δ_{1}$ mueve a $i$ , entonces $δ_{1}$ es de la forma $δ_{1} = (i δ_{1} (i) \dots δ_{1}^{k - 1} (i)),$ con $k$ el menor natural positivo tal que $δ_{1}^{k} (i) = i$ .

Pero, debido a que $β_{1}, \dots, β_{r}$ son disjuntos, conmutan, y entonces $α^{j} (i) = (β_{1} \dots β_{t})^{j} (i) = β_{1}^{j} \dots β_{t}^{j} (i) = β_{1}^{j} (i)$ para toda $j \in N^{+}$ . Análogamente $α^{j} (i) = δ_{1}^{j} (i)$ para toda $j \in N^{+}$ . Concluimos con ello que $β_{1}^{j} (i) = δ_{1}^{j} (i)$ para toda $j \in N^{+}$ y en consecuencia $t = k$ y $β_{1} = δ_{1}$ , contradiciendo la elección de $β_{1}$ .

Así, toda factorización completa es única salvo por el orden de los factores.

Tarea moral

Considera el siguiente elemento de $S_{9}$
$\begin{array}{r} α = (\begin{array}{c} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 9 & 8 & 1 & 4 & 3 & 7 & 6 & 2 & 5 \end{array}) . \end{array}$
Encuentra la factorización completa de $α$ .
Sea $α \in S_{n}$ y $α = β_{1} \dots β_{t}$ una factorización completa de $α$ . Analiza qué ocurre con $\sum_{i = 1}^{t} long β_{i}$ .
Considera el ejercicio 3 de la entrada de permutaciones:
Sean $α, β \in S_{10}$ ,
$\begin{array}{r} α = (\begin{array}{c} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 10 & 4 & 3 & 2 & 9 & 7 & 5 & 1 & 6 & 8 \end{array}) \\ β = (\begin{array}{c} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{array}) . \end{array}$
Encuentra las factorizaciones completas de $α, β, α β, β α$ y $β^{- 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.

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

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{array}{r} S_{X} = {σ : X \to X | σ es biyectiva} . \end{array}$

Si $X = {1, \dots, n}$ , $S_{X}$ se denota por $S_{n}$ . Si tomamos $α, β \in S_{X}$ la composición de $α$ seguida de $β$ se denota por $β α$ .

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 $α \in S_{n}$ , $i \in {1, 2, \dots, n}$ .

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

$\begin{array}{r} sop α = {i \in {1, \dots, n} : α (i) \neq i} . \end{array}$

Ejemplo

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

$\begin{array}{r} α = (\begin{array}{c} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 8 & 3 & 1 & 7 & 2 & 6 & 4 & 5 & 9 & 10 \end{array}) . \end{array}$

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 $α$ de cada elemento de la fila de arriba. Es decir, la matriz de $α$ se puede leer como: « $α$ manda al $1$ al $8$ », «el $2$ lo manda al $3$ », etc. Entonces tenemos que, $α$ mueve a $1, 2, 3, 4, 5, 7, 8$ y fija al $6, 9, 10$ . Así

$\begin{array}{r} sop α = {1, 2, 3, 4, 5, 7, 8} . \end{array}$

Definición de ciclo

Definición. Sea $α \in S_{n}$ , $r \in Z$ , $r > 1$ . Decimos que $α$ es un ciclo de longitud $r$ o un $r$ -ciclo si existen $i_{1}, \dots, i_{r} \in {1, \dots, n}$ distintos tales que $sop α = {i_{1}, \dots, i_{r}}$ y

$\begin{array}{r} α (i_{t}) = {\begin{cases} i_{t + 1} & si t \in {1, \dots, r - 1} \\ i_{1} & si t = r \end{cases} \end{array}$

Figura para ilustrar la definición de un ciclo.

Diremos que la permutación $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 $α$ , tal que cada $i_{j}$ va a $i_{j + 1}$ para cada $j \in {1, \dots, r - 1}$ y $i_{r}$ regresa a $i_{1}$ se denota como $α = (i_{1} i_{2} \dots i_{r})$ .
Además, denotamos como $r = long α$ a la longitud de $α$ .

Ejemplos

$α \in S_{8}$ con $α = (\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 4 & 3 & 5 & 8 & 2 & 7 & 6 \end{matrix})$ .

$\begin{aligned} α & = (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{aligned}$

En este caso, $α$ es un $5 -$ ciclo y $long α = 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 $β \in S_{8}$ como

$\begin{array}{r} β = (\begin{array}{c} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 2 & 5 & 4 & 3 & 6 & 7 & 8 \end{array}), \end{array}$
entonces podemos decir que $β = (3 5)$ , porque a los otros elementos los deja fijos.

Si componemos $β$ con el $α$ del ejemplo anterior obtenemos:

$\begin{aligned} α β & = (2 4 5 8 6) (3 5) = (2 4 5 3 8 6) . \end{aligned}$

Para verificar qué ésta es efectivamente la composición de $β$ seguida de $α$ , 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 $β$ lo deja fijo, entonces nos fijamos a dónde lo manda $α$ , en este caso, el $2$ es mandado al $4$ . Así, $α β$ manda al $2$ en el $4$ .
Repetimos el proceso con el $4$ , $β$ lo deja fijo y $α$ lo manda al $5$ . Así, $α β$ manda al $4$ en el $5$ .
Ahora con el $5$ , $β$ manda al $5$ en $3$ , entonces ahora vemos a dónde manda $α$ al $3$ , en este caso lo deja fijo. Así, $α β$ 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, $β$ manda el $3$ al $5$ y $α$ manda el $5$ al $8$ , por lo tanto $α β$ manda el $3$ al $8$ .
Así continuamos con todos los elementos que aparezcan en la composición hasta terminar.

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

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{array}{r} (1 2 3 4) (2 4 5) = (1 2) (3 4 5) . \end{array}$

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

Demostrar la observación 1: $S_{X}$ con la composición es un grupo, se llama el Grupo Simétrico.
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}$ ?
Considera los siguientes elementos de $S_{10}$
$\begin{aligned} α & = (\begin{array}{c} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 10 & 4 & 3 & 2 & 9 & 7 & 5 & 1 & 6 & 8 \end{array}) \\ β & = (\begin{array}{c} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{array}) . \end{aligned}$
Encuentra $α β, β α, α^{- 1}$ y $β^{- 1}$ .
Sea $a \in S_{n},$ con $n > 2$ . Si $α$ conmuta con toda permutación de $S_{n}$ ¿puedes decir quién debe ser $α$ ?

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

Ir a Álgebra Moderna I.
Entrada anterior del curso: Palabras.
Siguiente entrada del curso: Permutaciones disjuntas.
Resto de cursos: Cursos.

El blog de Leo

Aprendiendo, creando y compartiendo matemáticas

Archivo de la etiqueta: permutacion

Álgebra Moderna I: Factorización Completa

Introducción

Definición de una factorización completa

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

Tarea moral

Más adelante…

Entradas relacionadas

Álgebra Moderna I: Permutaciones y Grupo Simétrico

Introducción

Primeras definiciones

Ejemplo

Definición de ciclo

Ejemplos

Tarea moral

Más adelante…

Entradas relacionadas