Order of a Permutation: Definition, Examples, How to Find

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 σⁿ=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, σ² = $\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)$

⇒ σ³ = σ² ⋅ σ

= $\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 σ³=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

σ = σ₁ σ₂ … σ_m

is the decomposition of σ as the product of disjoint cycles σ₁, σ₂, …, σ_m of lengths r₁, r₂, …, r_m. We have

σ₁^r₁ = i, σ₂^r₂ = i, …, σ_m^r_m = i.

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

σⁿ = σ₁ⁿ σ₂ⁿ … σ_mⁿ

Let t : =lcm( r₁, r₂, …, r_m). Then σ^t = σ₁^t σ₂^t … σ_m^t = 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