Decomposition of Permutations as Products of Disjoint Cycles

Recall from the Permutations as Products of Cycles page that if we are given a finite $n$-element set $\{1, 2, ..., n \}$ and say $\alpha = (a_1a_2...a_s)$ and $\beta = (b_1b_2...b_t)$ are two cycles (and hence permutations themselves) then the composition $\alpha \circ \beta$ is equal to some permutation $\sigma$. In fact, it's not hard to see that for all permutations of elements in $\{ 1, 2, ..., n \}$ that $\sigma$ can be written as some finite product of cycles. To illustrate this, consider the following permutation:

(1)

\begin{align} \quad \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 1 & 3 & 5 \end{pmatrix} \end{align}

Any fixed elements, i.e., elements $a \in \{ 1, 2, 3, 4, 5 \}$ such that $\sigma (a) = a$, will not be in a cycle. Now notice that $\sigma(1) = 2$, $\sigma(2) = 4$, $\sigma (4) = 3$, and $\sigma(3) = 1$. Hence if we let $\alpha = (1243)$ and $\beta$ be the identity bijection then:

(2)

\begin{align} \quad \sigma = \alpha \end{align}

In general, any fixed elements $a \in \{ 1, 2, ..., n \}$ will not appear in the product, and all other elements must then form a cycle of at minimum length $2$. Using the procedure described above will actually always yield a product of disjoint cycles which we guarantee with the theorem below.

Theorem 1: Let $\sigma$ be a permutation of the set $\{ 1, 2, ..., n \}$. If $\sigma$ is not the identity permutation $\epsilon$, then $\sigma$ can be written uniquely as a single cycle or a finite product of disjoint cycles.

For simplicity's sake, we will say that if $\sigma$ is itself the identity permutation or if $\sigma$ is wholly a cycle, then $\sigma$ can be written trivially as a product of a single cycle. Hence the statement, "$\sigma$ can be written as a finite product of disjoint cycles" will not be ambiguous.

• Proof: Let $\sigma$ be a permutation of the set $\{ 1, 2, ..., n \}$ where $\sigma$ is not the identity bijection.

• Let $a_1 \in \{ 1, 2, ..., n \}$ be the first smallest element such that $\sigma(a_1) \neq a_1$. Then for some $a_2, a_3, ..., a_k \in \{1, 2, ..., n \}$ we have that $\sigma(a_1) = a_2$, [$\sigma(a_2) = a_3$, …, $\sigma(a_{k-1}) = a_k$.

• Let $k$ be such that $\sigma (a_k) = a_i$ for some $i \in \{1, 2, ..., k \}$. If $\sigma (a_k) = a_2$ then a contradiction arises since $\sigma(a_1) = \sigma(a_k)$ and $a_1 \neq a_k$ so $\sigma$ would not be injective (and all permutations are bijective by definition). If $\sigma (a_k) = a_3$ or $\sigma (a_k) = a_4$, …, or $\sigma (a_k) = a_k$ then the same sort of contradiction arises. Therefore $\sigma (a_k) = a_1$ and hence:

(3)

\begin{align} \quad a_1 \to a_2 \to ... \to a_k \to a_1 \end{align}

• Therefore $(a_1a_2...a_k)$ is a cycle.

• Now let $b_1 \in \{ 1, 2, ..., n \}$ be the smallest element such that $\sigma (b_1) \neq b_1$ and such that $b_1 \not \in \{ a_1, a_2, ..., a_k \}$. We repeat the process described above to get a cycle $(b_1b_2...b_j)$ where $a_s \neq b_t$ for all $s \in \{ 1, 2, ..., k \}$ and for all $t \in \{ 1, 2, ..., j \}$.

• Since $\{ 1, 2, ..., n \}$ is a finite set, this process must eventually end with $\sigma$ decomposed as a finite product of disjoint cycles. $\blacksquare$