Disjoint Cycles

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

Now suppose that we have two cycles of elements from $\{ 1, 2, ..., n \}$. One way to compare these cycles is to see whether they "move" any elements in common. If two cycles do not move any elements in common, then we give the pair of cycles a special name which we define below.

Definition: If $(a_1a_2...a_s)$ and $(b_1b_2...b_t)$ are cycles of $\{1, 2, ..., n \}$ then these cycles are said to be Disjoint if $a_i \neq b_j$ for all $i \in \{1, 2, ..., s \}$ and for all $j \in \{1, 2, ..., t \}$.

If $\alpha \circ \beta = \sigma$ then it is common to say that $\sigma$ is the Product of $\alpha$ and $\beta$.

For example, consider the set $\{ 1, 2, 3, 4, 5, 6 \}$ and the following cycles:

(1)

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

We see that the numbers in the parentheses between both cycles are difference. Hence $(23)$ and $(165)$ are disjoint cycles. Also notice that:

(2)

\begin{align} \quad (23) \circ (165) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 3 & 2 & 4 & 5 & 6 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 6 & 2 & 3 & 4 & 1 & 5 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 6 & 3 & 2 & 4 & 1 & 5 \end{pmatrix} \end{align}

We also have that:

(3)

\begin{align} \quad (165) \circ (23) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 6 & 2 & 3 & 4 & 1 & 5 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 3 & 2 & 4 & 5 & 6 \end{pmatrix} \circ = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 6 & 3 & 2 & 4 & 1 & 5 \end{pmatrix} \end{align}

Therefore $(23) \circ (165) = (165) \circ (23)$. In general, if $\alpha$ and $\beta$ are cycles then $\alpha$ and $\beta$ need not commute. This gives us the following theorem:

Theorem 1: $(S_n, \circ)$ is non-abelian for all $n \geq 3$.

• Proof: Consider the cycles $(12), (13) \in S_n$. It is easy to check that $(12) \circ (13) = (132) \neq (123) = (13) \circ (12)$, and so $(S_n, \circ)$ is non-abelian for $n \geq 3$. $\blacksquare$

As we will see in the following proposition - if $\alpha$ and $\beta$ are instead disjoint cycles then they'll always commute.

Proposition 2: If $\alpha$ and $\beta$ are disjoint cycles of the set $\{ 1, 2, ..., n \}$ then $\alpha \circ \beta = \beta \circ \alpha$.

• Proof: Let $\alpha = (a_1a_2...a_s)$ and $\beta = (b_1b_2...b_t)$ be disjoint cycles of the set $\{1, 2, ..., n \}$. Then $a_i \neq b_j$ for all $i \in \{1, 2, ..., s \}$ and for all $j \in \{ 1, 2, ..., t \}$.

• For each each $x \in \{1, 2, ..., n \}$ we have that:

(4)

\begin{align} \quad \beta (x) = \left\{\begin{matrix} x & \mathrm{if} \: x \neq b_j \: \mathrm{for \: all} \: j \in \{1, 2, ... t\}\\ b_j & \mathrm{if} \: \mathrm{otherwise} \end{matrix}\right. , \quad \alpha (x) =\left\{\begin{matrix} x & \mathrm{if} \: x \neq a_i \: \mathrm{for \: all} \: i \in \{1, 2, ..., s \}\\ a_i & \mathrm{otherwise} \end{matrix}\right. \end{align}

• First consider the composition $\alpha \circ \beta$ of applying $\beta$ first and then $\alpha$. Let $x \in \{1, 2, ..., n \}$. There are three cases to consider. Firstly, if $x \neq a_i$ and $x \neq b_j$ for all $i \in \{ 1, 2, ..., s \}$ and for all $j \in \{ 1, 2, ..., t \}$ then $\alpha(\beta(x)) = x$. Secondly, if $x \neq b_j$ for all $j \in \{ 1, 2, ..., t \}$ and $x$ equals one of the $a$s, then $\alpha(\beta(x)) = a_i$ for some $i$. Thirdly, if $x$ is equal to one of the $b$s and $x \neq a_i$ for all $i \in \{1, 2, ..., s \}$ then $\alpha(\beta(x)) = \alpha(b_j) = b_j$ for some $j$. (Note that the fourth case occurs when $x = a_i$ and $x = b_j$ for some $i \in \{1, 2, ..., s \}$ and $j \in \{1, 2, ..., t \}$ which cannot happen since $\alpha$ and $\beta$ are disjoint).

• Now consider the composition $\beta \circ \alpha$ of applying $\alpha$ first and then $\beta$. Let $x \in \{1, 2, ..., n \}$ again. Then there are, once again, three cases to consider. Firstly, if $x \neq a_i$ and $x \neq b_j$ for all $i \in \{1, 2, ..., s \}$ and for all $j \in \{1, 2, ..., t \}$ then $\beta (\alpha(x)) = x$. Secondly, if $x \neq a_i$ for all $i \in \{1, 2, ..., t \}$ and $x$ equals one of the $b$s then $\beta(\alpha(x)) = b_j$ for some $j$. Thirdly, if $x$ is equal to one of the $a$s and $x \neq b_j$ for all $j \in \{1, 2, ..., t \}$ then $\beta(\alpha(x)) = \beta(a_i) = a_i$ for some $i$.

• The first cases for $\alpha \circ \beta$ and $\beta \circ \alpha$ correspond. The second case of $\alpha \circ \beta$ corresponds to the third case of $\beta \circ \alpha$, and the third case of $\alpha \circ \beta$ corresponds to the second case of $\beta \circ \alpha$. Between all of these correspondences we see that $\alpha(\beta(x)) = \beta(\alpha(x))$. Since $x$ was arbitrary, we conclude that:

(5)

\begin{align} \quad \alpha \circ \beta = \beta \circ \alpha \quad \blacksquare \end{align}