Cycles in Permutations

Consider the set $\{1, 2, 3, 4, 5, 6 \}$ and the following permutation:

(1)

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

Notice that $\sigma(1) = 2$, and $\sigma(2) = 1$. Therefore:

(2)

\begin{align} \quad (\sigma \circ \sigma)(2) = \sigma(\sigma(1)) = 1 \end{align}

Also notice that $\sigma(3) = 4$, $\sigma(4) = 5$, $\sigma(5) = 6$, and $\sigma(6) = 3$. Therefore:

(3)

\begin{align} \quad (\sigma \circ \sigma \circ \sigma \circ \sigma)(3) = \sigma(\sigma(\sigma(\sigma(3)))) = 3 \end{align}

We can represent these "cycles" in this permutation with the following set of directed graphs:

Definition: Consider the $n$-element set $\{ 1, 2, ..., n \}$. If $\sigma$ is a permutation of this set then a Cycle of length $s$ denoted by $(a_1a_2...a_n)$ for which $a_1, a_2, ..., a_s \in \{ 1, 2, ..., n \}$ are distinct elements, is a permutation where $\sigma (a_1) = a_2$, $\sigma(a_2) = a_3$, …, $\sigma(a_{s-1}) = a_s$, $\sigma(a_s) = a_1$ and where all other elements in the permutation are mapped to themselves.

Cycles themselves are indeed permutations as well!

From above, we see that the permutation $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 1 & 4 & 5 & 6 & 3 \end{pmatrix}$ has two cycles, namely:

(4)

\begin{align} \quad (12) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 1 & 3 & 4 & 5 & 6 \end{pmatrix} , \quad (3456) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 2 & 4 & 5 & 6 & 3 \end{pmatrix} \end{align}

We can also compose cycles. Let $\alpha = (12)$ and $\beta = (3456)$ and consider the composition $(\alpha \circ \beta)(x) = \alpha(\beta(x))$ for all $x \in \{ 1, 2, 3, 4, 5, 6 \}$. We have that $(\alpha(\beta(1)) = \alpha(1) = 2$, $(\alpha(\beta(2)) = \alpha(2) = 1$, $\alpha(\beta(3)) = \alpha(4) = 4$, $\alpha(\beta(4)) = \alpha(5) = 5$, $\alpha(\beta(5)) = \alpha(6) = 6$, and $\alpha(\beta(6)) = \alpha(3) = 3$, and so:

(5)

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