Ciclo (permutación)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Un ciclo que deja fijos a los elementos 2 y 5 y mueve cíclicamente al resto.

Un ciclo es un tipo especial de permutación que fija cierto número de elementos (quizás ninguno) mientras que mueve cíclicamente el resto. En caso de no fijar ningún elemento lo denominaríamos permutación cíclica.

Más concretamente, si un ciclo afecta a un elemento x cualquiera del conjunto, al aplicar dicho ciclo reiteradamente todos los elementos afectados por el reordenamiento pasarán por la posición de x en algún momento. Y de forma recíproca, el elemento x pasará por todas las posiciones de todos los elementos afectados por la permutación.

Los ciclos son tipos de permutación especialmente importantes, pues pueden usarse como piezas básicas para construir cualquier otra permutación.

Definición formal[editar]

Sea n\geq2 y 2\leq r\leq n. Un ciclo de longitud r o r-ciclo de S_n es una permutación \sigma tal que del conjunto \{1,2,...,n\} hay r elementos diferentes secuenciados, a_1,a_2,...,a_r, para los cuales se cumple que:

M(\sigma) = \{a_1,a_2,...,a_r\}, de tal manera que \sigma(x)=x si x\neq a_i \forall i.
\sigma(a_1)=a_2,\sigma(a_2)=a_3,...,\sigma(a_{r-1})=a_r y \sigma(a_r)=a_1.

Ejemplos[editar]

Ejemplo de un ciclo
  • La permutación \sigma es un ciclo que no fija ningún elemento. Por ello, también se dice que es una permutación cíclica.

\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 7 & 6 & 8 \\ 4 & 5 & 7 & 6 & 8 & 1 & 2 & 3 \end{pmatrix} =
\begin{pmatrix} 1 & 4 & 6 & 2 & 5 & 8 & 3 & 7 \\ 4 & 6 & 2 & 5 & 8 & 3 & 7 & 1 \end{pmatrix}
Ejemplo de una permutación formada por dos ciclos
  • La permutación \omega no es un ciclo, ya que es una permutación compuesta por dos ciclos.

\omega = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 7 & 6 & 8 \\ 3 & 4 & 5 & 7 & 6 & 8 & 1 & 2 \end{pmatrix} =\begin{pmatrix} 1 & 3 & 5 & 6 \\ 3 & 5 & 6 & 1 \end{pmatrix} \begin{pmatrix} 2 & 4 & 7 & 8 \\ 4 & 7 & 8 & 2 \end{pmatrix}
De hecho, se demuestra que cualquier permutación puede descomponerse como producto de ciclos disjuntos.[1]
  • Transposición: es un ciclo de longitud 2, es decir, un 2-ciclo.

Propiedades[editar]

Notación: Si un elemento a de un conjunto A se ve 'afectado' por un ciclo \sigma:A\to A entonces decimos que a\in M(\sigma).

  • Sea \sigma un ciclo de longitud r, entonces
Si a \in M(\sigma) entonces se puede escribir como
\sigma = (a,\sigma(a),...,\sigma^{r-1}(a))
y r es el mínimo natural k\geq1 : \sigma^k(a)=a.
  • Sea \sigma un ciclo de longitud r, entonces
\sigma^r = Id y además r es el mínimo natural k\geq1 : \sigma^k = Id.
De ésta proposición se deduce directamente el segundo enunciado de la proposición 1.
  • Sea \sigma un ciclo de longitud r, entonces
\sigma^{r-i}=\sigma^{-i}

Referencias[editar]

  1. Birkhoff & MacLane, A survey of modern algebra, McMillan Publishing, 1977. ISBN 0-02-310070-2

Véase también[editar]