Archivo de la etiqueta: factorización completa

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

Por Cecilia del Carmen Villatoro Ramos

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

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.

Se verá que toda permutación se descompone siempre como un producto de una cantidad par de intercambios, o siempre con una cantidad impar de intercambios. Para ello seguiremos el enfoque presentado en el libro de Herstein, al igual que en el libro Grupos I de Avella, Mendoza, Sáenz y Souto, y en el libro de Dummit mencionados en la bibliografía, en los que se introduce un polinomio en varias indeterminadas llamado el polinomio de Vandermonde.

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 α,βSn. Decimos que α y β tienen la misma estructura cíclica si su factorización completa tiene el mismo número de rciclos para toda rZ+.

Ejemplo.

En S9, tomemos α y β como sigue

α=(2479)(13)(56)(8)β=(24)(1589)(37)(6).

Claramente, α y β tienen la misma estructura cíclica, ya que ambas están formadas por un 4ciclo, dos transposiciones y un uno ciclo.

Permutación Conjugada

Definición. Sean α,βSn. Decimos que β es conjugada de α si existe γSn tal que β=γαγ1.

Ejemplo.

Tomemos γ=(123), entonces γ=(124) y α=(3568). Entonces podemos calcular a β como sigue,

γαγ1=(123)(3568)(132)=(1568)=β.

Así, β=(1568) es conjugada de (1568)=α.

Podemos observar que si consideramos la relación en Sn dada por αβ si y sólo si α es conjugada de β, es una relación de equivalencia. Aquí no lo demostraremos, pero queda como tarea moral. Aunque no es evidente en primera instancia, el hecho de que dos permutaciones sean conjugadas puede analizarse a partir de la estructura cíclica que tienen. En la tarea moral hay ejercicios relacionados con ello.

¿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 σ=(12345), 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 σ, en vez la lista 12345 tendremos ahora la lista 234,51. Entonces nos preguntamos, ¿cómo podemos llegar de la lista 12345 a la lista 23451 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 21345. 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 23145.
  3. Ahora, nos toca intercambiar 1 y 4. Así obtenemos 23415
  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 σ 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 (12), (13), (14) y (15). Debido a que escribimos la composición de permutaciones de derecha a izquierda, nuestra sigma quedaría de la siguiente manera:

σ=(12345)=(15)(14)(13)(12).

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.

Teorema. La siguiente igualdad de conjuntos se cumple,

Sn={τSn|τ es una transposición}.

Demostración.

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

(i1ir)=(i1ir)(i1i3)(i1i2).

Por lo tanto Sn={τSn|τ es una transposición}.

◻

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. Con el fin probar este resultado introduciremos un polinomio con distintas indeterminadas que permutaremos usando permutaciones, para lo cual consideraremos polinomios en varias indeterminadas, que serán permutadas por los elementos del grupo simétrico.

Definición. Sea P(x1,,xn) un polinomio en las indeterminadas x1,,xn con coeficientes enteros y αSn. El polinomio αP se define como

αP(x1,,xn)=P(xα(1),,xα(n)).

Ejemplo.

Consideremos el polinomio P(x1,x2,x3,x4,x5)=3x1x2+x3x52+x1x2x3x4x5 y α=(123)(45). Entonces

αP(x1,x2,x3,x4)=(123)(45)P(x1,x2,x3,x4)=3xα(1)xα(2)+xα(3)xα(5)2+xα(1)xα(2)xα(3)xα(4)xα(5)=3x2x3+x1x42+x2x3x1x5x4.

Definición. El polinomio de Vandermonde en las indeterminadas x1,,xn con coeficientes enteros es

V(x1,,xn)=1i<jn(xixj).

Dado αSn, el αpolinomio de Vandermonde es αP, es decir:

αV(x1,,xn)=1i<jn(xα(i)xα(j)).

Ejemplo.

V(x1,x2,x3,x4)=(x1x2)(x1x3)(x1x4)(x2x3)(x2x4)(x3x4).

Calculemos ahora (24)V(x1,x2,x3,x4). 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 (x1x2) cambiará al factor (x1x4). Así

(24)V(x1,x2,x3,x4)=(x1x4)(x1x3)(x1x2)(x4x3)(x4x2)(x3x2)=V(x1,x2,x3,x4).

Observación 1. Dado que cada factor del polinomio de Vandermonde se queda igual o cambia de signo, sólo pueden suceder dos cosas, αV=V ó αV=V para todo αSn, de acuerdo a si hay un número impar de cambios de signo o si hay un número par de cambio de signo.

Observación 2. Sea αSn. Tenemos que α(V)=αV.

Observación 3. Sean α,βSn. Tenemos que α(βV)=(αβ)V.

Demostración.

Sea αSn. Tenemos que:

α(βV(x1,,xn))=αV(xβ(1),,xβ(n))=V(xα(β(1)),,xα(β(n)))=V(x(αβ)(1),,x(αβ)(n))=(αβ)V(x1,,xn).

◻

Vandermonde y las Transposiciones

Veamos cuál es el efecto que tienen dos permutaciones sobre un polinomio. Primero analizaremos qué efecto tienen las transposiciones en el polinomio de Vandermonde. Seguiremos para ello la idea del libro de Dummit que se menciona en la bibliografía, veremos primero qué efecto tiene la transposición (12), y con ello entenderemos qué efecto tienen el resto de las transposiciones.

Lema. Sea τSn una transposición. Entonces τV=V.

Demostración.

Caso 1 τ=(12)

