Permutación cíclica

Tipo de permutación (matemática) sin elemento fijo

En matemáticas , y en particular en teoría de grupos , una permutación cíclica es una permutación que consiste en un solo ciclo. ^{[1] [2]} En algunos casos, las permutaciones cíclicas se denominan ciclos ; ^[3] si una permutación cíclica tiene k elementos, puede llamarse k -ciclo . Algunos autores amplían esta definición para incluir permutaciones con puntos fijos además de como máximo un ciclo no trivial. ^{[3] [4]} En la notación de ciclos , las permutaciones cíclicas se denotan por la lista de sus elementos encerrados entre paréntesis, en el orden en que se permutan.

Por ejemplo, la permutación (1 3 2 4) que envía 1 a 3, 3 a 2, 2 a 4 y 4 a 1 es un 4-ciclo, y la permutación (1 3 2)(4) que envía 1 a 3, 3 a 2, 2 a 1 y 4 a 4 es considerada un 3-ciclo por algunos autores. Por otro lado, la permutación (1 3)(2 4) que envía 1 a 3, 3 a 1, 2 a 4 y 4 a 2 no es una permutación cíclica porque permuta por separado los pares {1, 3} y {2, 4}.

Para una definición más amplia de una permutación cíclica, que permite puntos fijos, estos puntos fijos constituyen cada uno órbitas triviales de la permutación, y hay una única órbita no trivial que contiene todos los puntos restantes. Esto se puede utilizar como definición: una permutación cíclica (que permite puntos fijos) es una permutación que tiene una única órbita no trivial. Toda permutación en un número finito de elementos se puede descomponer en permutaciones cíclicas cuyas órbitas no triviales son disjuntas. ^[5]

Las partes cíclicas individuales de una permutación también se denominan ciclos , por lo que el segundo ejemplo se compone de un ciclo 3 y un ciclo 1 (o punto fijo ) y el tercero se compone de dos ciclos 2.

Definición

Una permutación cíclica que consta de un único ciclo de 8.

No existe un consenso generalizado sobre la definición precisa de una permutación cíclica. Algunos autores definen una permutación σ de un conjunto X como cíclica si "la aplicación sucesiva llevaría a cada objeto del conjunto permutado sucesivamente a través de las posiciones de todos los demás objetos", ^[1] o, equivalentemente, si su representación en notación cíclica consiste en un solo ciclo. ^[2] Otros proporcionan una definición más permisiva que permite puntos fijos. ^{[3] [4]}

Un subconjunto no vacío S de X es un ciclo de si la restricción de a S es una permutación cíclica de S . Si X es finito , sus ciclos son disjuntos , y su unión es X . Es decir, forman una partición , llamada descomposición cíclica de Entonces, según la definición más permisiva, una permutación de X es cíclica si y solo si X es su ciclo único. ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \sigma .}$

Por ejemplo, la permutación, escrita en notación cíclica y notación de dos líneas (de dos maneras) como

${\displaystyle {\begin{aligned}(1\ 4\ 6\ &8\ 3\ 7)(2)(5)\\&={\begin{pmatrix}1&2&3&4&5&6&7&8\\4&2&7&6&5&8&1&3\end{pmatrix}}\\&={\begin{pmatrix}1&4&6&8&3&7&2&5\\4&6&8&3&7&1&2&5\end{pmatrix}}\end{aligned}}}$

Tiene un ciclo de 6 y dos de 1. Su diagrama de ciclos se muestra a la derecha. Algunos autores consideran que esta permutación es cíclica, mientras que otros no.

Una permutación que es cíclica para la definición ampliada pero no para la restringida, con dos puntos fijos (1-ciclos) y un 6-ciclo

Con la definición ampliada, hay permutaciones cíclicas que no consisten en un solo ciclo.

Más formalmente, para la definición ampliada, una permutación de un conjunto X , vista como una función biyectiva , se llama ciclo si la acción sobre X del subgrupo generado por tiene como máximo una órbita con más de un elemento. ^[6] Esta noción se usa más comúnmente cuando X es un conjunto finito; entonces la órbita más grande, S , también es finita. Sea cualquier elemento de S , y puesto para cualquier . Si S es finito, hay un número mínimo para el cual . Entonces , y es la permutación definida por ${\displaystyle \sigma }$ ${\displaystyle \sigma :X\to X}$ ${\displaystyle \sigma }$ ${\displaystyle s_{0}}$ ${\displaystyle s_{i}=\sigma ^{i}(s_{0})}$ ${\displaystyle i\in \mathbf {Z} }$ ${\displaystyle k\geq 1}$ ${\displaystyle s_{k}=s_{0}}$ ${\displaystyle S=\{s_{0},s_{1},\ldots ,s_{k-1}\}}$ ${\displaystyle \sigma }$

