Ciclos

Ciclos

Um exemplo simples de uma permutação é obtido como segue: escolha quaisquer dois inteiros distintos entre \(1\) e \(k\) , digamos, \(p\) e \(q\) , e escreva \begin{align} \tau (p) &= q,\\ \tau (q) &= p, \\ \tau(i) &= i \text{ if } i\ne p,q. \end{align}

Tal permutação é chamada de transposição porque ele troca dois elementos.

Mais geralmente, seja \(a_1, \ldots, a_k\) ser \(k\) distintos elementos de \(\{1,\ldots,n\}\) . Consideramos a permutação \(\sigma\) definido por \begin{align} \sigma(a_1) &= a_2,\\ \sigma(a_2) &= a_3,\\ &\vdots\\ \sigma(a_{k-1}) &= a_k,\\ \sigma(a_k) &= a_1,\\ \sigma(i) &= i \text{ if } i\not\in \{a_1,\ldots,a_k\}. \end{align}

Uma permutação como essa é chamado de k-ciclo ou um ciclo de comprimento k. Denotamos um ciclo por \((a_1 a_2 \ldots a_k)\) .

Note que \((a_1 a_2 \ldots a_k) = (a_2 a_3 \ldots a_k a_1) = \ldots\) , então há múltiplas formas de escrever o mesmo ciclo.

Cada transposição é um 2-ciclo. O ciclo de identidade \(\sigma(i)=i\) para todos \(i\) é considerado um 1-ciclo.

Disjoint cycles commute. That is, if \((a_1 \ldots a_k)\) and \((b_1 \ldots b_m)\) are cycles with \(\{a_1,\ldots, a_k\} \cap \{b_1,\ldots,b_m\} = \emptyset\) , then \begin{align} (a_1 \ldots a_k)(b_1 \ldots b_m) = (b_1 \ldots b_m)(a_1 \ldots a_k). \end{align}

Every permutation can be written as a product of disjoint cycles. This representation is unique up to the order in which we write the cycles.

Parity of a Permutation

A transposition changes the parity of a permutation. That is, if \(\sigma\) is any permutation and \(\tau\) is a transposition, then the parity of \(\sigma\tau\) is opposite to the parity of \(\sigma\) .

We can write any permutation as a product of transpositions. The parity of a permutation is well defined: it doesn't depend on how we write a permutation as a product of transpositions.

Even and Odd Permutations

A permutation with even parity is called an even permutation. A permutation with odd parity is called an odd permutation.