Estudiar sin beca

https://youtu.be/z0Katkl-nTY

Vigilados

viernes, 22 de marzo de 2013

Grupo simétrico

Esta entrada es en realidad un proyecto de entrada, pero lo publico para recibir opiniones con vistas a futuras modificaciones y también para olvidarme momentáneamente del tema, ya que hay varios asuntos que requieren mi atención y me mantendrán ocupado durante las próximas semanas.



El proyecto consiste en estudiar el grupo simétrico partiendo de cero y llegar a probar que el grupo alternado es simple para $ n \geq 5 $

Aunque esta  entrada contiene elementos elaborados por mi, antes de comenzar, pondré unas direcciones donde encontrar información sobre el grupo simétrico, comenzando por un nivel relativamente elemental:
http://www.youtube.com/watch?v=5wRasv9ghic&list=PLxt0Hgnl0gCUwSDbJDLmSuw8YD28Ypx6o&index=3
Junto a este vídeo aparecen otros que lo continúan, dentro de un curso sobre teoría de grupos, de manera que se introducen los conceptos básicos sobre grupos simétricos.

De nivel más avanzado son los siguientes:
http://www.youtube.com/watch?v=v2wofSgpm4g
http://www.youtube.com/watch?v=hjFXbq6ktK8
http://www.youtube.com/watch?v=AW_11TB2BIY
http://www.youtube.com/watch?v=O2HO9POW32I
http://www.youtube.com/watch?NR=1&v=yBPp5swknW8&feature=endscreen
http://www.youtube.com/watch?v=lcu30Ku-W_o
http://alexmoqui.wordpress.com/2011/12/09/grupo-de-automorfismos-del-grupo-simetrico-en-6-letras/

Junto a éstos aparecerán algunos más, todos del blog de Alex Moretó
http://www.youtube.com/user/alexmoqui/videos?view=0
http://alexmoqui.wordpress.com/
Con todo esto podemos ir adquiriendo base teórica sobre el grupo simétrico, lo cual significa aumentar nuestros conocimientos sobre teoría de grupos.


A partir de aquí retomamos el cuerpo principal de esta entrada. Al final aparecen más direcciones de internet  con información sobre el grupo simétrico.

Un esquema de lo que me gustaría hacer en esta entrada es el siguiente:

PARTE I
1) Definición de permutación. Grupo $S_n$
2) Notaciones para representar permutaciones. El "lío" de la composición de permutaciones.
3) Ciclo de longitud n. Notación para ciclos.Maneras diferentes de representar el mismo ciclo.
4)  El orden de un ciclo de longitud n.
5) Ciclos disjuntos.  Los ciclos disjuntos conmutan.  Representación de cualquier permutación mediante ciclos  disjuntos
6)  El orden de una permutación es el mínimo común múltiplo de las longitudes de los ciclos disjuntos en que se descompone.
7)  Definición de trasposición.
8) Toda permutación es producto de trasposiciones, aunque esa descomposición no es única.
9) Inversiones de una permutación. Número total de inversiones de una permutación.
10) El número total de inversiones de una trasposición es impar.
11) Comparación entre el número total de inversiones de una permutación y del producto de dicha permutación por una trasposición
12) Al descomponer una permutación en producto de trasposiciones, de cualquier manera posible, el número de transposiciones siempre tiene la misma paridad, que coincide con la paridad del número total de inversiones de la permutación
13) Paridad de una permutación. Permutaciones pares e impares.El grupo alternado.
14) Método práctico para descomponer permutaciones en producto de trasposiciones.

PARTE II:
CONCEPTOS Y RESULTADOS BÁSICOS DE TEORÍA DE GRUPOS.
Aquí tengo que decidir qué poner para incluir todo lo relevante para el tema y que no sea excesivamente largo y farragoso.


PARTE III
1) $A_n$ con $n\geq 5$ está generado por los ciclos de longitud 3
2) Si $A_n$ con $n\geq 5$ posee un subgrupo normal que contiene un 3-ciclo, entonces dicho subgrupo
    coincide con $A_n$
3) El lema anterior vale para n=3 y para n=4
4) $A_n$ ($n \geq 5$) es grupo simple



Los "puntos críticos"  en este este esquema son:
PARTE I:  11)  y 12)
PARTE II   Tengo que seleccionar qué conceptos y resultados de teoría de grupos incluir, esa es la dificultad, hacer una elección adecuada, que no sea excesivamente larga y que sea relevante para la
PARTE III
Para mí es la Parte III desconocida  casi en su totalidad.

