The Order Theorem for Permutations

The Order Theorem for Permutations

Recall from The Order of a Permutation page that if $\sigma$ is a permutation of the elements in $\{1, 2, ..., n \}$ then the order of $\sigma$ is the smallest positive integer $m$ such that $\sigma^m = \epsilon$ which we denote:

(1)
\begin{align} \quad \mathrm{order} (\sigma) = m \end{align}

We proved that $\mathrm{order}(\sigma) = 1$ if and only if $\sigma = \epsilon$ where $\epsilon$ is the identity permutation. We also proved that if $\alpha = (a_1a_2...a_s)$ is a cycle of length $s$ then $\mathrm{order} (\alpha) = s$.

So what exactly can be said about the order of a general permutation? Consider the set $\{1, 2, 3, 4, 5, 6, 7 \}$ and the following permutation:

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

We can represent this permutation with the following diagram which illustrates the decomposition this permutation into disjoint cycles:

Screen%20Shot%202015-09-10%20at%207.04.24%20AM.png

From the diagram above, we see that applying $\sigma$ each time maps $6$ to $6$ and $7$ to $7$. Applying $\sigma$ twice maps $1$ to $1$ and $2$ to $2$. Applying $\sigma$ three times maps $3$ to $3$, $4$ to $4$, and $5$ to $5$. Therefore, if $m^*$ is a multiple of $1$, $2$, and $3$, them $\sigma^{m^*} = \epsilon$. However, $m^*$ need not equal $m$ if $m^*$ is not the smallest positive integer that satisfies $\sigma^m = \epsilon$. In fact, as we will see in the following theorem, $m$ will be the least common multiple of orders of the disjoint cycles that compose $\sigma$.

Theorem 1 (The Order Theorem for Permutations): Let $\sigma$ be a permutation of the elements in $\{1, 2, ..., n \}$ and let $t_1 \circ t_2 \circ ... \circ t_k$ be the decomposition of $\sigma$ into disjoint cycles $t_1, t_2, ..., t_k$ with orders $m_1, m_2, ..., m_k$ respectively. Then $\mathrm{order} (\sigma) = \mathrm{lcm} \{ m_1, m_2, ..., m_k \}$.
  • Recall that if $\sigma$ is a permutation of the elements in $\{1, 2, ..., n \}$ then $\sigma$ can be written as a finite product of $k$ disjoint cycles, say:
(3)
\begin{align} \quad \sigma = t_1 \circ t_2 \circ ... \circ t_k \end{align}
  • Each of these cycles $t_1, t_2, ..., t_k$ has an order. Denote them by $\mathrm{order} (t_1) = m_1$, $\mathrm{order} (t_2) = m_2$, …, $\mathrm{order} (t_k) = m_k$, and let $\mathrm{order} (\sigma) = m$. Then:
(4)
\begin{align} \quad \sigma^m = (t_1 \circ t_2 \circ ... \circ t_k)^m = \epsilon \end{align}
  • We have already proven on the Basic Theorems Regarding Disjoint Cycles page that if $\alpha$ and $\beta$ are disjoint cycles then for any positive integer $m$ that $(\alpha \circ \beta)^m = \alpha^m \circ \beta^m$, and so:
(5)
\begin{align} \quad \sigma^m = t_1^m \circ t_2^m \circ ... \circ t_k^m = \epsilon \end{align}
  • Now notice that $t_1^m \circ t_2^m \circ ... \circ t_k^m = \epsilon$ if and only if $t_1^m = \epsilon$, $t_2^m = \epsilon$, and $t_k^m = \epsilon$ (see the link above to when we proved this). However, for each $i \in \{1, 2, ..., k \}$ we have that $t_i^m = \epsilon$ if and only if $m = j_im_i$ for some positive integer $j_i$. Therefore we must have that $m$ is the smallest integer such that $m_i \mid m$ for all $i \in \{1, 2, ..., k \}$. In other words:
(6)
\begin{align} \quad m = \mathrm{lcm} \{ m_1, m_2, ..., m_k \} \quad \blacksquare \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License