2 Sets and functions 2.14 Products of disjoint cycles 2.16 Transpositions

2.15 Powers and orders

2.15.1 Powers of a permutation

Since the composition of two permutations is another permutation, we can form powers of a permutation by composing it with itself some number of times.

Definition 2.15.1.

Let $s$ be a permutation and let $m$ be an integer. Then

s^{m}=\begin{cases}s\cdots s\;(m\text{ times})&m>0\\ \operatorname{id}&m=0\\ s^{-1}\cdots s^{-1}\;(-m\text{ times})&m<0\end{cases}

It’s tedious but straightforward to check that for any integers $a$ , $b$ ,

•

$s^{a}\circ s^{b}=s^{a+b}$ , and
•

$(s^{a})^{b}=s^{ab}$

so that some of the usual exponent laws for real numbers hold for composing permutations. The two facts above are called the exponent laws for permutations.

2.15.2 Order of a permutation

Definition 2.15.2.

The order of a permutation $\sigma$ , written $o(\sigma)$ , is the smallest strictly positive number $n$ such that $\sigma^{n}=\operatorname{id}$ .

For example, let

	$\displaystyle s$	$\displaystyle=\begin{pmatrix}1&2&3\\ 2&3&1\end{pmatrix}$
	$\displaystyle t$	$\displaystyle=\begin{pmatrix}1&2&3\\ 2&1&3\end{pmatrix}$

You should check that $s^{2}\neq\operatorname{id}$ but $s^{3}=\operatorname{id}$ , so the order of $s$ is 3, and that $t\neq\operatorname{id}$ but $t^{2}=\operatorname{id}$ so the order of $t$ is 2.

2.15.3 Order of an $m$ -cycle

Lemma 2.15.1.

The order of an $m$ -cycle is $m$ .

Proof.

Let the $m$ -cycle be $a=(a_{0},\ldots,a_{m-1})$ . If $r<m$ then $a^{r}(a_{0})=a_{r}\neq a_{0}$ , so $a^{r}\neq\operatorname{id}$ . On the other hand $a^{m}(a_{0})=a(a_{m-1})=a_{0}$ and in general $a^{m}(a_{i})=a^{i}(a^{m-i}(a_{i}))=a^{i}(a_{0})=a_{i}$ , so $a^{m}=\operatorname{id}$ . ∎