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 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
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). [1]
Por ejemplo, la permutación, escrita en notación de dos líneas (de dos formas) y también notación cíclica,
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). [2]
Por ejemplo, la permutación
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 portiene como máximo una órbita con más de un elemento. [3] 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. Dejarser cualquier elemento de S , y poner para cualquier . Si S es finito, hay un número mínimo para cual . Luego, y es la permutación definida por
- para 0 ≤ i < k
y para cualquier elemento de . Los elementos no arreglados por se puede representar como
- .
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.
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 . [4] Cuando se utiliza la notación de ciclo, los ciclos 1 a menudo se suprimen cuando no se produce confusión. [5]
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. [a] El conjunto múltiple de longitudes de los ciclos en esta expresión (el tipo de ciclo ) está determinado únicamente 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. [6]
Se da el número de k- ciclos en el grupo simétrico S n , para, por las siguientes fórmulas equivalentes
Un ciclo k tiene la firma (−1) k - 1 .
La inversa de un ciclo se da invirtiendo el orden de las entradas: . En particular, desde, 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.
Transposiciones
Un ciclo con solo dos elementos se llama transposición . Por ejemplo, la permutación que intercambia 2 y 4.
Propiedades
Cualquier permutación puede expresarse como la composición (producto) de las transposiciones; formalmente, son generadoras del grupo . [7] 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í. Esto se debe a que una transposición arbitraria se puede expresar como el producto de transposiciones adyacentes. Concretamente, se puede expresar la transposición dónde moviendo k a l un paso a la vez, luego moviendo l de regreso a donde estaba k , lo que intercambia estos dos y no hace otros cambios:
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:
Esto significa que la solicitud inicial es mover a a a y finalmente a En su lugar, uno puede rodar los elementos manteniendo donde es ejecutando el factor correcto primero (como es habitual en la notación de operadores y siguiendo la convención del artículo sobre Permutaciones ). Esto se ha movido a la posición de así que después de la primera permutación, los elementos y aún no están en sus posiciones finales. La transposición ejecutado a partir de entonces, luego se dirige por el índice de para intercambiar lo que inicialmente eran y
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. [8] 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
- ^ Tenga en cuenta que la notación de ciclo no es única: cada k- ciclo puede escribirse en k formas diferentes, dependiendo de la elección de en su órbita.
Referencias
- ^ Bogart, Kenneth P. (1990), Introducción a la combinatoria (2ª ed.), Harcourt, Brace, Jovanovich, p. 486, ISBN 0-15-541576-X
- ^ Gross, Jonathan L. (2008), Métodos combinatorios con aplicaciones informáticas , Chapman & Hall / CRC, p. 29, ISBN 978-1-58488-743-0
- ^ Fraleigh 1993 , p. 103
- ^ Rotman , 2006 , p. 108
- ^ Sagan 1991 , p. 2
- ^ Rotman , 2006 , p. 117, 121
- ^ Rotman , 2006 , p. 118, Prop. 2.35
- ^ Rotman , 2006 , p. 122
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 (5a 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 .