## You are here

Homeevery permutation has a cycle decomposition

## Primary tabs

# 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<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\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.

## Mathematics Subject Classification

03-00*no label found*05A05

*no label found*20F55

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections