Permutation Groups

After studying additive groups modulo

n

, we now move from number-based groups to transformation groups. A permutation is a bijective function from a finite set to itself, and permutations form groups under composition. These groups are central because they describe symmetry and rearrangement. They also provide the first natural examples of non-commutative groups. In this lesson, students will learn the symmetric group

\mathbb{S}_n

, verify the group axioms under composition, and compute basic products and inverses of permutations.

Let

X

be a non-empty finite set. A

\textbf{permutation}

X

is a bijective function

\begin{equation*} \sigma:X\to X. \end{equation*}

When

X=\{1,2,\ldots,n\}

, the set of all permutations of

X

is denoted by

\mathbb{S}_n

After studying additive groups modulo

n

\mathbb{S}_n

, verify the group axioms under composition, and compute basic products and inverses of permutations.

Let

X

be a non-empty finite set. A

\textbf{permutation}

X

is a bijective function

\begin{equation*} \sigma:X\to X. \end{equation*}

When

X=\{1,2,\ldots,n\}

, the set of all permutations of

X

is denoted by

\mathbb{S}_n

Let

n\in\mathbb{N}

. The set

\mathbb{S}_n

of all permutations of

\{1,2,\ldots,n\}

is called the

\textbf{symmetric group of degree n}

under composition of functions.

The operation in

\mathbb{S}_n

is composition. If

\sigma,\tau\in\mathbb{S}_n

, then

\sigma\circ\tau

means first apply

\tau

and then apply

\sigma

. This order is important. In general,

\sigma\circ\tau

need not equal

\tau\circ\sigma

. This is why permutation groups are the standard first examples of non-abelian groups.

Let

n\in\mathbb{N}

. Then

(\mathbb{S}_n,\circ)

is a finite group under composition of functions.

Given that

\mathbb{S}_n

is the set of all permutations of

\{1,2,\ldots,n\}

and

\circ

is composition of functions. To prove that

(\mathbb{S}_n,\circ)

is a finite group. [1] To prove closure. Let

\sigma,\tau\in\mathbb{S}_n

. Then

\sigma

and

\tau

are bijections from

\{1,2,\ldots,n\}

to itself. The composition of two bijections is again a bijection. Therefore

\begin{equation*} \sigma\circ\tau\in\mathbb{S}_n. \end{equation*}

[2] To prove associativity. Let

\sigma,\tau,\rho\in\mathbb{S}_n

. Since composition of functions is associative,

\begin{equation*} (\sigma\circ\tau)\circ\rho=\sigma\circ(\tau\circ\rho). \end{equation*}

[3] To prove the existence of identity element. Let

I

be the identity function on

\{1,2,\ldots,n\}

. Then

I\in\mathbb{S}_n

and

\begin{equation*} \sigma\circ I=I\circ\sigma=\sigma \quad \forall\, \sigma\in\mathbb{S}_n. \end{equation*}

Therefore

I

is the identity element. [4] To prove the existence of inverse elements. Let

\sigma\in\mathbb{S}_n

. Since

\sigma

is a bijection, it has an inverse function

\sigma^{-1}

, which is also a bijection from

\{1,2,\ldots,n\}

to itself. Thus

\sigma^{-1}\in\mathbb{S}_n

and

\begin{equation*} \sigma\circ\sigma^{-1}=\sigma^{-1}\circ\sigma=I. \end{equation*}

Therefore every element has an inverse in

\mathbb{S}_n

. Since there are

n!

permutations of an

n

-element set,

\mathbb{S}_n

is finite and

\begin{equation*} |\mathbb{S}_n|=n!. \end{equation*}

Hence,

(\mathbb{S}_n,\circ)

is a finite group.

\square

The group

\mathbb{S}_3

has

3!=6

elements. They are

\begin{equation*} I,\quad (12),\quad (13),\quad (23),\quad (123),\quad (132). \end{equation*}

Here

(12)

swaps

1

and

2

, while

(123)

sends

1

2

2

3

, and

3

