jueves, 3 de octubre de 2013

Ciclos (1) Grupo simétrico


Solemos considerar las permutaciones como las distintas ordenaciones de un conjunto. Existe otro punto de vista alternativo, que es muy fructífero, y es considerarlas como  aplicaciones biyectivas del conjunto en sí mismo. Así, la permutación S=(3,2,1,4) se puede considerar derivada de (1,2,3,4) (orden principal) mediante la aplicación S(1)=3, S(2)=2, S(3)=1 y S(4)=4. Así la interpretaremos aquí.

Como la naturaleza de los elementos no influye en la teoría, imaginaremos que se trabaja siempre sobre el conjunto {1,2,3,4,…,n} y que una permutación como S=(5,1,3,2,…) se interpreta: S(1)=5, S(2)=1, S(3)=3, S(4)=2,…La escribimos así, como un conjunto de imágenes, por comodidad de escritura, pero te la puedes imaginar con los orígenes sobre ellas formando una matriz de dos filas, con lo que cae cada imagen debajo del origen

Las permutaciones se pueden componer como todas las aplicaciones, usando una de ellas  y después la otra sobre las imágenes de la primera. No es fácil verlo en este caso, por lo que usaremos un ejemplo:
Sean G=(4,2,5,3,1) y H=(1,4,3,5,2), o escribiendo orígenes:

G:







H:








La composición H*G (escribiendo de derecha a izquierda) se formaría así (hay que estar atentos):

H*G(1)=H(G(1))=H(4)=5   H*G(2)=H(G(2))=H(2)=4   H*G(3)=H(G(3))=H(5)=2
H*G(4)=H(G(4))=H(3)=3   H*G(5)=H(G(5))=H(1)=1, con lo que resultaría
H*G=(5,4,2,3,1)  Como ves, no es nada intuitivo.

Es fácil demostrar que las n! permutaciones forman grupo para esta composición, siendo la identidad E=(1,2,3,4,…, n) y el inverso la permutación que convierte las imágenes en orígenes. A este grupo lo llamaremos Grupo simétrico para {1,2,3,…, n} y lo representaremos como Sn.

¿Te apetecería comprobar composiciones de permutaciones con hoja de cálculo? Te damos unas ideas:

Puedes escribir en filas distintas, una debajo de la otra, las dos permutaciones G y H (en la imagen, filas 12 y 16) y después la composición de ambas (fila 20), que es la única que contendrá fórmulas. El resto de la hoja sólo contiene datos.

Es muy interesante estudiar qué fórmula podemos implementar en la fila 20 de la imagen. Explicaremos la primera celda, B20, y después bastará extenderla al resto de la fila. La fórmula adecuada es:

=ÍNDICE($B16:$J16;1;B12)

La función ÍNDICE elige en una lista el elemento que presenta un número de orden. En este caso la lista es la permutación H. De ahí que hayamos usado el rango $B16:$J16. Después hay que indicar la fila del rango. Como solo hay una fila, hemos escrito un 1. El siguiente parámetro es el número de orden, y aquí va a residir el truco: Hemos de elegir en H el elemento que ocupe el lugar que indica G en la misma columna. Insistimos en que esto, al principio, no es fácil. Hemos escrito en la fórmula “B12”, que es la primera imagen de G, un 6, luego deberemos ir a H y buscar el sexto elemento, un 8, y por eso en la celda B20 aparece ese 8.

Como puede que te siga costando, te ofrecemos esta hoja en la dirección

http://hojamat.es/blog/compopermu.zip

Como el grupo simétrico opera sobre un conjunto finito (cardinal n!), la aplicación reiterada de una sustitución consigo misma (potencia de la permutación) llevará a la repetición de resultados, es decir, a que dos potencias distintas sean equivalentes:

Pm=Pn

Si suponemos, por ejemplo que m<n, entonces esa igualdad, si le aplicamos la permutación inversa para simplicar, se convertiría en

Pn-m=Pk=E (identidad)

Toda permutación, aplicada un número determinado de veces, se convierte en la identidad.

El número mínimo para el que eso ocurre recibe el nombre de orden de la permutación. En los ejemplos de arriba, el orden de G es 4, y el de H es 3. Compruébalo. Esta idea nos servirá en lo que sigue.

Una propuesta: En la imagen se ha compuesto G consigo misma, y el conjunto total parece haberse dividido en tres subconjuntos, cada uno de los cuales parece que va “a su aire”, sin mezclarse con los otros. ¿Cuáles son?


En otra entrada los relacionaremos con los ciclos. Te puedes adelantar en su estudio.