View source for 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|[[permutation IAPS admits unique class factorization]]}}

==Proof==

Let <math>S</math> be the finite set and <math>\sigma:S \to S</math> be a permutation.

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

<math>(a, \sigma(a) ,\sigma^2(a), \dots, \sigma^{r-1}(a))</math>

Thus, every element of <math>S</math> is part of a cycle. Moreover, any cycle containing <math>a</math> ''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 <math>a,b \in S</math>. Then, if the cycles of <math>a</math> and <math>b</math> are not disjoint, there exist <math>j,k</math> such that <math>\sigma^j(b) = \sigma^k(a)</math>. This forces <math>b = \sigma^{k-j}(a)</math>, so <math>b</math> is in the cycle of <math>a</math>. But then, starting the cycle at <math>b</math>, we see that the cycle of <math>b</math> is the same as the cycle of <math>a</math>.