# 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\le i\le n\}$, then there exists a cycle $({y}_{1},\mathrm{\dots}{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},\mathrm{\dots}{y}_{m})\circ g$ and $g({y}_{i})={y}_{i}$.

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

${z}_{1}$ | $=z$ | ||

${z}_{k+1}$ | $=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)\ne z={z}_{1}$. Suppose
that $f({z}_{k})\ne {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})\ne {z}_{k}$,
then $f({z}_{k+1})\ne {z}_{k+1}$ so, by induction,
$f({z}_{k})\ne {z}_{k}$ for all $k$.

By the pigeonhole principle^{}, there must exist $p$ and $q$
such that $$ 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})\ne f({s}_{p+k})$ when $$. Set ${y}_{k}={z}_{k+p}$.
Then we have that $({y}_{1},\mathrm{\dots}{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:

$$g(z)=\{\begin{array}{cc}z\hfill & z\in \{{y}_{i}\mid 1\le i\le m\}\hfill \\ f(z)\hfill & z\in \{{x}_{i}\mid 1\le i\le n\}\setminus \{{y}_{i}\mid 1\le i\le m\}\hfill \end{array}$$ |

Then it is easily verified that $f=({y}_{1},\mathrm{\dots}{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)\ne 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 |
---|---|

Canonical name | EveryPermutationHasACycleDecomposition |

Date of creation | 2013-03-22 16:48:39 |

Last modified on | 2013-03-22 16:48:39 |

Owner | rspuzio (6075) |

Last modified by | rspuzio (6075) |

Numerical id | 10 |

Author | rspuzio (6075) |

Entry type | Proof |

Classification | msc 03-00 |

Classification | msc 05A05 |

Classification | msc 20F55 |