The Order of a Permutation
The Order of a Permutation
| Definition: If $\sigma$ is a permutation of the elements in $\{ 1, 2, ..., n \}$ then the order of $\sigma$ denoted $\mathrm{order} (\sigma) = m$ is the smallest positive integer $m$ such that $\sigma^m = \epsilon$ where $\epsilon$ is the identity permutation. |
For example, consider the set $\{ 1, 2, 3, 4 \}$ and the following permutation:
(1)\begin{align} \quad \sigma = \begin{pmatrix} 1 & 2 & 3 & 4\\ 4 & 3 & 2 & 1 \end{pmatrix} \end{align}
Applying the permutation $\sigma$ twice yields:
(2)\begin{align} \quad \sigma^2 = \sigma \circ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4\\ 4 & 3 & 2 & 1 \end{pmatrix} \circ \begin{pmatrix} 1 & 2 & 3 & 4\\ 4 & 3 & 2 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 2 & 3 & 4 \end{pmatrix} = \epsilon \end{align}
So $m = 2$ is the smallest positive integer such that $\sigma^m = \epsilon$, so $\mathrm{order} (\sigma) = 2$.
We will now look at two rather simple theorems regarding the order of transpositions and the order of cycles in general.
| Theorem 1: If $\sigma$ is a permutation of the elements in $\{ 1, 2, ..., n \}$ then $\mathrm{order} (\sigma) = 1$ if and only if $\sigma = \epsilon$. |
- Proof: $\Rightarrow$ Suppose that $\mathrm{order}(\sigma) = m = 1$. Then:
\begin{align} \quad \sigma^{m} = \epsilon \\ \quad \sigma^1 = \epsilon \\ \quad \sigma = \epsilon \end{align}
- $\Leftarrow$ Now suppose that $\sigma = \epsilon$. Then $m = 1$ is the smallest positive integer such that $\sigma^m = \epsilon$. Therefore $\mathrm{order} (\sigma) = 1$. $\blacksquare$
| Theorem 2: If $\alpha = (ab)$ is a transposition of $\{ 1, 2, ..., n \}$ then $\mathrm{order} (\alpha) = 2$. |
- Proof: Since $\alpha \neq \epsilon$ we must have that $\mathrm{order}(\alpha) \geq 2$. On the Basic Theorems Regarding Transpositions we proved that for any transposition $\alpha = (ab)$ that:
\begin{align} \quad \alpha = (ab) \circ (ab) = \epsilon \end{align}
- Therefore $\alpha^2 = (ab)^2 = \epsilon$, so $2 \leq \mathrm{order}(\alpha) \leq 2$. Thus $\mathrm{order} (\alpha) = 2$. $\blacksquare$
| Theorem 3: If $\alpha = (a_1a_2...a_s)$ is a cycle of length $s$ from $\{ 1, 2, ..., n \}$ then $\mathrm{order} (\alpha) = s$. |
- Proof: Let $\alpha = (a_1a_2...a_s)$ be a cycle of length $s$ from $\{1, 2, ..., n \}$. Then $\alpha(a_1) = a_2$, $\alpha(a_2) = a_3$, …, $\alpha(a_{s-1}) = a_s$, and $\alpha(a_s) = a_1$.
- Applying $\alpha$ again gives us that $\alpha^2(a_1) = a_3$, $\alpha^2(a_2) = a_4$, …, $\alpha^2(a_{s-1}) = a_1$, and $\alpha^2 (a_s) = a_2$.
- Applying $\alpha$, $s$ times gives us $\alpha^s (a_i) = a_i$ for all $i \in \{ 1, 2, ..., s \}$, and so $\mathrm{order} (\alpha) \leq s$
- Now suppose that $\mathrm{order} = m < s$. Then $\alpha^m = \epsilon$, and for $a_1$ we have that:
\begin{align} \quad \alpha^m (a_1) = \alpha^{m-1} (a_2) = \alpha^{m-2}(a_3) = ... = \alpha(a_m) = a_{m+1} \end{align}
- But $a_{m+1} \neq a_1$, so $\alpha^m \neq \epsilon$ which contradicts our assumption that $\mathrm{order} = m < s$. Hence $s \leq \mathrm{order}(\alpha) \leq s$, so $\mathrm{order} (\alpha) = s$. $\blacksquare$