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 $f$ is a non-trivial permutation of a set $\{ x_i \mid 1 \le i \le n \}$ , then there exists a cycle $(y_1, \ldots y_m)$ where $$ \{ y_i \mid 1 \le i \le m \} \subseteq \{ x_i \mid 1 \le i \le n \} $$ and a permutation $g$ of $\{ x_i \mid 1 \le i \le n \}$ such that $f = (y_1, \ldots y_m) \circ g$ and $g(y_i) = y_i$ .

Since the permutation is not trivial, there exists $z$ such that $f(z) \neq z$ . Define a sequence inductively as follows:

By the pigeonhole principle, there must exist $p$ and $q$ such that $p < q$ but $f(z_p) = f(z_q)$ . Let $m$ be the least integer such that $f(z_p) = f(z_{p+m})$ but $f(z_p) \neq f(s_{p+k})$ when $k < m$ . Set $y_k = z_{k+p}$ . Then we have that $(y_1, \ldots y_m)$ is a cycle.

Since $f$ is a permutation and $\{ y_i \mid 1 \le i \le m \}$ is closed under $f$ , it follows that $$ \{ x_i \mid 1 \le i \le n \} \setminus \{ y_i \mid 1 \le i \le m \} $$ is also closed under $f$ . Define $g$ as follows:

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 $n$ elements can be decomposed into cycles. Let $f$ be a permutation on a set with $n$ elements. Then, by what we have shown, $f$ can be written as the product of a cycle and a permutation $g$ which fixes the elements of the cycle. The restriction of $g$ to those elements $z$ such that $g(z) \neq z$ is a permutation on less than $n$ elements and hence, by our supposition, can be decomposed into cycles. Thus, $f$ can also be decomposed into cycles. By induction, we conclude that any permutation of a finite set can be decomposed into cycles.