${\displaystyle \sigma (s_{i})=s_{i+1}}$para 0 ≤ i < k

y para cualquier elemento de . Los elementos no fijados por pueden representarse como ${\displaystyle \sigma (x)=x}$ ${\displaystyle X\setminus S}$ ${\displaystyle \sigma }$

${\displaystyle s_{0}\mapsto s_{1}\mapsto s_{2}\mapsto \cdots \mapsto s_{k-1}\mapsto s_{k}=s_{0}}$.

Una permutación cíclica se puede escribir utilizando la notación de ciclo compacto (no hay comas entre los elementos en esta notación, para evitar confusiones con una k - tupla ). La longitud de un ciclo es el número de elementos de su órbita más grande. Un ciclo de longitud k también se denomina k -ciclo. ${\displaystyle \sigma =(s_{0}~s_{1}~\dots ~s_{k-1})}$

La órbita de un 1-ciclo se denomina punto fijo de la permutación, pero como permutación cada 1-ciclo es la permutación identidad . ^[7] Cuando se utiliza la notación de ciclo, los 1-ciclos se omiten a menudo cuando no se produce ninguna confusión. ^[8]

Propiedades básicas

Uno de los resultados básicos sobre los grupos simétricos es que cualquier permutación puede expresarse como el producto de ciclos disjuntos (más precisamente: ciclos con órbitas disjuntas); dichos ciclos conmutan entre sí, y la expresión de la permutación es única hasta el orden de los ciclos. ^[a] El multiconjunto de longitudes de los ciclos en esta expresión (el tipo de ciclo ) está por lo tanto determinado de forma única por la permutación, y tanto la firma como la clase de conjugación de la permutación en el grupo simétrico están determinadas por ella. ^[9]

El número de k -ciclos en el grupo simétrico S _n viene dado, para , por las siguientes fórmulas equivalentes: ${\displaystyle 1\leq k\leq n}$ $${\displaystyle {\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n!}{(n-k)!k}}.}$$

Un k -ciclo tiene la firma (−1) ^{k  − 1} .

La inversa de un ciclo se obtiene invirtiendo el orden de las entradas: . En particular, dado que , cada ciclo de dos es su propia inversa. Dado que los ciclos disjuntos conmutan, la inversa de un producto de ciclos disjuntos es el resultado de invertir cada uno de los ciclos por separado. ${\displaystyle \sigma =(s_{0}~s_{1}~\dots ~s_{k-1})}$ ${\displaystyle \sigma ^{-1}=(s_{k-1}~\dots ~s_{1}~s_{0})}$ ${\displaystyle (a~b)=(b~a)}$

Transposiciones

Matriz de ${\displaystyle \pi }$

Un ciclo con solo dos elementos se llama transposición . Por ejemplo, la permutación que intercambia 2 y 4. Como es un ciclo de 2, se puede escribir como . ${\displaystyle \pi ={\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}}$ ${\displaystyle \pi =(2,4)}$

Propiedades

Cualquier permutación puede expresarse como la composición (producto) de transposiciones; formalmente, son generadores para el grupo . ^[10] De hecho, cuando el conjunto que se está permutando es {1, 2, ..., n } para algún entero n , entonces cualquier permutación puede expresarse como un producto detransposiciones adyacentes , etc. Esto se debe a que una transposición arbitraria se puede expresar como el producto de transposiciones adyacentes. En concreto, se puede expresar la transposicióndondeal mover k a l un paso a la vez, luego mover l de regreso a donde estaba k , lo que intercambia estos dos y no hace otros cambios: ${\displaystyle (1~2),(2~3),(3~4),}$ ${\displaystyle (k~~l)}$ ${\displaystyle k<l}$

${\displaystyle (k~~l)=(k~~k+1)\cdot (k+1~~k+2)\cdots (l-1~~l)\cdot (l-2~~l-1)\cdots (k~~k+1).}$

La descomposición de una permutación en un producto de transposiciones se obtiene, por ejemplo, escribiendo la permutación como un producto de ciclos disjuntos y luego dividiendo iterativamente cada uno de los ciclos de longitud 3 y mayor en un producto de una transposición y un ciclo de longitud uno menos:

