Parity of a permutation
Property in group theory / From Wikipedia, the free encyclopedia
In mathematics, when X is a finite set with at least two elements, the permutations of X (i.e. the bijective functions from X to X) fall into two classes of equal size: the even permutations and the odd permutations. If any total ordering of X is fixed, the parity (oddness or evenness) of a permutation of X can be defined as the parity of the number of inversions for σ, i.e., of pairs of elements x, y of X such that x < y and σ(x) > σ(y).
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Symmetric_group_4%3B_permutation_list.svg/220px-Symmetric_group_4%3B_permutation_list.svg.png)
Odd permutations have a green or orange background. The numbers in the right column are the inversion numbers (sequence A034968 in the OEIS), which have the same parity as the permutation.
The sign, signature, or signum of a permutation σ is denoted sgn(σ) and defined as +1 if σ is even and −1 if σ is odd. The signature defines the alternating character of the symmetric group Sn. Another notation for the sign of a permutation is given by the more general Levi-Civita symbol (εσ), which is defined for all maps from X to X, and has value zero for non-bijective maps.
The sign of a permutation can be explicitly expressed as
- sgn(σ) = (−1)N(σ)
where N(σ) is the number of inversions in σ.
Alternatively, the sign of a permutation σ can be defined from its decomposition into the product of transpositions as
- sgn(σ) = (−1)m
where m is the number of transpositions in the decomposition. Although such a decomposition is not unique, the parity of the number of transpositions in all decompositions is the same, implying that the sign of a permutation is well-defined.[1]