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.

Thanks in advance,
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/