Permutation/Sign/Introduction/Section


Let and let be a permutation on . Then we call the number

the sign of the permutation .

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 . We call an index pair

an inversion (of ), if

holds.


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 denote groups. A mapping

is called group homomorphism, if the equality

holds for all

.


The sign mapping

is a

group homomorphism.

Let two permutations and be given. Then



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 .