every permutation has a cycle decomposition

In this entry, we shall show that every permutation of afinite 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-trivialpermutation 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 sequenceinductively 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. Bydefinition $f(z_1)=f(z)\ne z=z_1$. Supposethat $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 apermutation, $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)$, whichcontradicts 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 theleast 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:

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 thatevery permutation can be decomposed into cycles.Trivially, a permutation of a set with one elementcan be decomposed into cycles because the onlypermutation of a set with one element is theidentity permutation, which requires no cyclesto decompose. Next, suppose that any set with lessthan $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 asthe product of a cycle and a permutation $g$ whichfixes 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 andhence, by our supposition, can be decomposed intocycles. Thus, $f$ can also be decomposed intocycles. By induction, we conclude that anypermutation of a finite set can be decomposed into cycles.