In mathematics, when X is a finite set of at least two elements, the permutations of X (i.e. the bijective mappings 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).
The sign or signature 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 S_{n}. Another notation for the sign of a permutation is given by the more general LeviCivita symbol (ε_{σ}), which is defined for all maps from X to X, and has value zero for nonbijective maps.
The sign of a permutation can be explicitly expressed as
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
where m is the number of transpositions in the decomposition. Despite that 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 welldefined.^{[1]}
Contents
Example
Consider the permutation σ of the set {1,2,3,4,5} which turns the initial arrangement 12345 into 34521. It can be obtained by three transpositions: first exchange the places of 3 and 5, then exchange places 2 and 4, and finally exchange places 1 and 5. This shows that the given permutation σ is odd. Using the notation explained in the permutation article, we can write
There are many other ways of writing σ as a composition of transpositions, for instance
but it is impossible to write it as a product of an even number of transpositions.
Full article ▸