Por tanto en un primer momento trataré la parte I, pero no en su totalidad, sino sólo los puntos más difíciles, porque no tengo tiempo.
Antes, sin embargo quisiera recoger el comentario que se puede ver en http://rinconmatematico.com/foros/index.php?topic=65819.msg265540#msg265540

En la dirección que acabo de escribir se señala que la opinión de que la teoría de acción de grupo sobre conjunto es esencial para la demostración de que se puede asignar paridad a las permutaciones NO es correcta. Próximamente modificaré en ese sentido todo lo que sigue.

Esta discusión trata de que la prueba de la existencia del grupo alternado, en concreto de que podemos definir la paridad de una permutación como la paridad del número de trasposiciones que  intervienen en cualquier descomposición de la permutación dada en producto de trasposiciones.
Para demostrar tal cosa he visto en diferentes libros y archivos de internet que se usa la teoría de acción de un grupo sobre un conjunto.
Entonces he buscado pruebas alternativas que no usaran tal noción y he encontrado varias pruebas que usan el concepto de número de inversiones de una permutación o el polinomio $ P(x_1 , x_2 , ... , x_n ) = {\displaystyle\prod_{i<j}^{}}_{1\leq i \leq n}{(x_i - x_j )} $
Pero a mí me parece que son formas disimuladas de introducir acciones de grupos sobre conjuntos, aunque sin dar la teoría general, sino desarrollándola en casos concretos.
En el caso de las pruebas basadas en el número de inversiones de una permutación estamos hablando de la acción del grupo simétrico $ S_n  $ sobre el conjunto de números naturales {1,2,...,n}
En el caso de usar el polinomio arriba mencionado, se trata de la acción del grupo $ S_n  $ sobre el conjunto de polinomios antisimétricos en las n variables anteriormente citadas.

Antes de ver las secciones propiamente difíciles tengo que comentar el "lío" de la composición de permutaciones: ¿Cómo interpretamos $ \alpha \circ \beta $  En Análisis significa hallar la imagen de un elemento arbitrario mediante $\beta$ y luego hallar la imagen del elemento resultante mediante $\alpha$. Es decir, operamos de derecha a izauierda. Eso está bien y hace más cómodas las "frases" con símbolos y por ende las demostraciones. Sin embargo en el contexto de teoría de grupos entendemos una expresión $a \circ b \circ c $ como operar de izquierda a derecha, partimos de a lo operamos con b y el resultado lo operamos con c.
Como este modo de operar es más cómodo en teoría de grupos, para resolver la contradicción que se presenta, pues las permutaciones son biyecciones entre elementos de un conjunto y deberían operar de derecha a izquierda como funciones que se componen que son, defino un producto o multiplicación entre permutaciones, que denoto simplemente por yuxtaposición, así:
$ \alpha \beta = \beta \circ \alpha $ de manera que opero de izquierda a derecha igual que si multiplico dos matrices, por ejemplo.

 Ahora pasamos a comentar algunos de los puntos "críticos"

11) Comparación entre el número total de inversiones de una permutación y del producto de dicha permutación por una trasposición
Sea  $ \sigma \in{S_n} $. Supongamos que esta permutación contiene p inversiones, es decir p parejas de elementos marcados con los rótulos $ \{1,2,3,...,n-1,n \} $. Entonces contiene
 $$ C^2 _n   - p = \displaystyle\frac{n (n-1)}{2}  - p $$  parejas de elementos que están en sucesión (o sea, que no forman inversión)
Vamos a ver la relación de este número p con el número de inversiones de la permutación  $ \sigma \tau $ siendo $\tau$ una trasposición.
Esto significa que primero hago la permutación y después la trasposición ($ \tau \circ \sigma $ )
Vamos a representar la permutación $\sigma$ de la siguiente manera:
$ \sigma \equiv \begin{bmatrix} 1 & 2 & \ldots & i & {i+1} & \ldots & j-1 & j& \ldots & {n-1} & n \\ t_1 &t_2 & \ldots & t_i & t_{i+1} & \ldots & t_{j-1} & t_j & \ldots & t_{n-1} & t_n \\ \end{bmatrix} $

