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
.