Cayley Theorem and Permutation Groups

After studying homomorphisms, kernels, isomorphisms, and cyclic examples, we reach one of the most important representation results in elementary group theory. The focus keyword Cayley theorem and permutation groups states that every group is structurally the same as a group of permutations. This means an abstract group can always be realized through bijections of a set. The construction is not mysterious: each group element acts on the group by left multiplication. Students often think permutation groups are special examples, but Cayley's theorem shows that they are universal models for all groups.

Let

A

be a non-empty set. A \textbf{permutation} of

A

is a bijective function from

A

onto

A

Let

A

be a non-empty set. A \textbf{permutation} of

A

is a bijective function from

A

onto

A

Let

A

be a non-empty set. The set of all permutations of

A

, under composition of functions, is called the \textbf{symmetric group} on

A

and is denoted by

S_A

. If

A

has

n

elements, then

S_A

is commonly denoted by

S_n

, and

\begin{equation*} |S_n|=n!. \end{equation*}

A \textbf{permutation group} is a subgroup of a symmetric group. Thus a permutation group is a group whose elements are bijections of some set and whose operation is composition.

Let

G

be a group and fix

a\in G

. Define

L_a:G\to G

L_a(x)=ax

. This map is a bijection: multiplying by

a^{-1}

reverses it. Cayley's theorem uses these left multiplication maps to build a faithful permutation model of

G

. The group element

a

is replaced by the permutation

L_a

, and multiplication in

G

becomes composition of these permutations.

Every group is isomorphic to a permutation group.

Given that

G

is a group. To prove that

G

is isomorphic to a permutation group. For each

a\in G

, define

L_a:G\to G

\begin{equation*} L_a(x)=ax. \end{equation*}

First,

L_a

is one-to-one. If

L_a(x)=L_a(y)

, then

ax=ay

. Multiplying by

a^{-1}

on the left gives

x=y

. Next,

L_a

is onto. Let

y\in G

. Put

x=a^{-1}y

. Then

\begin{equation*} L_a(x)=a(a^{-1}y)=y. \end{equation*}

Thus

L_a

is a permutation of

G

. Let

\begin{equation*} L(G)=\{L_a\mid a\in G\}. \end{equation*}

Define

\Phi:G\to L(G)

\Phi(a)=L_a

. Let

a,b\in G

. For every

x\in G

\begin{align*} L_{ab}(x)&=(ab)x,\\ (L_a\circ L_b)(x)&=L_a(bx)\\ &=a(bx)\\ &=(ab)x. \end{align*}

Therefore

L_{ab}=L_a\circ L_b

, so

\begin{equation*} \Phi(ab)=\Phi(a)\circ\Phi(b). \end{equation*}

Thus

\Phi

is a homomorphism. If

\Phi(a)=\Phi(b)

, then

L_a=L_b

. Applying both functions to

e

gives

\begin{equation*} a=L_a(e)=L_b(e)=b. \end{equation*}

Thus

\Phi

is one-to-one. By definition of

L(G)

, the map

\Phi

is onto. Hence

\Phi

is an isomorphism from

G

onto the permutation group

L(G)

\square

G

is a finite group of order

n

, then

G

is isomorphic to a subgroup of

S_n

Given that

G

is a finite group of order

n

. To prove that

G

is isomorphic to a subgroup of

S_n

. By Cayley's theorem,

G\cong L(G)

, where

L(G)

is a group of permutations of the set

G

. Since

G

has

n

elements, the symmetric group on the set

G

is isomorphic to

S_n

. Therefore

L(G)

may be viewed as a subgroup of

S_n

. Hence

G

is isomorphic to a subgroup of

S_n

\square

Let

G=\{1,i,-1,-i\}

under multiplication. For each

a\in G

, define

L_a(x)=ax

. Then

\begin{align*} L_1&=(1)(i)(-1)(-i),\\ L_i&=(1\ i\ -1\ -i),\\ L_{-1}&=(1\ -1)(i\ -i),\\ L_{-i}&=(1\ -i\ -1\ i). \end{align*}

The set

\{L_1,L_i,L_{-1},L_{-i}\}

is a permutation group, and the map

a\mapsto L_a

is an isomorphism from

G

onto this permutation group.

Let

G

be a finite group of order

3

. Use Cayley's theorem to explain why

G

is isomorphic to a subgroup of

S_3

Let

G

be a finite group of order

3

. To prove that

G

is isomorphic to a subgroup of

S_3

. For each

a\in G

, define

L_a:G\to G

L_a(x)=ax

. Each

L_a

is a permutation of the three-element set

G

. Therefore

L_a\in S_G

, where

S_G

is the symmetric group on

G

. Let

L(G)=\{L_a\mid a\in G\}

. By Cayley's theorem, the map

a\mapsto L_a

is an isomorphism from

G

onto

L(G)

. Since

S_G

is isomorphic to

S_3

, the group

L(G)

corresponds to a subgroup of

S_3

. Hence

G

is isomorphic to a subgroup of

S_3

\square

Cayley's theorem does not say that every group is equal to a subgroup of

S_n

. It says every finite group of order

n

is isomorphic to such a subgroup. This distinction matters: the original elements of

G

may be numbers, matrices, symmetries, or abstract symbols, while the Cayley representation uses permutations.

In the proof of Cayley theorem and permutation groups, the left multiplication map must be shown to be bijective before it can be called a permutation. The inverse of

L_a

L_{a^{-1}}

, because

L_{a^{-1}}(L_a(x))=x

and

L_a(L_{a^{-1}}(x))=x

1. For a group

G

, prove directly that

L_a\circ L_b=L_{ab}

for all

a,b\in G

. 2. If

|G|=4

, what symmetric group contains a subgroup isomorphic to

G

by Cayley's theorem? 3. Why is the map

a\mapsto L_a

one-to-one?

1. For

x\in G

(L_a\circ L_b)(x)=L_a(bx)=a(bx)=(ab)x=L_{ab}(x)

. 2. Cayley's theorem gives a subgroup of

S_4

isomorphic to

G

. 3. If

L_a=L_b

, then applying both maps to

e

gives

a=L_a(e)=L_b(e)=b

Yes. Every group is isomorphic to a group of permutations of its underlying set.

Left multiplication gives

L_{ab}=L_a\circ L_b

with the usual composition order used here.

It shows that permutation groups are universal models for group structure.

BMLabs Mathematics

BMLabs Mathematics

Cayley Theorem and Permutation Groups

Cayley Theorem and Permutation Groups

EVERY GROUP AS PERMUTATIONS

PERMUTATION

SYMMETRIC GROUP

PERMUTATION GROUP

LEFT MULTIPLICATION AS A PERMUTATION

CAYLEY THEOREM

CYCLIC GROUP OF ORDER FOUR AS PERMUTATIONS

FREQUENTLY ASKED QUESTIONS

REVIEW HOMOMORPHISMS OF GROUPS

Introduction To Discrete Mathematics

Paths and Circuits