Order of a Permutation

A bijective mapping on a finite set S is called a permutation on S. In this post, we will discuss the order of a permutation, how to find the order of a permutation with examples, and related theorems.

Definition of Order of a Permutation

Order of permutation:- The order of a permutation σ on a finite set S is the least positive integer n such that σn=i where i denotes the identity permutation on S.

By definition, the order of the identity permutation is 1.

Example of Order of permutation:- Let σ= $\left( {\begin{array}{*{20}{c}}1&2&3 \\ 2&3&1 \end{array}} \right)$ be a permutation on {1, 2, 3}.

Now, σ2 = $\left( {\begin{array}{*{20}{c}}1&2&3 \\ 2&3&1 \end{array}} \right)$ $\left( {\begin{array}{*{20}{c}}1&2&3 \\ 2&3&1 \end{array}} \right)$

= $\left( {\begin{array}{*{20}{c}}1&2&3 \\ 3&1&2 \end{array}} \right)$

⇒ σ3 = σ2 ⋅ σ

= $\left( {\begin{array}{*{20}{c}}1&2&3 \\ 3&1&2 \end{array}} \right)$ $\left( {\begin{array}{*{20}{c}}1&2&3 \\ 2&3&1 \end{array}} \right)$

= $\left( {\begin{array}{*{20}{c}}1&2&3 \\ 1&2&3 \end{array}} \right)$

= i, the identity permutation on {1, 2, 3}

Thus 3 is the least positive integer such that σ3=i. So the order of σ is 3.

How to Find Order of a Permutation

The order of a given permutation is determined by the least common multiple of the lengths of the cycles in the decomposition of the given permutation into disjoint cycles. This will be proved in the theorem below.

Theorem: The order of a permutation on a finite set is the least common multiple (lcm) of the lengths of its disjoint cycles.

Proof:

Let σ be a permutation on a set S={1, 2, 3, …, n}. We assume that

σ = σ1 σ2 … σm

is the decomposition of σ as the product of disjoint cycles σ1, σ2, …, σm of lengths r1, r2, …, rm. We have

σ1r1 = i, σ2r2 = i, …, σmrm = i.

As the multiplication of disjoint cycles is commutative, we obtain that

σn = σ1n σ2n … σmn

Let t : =lcm( r1, r2, …, rm). Then σt = σ1t σ2t … σmt = i, the identity permutation. Since t is the lcm, we can easily check that t is the smallest positive integer such that σt = i. Therefore,

t= order of σ.

In other words, the order of σ is the lcm of the lengths of its disjoint cycles.

Solved Examples on Order of Permutation

Example 1: Find the order of (1 4 5 7) (2 6 3).

Solution:

See that σ = (1 4 5 7) (2 6 3) is the product of two disjoint cycles. Here (1 4 5 7) is a cycle of length 4 and (2 6 3) is a cycle of length 3.

By the above theorem on orders of permutations, we deduce that:

The order of σ is

= lcm(4, 3)

= 12.

∴ The order of (1 4 5 7) (2 6 3) is 12.

FAQs on Order of Permutation

Q1: What is the order of (2 3 4)?

Answer: As (2 3 4) is a 3-cycle, the order of (2 3 4) is 3.

Q2: What is the order of (1 2 3) (1 3 2)?

Answer: By multiplication of permutations, we have (1 2 3) (1 3 2) =i, where i is the identity permutation. So the order of (1 2 3) (1 3 2) is 1.