# every permutation has a cycle decomposition

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\leq i\leq n\}$, then there exists a cycle $(y_{1},\ldots y_{m})$ where

 $\{y_{i}\mid 1\leq i\leq m\}\subseteq\{x_{i}\mid 1\leq i\leq n\}$

and a permutation $g$ of $\{x_{i}\mid 1\leq i\leq 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:

 $\displaystyle z_{1}$ $\displaystyle=z$ $\displaystyle z_{k+1}$ $\displaystyle=f(z_{k})$

Note that we cannot have $z_{k+1}=z_{k}$ for any $k$. This follows from a simple induction argument. By definition $f(z_{1})=f(z)\neq z=z_{1}$. Suppose that $f(z_{k})\neq z_{k}$ but that $f(z_{k+1})=z_{k+1}$. By definition, $f(z_{k})=z_{k+1}$. Since $f$ is a permutation, $f(z_{k})=z_{k+1}$ and $f(z_{k+1})=z_{k+1}$ imply that $z_{k}=z_{k+1}$, so $z_{k}=f(z_{k})$, which contradicts a hypothesis. Hence, if $f(z_{k})\neq z_{k}$, then $f(z_{k+1})\neq z_{k+1}$ so, by induction, $f(z_{k})\neq z_{k}$ for all $k$.

By the pigeonhole principle, there must exist $p$ and $q$ such that $p 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. 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\leq i\leq m\}$ is closed under $f$, it follows that

 $\{x_{i}\mid 1\leq i\leq n\}\setminus\{y_{i}\mid 1\leq i\leq m\}$

is also closed under $f$. Define $g$ as follows:

 $g(z)=\begin{cases}z&z\in\{y_{i}\mid 1\leq i\leq m\}\\ f(z)&z\in\{x_{i}\mid 1\leq i\leq n\}\setminus\{y_{i}\mid 1\leq i\leq m\}\end{cases}$

Then it is easily verified that $f=(y_{1},\ldots y_{m})\circ g$.

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.

Title every permutation has a cycle decomposition EveryPermutationHasACycleDecomposition 2013-03-22 16:48:39 2013-03-22 16:48:39 rspuzio (6075) rspuzio (6075) 10 rspuzio (6075) Proof msc 03-00 msc 05A05 msc 20F55