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 consta de 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 denominarse 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 notación cíclica , las permutaciones cíclicas se indican mediante la lista de sus elementos 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 ciclo de 4, y la permutación (1 3 2)(4) que envía 1 a 3 Algunos autores consideran que 3 a 2, 2 a 1 y 4 a 4 son 3 ciclos. 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}.

El conjunto de elementos que no están fijados por una permutación cíclica se llama órbita de la permutación cíclica. ^{[ cita necesaria ]} Cada permutación en un número finito de elementos se puede descomponer en permutaciones cíclicas en órbitas disjuntas.

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

Definición

Una permutación cíclica que consta de un solo 8 ciclos.

No existe un consenso generalizado sobre la definición precisa de permutación cíclica. Algunos autores definen una permutación σ de un conjunto X como cíclica si "la aplicación sucesiva tomaría cada objeto del conjunto permutado sucesivamente a través de las posiciones de todos los demás objetos", ^[1] o, de manera equivalente, si su representación en notación cíclica consiste de 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 sólo 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 ciclos de 1, su diagrama de ciclo 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 ciclo) y un 6 ciclo.

Con la definición ampliada, existen permutaciones cíclicas que no constan de 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. ^[5] 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 pongamos cualquier . Si S es finito, existe 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 ≤ yo < k

y para cualquier elemento de . Los elementos no fijados por se pueden representar 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}}$.

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

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

Propiedades básicas

Uno de los resultados básicos de 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] Por lo tanto, el conjunto múltiple de longitudes de los ciclos en esta expresión (el tipo de ciclo ) está 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. ^[8]

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 firma (−1) ^{k  − 1} .

La inversa de un ciclo se obtiene invirtiendo el orden de las entradas: . En particular, desde , cada dos ciclos es su propio inverso. Dado que los ciclos disjuntos se conmutan, la inversa de un producto de ciclos disjuntos es el resultado de revertir 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 sólo 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 del grupo . ^[9] De hecho, cuando el conjunto que se está permutando es {1, 2, ..., n } para algún número entero n , entonces cualquier permutación se puede expresar como un producto detransposiciones adyacentes , etc. Esto se debe a que una transposición arbitraria puede expresarse como el producto de transposiciones adyacentes. Concretamente, se puede expresar la transposicióndondemoviendo k a l un paso a la vez, luego moviendo l de regreso a donde estaba k , lo que intercambia estos dos y no realiza 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 más 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 pasar a a y finalmente a. En lugar de eso, se pueden hacer rodar los elementos manteniéndolos 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 ). Este se ha movido a la posición de así que después de la primera permutación, los elementos aún no están en sus posiciones finales. La transposición ejecutada posteriormente, 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 determinada forma.

Uno de los principales resultados sobre grupos simétricos establece que o 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. ^[10] Esto permite que la paridad de una permutación sea un concepto bien definido .

Ver también

• Clasificación por ciclos : un algoritmo de clasificación que se basa en la idea de que la permutación que se va a clasificar se puede factorizar en ciclos, que se pueden rotar individualmente para dar un resultado ordenado.
• Ciclos y puntos fijos
• Permutación cíclica de un número entero
• Notación de ciclo
• Permutación circular en proteínas.
• Mezcla Fisher-Yates

Notas

1. Tenga en cuenta que la notación del ciclo no es única: cada k -ciclo se puede escribir 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ática discreta y sus aplicaciones. Boca Ratón, Florida: Chapman & Hall/CRC. pag. 29.ISBN​ 978-1-58488-743-0.
2. Knuth, Donald E. (2002). El arte de la programación informática . Addison-Wesley. pag. 35.
3. Bogart, Kenneth P. (2000). Combinatoria introductoria (3 ed.). Londres: Harcourt Academic Press. pag. 554.ISBN​ 978-0-12-110830-4.
4. Rosen, Kenneth H. (2000). Manual de matemáticas discretas y combinatorias . Boca Ratón Londres Nueva York: prensa CRC. ISBN 978-0-8493-0149-0.
5. Fraleigh 1993, pág. 103
6. Rotman 2006, pag. 108
7. Sagan 1991, pag. 2
8. Rotman 2006, pag. 117, 121
9. Rotman 2006, pag. 118, Proposición 2.35
10. Rotman 2006, pag. 122

Fuentes

• Anderson, Marlow y Feil, Todd (2005), Un primer curso de álgebra abstracta , Chapman & Hall/CRC; 2da 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

Este artículo incorpora material del ciclo en PlanetMath , que tiene la licencia Creative Commons Attribution/Share-Alike License .