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

=

τ

0

1

· · · τ

0

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 transpo-

sitions,

σ

=

τ

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

=

τ

0

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.