7Permutation representations
II Representation Theory
7 Permutation representations
In this chapter, we are going to study permutation representations in a bit more
detail, since we can find some explicit formulas for the character of them. This
is particularly useful if we are dealing with the symmetric group.
Let
G
be a finite group acting on a finite set
X
=
{x
1
, ··· , x
n
}
(sometimes
known as a
G
-set). We define
CX
to be the complex vector space with basis
{e
x
1
, ··· , e
x
n
}. More explicitly,
CX =
X
j
a
j
e
x
j
: a
j
∈ C
.
There is a corresponding representation permutation
ρ
X
: G → GL(CX)
g 7→ ρ(g)
where
ρ
(
g
) :
e
x
j
7→ e
gx
j
, extended linearly. We say
ρ
X
is the representation
corresponding to the action of G on X.
This is a generalization of the group algebra — if we let
G
act on itself by
left multiplication, then this is in fact the group algebra.
The corresponding matrix representations
ρ
X
(
g
) with respect to the basis
{e
x
}
x∈X
are permutation matrices — it is 0 everywhere except for one 1 in each
row and column. In particular, (
ρ
(
g
))
ij
= 1 precisely when
gx
j
=
x
i
. So the
only non-zero diagonal entries in
ρ
(
g
) are those
i
such that
x
i
is fixed by
g
. Thus
we have
Definition (Permutation character). The permutation character π
X
is
π
X
(g) = |fix(g)| = |{x ∈ X : gx = x}|.
Lemma. π
X
always contains the trivial character 1
G
(when decomposed in the
basis of irreducible characters). In particular,
span{e
x
1
+
···
+
e
x
n
}
is a trivial
G-subspace of CX, with G-invariant complement {
P
x
a
x
e
x
:
P
a
x
= 0}.
Lemma. hπ
X
,
1
i
, which is the multiplicity of 1 in
π
X
, is the number of orbits
of G on X.
Proof.
We write
X
as the disjoint union of orbits,
X
=
X
1
∪ ··· ∪ X
`
. Then
it is clear that the permutation representation on
X
is just the sum of the
permutation representations on the X
i
, i.e.
π
X
= π
X
1
+ ··· + π
x
`
,
where
π
X
j
is the permutation character of
G
on
X
j
. So to prove the lemma, it
is enough to consider the case where the action is transitive, i.e. there is just
one orbit.
So suppose
G
acts transitively on
X
. We want to show
hπ
X
,
1
i
= 1. By
definition, we have
hπ
X
, 1i =
1
|G|
X
g
π
X
(g)
=
1
|G|
|{(g, x) ∈ G × X : gx = x}|
=
1
|G|
X
x∈X
|G
x
|,
where
G
x
is the stabilizer of
x
. By the orbit-stabilizer theorem, we have
|G
x
||X|
=
|G|. So we can write this as
=
1
|G|
X
x∈X
|G|
|X|
=
1
|G|
· |X| ·
|G|
|X|
= 1.
So done.
Lemma. Let G act on the sets X
1
, X
2
. Then G acts on X
1
× X
2
by
g(x
1
, x
2
) = (gx
1
, gx
2
).
Then the character
π
X
1
×X
2
= π
X
1
π
X
2
,
and so
hπ
X
1
, π
X
2
i = number of orbits of G on X
1
× X
2
.
Proof.
We know
π
X
1
×X
2
(
g
) is the number of pairs (
x
1
, x
2
)
∈ X
1
× X
2
fixed by
g
. This is exactly the number of things in
X
1
fixed by
g
times the number of
things in X
2
fixed by g. So we have
π
X
1
×X
2
(g) = π
X
1
(g)π
X
2
(g).
Then using the fact that π
1
, π
2
are real, we get
hπ
X
1
, π
X
2
i =
1
|G|
X
g
π
X
1
(g)π
X
2
(g)
=
1
|G|
X
g
π
X
1
(g)π
X
2
(g)1
G
(g)
= hπ
X
1
π
X
2
, 1i
= hπ
X
1
×X
2
, 1i.
So the previous lemma gives the desired result.
Recall that a 2-transitive action is an action that is transitive on pairs, i.e.
it can send any pair to any other pair, as long as the elements in the pair are
distinct (it can never send (
x, x
) to (
x
0
, x
00
) if
x
0
6
=
x
00
, since
g
(
x, x
) = (
gx, gx
)).
More precisely,
Definition
(2-transitive)
.
Let
G
act on
X
,
|X| >
2. Then
G
is 2-transitive on
X
if
G
has two orbits on
X × X
, namely
{
(
x, x
) :
x ∈ X}
and
{
(
x
1
, x
2
) :
x
i
∈
X, x
1
6= x
2
}.
Then we have the following lemma:
Lemma. Let G act on X, with |X| > 2. Then
π
X
= 1
G
+ χ,
with χ irreducible if and only if G is 2-transitive on X.
Proof. We know
π
X
= m
1
1
G
+ m
2
χ
2
+ ··· + m
`
χ
`
,
with 1
G
, χ
2
, ··· , χ
`
distinct irreducible characters and
m
i
∈ N
are non-zero.
Then by orthogonality,
hπ
X
, π
X
i =
j
X
i=1
m
2
i
.
Since
hπ
X
, π
X
i
is the number of orbits of
X × X
, we know
G
is 2-transitive on
X if and only if ` = 2 and m
1
= m
2
= 1.
This is useful if we want to understand the symmetric group, since it is
always 2-transitive (modulo the silly case of S
1
).
Example. S
n
acting on
X
=
{
1
, ··· , n}
is 2-transitive for
n ≥
2. So
π
X
= 1+
χ
,
with
χ
irreducible of degree
n −
1 (since
π
X
has degree
n
). This works similarly
for A
n
, whenever n ≥ 3.
This tells us we can find an irreducible character of
S
n
by finding
π
X
, and
then subtracting 1 off.
Example.
Consider
G
=
S
4
. The conjugacy classes correspond to different
cycle types. We already know three characters — the trivial one, the sign, and
π
X
− 1
G
.
1 3 8 6 6
1 (1 2)(3 4) (1 2 3) (1 2 3 4) (1 2)
trivial χ
1
1 1 1 1 1
sign χ
2
1 1 1 −1 −1
π
X
− 1
G
χ
3
3 −1 0 −1 1
χ
4
χ
5
We know the product of a one-dimensional irreducible character and another
character is another irreducible character, as shown on the first example sheet.
So we get
1 3 8 6 6
1 (1 2)(3 4) (1 2 3) (1 2 3 4) (1 2)
trivial χ
1
1 1 1 1 1
sign χ
2
1 1 1 −1 −1
π
X
− 1
G
χ
3
3 −1 0 −1 1
χ
3
χ
2
χ
4
3 −1 0 1 −1
χ
5
For the last representation we can find the dimension by computing 24
−
(1
2
+
1
2
+ 3
2
+ 3
2
) = 2
2
. So it has dimension 2. To obtain the whole of
χ
5
, we can
use column orthogonality — for example, we let the entry in the second column
be
x
. Then column orthogonality says 1 + 1
−
3
−
3 + 2
x
= 0 . So
x
= 2. In the
end, we find
1 3 8 6 6
1 (1 2)(3 4) (1 2 3) (1 2 3 4) (1 2)
trivial χ
1
1 1 1 1 1
sign χ
2
1 1 1 −1 −1
π
X
− 1
G
χ
3
3 −1 0 −1 1
χ
3
χ
2
χ
4
3 −1 0 1 −1
χ
5
2 2 −1 0 0
Alternatively, we have previously shown that
χ
reg
=
χ
1
+
χ
2
+ 3
χ
3
+ 3
χ
4
+ 2
χ
5
.
By computing χ
reg
directly, we can find χ
5
.
Finally, we can obtain
χ
5
by observing
S
4
/V
4
∼
=
S
3
, and “lifting” characters.
We will do this in the next chapter. In fact, this
χ
5
is the degree-2 irreducible
representation of S
3
∼
=
D
6
lifted up.
We can also do similar things with the alternating group. The issue of course
is that the conjugacy classes of the symmetric group may split when we move to
the alternating group.
Suppose g ∈ A
n
. Then
|C
S
n
(g)| = |S
n
: C
S
n
(g)|
|C
A
n
(g)| = |A
n
: C
A
n
(g)|.
We know
C
S
n
(
g
)
⊇ C
A
n
(
g
), but we need not have equality, since elements needed
to conjugate
g
to
h ∈ C
S
n
(
g
) might not be in
A
n
. For example, consider
σ = (1 2 3) ∈ A
3
. We have C
A
3
(σ) = {σ} and C
S
3
(σ) = {σ, σ
−1
}.
We know
A
n
is an index 2 subgroup of
S
n
. So
C
A
n
(
g
)
⊆ C
S
n
(
g
) either has
index 2 or 1. If the index is 1, then
|C
A
n
|
=
1
2
|C
S
n
|
. Otherwise, the sizes are
equal.
A useful criterion for determining which case happens is the following:
Lemma.
Let
g ∈ A
n
,
n >
1. If
g
commutes with some odd permutation in
S
n
,
then
C
S
n
(
g
) =
C
A
n
(
g
). Otherwise,
C
S
n
splits into two conjugacy classes in
A
n
of
equal size.
This is quite useful for doing the examples on the example sheet, but we will
not go through any more examples here.