Theorem 9.8
Return to Theorems, Glossary, Homework Problems.
Statement:
Every permutation $\sigma$ of a finite set is a product of disjoint cycles.
Proof:
Let $B_{1},B_{2},...,B_{r}$ be the orbits of $\sigma$, and let $\mu_{i}$ be the cycle defined by:
$\mu_{i}(x) = \begin{cases}\sigma(x) \text{ for } x \in B_{i}\\\ x \text{ otherwise }\\ \end{cases}$
Clearly $\sigma = \mu_{1}\mu_{2}...\mu_{r}$. Since the equivalence-class orbits $B_{1},B_{2},...B_{r}$, being distinct equivalence classes, are disjoint, the cycles $\mu_{1},\mu_{2},...,\mu_{r}$ are also disjoint.