Disjoint-Cycle Decomposition
Every is a product of disjoint cycles, uniquely up to cyclic shifts within each cycle and reordering the cycles.
Theorem 8.7 (Disjoint Cycles)
Every can be written as a product of disjoint cycles. This expression is unique up to
Proof
The action of on partitions the set into orbits. Choosing one representative from each orbit gives
where is the size of the orbit of . Changing an orbit representative cyclically shifts its cycle, and changing the order of the orbits reorders the cycles.
Related
Stated in
- Theorem 8.7 (Disjoint Cycles)§8.1 Permutations and Cycle Notation