2Symmetric group I
IA Groups
2.2 Sign of permutations
To classify different permutations, we can group different permutations according
to their cycle type. While this is a very useful thing to do, it is a rather fine
division. In this section, we will assign a “sign” to each permutation, and each
permutation can either be odd or even. This high-level classification allows us
to separate permutations into two sets, which is also a useful notion.
To define the sign, we first need to write permutations as products of
transpositions.
Proposition. Every permutation is a product of transpositions.
This is not a deep or mysterious fact. All it says is that you can rearrange
things however you want just by swapping two objects at a time.
Proof.
As each permutation is a product of disjoint cycles, it suffices to prove
that each cycle is a product of transpositions. Consider a cycle (
a
1
a
2
a
3
· · · a
k
).
This is in fact equal to (
a
1
a
2
)(
a
2
a
3
)
· · ·
(
a
k−1
a
k
). Thus a
k
-cycle can be written
as a product of k − 1 transpositions.
Note that the product is not unique. For example,
(1 2 3 4 5) = (1 2)(2 3)(3 4)(4 5) = (1 2)(2 3)(1 2)(3 4)(1 2)(4 5).
However, the number of terms in the product, mod 2, is always the same.
Theorem. Writing
σ ∈ S
n
as a product of transpositions in different ways,
σ
is
either always composed of an even number of transpositions, or always an odd
number of transpositions.
The proof is rather magical.
Proof.
Write #(
σ
) for the number of cycles in disjoint cycle notation, including
singleton cycles. So #(
e
) =
n
and #((1 2)) =
n −
1. When we multiply
σ
by a
transposition τ = (c d) (wlog assume c < d),
–
If
c, d
are in the same
σ
-cycle, say, (
c a
2
· · · a
k−1
d a
k+1
· · · a
k+l
)(
c d
) =
(c a
k+1
a
k+2
· · · a
k+l
)(d a
2
a
3
· · · a
k−1
). So #(στ) = #(σ) + 1 .
– If c, d are in different σ-cycles, say
(d a
2
a
3
· · · a
k−1
)(c a
k+1
a
k+2
· · · a
k+l
)(c d)
= (c a
2
· · · a
k−1
d a
k+1
· · · a
k+l
)(c d)(c d)
= (c a
2
· · · a
k−1
d a
k+1
· · · a
k+l
) and #(στ ) = #(σ) − 1.
Therefore for any transposition τ, #(στ) ≡ #(σ) + 1 (mod 2).
Now suppose
σ
=
τ
1
· · · τ
l
=
τ
′
1
· · · τ
′
k
. Since disjoint cycle notation is unique,
#(σ) is uniquely determined by σ.
Now we can construct
σ
by starting with
e
and multiplying the transpositions
one by one. Each time we add a transposition, we increase #(
σ
) by 1 (
mod
2).
So #(
σ
)
≡
#(
e
) +
l
(
mod
2). Similarly, #(
σ
)
≡
#(
e
) +
k
(
mod
2). So
l ≡ k
(mod 2).
Definition (Sign of permutation). Viewing
σ ∈ S
n
as a product of transpositions,
σ
=
τ
1
· · · τ
l
, we call
sgn
(
σ
) = (
−
1)
l
. If
sgn
(
σ
) = 1, we call
σ
an even permutation.
If sgn(σ) = −1, we call σ an odd permutation.
While
l
itself is not well-defined, it is either always odd or always even, and
(−1)
l
is well-defined.
Theorem. For n ≥ 2, sgn : S
n
→ {±1} is a surjective group homomorphism.
Proof.
Suppose
σ
1
=
τ
1
· · · τ
l
1
and
σ
2
=
τ
′
1
· · · τ
l
2
. Then
sgn
(
σ
1
σ
2
) = (
−
1)
l
1
+l
2
=
(−1)
l
1
(−1)
l
2
= sgn(σ
1
) sgn(σ
2
). So it is a homomorphism.
It is surjective since sgn(e) = 1 and sgn((1 2)) = −1.
It is this was rather trivial to prove. The hard bit is showing that
sgn
is
well defined. If a question asks you to show that
sgn
is a well-defined group
homomorphism, you have to show that it is well-defined.
Lemma.
σ
is an even permutation iff the number of cycles of even length is
even.
Proof.
A
k
-cycle can be written as
k −
1 transpositions. Thus an even-length
cycle is odd, vice versa.
Since
sgn
is a group homomorphism, writing
σ
in disjoint cycle notation,
σ
=
σ
1
σ
2
· · · σ
l
, we get
sgn
(
σ
) =
sgn
(
σ
1
)
· · · sgn
(
σ
l
). Suppose there are
m
even-
length cycles and
n
odd-length cycles, then
sgn
(
σ
) = (
−
1)
m
1
n
. This is equal to
1 iff (−1)
m
= 1, i.e. m is even.
Rather confusingly, odd length cycles are even, and even length cycles are
odd.
Definition (Alternating group
A
n
). The alternating group
A
n
is the kernel of
sgn
, i.e. the even permutations. Since
A
n
is a kernel of a group homomorphism,
A
n
≤ S
n
.
Among the many uses of the
sgn
homomorphism, it is used in the definition
of the determinant of a matrix: if A
n×n
is a square matrix, then
det A =
X
σ∈S
n
sgn(σ)a
1σ(1)
· · · a
nσ(n)
.
Proposition. Any subgroup of
S
n
contains either no odd permutations or
exactly half.
Proof.
If
S
n
has at least one odd permutation
τ
, then there exists a bijection
between the odd and even permutations by
σ 7→ στ
(bijection since
σ 7→ στ
−1
is a well-defined inverse). So there are as many odd permutations as even
permutations.
After we prove the isomorphism theorem later, we can provide an even shorter
proof of this.