= Cyclic permutation
{title2=$(a_1\,a_2\,\ldots\,a_k)$}
{wiki}
A <cyclic permutation>, also called a <permutation cycle>, sends $k\geq1$ distinct elements $a_1\mapsto a_2\mapsto\cdots\mapsto a_k\mapsto a_1$ and fixes every element outside this list. Its notation is $(a_1\,a_2\,\ldots\,a_k)$. For example, $(1\,3\,4\,2)$ is the <permutation> with image list $(3,1,4,2)$: all four labels lie on one directed loop. In contrast,
$$
\rho=\begin{pmatrix}1&2&3&4\\3&4&1&2\end{pmatrix}=(1\,3)(2\,4)
$$
has two separate loops, exchanging $1$ with $3$ and $2$ with $4$. It is a <permutation> composed of two <transpositions>, rather than a single <cyclic permutation>.
\Image[/permutation-cycle-structure.png]
{title=Two <permutations> on four labels: one <cyclic permutation> $(1\,3\,4\,2)$ and two <disjoint permutation cycles> $(1\,3)(2\,4)$, with arrows showing every image}
Starting at a different point of the same loop changes the written list but preserves the <cyclic permutation>: $(1\,3\,4\,2)=(3\,4\,2\,1)$. Reversing the direction generally changes the <permutation>; it gives the <inverse function>, here $(1\,2\,4\,3)$. A <transposition> is a <cyclic permutation> of length two; a one-element <permutation cycle> records a <fixed point>. In a <cycle decomposition of a permutation>, one-element <permutation cycles> are usually omitted, with the underlying <set> understood.
The beauty of this representation is that repeated rearrangements become motion around independent loops. Applying $(1\,3\,4\,2)$ four times returns every label to its start, while applying $(1\,3)(2\,4)$ twice already does so. <Disjoint permutation cycles> commute under <function composition>, since each moves only labels the others fix. On $n\geq1$ labels, there are $(n-1)!$ <cyclic permutations> whose single loop contains every label: fix $1$ as the first written entry and order the other $n-1$ labels freely, giving a <factorial>. This is also the count of <cyclic orderings>; choosing a starting position would otherwise count each loop $n$ times. Rotations are identified here, while reversing direction is allowed to give a different <cyclic ordering>.
\b[Proof outline for decomposition.] Starting at any label in a <finite set>, repeatedly apply the <permutation>. The <pigeonhole principle> forces a repeated label. If the first repetition were at a label other than the starting one, its two predecessors would be different labels with the same <image>, contradicting the <injective function> property. This produces a <permutation cycle> returning to the start. Start again at a label not yet visited; the new <permutation cycle> cannot meet an earlier one, since the <bijection> gives every label a unique predecessor. Continue until every label belongs to a loop. The resulting <cycle decomposition of a permutation> is unique up to the order of the <disjoint permutation cycles> and the starting point written in each one. https://math.mit.edu/~fgotti/docs/Courses/C.%20Combinatorial%20Analysis/11.%20Permutations%20I/Permutations%20I.pdf[Felix Gotti, MIT 18.211, lecture 11, definitions 1–2 and the preceding argument]{ref}
Back to article page
