Basic Theorems Regarding Disjoint Cycles

Basic Theorems Regarding Disjoint Cycles

Recall from the Disjoint Cycles page that the cycles $\alpha = (a_1a_2...a_s)$ and $\beta = (b_1b_2...b_t)$ of elements in the set $\{ 1, 2, ..., n \}$ 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 \}$. For example, the cycles $(123)$ and $(45)$ of the set $\{1, 2, 3, 4, 5, 6, 7 \}$ are disjoint.

One important theorem we noted was that disjoint cycles always commute. That is, if $\alpha$ and $\beta$ are disjoint cycles then:

(1)
\begin{align} \quad \alpha \circ \beta = \beta \circ \alpha \end{align}

We will now look at some more important theorems regarding disjoint cycles.

Theorem 1: If $\alpha= (a_1a_2...a_s)$ and $\beta = (b_1b_2...b_t)$ are disjoint cycles of $\{ 1, 2, ..., n \}$ then for all positive integers $m$, $(\alpha \circ \beta)^m = \alpha^m \circ \beta^m$.
  • Proof: Since $\alpha$ and $\beta$ are disjoint, they're commutative, and so $\alpha \circ \beta = \beta \circ \alpha$. Hence:
(2)
\begin{align} \quad (\alpha \circ \beta)^m = \underbrace{(\alpha \circ \beta) \circ (\alpha \circ \beta) \circ ... \circ (\alpha \circ \beta)}_{m \: \mathrm{many \: factors}} = \underbrace{(\alpha \circ \alpha \circ ... \circ \alpha)}_{m \: \mathrm{many \: factors}} \circ \underbrace{(\beta \circ \beta \circ ... \circ \beta)}_{m \: \mathrm{many \: factors}} = \alpha^m \circ \beta^m \quad \blacksquare \end{align}
Theorem 2:Let $\alpha= (a_1a_2...a_s)$ and $\beta = (b_1b_2...b_t)$ be disjoint cycles of $\{ 1, 2, ..., n \}$ and let $\epsilon$ be the identity permutation (i.e., $\epsilon : \{ 1, 2, ..., n \} \to \{ 1, 2, ..., n \}$ is the identity bijection such that for all $x \in \{ 1, 2, ..., n \}$ we have that $\epsilon (x) = x$). If $\alpha \circ \beta = \epsilon$ then $\alpha = \beta$.
  • Proof: Let $\alpha \circ \beta = \epsilon$. Then for all $x \in \{ 1, 2, ..., n \}$ we have that:
(3)
\begin{align} \quad \alpha(\beta(x)) = x \end{align}
  • Since $\alpha$ and $\beta$ are disjoint, this happens if and only if for all $x \in \{ 1, 2, ..., n \}$ we have that $\beta(x) = x$ and $\alpha(x) = x$. If not, say $\beta(x) = b_j$ for some $j \in \{1, 2, ..., t \}$ where $x \neq b_j$, then since $\alpha$ and $\beta$ are disjoint we must have that $\alpha(b_j) = b_j$. Therefore:
(4)
\begin{align} \quad \alpha(\beta(x)) = \alpha(b_j) = b_j \end{align}
  • Therefore $\alpha(\beta(x)) = b_j \neq x$ implying that $\alpha \circ \beta \neq \epsilon$ which is a contradiction. Similarly, if instead $\alpha(x) = a_i$ for some $i \in \{1, 2, ... s \}$ where $x \neq a_i$, then since $\alpha$ and $\beta$ are disjoint we must have that $\beta(x) = x$. Therefore:
(5)
\begin{align} \quad \alpha(\beta(x)) = \alpha(x) = a_i \end{align}
  • Therefore $\alpha(\beta(x)) = a_i \neq x$ implying yet again that $\alpha \circ \beta \neq \epsilon$ which is a contradiction. Hence $\alpha = \beta$ as desired. $\blacksquare$
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License