Si la trasposición $ \tau $ es la que consiste en intercambiar $ t_i $ con $ t_j $ es decir $ \tau =(t_i , t_j ) $ y si en $ \sigma $ entre ambos elementos hay k, entonces el efecto que obtengo lo puedo pensar como si trasladara $ t_j $ k lugares a la izquierda,hasta llegar a 

 $  \begin{bmatrix} 1 & 2 & \ldots & i & {i+1}& i+2 & \ldots & j-1 & j& j+1&\ldots & {n-1} & n \\ t_1 &t_2 & \ldots & t_i & t_ j & t_{i+1} & \ldots & t_{j-2} & t_{j-1} & t_{j+1} &\ldots & t_{n-1} & t_n \\ \end{bmatrix} $


Cada una de estas trasposiciones elementales que consisten en intercambiar dos elementos consecutivos provoca que haya una inversión más o una inversión menos respecto de la situación anterior. Es decir que hay un cambio en el número de inversiones. Por tanto, la paridad de $\sigma$ cambia una vez. Como hemos aplicado k de estas trasposiciones elementales, la paridad de $\sigma$ ha cambiado k veces.

Ahora practicamos una nueva trasposición elemental para intercambiar $ t_i$ con $ t_j$  quedando la situación así 
 $  \begin{bmatrix} 1 & 2 & \ldots & i & {i+1}& i+2 & \ldots & j-1 & j& j+1&\ldots & {n-1} & n \\ t_1 &t_2 & \ldots & t_j & t_ i & t_{i+1} & \ldots & t_{j-2} & t_{j-1} & t_{j+1} &\ldots & t_{n-1} & t_n \\ \end{bmatrix} $

Por último realizamos otras k  trasposiciones elementales para llevar $ t_i $ a la posición j, de manera que obtenemos:


$ \sigma  \tau \equiv \begin{bmatrix} 1 & 2 & \ldots & i & {i+1} & \ldots & j-1 & j& \ldots & {n-1} & n \\ t_1 &t_2 & \ldots & t_j & t_{i+1} & \ldots & t_{j-1} & t_i & \ldots & t_{n-1} & t_n \\ \end{bmatrix} $

En total hemos realizado 2k+1 trasposiciones elementales, lo cual significa que la paridad de $ \sigma $ ha cambiado 2k+1 veces, es decir que si $\sigma  $ era par, ahora $ \sigma \tau $ es impar y si $ \sigma $ era impar ahora $ \sigma \tau $ es par.


Hemos probado que al multiplicar una permutación por una trasposición se produce cambio de paridad.


Como complemento podemos añadir que en el razonamiento anterior $ k= j-i-1$ y por tanto $2k+1 = 2(j-i)-1$



12) Ahora supongamos $ \sigma = \tau_1  \tau_2 ... \tau_n  $ donde las $ \tau_i $ son trasposiciones
Sabemos que ésta es sólo una de las descomposiciones posibles de $ \sigma $ en producto de trasposiciones.
Sin embargo está claro que al aplicar sucesivamente las n trasposiciones llegamos a una permutación que tiene el mismo número de inversiones que $ \sigma $ ya que es la misma $ \sigma $ 
Como cada trasposición cambia la paridad de la permutación sobre la que se aplica y partimos de la identidad que tiene cero inversiones, o sea un número par de inversiones se tiene:

Si el número total de inversiones de $ \sigma $ es par, entonces n es par, para poder llegar, después de aplicar las n trasposiciones, a una permutación con un número par de de inversiones.

Si el número total de inversiones de $ \sigma $ es impar, entonces n es impar para poder llegar, después de aplicar las n trasposiciones, a una permutación con un número impar de inversiones.

En consecuencia la permutación $ \sigma $ es par o impar si y sólo si lo es el número n de trasposiciones $ \tau_i $ tales que $ \sigma = \tau_1  \tau_2 ... \tau_n  $ 

COMO QUERÍAMOS DEMOSTRAR

Recapitulamos:
Mi dificultad con la paridad de las permutaciones es la siguiente:

Hay varias formas de definir la paridad, me centro en dos:

Una de ellas es a partir del número de inversiones de la permutación y otra a partir del número de trasposiciones que intervienen en cualquier factorización de la permutación.

Esta segunda manera parece en principio más complicada la factorización de una permutación no es única, y en distintas factorizaciones intervienen diferente numero de trasposiciones. Hay que probar que esos diferentes números son todos pares o todos impares para una permutación dada.

