Associated Topics || Dr. Math Home || Search Dr. Math

Parity of Permutations

```
Date: 7/8/96 at 17:46:38
From: Peter Grant
Subject: Parity of Permutations

I can't remember how to PROVE that permutations are either odd or
even.

I can PROVE that any permutation is expressible as a product of
transpositions; I KNOW that for any given permutation the number of
terms in all such expressions is odd or even - and I believe I can
prove it too, but my proof is unbelievably ugly. Surely there's an
elegant one? I'm jiggered if I can remember it, though.

Just a sketch of the "classic" proof would do I think - I do have a
math degree but it was 30+ years ago and the memory's faded but I
think I could still fill in details.

Peter Grant
```

```
Date: 7/9/96 at 5:52:56
From: Doctor Pete
Subject: Re: Parity of Permutations

I don't know if this method is the classical approach, but it appears
in D. Dummit and R. Foote's _Abstract Algebra_.  As requested, I won't
go through all the details (just most :) ), and a complete treatment
can be found in the aforementioned text.

We will denote S(n) to be the symmetric group on n letters, i.e., the
set of permutations of n distinct objects.

Proposition: Every element of S(n) may be written as a product of
transpositions.  (You've proven this.)

Note that such an expression is not necessarily unique.  Therefore, we
show that for any s in S(n), the parity of the number of
transpositions is the same for any product of transpositions equalling
s.

Let x[1],...,x[n] be independent variables and let D be the polynomial

_____
|   |
D =  |   | (x[i]-x[j]) ,
|   |
1<=i<j<=n

i.e., the product of all the terms x[i]-x[j] for i<j.  For each s in
S(n) let's act on D by permuting the variables in the same way it
permutes their indices:

_____
|   |
s(D) =  |   | (x[s(i)]-x[s(j)]) .
|   |
1<=i<j<=n

Note in general that D contains one factor x[i]-x[j] for all i<j, and
since s is a bijection of the indices, s(D) must contain either x[i]-
x[j] or x[j]-x[i], but not both.  In the latter case, we write this as
-(x[i]-x[j]); thus we see that D and s(D) have the same factors up to
a product of -1's; hence s(D) = +/- D, for all s in S(n).

To this end, let e(s) = +1 if s(D) = D, and -1 if s(D) = -D.

Definition:  e(s) is called the *sign* of s
Definition:  s is called an *even permutation* if e(s)=1 and an
*odd permutation* if e(s)=-1.

Proposition:  The map e : S(n) --> {-1, +1} is a homomorphism.

Proof:  Suppose s(D) has exactly k factors of the form x[j]-x[i] with
j>i, so e(s)=(-1)^k.  When calculating (ts)(D) (where s, t are
permutations in S(n)), after first applying s to the indices we see
that (ts)(D) has exactly k factors of the form x[t(j)]-x[t(i)] with
j > i.  Interchanging these, all factors now have the form
x[t(p)]-x[t(q)], with p < q.  Thus

_____
|   |
(ts)(D) = e(s) |   | (x[t(p)]-x[t(q)]) .
|   |
1<=p<q<=n

But this latter product is e(t)D, so (ts)(D) = e(s)e(t)D, and it
follows that e(ts) = e(s)e(t) = e(t)e(s).

Proposition:  Transpositions are all odd permutations and e is a
surjective homomorphism.

Proof:  This is seen by finding e((i j)) for any (i j) in S(n).
Clearly, e((1 2)) = -1.  Let L be the permutation that interchanges 1
and i, 2 and j, and fixes the remainder.  Then (i j) = L(1 2)L, and
since e is a homomorphism, computation yields e((i j)) = -1.

From this, it is easy to see that any two equivalent representations
of a permutation written as a product of transpositions have the same
parity of transpositions, and thus any permutation is either even or
odd.  In addition, a permutation is odd if and only if the number of
cycles of even length in its cycle decomposition is odd.

I rather like it, don't you?

-Doctor Pete,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
College Linear Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search