Cycle decomposition theorem for permutations
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.
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
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 .