Cycle decomposition theorem for permutations

Statement

Statement for a finite set

Any permutation on a finite set admits a cycle decomposition: it can be expressed as a product of a finite number of pairwise disjoint cycles.

Moreover, this cycle decomposition is unique.

Importance

This result has several close analogues. One close analogue is for the general linear group, with the existence of a rational canonical form and a Jordan canonical form. A common framework that unifies results in both contexts is the framework of APS theory. In this framework, we say that the permutation IAPS admits unique class factorization.

Further information: permutation IAPS admits unique class factorization

Proof

Let $S$ be the finite set and $\sigma:S \to S$ be a permutation.

Pick $a \in S$. Then, consider the sequence $a, \sigma(a), \sigma^2(a), \dots$. This sequence must eventually repeat, so there exist $k < l$ such that $\sigma^k(a) = \sigma^l(a)$, so by the definition of group action, we have $\sigma^{l-k}(a) = a$. Let $r$ be the smallest positive integer such that $\sigma^r(a) = a$. Then, we have a cycle:

$(a, \sigma(a) ,\sigma^2(a), \dots, \sigma^{r-1}(a))$

Thus, every element of $S$ is part of a cycle. Moreover, any cycle containing $a$ has to be of the above form (up to a cyclic re-ordering).

It thus suffices to show that any two cycles obtained this way are either equal or disjoint. Suppose $a,b \in S$. Then, if the cycles of $a$ and $b$ are not disjoint, there exist $j,k$ such that $\sigma^j(b) = \sigma^k(a)$. This forces $b = \sigma^{k-j}(a)$, so $b$ is in the cycle of $a$. But then, starting the cycle at $b$, we see that the cycle of $b$ is the same as the cycle of $a$.