Parity of PermutationsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/