Permutación cíclica

En la teoría de grupos, una permutación cíclica es una permutación de los elementos de algún conjunto X que reorganiza los elementos de algún subconjunto S del conjunto X de forma cíclica, manteniendo los elementos restantes de X en su lugar (es decir, mapeándolos en sí mismo) . Por ejemplo, la permutación {1, 2, 3, 4} que lleva 1 a 3, 3 a 2, 2 a 4 y 4 a 1 es cíclica, mientras que la permutación que toma 1 a 3, 3 a 1, 2 a 4 y 4 en 2 no es cíclico.

Un ciclo en una permutación es un subconjunto de elementos que se permutan de forma cíclica. El conjunto S se llama la órbita del ciclo. Cada permutación de un conjunto finito de elementos se puede descomponer en una unión de ciclos con órbitas que no se cruzan. En algunos contextos, una permutación cíclica se denomina ciclo.

Definición

Una permutación se llama cíclica si y sólo si consiste en un solo ciclo no trivial (es decir, un ciclo de longitud mayor que 1) [1] .

Ejemplo:

{\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}}=(146837)(2)(5)

Algunos autores limitan la definición a solo aquellas permutaciones que tienen exactamente un ciclo (es decir, las permutaciones que tienen puntos fijos no están permitidas [2] .

Ejemplo:

{\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&3&7&1\end{pmatrix}}=(14625837)

Más formalmente, una permutación de un conjunto X que es una función biyectiva se llama cíclica si la acción sobre X de un subgrupo con un generador tiene como máximo una órbita de más de un elemento [3] . Este concepto se usa con mayor frecuencia cuando X es un conjunto finito. Entonces, por supuesto, la órbita más grande S también es finita. Sea cualquier elemento de S , conjunto para cualquier . Si el conjunto S es finito, entonces existe un número mínimo para el cual . Entonces y es una permutación definida por la fórmula ${\ estilo de visualización \ sigma: X \ a X}$ $\sigma$ ${\ estilo de visualización s_ {0}}$ $s_{i}=\sigma^{i}(s_{0})$ $i\en \mathbf {Z}$ $k\geqslant 1$ ${\displaystyle s_{k}=s_{0))$ ${\displaystyle S=\{s_{0},s_{1},\ldots,s_{k-1}\))$ $\sigma$

\sigma (s_{i})=s_{i+1}\quad

por

0\leq i<k

y para cualquier elemento . Los elementos no capturados por la pantalla se pueden representar como ${\ estilo de visualización \ sigma (x) = x}$ $X\setminus S$ $\sigma$

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

Un bucle se puede escribir utilizando la notación de bucle compacto (no hay comas entre los elementos en dicha notación para evitar confusiones con las tuplas ). La longitud de un ciclo es el número de elementos en su órbita más grande. En la notación de bucle, los bucles de longitud 1 a menudo se omiten si esto no causa confusión [4] . $\sigma =(s_{0}~s_{1}~\puntos ~s_{k-1})$

Propiedades básicas

De acuerdo con una de las principales propiedades de los grupos simétricos , cualquier permutación puede representarse como un producto de ciclos que no se intersecan (más precisamente, ciclos con órbitas que no se intersecan). Dichos ciclos se pueden permutar entre sí, y la expresión de permutación es única hasta el orden de los ciclos (tenga en cuenta que la notación cíclica no es única: cualquier k -ciclo en sí mismo se puede escribir en k formas diferentes, dependiendo de la elección en su órbita). El conjunto múltiple de longitudes de ciclo (tipo de ciclo) está determinado únicamente por una permutación. ${\ estilo de visualización s_ {0}}$

El número de ciclos diferentes de longitud k en el grupo simétrico S n viene dado por la siguiente fórmula ${\ estilo de visualización 1 \ leqslant k \ leqslant n}$

{\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n !}{(nk)!k}}

Un ciclo de longitud k tiene paridad (−1) k − 1 .

Transposiciones

Un ciclo que consta de dos elementos se denomina transposición . Por ejemplo, la permutación {1, 4, 3, 2} que lleva 1 a 1, 2 a 4, 3 a 3 y 4 a 2 es una transposición (es decir, una transposición que intercambia 2 y 4).

Cualquier permutación se puede representar como una composición (producto) de transposiciones; formalmente, son generadores de grupos [5] . Además, cualquier permutación del conjunto ordenado X = {1, 2, …, n } se puede expresar como un producto de transposiciones adyacentes , es decir, transposiciones de la forma Efectivamente, cualquier transposición se puede representar como un producto de transposiciones adyacentes. ${\ estilo de visualización (k~~k+1).}$

La descomposición de una permutación en un producto de transposiciones se puede obtener, por ejemplo, escribiendo una permutación como un producto de varios ciclos, y luego iterativamente descomponiendo ciclos de 3 o más longitudes en un producto de una transposición y un ciclo más corto. :

(a~b~c~d~\ldots ~y~z)=(a~b)\cdot (b~c~d~\ldots ~y~z)

El grupo simétrico es un grupo de Coxeter , en el sentido de que es generado por elementos de orden 2 (transposiciones adyacentes) y todas las relaciones tienen una forma definida.

Uno de los principales resultados de la teoría elemental de los grupos simétricos establece que o bien todas las descomposiciones de una permutación dada en transposiciones tienen un número par de transposiciones, o bien todas las descomposiciones tienen un número impar de transposiciones [6] . Esto permite que la paridad de la permutación sea una función bien definida.

Véase también

Loop sort es un algoritmo de clasificación basado en la idea de que una matriz se puede descomponer en bucles que se pueden recorrer individualmente para obtener una matriz ordenada
Ciclos y puntos fijos
Permutaciones cíclicas de enteros
Permutaciones cíclicas en proteínas

Nota

↑ Bogart, 1990 , pág. 486.
↑ Bruto, 2008 , p. 29
↑ Fraleigh, 1993 , pág. 103.
↑ Sagan, 1991 , pág. 2.
↑ Rotman, 2006 , pág. 118, prop. 2.35.
↑ Rotman, 2006 , pág. 122.

Literatura

Anderson M., Feil T. . Un primer curso de álgebra abstracta. 2ª edición. — Boca Ratón: Chapman & Hall/CRC, 2005. — 696 p. — ISBN 1-58488-515-7 .
Fraleigh J. Un primer curso de álgebra abstracta. 5ª edición. - Lectura: Addison-Wesley, 1993. - 576 p. - ISBN 978-0-201-53467-2 .
Rotman J. J. Un primer curso de álgebra abstracta con aplicaciones. 3ra edición. - Upper Saddle River: Prentice Hall, 2006. - 581 p. — ISBN 978-0-13-186267-8 .
Sagan BE El grupo simétrico: representaciones, algoritmos combinatorios y funciones simétricas . - Belmont: Wadsworth, 1991. - 197 p. — ISBN 978-0-534-15540-7 .
Bogart K. P. Combinatoria introductoria. 2ª edición. - San Diego: Harcourt, Brace, Jovanovich, 1990. - 622 p. — ISBN 0-15-541576-X .
Bruto J.L. Métodos Combinatorios con Aplicaciones Informáticas. - Boca Raton: Chapman & Hall/CRC, 2008. - xvii + 644 p. — ISBN 978-1-58488-743-0 .

Enlaces

Permutaciones como producto de transposiciones