Cycle Decompositions

At some point in their life, every mathematics student has computed out the orbits of a permutation (possibly without even realizing it). For instance, if we have the permutation $\sigma = 43512\in S_5$ (written in one-line notation), then we compute the cycle-notation by saying “1 goes to 4, 4 goes 1, 2 goes to 3, …”. This work will eventually show that, in cycle notation, $\sigma = (14)(235)$. An important(?) theorem in elementary algebra is that this process will always decompose a permutation in a product of disjoint cycle types.

It is not too difficult to show that this is the case by using group actions. The trick we will use is to consider the group $G$ generated by $\sigma$ and then passing to the quotient of $G$ by the stabilizer of a particular element of $[5]$. By direct computation, we can see that the orbits of $G$ acting on $[5]$ are ${1,4}$ and ${2, 3, 5}$. Passing to the quotient $G/\mathrm{Stab}(3)$ will isolate the cycle $(235)$, effectively “deleting out” $(14)$.

Theorem. Let $\sigma \in S_n$. Then $\sigma$ has an essentially unique decomposition into a product of disjoint cycles.

Proof (stolen from Dummit and Foote). First, we show existence of the cycle decomposition. We know that the orbits form a partition of $[n]$. Suppose that $O$ is one of the orbits and let $d = |O|$. Recall from our proof of the orbit-stabilizer theorem, there is a bijection $O \to G/\mathrm{Stab}(x)$ given by $\sigma^k(x) = \sigma^k \mathrm{Stab}(x)$. Furthermore, since $G$ is cyclic, the stabilizer of $x$ is normal in $G$ and $G/\mathrm{Stab}(x)$ is cyclic group of order $d$. Accordingly, the unique elements of the quotient are $\sigma^k \mathrm{Stab}(x)$ for $0 \le k < d$. This tells us that the unique elements of $O$ are $\sigma^k(x)$ for $0 \le k < d$. Indeed, if $m \ge d$, then

which then implies $\sigma^{m - r}(x) = x$. And that implies $\sigma^m(x) = \sigma^r(x)$. This tells us that $\sigma$ acts as a $d$-cycle on the orbit $O$. Applying this argument to each orbit of $G$ on $[n]$ shows that there exists a cycle decomposition of $\sigma$.

For essential uniqueness, we can simply choose any element $\sigma^k(x)$ and it is clear that doing so simply results in a cyclic shift of the list we obtained in the proof of existence.