In this entry, we shall show that every permutation of a finite set can be factored into a product of disjoint cycles. To accomplish this, we shall proceed in two steps.

We begin by showing that, if is a non-trivial permutation of a set , then there exists a cycle where

Since the permutation is not trivial, there exists such that . Define a sequence inductively as follows:

Note that we cannot have for any . This follows from a simple induction argument. By definition . Suppose that but that . By definition, . Since is a permutation, and imply that , so , which contradicts a hypothesis. Hence, if , then so, by induction, for all .

By the pigeonhole principle, there must exist and such that but . Let be the least integer such that but when . Set . Then we have that is a cycle.

Since is a permutation and is closed under , it follows that

We are now in a position to finish the proof that every permutation can be decomposed into cycles. Trivially, a permutation of a set with one element can be decomposed into cycles because the only permutation of a set with one element is the identity permutation, which requires no cycles to decompose. Next, suppose that any set with less than elements can be decomposed into cycles. Let be a permutation on a set with elements. Then, by what we have shown, can be written as the product of a cycle and a permutation which fixes the elements of the cycle. The restriction of to those elements such that is a permutation on less than elements and hence, by our supposition, can be decomposed into cycles. Thus, can also be decomposed into cycles. By induction, we conclude that any permutation of a finite set can be decomposed into cycles.