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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License