Permutación cíclica - Cyclic permutation

En matemáticas , y en particular en teoría de grupos , una permutación cíclica (o ciclo ) es una permutación de los elementos de algún conjunto X que mapea los elementos de algún subconjunto S de X entre sí de manera cíclica, mientras se fija (es decir , mapeo a sí mismos) todos los otros elementos de X . Si S tiene k elementos, el ciclo se llama k- ciclo . Los ciclos a menudo se indican mediante la lista de sus elementos entre paréntesis, en el orden en el que se permutan.

Por ejemplo, dado X = {1, 2, 3, 4}, la permutación (1, 3, 2, 4) que envía 1 a 3, 3 a 2, 2 a 4 y 4 a 1 (entonces S = X ) es un ciclo de 4, y la permutación (1, 3, 2) que envía 1 a 3, 3 a 2, 2 a 1 y 4 a 4 (entonces S = {1, 2, 3} y 4 es un elemento fijo ) es un ciclo de 3. Por otro lado, la permutación 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 S se llama órbita del ciclo. Cada permutación en un número finito de elementos se puede descomponer en ciclos en órbitas disjuntas.

Las partes cíclicas de una permutación son ciclos , por lo tanto, el segundo ejemplo se compone de un ciclo de 3 y un ciclo de 1 (o punto fijo ) y el tercero se compone de dos ciclos de 2, y se denota (1, 3) (2 , 4).

Definición

Diagrama de una permutación cíclica con dos puntos fijos; un ciclo de 6 y dos ciclos de 1.

Una permutación se denomina permutación cíclica si y solo si tiene un solo ciclo no trivial (un ciclo de duración> 1).

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

${\ displaystyle {\ 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 \\ 4 & 6 & 8 & 3 & 7 & 1 \ 1 & 5} {pmatrix} {2 & 5} (2) (5),}$

es un ciclo de seis; su diagrama de ciclo se muestra a la derecha.

Algunos autores restringen la definición a solo aquellas permutaciones que consisten en un ciclo no trivial (es decir, no se permiten puntos fijos).

Una permutación cíclica sin ciclos triviales; un ciclo de 8.

Por ejemplo, la permutación

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

es una permutación cíclica bajo esta definición más restrictiva, mientras que el ejemplo anterior no lo es.

Más formalmente, una permutación de un conjunto X , visto 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. Esta noción se usa más comúnmente cuando X es un conjunto finito; entonces, por supuesto, la órbita más grande, S , también es finita. Sea cualquier elemento de S y coloque cualquiera . 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 \ a 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 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}}$.

Un ciclo se puede escribir usando la notación de ciclo compacto (no hay comas entre los elementos en esta notación, para evitar confusiones 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 denomina k- ciclo. ${\ Displaystyle \ sigma = (s_ {0} ~ s_ {1} ~ \ dots ~ s_ {k-1})}$

La órbita de un ciclo 1 se denomina punto fijo de la permutación, pero como permutación, cada ciclo 1 es la permutación de identidad . Cuando se utiliza la notación de ciclo, los ciclos 1 a menudo se suprimen cuando no se produce confusión.

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 se conmutan entre sí, y la expresión de la permutación es única hasta el orden de los ciclos. Por 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.

El número de k -ciclos en el grupo simétrico S _n viene dado, por , 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 !} {(nk)! k}}}$

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

El inverso de un ciclo se da invirtiendo el orden de las entradas: . En particular, dado que cada dos ciclos es su propio inverso. 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. ${\ displaystyle \ pi = {\ begin {pmatrix} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \ end {pmatrix}}}$

Propiedades

Cualquier permutación puede expresarse como la composición (producto) de las transposiciones; formalmente, son generadoras del grupo . De hecho, cuando el conjunto que se permuta es {1, 2, ..., n } para algún número entero n , entonces cualquier permutación se puede expresar como un producto de transposiciones adyacentes y así sucesivamente. Esto se sigue porque una transposición arbitraria se puede expresar como el producto de transposiciones adyacentes. Concretamente, uno puede expresar la transposicióndondemoviendo k a l un paso a la vez, luego moviendo l de regreso a dondeestaba 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 más largos 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 mover a a a y, finalmente, a su lugar uno pueden rodar los elementos de mantenimiento de donde es mediante la ejecución del factor de derecho primero (como es habitual en la notación de operador, y siguiendo la convención en el artículo sobre permutaciones ). Esto se ha movido a la posición de entonces después de la primera permutación, los elementos y aún no están en sus posiciones finales. La transposición ejecutada a partir de entonces, 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 es generado por elementos de orden 2 (las transposiciones adyacentes), y todas las relaciones son de cierta forma.

Uno de los principales resultados de los 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. Esto permite que la paridad de una permutación sea ​​un concepto bien definido .

Ver también

• Orden de ciclo : un algoritmo de ordenación 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 entero
• Notación de ciclo
• Permutación circular en proteínas

Notas

Referencias

Fuentes

• Anderson, Marlow y Feil, Todd (2005), 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.a ed.), Addison Wesley, ISBN 978-0-201-53467-2
• Rotman, Joseph J. (2006), Un primer curso de álgebra abstracta con aplicaciones (3a 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 y 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 .