Symmetric Group

Definition: Let X be a set. Let Sym(X) denote the set

of all bijective maps from X to X. Then, Sym(X) is a group

with respect to the composition of maps. This group is called the

Symmetric group or the Transformation group or the

Permutation group on X.

If X = {1, 2, . . . , n}, then Sym(X) is denoted by Sn and is

called Symmetric group of degree n. Thus, Sn is the group of all

bijective maps from {1, 2, . . . , n} to itself, the operation being the

composition of maps. An element f ∈ Sn can be represented by

Definition: A permutation α ∈ Sn is called a cycle of length

1
r ≥ 1 if there exists a subset {i1, i2, . . . , ir } of {1, 2, . . . , n} con-

taining r distinct elements such that α(i1) = i2, α(i2) = i3, . . . , α(ir1) =

ir , α(ir ) = i1 and α(j) = j for all j ∈ {1, 2, . . . , n}−{i1, i2, . . . , ir }.

The cycle α is denoted by (i1i2 . . . ir ). A cycle of length 2 is called

a transposition.

Two cycles (i1i2 . . . ir ) and (j1j2 . . . js) are said to be disjoint

if {i1, i2, . . . , ir } ∩ {j1, j2, . . . js} = ∅

Proposition: Any two disjoint cycles commute.

Proposition: If α and β are disjoint cycles, then < α >

∩ < β >= {I}.

Proposition: Let α ∈ Sn be a cycle of length r. Then,

o(α) = r.

Proposition: Let {α1, α2, . . . , αr } be a set of pairwise dis-

joint cycles of lengths m1, m2, . . . , mr respectively. Let α =

2
α1α2 . . . αr . Then, o(α) = lcm[m1, m2, . . . , mr ] the least com-

mon multiple of m1, m2, . . . mr .

Theorem: Every nonidentity permutation can be written as

a product of disjoint cycles. Further, any two representations of a

nonidentity permutation as product of disjoint cycles is same up

to rearrangement of cycles.

Proof: Let f be a nonidentity permutation in Sn. Then,

there exists i1 ∈ {1, 2, . . . , n} such that f (i1) 6= i1. Since o(Sn) =

n!, f n! = I. Hence, f n!(i1) = i1. Let l1 be the least positive inte-

ger such that f l1 (i1) = i1. Thus, i1, f (i1), f 2(i1), . . . , f l1−1(i1) are

all distinct. Now, given k ∈ Z, by the division algorithm, there

exist q, r ∈ Z such that k = l1q + r, where 0 ≤ r ≤ l1 − 1.

But, then f k (i1) = f ql1+r (i1) = f r (i1). It is clear from the above

observation that the effect of the permutation f on symbols in

3
{i1, f (i1), f 2(i1), . . . , f 111(i1)} is same as that of the cycle C1 =

(i1f (i1)f 2(i2) . . . f l11(i1)). If f = C1, there is nothing to do. If

not, there exists i2 ∈ {1, 2, . . . , n}−{i1, f (i1), f 2(i1), . . . f l1−1(i1)}