1

The group

\mathbb{S}_2

has

2

elements:

\begin{equation*} \mathbb{S}_2=\{I,(12)\}. \end{equation*}

The element

(12)

has order

2

, because

\begin{equation*} (12)\circ(12)=I. \end{equation*}

Thus

\mathbb{S}_2

is a finite group of order

2

Compute

(123)\circ(12)

\mathbb{S}_3

, using the convention that the right permutation is applied first.

Let

\sigma=(123)

and

\tau=(12)

. To compute

\sigma\circ\tau

. Apply

\tau

first and then

\sigma

. For

1

\begin{align*} 1&\xrightarrow{\tau}2\\ 2&\xrightarrow{\sigma}3. \end{align*}

Thus

1

maps to

3

. For

3

\begin{align*} 3&\xrightarrow{\tau}3\\ 3&\xrightarrow{\sigma}1. \end{align*}

Thus

3

maps to

1

. For

2

\begin{align*} 2&\xrightarrow{\tau}1\\ 1&\xrightarrow{\sigma}2. \end{align*}

Thus

2

maps to

2

. Therefore the product sends

1

3

3

1

, and fixes

2

. Hence,

\begin{equation*} (123)\circ(12)=(13). \end{equation*}

\square

Show that

\mathbb{S}_3

is not abelian.

Let

\sigma=(123)

and

\tau=(12)

\mathbb{S}_3

. To prove that

\mathbb{S}_3

is not abelian. From the previous computation,

\begin{equation*} \sigma\circ\tau=(13). \end{equation*}

Now compute

\tau\circ\sigma

. Apply

\sigma

first and then

\tau

. For

1

\begin{align*} 1&\xrightarrow{\sigma}2\\ 2&\xrightarrow{\tau}1. \end{align*}

Thus

1

maps to

1

. For

2

\begin{align*} 2&\xrightarrow{\sigma}3\\ 3&\xrightarrow{\tau}3. \end{align*}

Thus

2

maps to

3

. For

3

\begin{align*} 3&\xrightarrow{\sigma}1\\ 1&\xrightarrow{\tau}2. \end{align*}

Thus

3

maps to

2

. Therefore

\begin{equation*} \tau\circ\sigma=(23). \end{equation*}

Since

\begin{equation*} (13)\neq(23), \end{equation*}

we get

\begin{equation*} \sigma\circ\tau\neq\tau\circ\sigma. \end{equation*}

Hence,

\mathbb{S}_3

is not abelian.

\square

The identity element in a permutation group is the identity function, not the number

1

. The inverse of a permutation is its inverse function. Students often confuse cycle notation with multiplication of numbers. In permutation groups, the operation is function composition, and the order of composition must be respected.

Use the calculator below to compose two permutations of

\{1,2,3\}

. Enter each permutation as a list of images. For example, the list

2,3,1

represents the cycle

(123)

. The calculator applies the second permutation first and then the first.

[1] Define

\mathbb{S}_n

. [2] Prove that

\mathbb{S}_n

is closed under composition. [3] How many elements does

\mathbb{S}_4

have? [4] Find the inverse of

(123)

\mathbb{S}_3

. [5] Give two elements of

\mathbb{S}_3

that do not commute.

[1]

\mathbb{S}_n

is the set of all permutations of

\{1,2,\ldots,n\}

. [2] The composition of two bijections from the set to itself is again a bijection from the set to itself. [3]

|\mathbb{S}_4|=4!=24

. [4] The inverse of

(123)

(132)

. [5] For example,

(123)

and

(12)

do not commute.

The operation is composition of functions.

The identity permutation

I

It has

n!

elements.

No.

\mathbb{S}_n

is non-abelian for

n\geq3

BMLabs Mathematics

BMLabs Mathematics

Permutation Groups

Permutation Groups

PERMUTATION

SYMMETRIC GROUP

PERMUTATION PRODUCT

ALTERNATING GROUPS

Coordinates and Locus

Invariants under Orthogonal Transformation