2Symmetric group I

IA Groups

2.1 Symmetric groups

Definition

(Permutation)

.

A permutation of

X

is a bijection from a set

X

to

X itself. The set of all permutations on X is Sym X.

When composing permutations, we treat them as functions. So if

σ

and

ρ

are permutations, σ ◦ ρ is given by first applying ρ, then applying σ.

Theorem. Sym X with composition forms a group.

Proof. The groups axioms are satisfied as follows:

0.

If

σ

:

X → X

and

τ

:

X → X

, then

σ ◦ τ

:

X → X

. If they are both

bijections, then the composite is also bijective. So if

σ, τ ∈ Sym X

, then

σ ◦ τ ∈ Sym X.

1.

The identity 1

X

:

X → X

is clearly a permutation, and gives the identity

of the group.

2.

Every bijective function has a bijective inverse. So if

σ ∈ Sym X

, then

σ

−1

∈ Sym X.

3. Composition of functions is associative.

Definition

(Symmetric group

S

n

)

.

If

X

is finite, say

|X|

=

n

(usually use

X

=

{

1

,

2

, · · · , n}

), we write

Sym X

=

S

n

. The is the symmetric group of degree

n.

It is important to note that the degree of the symmetric group is different

from the order of the symmetric group. For example,

S

3

has degree 3 but order

6. In general, the order of S

n

is n!.

There are two ways to write out an element of the symmetric group. The

first is the two row notation.

Notation.

(Two row notation) We write 1

,

2

,

3

, · · · n

on the top line and their

images below, e.g.

1 2 3

2 3 1

∈ S

3

and

1 2 3 4 5

2 1 3 4 5

∈ S

5

In general, if σ : X → X, we write

1 2 3 · · · n

σ(1) σ(2) σ(3) · · · σ(n)

Example. For small n, we have

(i) When n = 1, S

n

=

1

1

= {e}

∼

=

C

1

.

(ii) When n = 2, S

n

=

1 2

1 2

,

1 2

2 1

∼

=

C

2

(iii) When n = 3,

S

n

=

1 2 3

1 2 3

,

1 2 3

2 3 1

,

1 2 3

3 1 2

1 2 3

2 1 3

,

1 2 3

3 2 1

,

1 2 3

1 3 2

∼

=

D

6

.

Note that

S

3

is not abelian. Thus

S

n

is not abelian for

n ≥

3 since we can

always view S

3

as a subgroup of S

n

by fixing 4, 5, 6, · · · n.

In general, we can view

D

2n

as a subgroup of

S

n

because each symmetry is

a permutation of the corners.

While the two row notation is fully general and can represent any (finite)

permutation, it is clumsy to write and wastes a lot of space. It is also very

annoying to type using L

A

T

E

X. Hence, most of the time, we actually use the

cycle notation.

Notation

(Cycle notation)

.

If a map sends 1

7→

2, 2

7→

3, 3

7→

1, then we

write it as a cycle (1 2 3). Alternatively, we can write (2 3 1) or (3 1 2), but by

convention, we usually write the smallest number first. We leave out numbers

that don’t move. So we write (1 2) instead of (1 2)(3).

For more complicated maps, we can write them as products of cycles. For

example, in S

4

, we can have things like (1 2)(3 4).

The order of each cycle is the length of the cycle, and the inverse is the cycle

written the other way round, e.g. (1 2 3)

−1

= (3 2 1) = (1 3 2).

Example.

(i)

Suppose we want to simplify (1 2 3)(1 2). Recall that composition is from

right to left. So 1 gets mapped to 3 ((1 2) maps 1 to 2, and (1 2 3) further

maps it to 3). Then 3 gets mapped to 1. 2 is mapped to 2 itself. So

(1 2 3)(1 2) = (1 3)(2)

(ii) (1 2 3 4)(1 4) = (1)(2 3 4) = (2 3 4).

Definition

(

k

-cycles and transpositions)

.

We call (

a

1

a

2

a

3

· · · a

k

) a

k

-cycle.

2-cycles are called transpositions. Two cycles are disjoint if no number appears

in both cycles.

Example. (1 2) and (3 4) are disjoint but (1 2 3) and (1 2) are not.

Lemma. Disjoint cycles commute.

Proof.

If

σ, τ ∈ S

n

are disjoint cycles. Consider any

n

. Show that:

σ

(

τ

(

a

)) =

τ

(

σ

(

a

)). If

a

is in neither of

σ

and

τ

, then

σ

(

τ

(

a

)) =

τ

(

σ

(

a

)) =

a

. Otherwise,

wlog assume that

a

is in

τ

but not in

σ

. Then

τ

(

a

)

∈ τ

and thus

τ

(

a

)

6∈ σ

. Thus

σ

(

a

) =

a

and

σ

(

τ

(

a

)) =

τ

(

a

). Therefore we have

σ

(

τ

(

a

)) =

τ

(

σ

(

a

)) =

τ

(

a

).

Therefore τ and σ commute.

In general, non-disjoint cycles may not commute. For example, (1 3)(2 3) =

(1 3 2) while (2 3)(1 3) = (1 2 3).

Theorem.

Any permutation in

S

n

can be written (essentially) uniquely as a

product of disjoint cycles. (Essentially unique means unique up to re-ordering of

cycles and rotation within cycles, e.g. (1 2) and (2 1))

Proof.

Let

σ ∈ S

n

. Start with (1

σ

(1)

σ

2

(1)

σ

3

(1)

· · ·

). As the set

{

1

,

2

,

3

· · · n}

is finite, for some

k

, we must have

σ

k

(1) already in the list. If

σ

k

(1) =

σ

l

(1),

with

l < k

, then

σ

k−l

(1) = 1. So all

σ

i

(1) are distinct until we get back to 1.

Thus we have the first cycle (1 σ(1) σ

2

(1) σ

3

(1) · · · σ

k−1

(1)).

Now choose the smallest number that is not yet in a cycle, say

j

. Repeat to

obtain a cycle (

j σ

(

j

)

σ

2

(

j

)

· · · σ

l−1

(

j

)). Since

σ

is a bijection, nothing in this

cycle can be in previous cycles as well.

Repeat until all

{

1

,

2

,

3

· · · n}

are exhausted. This is essentially unique

because every number

j

completely determines the whole cycle it belongs to,

and whichever number we start with, we’ll end up with the same cycle.

Definition

(Cycle type)

.

Write a permutation

σ ∈ S

n

in disjoint cycle notation.

The cycle type is the list of cycle lengths. This is unique up to re-ordering. We

often (but not always) leave out singleton cycles.

Example. (1 2) has cycle type 2 (transposition). (1 2)(3 4) has cycle type 2, 2

(double transposition). (1 2 3)(4 5) has cycle type 3, 2.

Lemma.

For

σ ∈ S

n

, the order of

σ

is the least common multiple of cycle

lengths in the disjoint cycle notation. In particular, a k-cycle has order k.

Proof.

As disjoint cycles commute, we can group together each cycle when we take

powers. i.e. if σ = τ

1

τ

2

· · · τ

l

with τ

i

all disjoint cycles, then σ

m

= τ

m

1

τ

m

2

· · · τ

m

l

.

Now if cycle

τ

i

has length

k

i

, then

τ

k

i

i

=

e

, and

τ

m

i

=

e

iff

k

i

| m

. To get an

m

such that

σ

m

=

e

, we need all

k

i

to divide

m

. i.e.

m

is a common multiple of

k

i

. Since the order is the least possible

m

such that

σ

m

=

e

, the order is the

least common multiple of k

i

.

Example. Any transpositions and double transpositions have order 2.

(1 2 3)(4 5) has order 6.