1Groups
IB Groups, Rings and Modules
1.3 Actions of permutations
When we first motivated groups, we wanted to use them to represent some
collection of “symmetries”. Roughly, a symmetry of a set
X
is a permutation
of
X
, i.e. a bijection
X → X
that leaves some nice properties unchanged. For
example, a symmetry of a square is a permutation of the vertices that leaves the
overall shape of the square unchanged.
Instead of just picking some nice permutations, we can consider the group of
all permutations. We call this the symmetric group.
Definition (Symmetric group). The symmetric group
S
n
is the group of all
permutations of {1, ··· , n}, i.e. the set of all bijections of this set with itself.
A convenient way of writing permutations is to use the disjoint cycle notation,
such as writing (1 2 3)(4 5)(6) for the permutation that maps
1 7→ 2 4 7→ 5
2 7→ 3 5 7→ 4
3 7→ 1 6 7→ 6.
Unfortunately, the convention for writing permutations is weird. Since permuta-
tions are bijections, and hence functions, they are multiplied the wrong way, i.e.
f ◦ g
means first apply
g
, then apply
f
. In particular, (1 2 3)(3 4) requires first
applying the second permutation, then the first, and is in fact (1 2 3 4).
We know that any permutation is a product of transpositions. Hence we
make the following definition.
Definition (Even and odd permutation). A permutation
σ ∈ S
n
is even if it
can be written as a product of evenly many transpositions; odd otherwise.
In IA Groups, we spent a lot of time proving this is well-defined, and we are
not doing that again (note that this definition by itself is well-defined — if a
permutation can be both written as an even number of transposition and an odd
number of transposition, the definition says it is even. However, this is not what
we really want, since we cannot immediately conclude that, say, (1 2) is odd).
This allows us to define the homomorphism:
sgn : S
n
→ ({±1}, ×)
σ 7→
(
+1 σ is even
−1 σ is odd
Definition (Alternating group). The alternating group
A
n
≤ S
n
is the subgroup
of even permutations, i.e. A
n
is the kernel of sgn.
This immediately tells us
A
n
C S
n
, and we can immediately work out its
index, since
S
n
A
n
∼
=
im(sgn) = {±1},
unless n = 1. So A
n
has index 2.
More generally, for a set X, we can define its symmetric group as follows:
Definition (Symmetric group of
X
). Let
X
be a set. We write
Sym
(
X
) for the
group of all permutations of X.
However, we don’t always want the whole symmetric group. Sometimes, we
just want some subgroups of symmetric groups, as in our initial motivation. So
we make the following definition.
Definition (Permutation group). A group
G
is called a permutation group if it
is a subgroup of
Sym
(
X
) for some
X
, i.e. it is given by some, but not necessarily
all, permutations of some set.
We say G is a permutation group of order n if in addition |X| = n.
This is not really a too interesting definition, since, as we will soon see, every
group is (isomorphic to) a permutation group. However, in some cases, thinking
of a group as a permutation group of some object gives us better intuition on
what the group is about.
Example.
S
n
and
A
n
are obviously permutation groups. Also, the dihedral
group
D
2n
is a permutation group of order
n
, viewing it as a permutation of the
vertices of a regular n-gon.
We would next want to recover the idea of a group being a “permutation”.
If
G ≤ Sym
(
X
), then each
g ∈ G
should be able to give us a permutation of
X
,
in a way that is consistent with the group structure. We say the group
G
acts
on X. In general, we make the following definition:
Definition (Group action). An action of a group (
G, ·
) on a set
X
is a function
∗ : G × X → X
such that
(i) g
1
∗ (g
2
∗ x) = (g
1
· g
2
) ∗ x for all g
1
, g
2
∈ G and x ∈ X.
(ii) e ∗ x = x for all x ∈ X.
There is another way of defining group actions, which is arguably a better
way of thinking about group actions.
Lemma. An action of
G
on
X
is equivalent to a homomorphism
φ
:
G →
Sym(X).
Note that the statement by itself is useless, since it doesn’t tell us how to
translate between the homomorphism and a group action. The important part
is the proof.
Proof.
Let
∗
:
G × X → X
be an action. Define
φ
:
G → Sym
(
X
) by sending
g
to the function
φ
(
g
) = (
g ∗ ·
:
X → X
). This is indeed a permutation —
g
−1
∗ ·
is an inverse since
φ(g
−1
)(φ(g)(x)) = g
−1
∗ (g ∗x) = (g
−1
· g) ∗x = e ∗x = x,
and a similar argument shows
φ
(
g
)
◦φ
(
g
−1
) =
id
X
. So
φ
is at least a well-defined
function.
To show it is a homomorphism, just note that
φ(g
1
)(φ(g
2
)(x)) = g
1
∗ (g
2
∗ x) = (g
1
· g
2
) ∗ x = φ(g
1
· g
2
)(x).
Since this is true for all
x ∈ X
, we know
φ
(
g
1
)
◦ φ
(
g
2
) =
φ
(
g
1
· g
2
). Also,
φ
(
e
)(
x
) =
e ∗ x
=
x
. So
φ
(
e
) is indeed the identity. Hence
φ
is a homomorphism.
We now do the same thing backwards. Given a homomorphism
φ
:
G →
Sym
(
X
), define a function by
g ∗x
=
φ
(
g
)(
x
). We now check it is indeed a group
action. Using the definition of a homomorphism, we know
(i) g
1
∗
(
g
2
∗ x
) =
φ
(
g
1
)(
φ
(
g
2
)(
x
)) = (
φ
(
g
1
)
◦ φ
(
g
2
))(
x
) =
φ
(
g
1
· g
2
)(
x
) =
(g
1
· g
2
) ∗ x.
(ii) e ∗ x = φ(e)(x) = id
X
(x) = x.
So this homomorphism gives a group action. These two operations are clearly in-
verses to each other. So group actions of
G
on
X
are the same as homomorphisms
G → Sym(X).
Definition (Permutation representation). A permutation representation of a
group G is a homomorphism G → Sym(X).
We have thus shown that a permutation representation is the same as a
group action.
The good thing about thinking of group actions as homomorphisms is that
we can use all we know about homomorphisms on them.
Notation. For an action of
G
on
X
given by
φ
:
G → Sym
(
X
), we write
G
X
= im(φ) and G
X
= ker(φ).
The first isomorphism theorem immediately gives
Proposition. G
X
C G and G/G
X
∼
=
G
X
.
In particular, if G
X
= {e} is trivial, then G
∼
=
G
X
≤ Sym(X).
Example. Let
G
be the group of symmetries of a cube. Let
X
be the set of
diagonals of the cube.
Then
G
acts on
X
, and so we get
φ
:
G → Sym
(
X
). What is its kernel? To pre-
serve the diagonals, it either does nothing to the diagonal, or flips the two vertices.
So G
X
= ker(φ) = {id, symmetry that sends each vertex to its opposite}
∼
=
C
2
.
How about the image? We have
G
X
=
im
(
φ
)
≤ Sym
(
X
)
∼
=
S
4
. It is an
exercise to show that
im
(
φ
) =
Sym
(
X
), i.e. that
φ
is surjective. We are not
proving this because this is an exercise in geometry, not group theory. Then the
first isomorphism theorem tells us
G
X
∼
=
G/G
X
.
So
|G| = |G
X
||G
X
| = 4! · 2 = 48.
This is an example of how we can use group actions to count elements in a
group.
Example (Cayley’s theorem). For any group
G
, we have an action of
G
on
G
itself via
g ∗g
1
= gg
1
.
It is trivial to check this is indeed an action. This gives a group homomorphism
φ
:
G → Sym
(
G
). What is its kernel? If
g ∈ ker
(
φ
), then it acts trivially on
every element. In particular, it acts trivially on the identity. So
g ∗e
=
e
, which
means g = e. So ker(φ) = {e}. By the first isomorphism theorem, we get
G
∼
=
G/{e}
∼
=
im φ ≤ Sym(G).
So we know every group is (isomorphic to) a subgroup of a symmetric group.
Example. Let
H
be a subgroup of
G
, and
X
=
G/H
be the set of left cosets of
H. We let G act on X via
g ∗g
1
H = gg
1
H.
It is easy to check this is well-defined and is indeed a group action. So we get
φ : G → Sym(X).
Now consider
G
X
=
ker
(
φ
). If
g ∈ G
X
, then for every
g
1
∈ G
, we have
g ∗g
1
H = g
1
H. This means g
−1
1
gg
1
∈ H. In other words, we have
g ∈ g
1
Hg
−1
1
.
This has to happen for all g
1
∈ G. So
G
X
⊆
\
g
1
∈G
g
1
Hg
−1
1
.
This argument is completely reversible — if
g ∈
T
g
1
∈G
g
1
Hg
−1
1
, then for each
g
1
∈ G, we know
g
−1
1
gg
1
∈ H,
and hence
gg
1
H = g
1
H.
So
g ∗g
1
H = g
1
H
So g ∈ G
X
. Hence we indeed have equality:
ker(φ) = G
X
=
\
g
1
∈G
g
1
Hg
−1
1
.
Since this is a kernel, this is a normal subgroup of
G
, and is contained in
H
.
Starting with an arbitrary subgroup
H
, this allows us to generate a normal
subgroup, and this is indeed the biggest normal subgroup of
G
that is contained
in H, if we stare at it long enough.
We can use this to prove the following theorem.
Theorem. Let
G
be a finite group, and
H ≤ G
a subgroup of index
n
. Then
there is a normal subgroup
K C G
with
K ≤ H
such that
G/K
is isomorphic to
a subgroup of S
n
. Hence |G/K| | n! and |G/K| ≥ n.
Proof.
We apply the previous example, giving
φ
:
G → Sym
(
G/H
), and let
K
be the kernel of this homomorphism. We have already shown that
K ≤ H
. Then
the first isomorphism theorem gives
G/K
∼
=
im φ ≤ Sym(G/H)
∼
=
S
n
.
Then by Lagrange’s theorem, we know
|G/K| | |S
n
|
=
n
!, and we also have
|G/K| ≥ |G/H| = n.
Corollary. Let
G
be a non-abelian simple group. Let
H ≤ G
be a proper
subgroup of index
n
. Then
G
is isomorphic to a subgroup of
A
n
. Moreover, we
must have n ≥ 5, i.e. G cannot have a subgroup of index less than 5.
Proof.
The action of
G
on
X
=
G/H
gives a homomorphism
φ
:
G → Sym
(
X
).
Then
ker
(
φ
)
C G
. Since
G
is simple,
ker
(
φ
) is either
G
or
{e}
. We first show
that it cannot be
G
. If
ker
(
φ
) =
G
, then every element of
G
acts trivially on
X
=
G/H
. But if
g ∈ G \ H
, which exists since the index of
H
is not 1, then
g ∗ H
=
gH 6
=
H
. So
g
does not act trivially. So the kernel cannot be the whole
of G. Hence ker(φ) = {e}.
Thus by the first isomorphism theorem, we get
G
∼
=
im(φ) ≤ Sym(X)
∼
=
S
n
.
We now need to show that G is in fact a subgroup of A
n
.
We know
A
n
C S
n
. So
im
(
φ
)
∩A
n
C im
(
φ
)
∼
=
G
. As
G
is simple,
im
(
φ
)
∩A
n
is either
{e}
or
G
=
im
(
φ
). We want to show that the second thing happens,
i.e. the intersection is not the trivial group. We use the second isomorphism
theorem. If im(φ) ∩ A
n
= {e}, then
im(φ)
∼
=
im(φ)
im(φ) ∩ A
n
∼
=
im(φ)A
n
A
n
≤
S
n
A
n
∼
=
C
2
.
So
G
∼
=
im
(
φ
) is a subgroup of
C
2
, i.e. either
{e}
or
C
2
itself. Neither of these are
non-abelian. So this cannot be the case. So we must have im(φ) ∩A
n
= im(φ),
i.e. im(φ) ≤ A
n
.
The last part follows from the fact that
S
1
, S
2
, S
3
, S
4
have no non-abelian
simple subgroups, which you can check by going to a quiet room and listing out
all their subgroups.
Let’s recall some old definitions from IA Groups.
Definition (Orbit). If G acts on a set X, the orbit of x ∈ X is
G · x = {g ∗ x ∈ X : g ∈ G}.
Definition (Stabilizer). If G acts on a set X, the stabilizer of x ∈ X is
G
x
= {g ∈ G : g ∗ x = x}.
The main theorem about these concepts is the orbit-stabilizer theorem.
Theorem (Orbit-stabilizer theorem). Let
G
act on
X
. Then for any
x ∈ X
,
there is a bijection between G · x and G/G
x
, given by g ·x ↔ g · G
x
.
In particular, if G is finite, it follows that
|G| = |G
x
||G · x|.
It takes some work to show this is well-defined and a bijection, but you’ve
done it in IA Groups. In IA Groups, you probably learnt the second statement
instead, but this result is more generally true for infinite groups.