Al aplicar τ a V los factores xixj con i,j{1,2} se preservan, mientras que el factor x1x2 cambia a x2x1 provocando un cambio de signo. Por otro lado los factores x1xj con j{3,,n} y los factores x2xj con j{3,,n} no producen cambios de signo. Concluimos entonces que sólo un factor produce un cambio de signo y así (12)V=V.

Caso 2 τ(12), es decir τ=(1l) con l{3,,n}, o τ=(2l) con j{3,,n}, o bien τ=(kl) con k,j{1,2}.

Notemos que (2l)(12)(2l)=(1l) , para l{3,,n},(1l)(12)(1l)=(2l) , para l{3,,n},(1k)(2l)(12)(1k)(2l)=(kl) , para k,j{1,2}. Así, siempre existe αSn tal que α(12)α=τ.

Si αV=V, tenemos que τV=(α(12)α)V=(α((12)(αV)))=(α((12)V))=α(V)=αV=V.

Si αV=V, tenemos que τV=(α(12)α)V=(α((12)(αV)))=(α((12)(V))=αV=V.

◻

Teoremas importantes

Teorema. Sea rZ+, α=τ1τrSn, τ1,,τr transposiciones. Entonces

αV=(1)rV.

Demostración. Por inducción sobre r.

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

αV=τ1V=V=(1)1VLema

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 r1 transposiciones.

P.D. αV=(1)rV.

Desarrollando αV y usando el lema previo, obtenemos:

αV=(τ1τ2τr)V=((τ1τ2τr1)τr)VAgrupamos=(τ1τr1)(τrV)Observación 3=(τ1τr1)(V)Lema=(τ1τr1)V.Observación 2

Ahora, como τ2τr tiene r1 transposiciones, podemos aplicar la hipótesis de inducción y continuar con las igualdades.

(τ2τr)V=(1)r1V=(1)rV.

Así, demostramos lo deseado.

◻

Teorema. Sean r,tZ+, α=τ1τr=ρ1ρtSn, con τ1,,τr, ρ1,,ρt transposiciones. Entonces r y t tienen la misma paridad.

Demostración.
Por el teorema anterior, obtenemos:

αV=(ρ1ρt)V=(1)tV.

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

αV=(τ1τr)V=(1)rV.

Entonces (1)tV=(1)rV. Por lo tanto t y r tienen la misma paridad.

◻

Tarea moral

  1. Prueba que la relación en Sn dada por αβ si y sólo si β es conjugada de α, es una relación de equivalencia.
  2. Encuentra σασ1 en cada inciso:
    1. α=(235),σ=(1356).
    2. α=(5431),σ=(24578).
    3. α=(175423),σ=(12467).
  3. Sean α,σSn con σ=(i1i2ir)Sn un rciclo.
  4. Considera α=(194)(102853)(3568)(72)S10.
    1. Escribe a α 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 αV.
  5. ¿Qué forma cíclica tiene ασα1?
  6. ¿Cómo podemos describir a la permutación ασα1 a partir de cómo son α y σ sin necesidad de hacer paso a paso la composición? ¿puedes encontrar una fórmula que lo describa?

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 αpolinomio de Vandermonde? ¿Cómo se relaciona con la descomposición de la permutación α? ¿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

Por Cecilia del Carmen Villatoro Ramos

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

Introducción

Consideremos αS7 como α=(132)(64), esta permutación fija a 5 y a 7. Entonces también podemos escribirla como α=(132)(64)(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 α=(132)(7)(64)(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 αSn. Una factorización completa de α es una descomposición de α en ciclos disjuntos con un 1ciclo por cada elemento fijado por α.

Ejemplos.

  1. Sea αS8 como
    α=(1234567832157648)

    Entonces α=(13)(457) es una factorización de α en ciclos distintos pero no es una factorización completa de α. Por otro lado α=(13)(457)(2)(6)(8) sí es una factorización completa de α.
  2. Sea β dada por β=(2468)(135)(7).

    Esa es una factorización completa de βS8, pero no en S10, en S10 una factorización completa de de β sería
    β=(2468)(135)(7)(9)(10).

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 αSn con dos factorizaciones completas distintas, no sólo por el orden de sus factores. Dado que en una factorización completa los 1ciclos corresponden a los elementos que quedan fijos, éstos coinciden en ambas factorizaciones. Igualando ambas factorizaciones y cancelando los 1ciclos y el resto de los factores comunes de ambas factorizaciones obtenemos β1βr=δ1δs, con r,sN+. Notemos que α=β1βr=δ1δ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{γ1,,γs}.

Sea i{1,,n} un elemento movido por β1, entonces, de acuerdo a lo que hemos estudiado, β1 es de la forma β1=(iβ1(i)β1t1(i)), con t el menor natural positivo tal que β1t(i)=i. Dado que β1,,βr son disjuntos, α mueve a i, y como δ1,,δs también son disjuntos, exactamente un factor δ1,,δ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)δ1k1(i)), con k el menor natural positivo tal que δ1k(i)=i.

Pero, debido a que β1,,βr son disjuntos, conmutan, y entonces αj(i)=(β1βt)j(i)=β1jβtj(i)=β1j(i) para toda jN+. Análogamente αj(i)=δ1j(i) para toda jN+. Concluimos con ello que β1j(i)=δ1j(i) para toda jN+ 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

  1. Considera el siguiente elemento de S9
    α=(123456789981437625).
    Encuentra la factorización completa de α.
  2. Sea αSn y α=β1βt una factorización completa de α. Analiza qué ocurre con i=1tlong βi.
  3. Considera el ejercicio 3 de la entrada de permutaciones:
    Sean α,βS10,
    α=(1234567891010432975168)β=(1234567891010987654321).
    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