${\displaystyle (a~b~c~d~\ldots ~y~z)=(a~b)\cdot (b~c~d~\ldots ~y~z).}$

Esto significa que la solicitud inicial es moverse a a a y finalmente a En cambio, uno puede hacer rodar los elementos manteniendo donde están ejecutando primero el factor correcto (como es habitual en la notación de operadores y siguiendo la convención del artículo Permutación ). Esto se ha movido a la posición de por lo que después de la primera permutación, los elementos y aún no están en sus posiciones finales. La transposición ejecutada a continuación, luego se dirige por el índice de para intercambiar lo que inicialmente eran y ${\displaystyle a}$ ${\displaystyle b,}$ ${\displaystyle b}$ ${\displaystyle c,}$ ${\displaystyle y}$ ${\displaystyle z,}$ ${\displaystyle z}$ ${\displaystyle a.}$ ${\displaystyle a}$ ${\displaystyle z}$ ${\displaystyle b,}$ ${\displaystyle a}$ ${\displaystyle z}$ ${\displaystyle (a~b),}$ ${\displaystyle z}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle z.}$

De hecho, el grupo simétrico es un grupo de Coxeter , lo que significa que está generado por elementos de orden 2 (las transposiciones adyacentes) y todas las relaciones son de una forma determinada.

Uno de los principales resultados sobre los grupos simétricos establece que todas las descomposiciones de una permutación dada en transposiciones tienen un número par de transposiciones, o todas tienen un número impar de transposiciones. ^[11] Esto permite que la paridad de una permutación sea un concepto bien definido .

Véase también

• Ordenamiento cíclico : un algoritmo de ordenamiento que se basa en la idea de que la permutación que se va a ordenar se puede factorizar en ciclos, que se pueden rotar individualmente para dar un resultado ordenado.
• Ciclos y puntos fijos
• Permutación cíclica de números enteros
• Notación de ciclo
• Permutación circular en proteínas
• Mezcla Fisher-Yates

Notas

1. Nótese que la notación de ciclo no es única: cada k -ciclo puede escribirse de k maneras diferentes, dependiendo de la elección de su órbita. ${\displaystyle s_{0}}$

Referencias

1. Gross, Jonathan L. (2008). Métodos combinatorios con aplicaciones informáticas . Matemáticas discretas y sus aplicaciones. Boca Raton, Fla.: Chapman & Hall/CRC. p. 29. ISBN 978-1-58488-743-0.
2. Knuth, Donald E. (2002). El arte de la programación informática . Addison-Wesley. pág. 35.
3. Bogart, Kenneth P. (2000). Combinatoria introductoria (3.ª ed.). Londres: Harcourt Academic Press. pág. 554. ISBN 978-0-12-110830-4.
4. Rosen, Kenneth H. (2000). Manual de matemáticas discretas y combinatorias . Boca Raton Londres Nueva York: CRC Press. ISBN 978-0-8493-0149-0.
5. Ehrlich, Gertrude (2013). Conceptos fundamentales del álgebra abstracta. Dover Books on Mathematics. Courier Corporation. pág. 69. ISBN 9780486291864.
6. Fraleigh 1993, pág. 103
7. Rotman 2006, pág. 108
8. Sagan 1991, pág. 2
9. Rotman 2006, pág. 117, 121
10. Rotman 2006, pág. 118, Proposición 2.35
11. Rotman 2006, pág. 122

Fuentes

• Anderson, Marlow y Feil, Todd (2005), Un primer curso de álgebra abstracta , Chapman & Hall/CRC; 2.ª edición. ISBN 1-58488-515-7 . 
• Fraleigh, John (1993), Un primer curso de álgebra abstracta (5ª ed.), Addison Wesley, ISBN 978-0-201-53467-2
• Rotman, Joseph J. (2006), Un primer curso de álgebra abstracta con aplicaciones (3.ª ed.), Prentice-Hall, ISBN 978-0-13-186267-8
• Sagan, Bruce E. (1991), El grupo simétrico / Representaciones, algoritmos combinatorios y funciones simétricas , Wadsworth & Brooks/Cole, ISBN 978-0-534-15540-7

Enlaces externos

• Notación cíclica de permutaciones, el vídeo explica la descomposición cíclica.

Este artículo incorpora material de cycle en PlanetMath , que está licenciado bajo la Licencia Creative Commons Atribución/Compartir-Igual .