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
σ
(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
σ
kl
(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) · · · σ
k1
(1)).
Now choose the smallest number that is not yet in a cycle, say
j
. Repeat to
obtain a cycle (
j σ
(
j
)
σ
2
(
j
)
· · · σ
l1
(
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.