Hispanopedia Wiki
Articulo de referencia

Permutación cíclica

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í...

Hispanopedia WikiContenido en espanolLectura gratuita

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 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 notación de ciclos , las permutaciones cíclicas se denotan mediante 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 ciclo de 4, 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 ciclo de 3 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 la definición más amplia de una permutación cíclica, que permite puntos fijos, cada uno de estos puntos fijos constituye una órbita trivial de la permutación, y existe una única órbita no trivial que contiene todos los puntos restantes. Esto puede usarse 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 con un número finito de elementos puede descomponerse 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 ; así, el segundo ejemplo se compone de un ciclo de 3 elementos y un ciclo de 1 elemento (o punto fijo ), y el tercero se compone de dos ciclos de 2 elementos.

Definición

Una permutación cíclica que consiste en un único ciclo de 8 elementos.

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 lleva 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σ{\displaystyle \sigma }si la restricción deσ{\displaystyle \sigma }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σ.{\displaystyle \sigma .}Así pues, según la definición más permisiva, una permutación de X es cíclica si y solo si X es su único ciclo.

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

(1 4 6 8 3 7)(2)(5)=(1234567842765813)=(1468372546837125){\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 esta permutación 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 (ciclos de 1) y un ciclo de 6.

Con la definición ampliada, existen permutaciones cíclicas que no constan de un solo ciclo.

De manera más formal, para la definición ampliada, una permutaciónσ{\displaystyle \sigma }de un conjunto X , visto como una función biyectivaσ:incógnita→incógnita{\displaystyle \sigma :X\to X}, se denomina ciclo si la acción sobre X del subgrupo generado porσ{\displaystyle \sigma }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. Seas0{\displaystyle s_{0}}Sea cualquier elemento de S y pongamossi=σi(s0){\displaystyle s_{i}=\sigma ^{i}(s_{0})}para cualquieri∈Z{\displaystyle i\in \mathbf {Z} }. Si S es finito, existe un número mínimok≥1{\displaystyle k\geq 1}para quésk=s0{\displaystyle s_{k}=s_{0}}. EntoncesS={s0,s1,…,sk−1}{\displaystyle S=\{s_{0},s_{1},\ldots ,s_{k-1}\}}, yσ{\displaystyle \sigma }es la permutación definida por

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

yσ(incógnita)=incógnita{\displaystyle \sigma (x)=x}para cualquier elemento deincógnita∖S{\displaystyle X\setminus S}. Los elementos no fijados porσ{\displaystyle \sigma }puede ser imaginado como

s0↦s1↦s2↦⋯↦sk−1↦sk=s0{\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 compacta.σ=(s0 s1 … sk−1){\displaystyle \sigma =(s_{0}~s_{1}~\dots ~s_{k-1})}(En esta notación no se utilizan comas entre los elementos 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.

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 ciclos, los 1-ciclos suelen omitirse cuando no se produce confusión. [ 8 ]

Propiedades básicas

Uno de los resultados básicos sobre 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 signatura como la clase de conjugación de la permutación en el grupo simétrico están determinadas por ella. [ 9 ]

Se da el número de k -ciclos en el grupo simétrico S n , para1≤k≤norte{\displaystyle 1\leq k\leq n}, mediante las siguientes fórmulas equivalentes: (nortek)(k−1)¡=norte(norte−1)⋯(norte−k+1)k=norte¡(norte−k)¡k.{\displaystyle {\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n!}{(nk)!k}}.}

Un ciclo k tiene signatura (−1) k  −  1 .

El inverso de un cicloσ=(s0 s1 … sk−1){\displaystyle \sigma =(s_{0}~s_{1}~\dots ~s_{k-1})}se obtiene invirtiendo el orden de las entradas:σ−1=(sk−1 … s1 s0){\displaystyle \sigma ^{-1}=(s_{k-1}~\dots ~s_{1}~s_{0})}. En particular, dado que(a b)=(b a){\displaystyle (a~b)=(b~a)}Cada ciclo de dos elementos es su propio inverso. Dado que los ciclos disjuntos conmutan, el inverso de un producto de ciclos disjuntos es el resultado de invertir cada uno de los ciclos por separado.

Transposiciones

Matriz deπ{\displaystyle \pi }

Un ciclo con solo dos elementos se llama transposición . Por ejemplo, la permutaciónπ=(12341432){\displaystyle \pi ={\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}}que intercambia 2 y 4. Dado que es un ciclo de 2, se puede escribir comoπ=(2 4){\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 permuta es {1, 2, ..., n } para algún entero n , entonces cualquier permutación puede expresarse como un producto detransposiciones adyacentes(1 2),(2 3),(3 4),{\displaystyle (1~2),(2~3),(3~4),}y así sucesivamente. Esto se deduce porque una transposición arbitraria puede expresarse como el producto de transposiciones adyacentes. Concretamente, se puede expresar la transposición(k  l){\displaystyle (k~~l)}dóndek<l{\displaystyle k<l}moviendo k a l un paso a la vez, y luego moviendo l de vuelta a donde estaba k , lo que intercambia estos dos y no produce ningún otro cambio:

(k  l)=(k  k+1)⋅(k+1  k+2)⋯(l−1  l)⋅(l−2  l−1)⋯(k  k+1).{\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 o más en un producto de una transposición y un ciclo de longitud uno menos:

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

Esto significa que la solicitud inicial es para movera{\displaystyle a}ab,{\displaystyle b,}b{\displaystyle b}ado,{\displaystyle c,}y{\displaystyle y}az,{\displaystyle z,}y finalmentez{\displaystyle z}aa.{\displaystyle a.}En cambio, uno puede hacer rodar los elementos manteniendoa{\displaystyle a}donde se ejecuta 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 movidoz{\displaystyle z}al puesto deb,{\displaystyle b,}así que después de la primera permutación, los elementosa{\displaystyle a}yz{\displaystyle z}aún no están en sus posiciones finales. La transposición(a b),{\displaystyle (a~b),}ejecutado posteriormente, luego abordaz{\displaystyle z}por el índice deb{\displaystyle b}cambiar lo que inicialmente erana{\displaystyle a}yz.{\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 tienen una forma determinada.

Uno de los principales resultados sobre grupos simétricos establece que todas las descomposiciones de una permutación dada en transposiciones tienen un número par de transposiciones, o bien 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

Notas

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

Referencias

  1. 1 2 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. 1 2 Knuth, Donald E. (2002). El arte de la programación informática . Addison-Wesley. pág. 35. 
  3. 1 2 3 Bogart, Kenneth P. (2000). Combinatoria introductoria (3.ª ed.). Londres: Harcourt Academic Press. pág. 554. ISBN   978-0-12-110830-4.
  4. 1 2 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ágs. 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

Este artículo incorpora material de cycle en PlanetMath , que está bajo la licencia Creative Commons Attribution/Share-Alike License .