Permutation/Sign/Introduction/Section
The sign is or , because in the numerator and in the denominator, up to sign, the same differences occur. Thus, for the sign, there are only two possible values. For , we say that is an even permutation, and for , we say that is an odd permutation.
Let and let be a permutation on . Let denote the number of inversions of . Then the sign of equals
We write
because, after this reordering, we have in the numerator as well as in the denominator the product of all positive differences.
We consider the permutation
with the cycle representation
The inversions are
so there are of those. The sign is due to fact, and the permutation is odd.
The sign is a group homomorphism in the sense of the following definition.
Let and let be a permutation on . Let
be written as a product of transpositions. Then the sign can be described as
Suppose that the transposition swaps the numbers . Then
The last equation follows from the fact that, in the first and the second product, all numerators and denominators are positive, and the fact that, in the third and in the forth product, the numerators are negative and the denominators are positive. Therefore, as the index sets of the third and the fourth product coincide, all the signs cancel each other.
The statement follows from the case of a transposition via the homomorphism property.
Let be an arbitrary set with elements, but without an ordering, and let be a permutation on . Then we can not talk about inversions, and the definition of sign via products of differences is not directly applicable. However, we can look at fact in order to define the sign in this slightly more general situation. For this, we write as a product of transpositions and define
To see that this is well-defined, we consider a bijection
The permutation on defines on the permutation . Let be a representation as a product of transpositions on . Then
where . These are also transpositions, so that the parity of is determined by the sign of .