Quizá por eso el camino que he visto en diferentes fuentes es el siguiente:

  1. Se define la paridad de una permutación como la paridad el número de inversiones que contiene la permutación (se produce una inversión en una permutación cuando $ i<j $ y sin embargo $ \sigma (i) > \sigma(j)  $ )
    Se da al valor 1 a la permutación par y -1 a la impar (se dice que las permutaciones pares tienen signatura 1 y las permutaciones impares signatura -1)
  2. Las trasposiciones son impares (paridad -1). La paridad de la trasposición $ (i,i+1) $ es -1 (sólo tiene una inversión). Estas trasposiciones de números consecutivos se llaman trasposiciones elementales. La trasposición $ (i,j) $ contiene $2(j-i) -1 $ inversiones y se puede expresar como producto de $2(j-i)-1 $ trasposiciones elmentales
  3. Cualquier permutación puede expresarse como producto de trasposiciones
  4. La paridad del producto de dos permutaciones es igual al producto de las paridades de las permutaciones
  5. Al efectuar la trasposición (i,j) con i<j sobre la permutación $ \sigma $ se cambia un número impar de veces la paridad de la permutación (concretamente 2(j-i)-1 veces)
    Por tanto $ \sigma \circ (i,j) $ tiene paridad diferente a $ \sigma $
  6. Si la permutación $ \sigma $ se expresa como producto de varias trasposiciones $ \sigma = \tau_1 \cdot \tau_2 … \tau_n $ es claro que los dos miembros de la igualdad tienen que tener la misma paridad. Si $ \sigma $ es par, el producto de las n trasposiciones tiene que ser par, por tanto n tiene tiene que ser par. Lo mismo en el caso impar.

Este es el camino que antes seguí, sólo que he mostrado únicamete algunos puntos, los que he calificado de "críticos
Ahora voy a "parafrasear" el tema tal y como viene en el libro "Álgebra" de Carlos Ivorra

Se trata de una demostración parecida a la anterior, pero más formalizada, que hace uso de la teoría de grupos.


Se trata de ver que la paridad de una permutación puede definirse como la paridad del número de trasposiciones en que se puede descomponer.
La dificultad esté en que la descomposición en producto de trasposiciones de una permutación no es única, y por tanto hay que demostrar que dos descomposiciones diferentes con diferente número de trasposiciones interviniendo cumplen que dichos números son ambos pares o impares.
La estrategia consiste en definir la paridad de otra manera, a partir del concepto de signatura de una permutación. 
Dicha signatura puede ser 1 o -1.
Si además probamos que la signatura del producto de permutaciones es el producto de las signaturas y que la signatura de cualquier trasposición es -1, entonces ya lo tenemos.
Si la signatura de la permutación es 1, una descomposición cualquiera en de dicha permutación en producto de digamos n trasposiciones tendrá  signatura $ (-1)^n $  y para que esa cantidad sea 1 el número n debe ser par. 
Análogamente, si la signatura es -1, el número n deberá ser impar.
Por tanto, dada una permutación, cualquier descomposición en producto de trasposiciones constará de un número par de elementos si la signatura de la permutación es 1 y de un número impar si es -1

Voy a transcribir la prueba del libro de Álgebra de Ivorra, añadiendo comentarios en otro color
En este enlace encontrarás, en el capítulo IX el apartado sobre grupos simétricos que paso a comentar inmediatamente:

PRIMERA PARTE: DEFINICIÓN DE SIGNATURA DE UNA PERMUTACIÓN 

Definición 9.31. Sea $ n \geq 2 $ , sea $ P_n = \{ \{i,j \} \: tq \: 1 \leq i < j \leq n \} $

Para cada permutación $ \sigma \in \Sigma_n $ y cada $ b= \{i,j \} $ con $ 1 \leq i<j \leq n $  sea

 

Denominamos signatura de $ \sigma $ a:

$  sig\, \sigma \: = \, \prod_{b \in P_n} {\epsilon ( \sigma , b)}  \; \in  \, \{ 1, \, -1 \} $

Las permutaciones de signatura 1 se llaman pares y las de signatura -1 se llaman impares

 Esta definición es la que he visto en otras fuentes, pero algo más formalizada. Intuitivamente se ve que cada permutación tiene asociada una única signatura 

Enseguida daremos una interpretación sencilla de este concepto. Primero conviene probar lo siguiente:

 SEGUNDA PARTE: LA SIGNATURA DEL PRODUCTO DE VARIAS PERMUTACIONES ES EL PRODUCTO DE SUS SIGNATURAS 

 Este es un punto que no entendía en otras versiones 



   Se pueden estudiar casos, que salen cuatro, combinando $ \sigma (i)  $ mayor o menor que $ \sigma (j) $  con $ \tau (i) $ o con $ \tau (j) $ y teniendo en cuenta que $ \sigma  \tau = \tau \circ \sigma $  

