Parity

Since ( ), we see that the representation of a permutation (even a cycle) as a product of transpositions is not necessarily unique. Since we see that even the number of transpositions needed to factor a cycle is not necessarily unique. There is, nevertheless, something unique about the factorization, namely, whether the number of transpositions needed is even or odd. We proceed to state this result precisely, and to prove it.

Assume, for simplicity of notation, that . Let be the polynomial (in four variables , , , ) defined by (In the general case is the product of all the differences , with .) Each permutation in converts into a new polynomial, denoted by ; by definition In words: to obtain , replace each variable in by the one whose subscript is obtained by allowing to act on the subscript of the given one. If, for instance, , then If , so that , then both and are equal to These computations illustrate, and indicate the proofs of, three important facts. (1) For every permutation , the factors of are the same as the factors of , except possibly for sign and order ; consequently or else . The permutation is called even if and odd if . The signum (or sign ) of a permutation , denoted by , is or according as is even or odd, so that we always have . The fact that is even, or odd, is sometimes expressed by saying that the parity of is even, or odd, respectively. (2) If is a transposition, then , or, equivalently, every transposition is odd. The proof is the obvious generalization of the following reasoning about the special example . Exactly one factor of contains both and , and that one changes sign in the passage from to . If a factor contains neither nor , it stays fixed. The factors containing only one of and come in pairs (such as the pair and , or the pair and ). Each factor in such a pair goes into the other factor, except possibly that its sign may change; if it changes for one factor, it will change for its mate. (3) If and are permutations then ; consequently is even if and only if and have the same parity. Observe that .

It follows from (2) and (3) that a product of a bunch of transpositions is even if and only if there are an even number of them, and it is odd otherwise. (Note, in particular, by looking at the proof of Section: Cycles , Theorem 2, that a -cycle is even if and only if is odd; in other words, if is a -cycle, then .) Conclusion: no matter how a permutation is factored into transpositions, the number of factors is always even (this is the case if is even), or else it is always odd (this is the case if is odd).

The product of two even permutations is even; the inverse of an even permutation is even; the identity permutation is even. These facts are summed up by saying that the set of all even permutations is a subgroup of ; this subgroup (to be denoted by ) is called the alternating group of degree k .

EXERCISES