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.

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