Como la aplicación  $ P_n \longrightarrow { P_n} $ dada por $ b \longrightarrow { \sigma [b] } $  es biyectiva, se cumple que

$ sig (\sigma \tau ) = \prod_{b \in P_n}{\epsilon (\sigma \tau , b)}= \prod_{b \in P_n}{\epsilon (\sigma , b)  \epsilon ( \tau , \sigma (b) } = \prod_{b \in P_n}{\epsilon (\sigma , b)} \prod_{b \in P_n}{ \epsilon ( \tau , \sigma [b] ) } =    $  ( aquí se aplica la  biyectividad de $ \sigma $  , ya que las parejas $ \sigma (b) $ son las mismas parejas b quizás cambiadas de orden  )  $ = \prod_{b \in P_n}{\epsilon (\sigma , b)}  \prod_{b \in P_n}{\epsilon (\tau , b)}   = (sig(\sigma) sig(\tau) $
                                                      FIN DE LA DEMOSTRACIÓN


 TERCERA PARTE: Las trasposiciones tienen signatura igual a -1 

Aquí se parte de que la trasposición (1,2) tiene signatura -1
Luego se prueba que cualquier trasposición es conjugada de (1,2) (se invoca el teorema 9.18) y también se prueba que las permutaciones conjugadas tienen la misma signatura, y se recuerda que cualquier permutación es producto de trasposiciones (descomposición no única).
Todo esto nos lleva a que:

 CONCLUSIÓN
Teorema 9.33  Una permutación es par o impar si y sólo si se descompone en un número par o impar de trasposiciones, respectivamente.


OTRA VEZ: COMO QUERÍAMOS DEMOSTRAR


INFORMACIÓN SOBRE EL GRUPO SIMÉTRICO EN LA RED

Algunas direcciones donde encontrar información:
http://el-chevere.com/video/JlXh7NlPbQA/7-11-11-parte-1-Notacio%CC%81n-ciclos.html     AQUÍ

http://www.veengle.com/s/permutacion/6.html       PINCHA
http://personales.unican.es/olazabaj/Docencia/T_Grupos/Apuntes/simetricos.pdf
https://www.ugr.es/~jurbano/aed/AED-Tema_2-Grupos.Grupo_simetrico.pdf
http://www.youtube.com/watch?v=Rz9xod4S5-o
http://alexmoqui.wordpress.com/2011/12/09/grupo-de-automorfismos-del-grupo-simetrico-en-6-letras/
http://cvb.ehu.es/open_course_ware/castellano/experimentales/algebra/tema5apto1.pdf
http://salvamate.wordpress.com/tag/grupo-simetrico/
http://webdelprofesor.ula.ve/ciencias/jlchacon/materias/discreta/permutaciones.pdf
http://www.youtube.com/playlist?list=PLxt0Hgnl0gCXhZCHGNmeh8ObDAvtzHz7b

Antes o después, nuestro interés por los grupos simétricos nos llevará a trabajar o profundizar en teoría de grupos.
Esta entrada es sobre teoría de grupos en general :http://matematicas-de-la-simetria.blogspot.com.es/
Tengo que añadir esta dirección, una entrada de este mismo blog, con información sobre teoría de grupos:
http://parafernaliasmatematicas.blogspot.com.es/2012/12/teoria-de-grupos.html

OTRA MANERA DE ENFOCAR EL CONTENIDO PROPUESTO EN ESTA ENTRADA
Se trata de seguir el desarrollo del último capítulo del libro "Foundations of Galois Theory" de M.M.Postnikov. 
A continuación va el índice del contenido que hay que desarrollar
1.-   Grupo de Galois de una ecuación como grupo de sustituciones.
        Nos fijamos en una ecuación polinómica y sus raices.
2.-   Factorización de permutaciones como producto de ciclos
3.-   Permutaciones pares. El grupo alternado.
4.-   Estructura de los grupos alternado y simétrico
5.-   Ejemplo de ecuación cuyo grupo de Galois es el grupo simétrico.
6.-   Discusión de los resultados
Bueno, acabo aquí de momento esta entrada, a la espera de tener tiempo, recopilar material y reunir energía para continuar el proyecto








No hay comentarios:

Publicar un comentario

Tu opinión respetuosa con elementales normas de cortesía y convivencia, será siempre bienvenida