Order of a Permutation

The order of a permutation is the smallest positive integer for which repeatedly applying the permutation brings every element back to its original position.

To determine the order of a permutation, follow the standard procedure.

Rewrite the permutation as a product of disjoint cycles.
Identify the length of each cycle.
Compute the least common multiple of these lengths.

The least common multiple of the cycle lengths is precisely the order of the permutation.

Note. The word "period" is sometimes used as a synonym for the order of a permutation. The term is borrowed from periodic phenomena in analysis, although the meaning here is completely analogous. Whether one says "order" or "period", the underlying concept is identical.

A Practical Example

Consider the following permutation written in two line notation.

$$ \sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} $$

This permutation is a single 3-cycle, namely (1 2 3). Here 1 maps to 2, 2 maps to 3 and 3 maps back to 1.

Applying the permutation three times, that is $2, 3, 1 \rightarrow 3, 1, 2 \rightarrow 1, 2, 3$, returns the set to its initial arrangement.

First application $$ \sigma_1 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} $$
Second application $$ \sigma_2 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} $$
Third application $$ \sigma_3 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = id $$

The order of this permutation is therefore 3.

Example 2

Now examine the following permutation.

$$ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 4 & 5 & 6 & 1 & 2 \end{pmatrix} $$

This permutation decomposes into two disjoint cycles.

In cycle notation it becomes:

$$ (1 \ 3 \ 5)(2 \ 4 \ 6) $$

We now compute the lengths of the cycles.

The cycle $(1, 3, 5)$ has length 3, since 1→3, 3→5 and 5→1.
The cycle $(2, 4, 6)$ also has length 3 because 2→4, 4→6 and 6→2.

The order is the least common multiple of the cycle lengths.

$$ mcm(3,3)=3 $$

Thus the order of the permutation is 3. After three iterations, the permutation returns every element to its initial position.

Verification. The successive powers of the permutation confirm this. $$ \sigma_1 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 4 & 5 & 6 & 1 & 2 \end{pmatrix} $$ $$ \sigma_2 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 6 & 1 & 2 & 3 & 4 \end{pmatrix} $$ $$ \sigma_3 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6 \end{pmatrix} = id $$ After three iterations we obtain the identity, as expected.

Example 3

Consider now the permutation of {1, 2, 3, 4, 5, 6} expressed in disjoint cycle notation:

$$ (1 \ 2 \ 4)(3 \ 6) $$

This permutation contains two cycles: (1 2 4) and (3 6).

Note. The element 5 does not appear in any cycle, which means it is a fixed point: 5→5. It is left unchanged by the permutation.

We compute the cycle lengths.

The cycle (1 2 4) has length 3 because 1→2, 2→4 and 4→1.
The cycle (3 6) has length 2 because 3→6 and 6→3.

The order is given by the least common multiple:

$$ mcm(3, 2) = 6 $$

So the order of the permutation is 6. Six successive applications return each element to its starting position.

Verification. The full sequence of powers is shown below, using two line notation for clarity. $$ \sigma_1 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 6 & 1 & 5 & 3 \end{pmatrix} $$ $$ \sigma_2 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 2 & 5 & 6 \end{pmatrix} $$ $$ \sigma_3 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 6 & 4 & 5 & 3 \end{pmatrix} $$ $$ \sigma_4 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 3 & 1 & 5 & 6 \end{pmatrix} $$ $$ \sigma_5 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 6 & 2 & 5 & 3 \end{pmatrix} $$ $$ \sigma_6 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 4 & 5 & 6 \end{pmatrix} = id $$ As expected, the sixth iterate is the identity.

Example 4

Finally, consider the following permutation of the set {1, 2, 3, 4, 5, 6, 7, 8}:

$$ (1 \ 2 \ 3)(4 \ 5)(6 \ 7 \ 8) $$

This permutation consists of three disjoint cycles.

We compute the length of each cycle.

The cycle $(1 \ 2 \ 3)$ has length 3.
The cycle $(4 \ 5)$ has length 2.
The cycle $(6 \ 7 \ 8)$ has length 3.

The order is the least common multiple of these lengths.

$$ mcm(3, 2, 3) = 6 $$

Thus the permutation $(1 \ 2 \ 3)(4 \ 5)(6 \ 7 \ 8)$ has order 6.

After six applications, every element returns to its original position.

And so on.