Permutations as Products of Cycles

Recall from the Cycles in Permutations page that if we have the $n$-element set $\{ 1, 2, ..., n \}$ and $\sigma$ is a permutation of this set, then a cycle of length $s$ denoted $(a_1a_2...a_s)$ where $a_1, a_2, ..., a_s \in \{1,2, ..., n \}$ are distinct is a permutation where $\sigma(a_1) = a_2$, $\sigma (a_2) = a_3$, …, $\sigma(a_{s-1}) = a_s$, and $\sigma(a_s) = a_1$ and where all other elements in the permutation are mapped to themselves.

For example, if we consider the set $\{1, 2, 3, 4, 5, 6, 7 \}$ then the cycle $(1462)$ is:

(1)

\begin{align} \quad (1462) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 4 & 1 & 3 & 6 & 5 &2 & 7 \end{pmatrix} \end{align}

Similarly, the cycle $(175)$ is:

(2)

\begin{align} \quad (175) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 7 & 2 & 3 & 4 & 1 & 6 & 5 \end{pmatrix} \end{align}

We also briefly noted that we could take the product (composition) of any two cycles from the same set. From above, if we let $\alpha = (1462)$ and $\beta =(175)$ then $\alpha \circ \beta$ is given by first applying $\beta$ and then $\alpha$. We have that:

(3)

\begin{align} \quad \alpha \circ \beta = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 7 & 1 & 3 & 6 & 4 & 2 & 5 \end{pmatrix} \end{align}

Furthermore, $\beta \circ \alpha$ is given by first applying $\alpha$ and then $\beta$. We have that:

(4)

\begin{align} \quad \beta \circ \alpha = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 4 & 7 & 3 & 6 & 1 & 2 & 5 \end{pmatrix} \end{align}

As we can see, in general, $\alpha \circ \beta \neq \beta \circ \alpha$ unless of course, $\alpha$ and $\beta$ are disjoint cycles as we've already proven on the Disjoint Cycles page.

So the product of cycles from $\{ 1, 2, ..., n \}$ is necessarily a permutation of $\{ 1, 2, ..., n \}$, though, can all permutations of $\{ 1, 2, ..., n \}$ be expressed as a product of cycles? The answer is yes, and in fact, every permutation can be expressed as a product of disjoint cycles as we will prove on the Decomposition of Permutations as Products of Disjoint Cycles page.