Order of a Permutation

The order (or period) of a permutation is defined as the minimum number of successive applications required for each element to cycle back to its original position.

This concept is quantified more formally as the number of iterations needed for a permutation to become the identity permutation, where every element remains unchanged.

To determine the order of a permutation, adhere to the following steps:

1. Cyclic Representation
   Transform the permutation into its cyclic form, which displays each group of elements that cycle among themselves as separate cycles.
2. Cycle Length
   Calculate the length of each identified cycle.
3. Least Common Multiple
   Find the least common multiple of all the cycle lengths, which gives you the permutation's order.

The order of a permutation, therefore, is the smallest positive integer such that its repeated application restores all elements to their initial positions.

This characteristic is pivotal in the study of algebraic structures, especially within the symmetric group, which includes all potential permutations of any finite set.

Example

Consider the simple permutation (1 2 3):

$$ \sigma = (1 \ 2 \ 3) $$

This sequence implies that 1 moves to 2, 2 to 3, and 3 back to 1. Essentially, each element advances to the position of the next, with the final one looping back to the first. 

In tabular form, this permutation is represented as: $$ \sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} $$

It consists of a single cycle (1 2 3). We then measure the length of this cycle.

• \( \sigma(1) = 2 \)
• \( \sigma(2) = 3 \)
• \( \sigma(3) = 1 \)

The permutation requires three iterations to revert to its starting arrangement.

Thus, the order of the permutation is 3.

Verification. Let's quickly verify using matrix notation. $$ \sigma_1 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} $$ $$ \sigma_2 = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} $$ $$ \sigma_3 = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} = id $$ After three steps, the permutation returns to the initial configuration (identity).

Example 2

Let's analyze the permutation (1 2 3 4 6):

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

In this configuration, each number transitions to the subsequent one, except the number four which skips to six, and six circles back to one.

This permutation indicates that 1→2, 2→3, 3→4, 4→6, and 6→1.

Its tabular representation is: $$ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 3 & 4 & 6 & 5 & 1 \end{pmatrix} $$

Initially, we express the permutation (1,2,3,4,6) as disjoint cycles.

The number 5 remains unchanged, hence it acts as a fixed point within the permutation.

Examining the cycles reveals:

• \( \sigma(1) = 2 \)
• \( \sigma(2) = 3 \)
• \( \sigma(3) = 4 \)
• \( \sigma(4) = 6 \)
• \( \sigma(6) = 1 \)

The single cycle \( (1\ 2\ 3\ 4\ 6) \) extends over five applications to reset to the starting configuration.

Thus, the order of the permutation is precisely 5.

This calculation implies that applying the permutation five times resets all elements to their initial placements.

Example 3

Examine the permutation (1 3 2)(4 5), consisting of two disjoint cycles:

$$ \sigma = (1\ 3\ 2)(4\ 5) $$

In tabular form, it appears as: $$ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 2 & 5 & 4 \end{pmatrix} $$

To ascertain the order of a permutation with multiple cycles, calculate the least common multiple of the cycle lengths:

• The cycle \( (1\ 3\ 2) \) spans three steps as 1→3, 3→2, 2→1.
• The cycle \( (4\ 5) \) encompasses two steps, 4→5 and 5→4.

The least common multiple of these lengths is:

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

Hence, the order of the permutation \( (1\ 3\ 2)(4\ 5) \) is 6.

This result means that six applications of the permutation are necessary to return all elements to their original positions.