# 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 be the finite set and be a permutation.

Pick . Then, consider the sequence . This sequence must eventually repeat, so there exist such that , so by the definition of group action, we have . Let be the smallest positive integer such that . Then, we have a cycle:

Thus, every element of is part of a cycle. Moreover, any cycle containing *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 . Then, if the cycles of and are not disjoint, there exist such that . This forces , so is in the cycle of . But then, starting the cycle at , we see that the cycle of is the same as the cycle of .