such that f (i2) 6= i2. As before consider the cycle C2 = (i2f (i2)f 2(i2) . . . f l2−1

where l2 is the smallest positive integer such that f l2 (i2) = i2.

Clearly, C1 and C2 are disjoint cycles. If f = C1C2, there is

nothing to do. If not proceed. This process stops after finitely

many steps giving f as product of disjoint cycles, because the

symbols are finitely many. Finally, we prove the uniqueness. Sup-

pose that f 6= I and f = C1C2 . . . Cr = C10 C20 . . . Cs0 , where Ci

and Cj are disjoint for i 6= j , and also Ck0 and Cl0 are disjoint for

k 6= l. Let i ∈ {1, 2, . . . , n} such that f (i) 6= i. Then, there exist

k, l(1 ≤ k ≤ r, 1 ≤ l ≤ s) such that Ck (i) 6= i and also Cl0(i) 6= i.

Since a cycle is completely determined by any symbol moved by

4
it, hence Ck = Cl0. Since disjoint cycle commutes, we may assume

that Ck = C1 and Cl0 = C10 . Canceling C1 and C10 , using induction

and the fact that products of nonidentity disjoint cycles can never

0
 r = s and Ci = Ci for alli.
be identity, we find that

1 2 3 4 5 6 7 8 9 10
Examples: 1.   = (16103827459)
 
 
6 7 8 5 9 10 4 2 1 3
a singlecycle. 
1 2 3 4 5 6 7 8 
2.   = (13)(4567)
 
 
3 2 1 5 6 7 4 8

Exercise:

• S7 contains no elements of order 8. For, a permutation is of

order 8 if and only if it can be written as product of disjoint

cycles such that the least common multiple of lengths of

these cycles equals 8. We also observe that l.c.m of certain

5
 numbers equals 8 only if at least one of them is 8. Thus,

we cannot have any such permutation in S7. Similarly, S7

contains no element of order 15, for a permutation of order

15 contains at least one cycle of length 5 and at least one

cycle of length 3, or it should contain a cycle of length 15 in

its decomposition as product of disjoint cycles.

• Does S6 contains an element of order 10?

• Does S14, S13, S12 has an element of order 42?

Definition: Let α and β be two nontrivial permutations in

Sn. We say that α and β are of same form if

(i) the number of cycles in the representation of α as product of

disjoint cycles is same as that in the representation of β as product

of disjoint cycles, and

6
(ii) there is a bijective correspondence between the set of cycles

used in the representation of α and that in the representation of

β so that the lengths of the corresponding cycles are same.

Thus, (123)(47)(5698) and (4523)(89)(167) are permutations

of same form where as (123)(47) and (4523)(89) are not of the

same form.

Theorem: Two cycles in Sn are conjugate if and only if they

have same length.

Theorem: Two permutations in Sn are conjugate if and only

if they are of same form.

Proposition: Let f ∈ Sn. Then, χ(f ) ∈ {1, −1}.

Proof: Let 1 ≤ k < l ≤ n. Then, k − l appears in the

denominator of χ(f ). Since f is a bijective map on {1, 2, . . . , n},

7
there exists unique p, q ∈ {1, 2, . . . , n} such that f (p) = k, f (q) =

l. Now, since k 6= l, so p 6= q (because f is bijective). If p < q,

then f (p) − f (q) is in the numerator of χ(f ). If p > q, then

f (q) − f (p) appears in the numerator of χ(f ). Hence k − l cancels

out with ± sign. Hence, χ(f ) ∈ {1, −1}.

Definition: The map χ : Sn → {±1} defined above is called

the alternating map.

Note that {±1} is a group with respect to the multiplication

of integer as binary operation.

Theorem: The alternating map χ : Sn → {±1} is an onto

group homomorphism.
Q f g(i)−f g(j)
Proof: Let f, g ∈ Sn, then χ(f g) = 1≤i<j≤n i−j =
Q f (g(i))−f (g(j)) Q f g(i)−f g(j) Q g(i)−g(j)
1≤i<j≤n i−j = 1≤i<j≤n g(i)−g(j) ·( 1≤i<j≤n i−j ) =

8
Q f g(i)−f g(j)
1≤i<j≤n g(i)−g(j) · χ(g) = χ(f ) · χ(g). Thus, χ is a homomor-

2−1 2−3
phism. Now, let f = (12) ∈ Sn, then χ(f ) = 1−2 · 1−3 · · · 2−n
1−n ·

1−3 (n−1)−n
2−3 · 1−4 1−n
2−4 · · · 2−n · · · (n−1)−n = −1. Therefore, χ is onto.

Definition: The kerχ is called the alternating group of

degree n and it is denoted by An.

Remark: By the fundamental theorem of homomorphism

Sn/An = Sn/kerχ ∼
= {±1}. Also, 2 = |Sn/An| =
|Sn |
An . This

n!
implies that |An| = 2.

Definition: Let f ∈ Sn, f is called even (odd) permuta-

tion if χ(f ) = 1(χ(f ) = −1).

Remark: 1. Note that, if f1, f2 ∈ Sn and there exists g ∈ Sn

such that gf1g −1 = f2, then χ(f2) = χ(gf1g −1) = χ(g) · χ(f1) ·

χ(g −1) = χ(f1) · χ(g) · χ(g)−1 = χ(f1).

9
 2. Let C = (i1i2 . . . ir ) ∈ Sn. Then, C = (i1ir )(i1ir−1)(i1ir−2) . . . (i1i2),

product of r − 1- transpositions. Thus, C is an even permutation

if and only if r − 1 is even if and only if r is odd.

Theorem: (Cayley’s Theorem) Let G be a group. Then

it is isomorphic to a subgroup of a symmetric group Sym(X) on

a set X.

Proof: Let X = G. Consider the group Sym(X) = Sym(G).

For g ∈ G, let Lg : G → G be the map defined by Lg (x) = g · x.

We show that Lg ∈ Sym(G). For this, let x1, x2 ∈ G such that

Lg (x1) = Lg (x2), then g · x1 = g · x2. This implies that x1 = x2.

Therefore, Lg is one-one. Next, let y ∈ G, then for x = g −1 · y,

we have Lg (x) = g · (g −1 · y) = (gg −1) · y = e · y = y. Thus, Lg

is onto. Therefore, Lg is a bijective map and so Lg ∈ Sym(G).

Now, define a map φ : G → Sym(G) by φ(g) = Lg . Then φ

10
is a group homomorphism. For, let g1, g2 ∈ G and x ∈ G, then

φ(g1 · g2)(x) = Lg1g2 (x) = (g1g2) · x = g1 · (g2 · x) = Lg1 (g2 · x) =

Lg1 (Lg2 (x)) = (Lg1 ◦ Lg2 )(x) = (φ(g1) ◦ φ(g2))(x). Therefore,

φ(g1g2) = φ(g1)φ(g2) and hence φ is a homomorphism.Next, let

g ∈ kerφ, then φ(g) = IG, the identity map on G. Therefore,

for all x ∈ G, g · x = φ(g)(x) = IG(x) = x. This implies that

g = e. Thus, kerφ = {e} and φ is one-one. Now by fundamental

theorem of homomorphism, G ∼
= G/kerφ ∼
= φ(G), a subgroup of

Sym(G).

Corollary: Let G be a group of order n. Then G is isomor-

phic to a subgropu of Sn.

Proof: Let G = {e = g1, g2, g3, . . . , gn}. Then Sym(G) ∼

Sn. By the above theorem G is isomorphic to a subgroup of

Sym(G) ∼
= Sn.
11
 Definition: The map φ : G → Sym(G) defined in the above

theorem is called the Cayley representation of G on G or the

left regular representation of G.

Exercise: Find the Cayley representation of the following:

1. Z3

2. V4

3. Q8

4. Zn

Theorem: An(n ≥ 3) is generated by 3-cycles.

Proof: Since permutations in An are products of even num-

ber of transpositions, it is sufficient to show that product of any

two transpositions is a product of cycles of length 3. Consider

(αβ)(γδ). It is I = (αβγ)(αγδ) if {α, β} = {γ, δ}. Next, sup-

pose that β = γ and α 6= δ. Then, (αβ)(γδ) = (αβ)(βδ) =

12
(αβδ). Now suppose that {α, β} ∩ γ, δ} = ∅. Then, (αβ)(γδ) =

(γαδ)(αβγ).

Theorem: An(n ≥ 5) is a simple group.

Proof: Exercise.

Proposition: The group Sn is generated by {(12), (23), . . . , (n−

1n)}.

Proposition: The group Sn is generated by {(12), (12 . . . n)}.

13