Even and odd permutations

related topics
{math, number, function}

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 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

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 well-defined.[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 ▸

related documents
Cauchy's integral formula
Morphism
Yoneda lemma
Weak topology
Stone–Weierstrass theorem
Positive-definite matrix
Integer factorization
Boolean algebra (structure)
Finite difference
Hypercomplex number
Liouville number
Expander graph
Topology
Line integral
LL parser
Solvable group
Power set
Algebraically closed field
Stokes' theorem
Parameter
Associative array
Antiderivative
Document Type Definition
Blackboard bold
Julia set
Henri Lebesgue
Optimization (mathematics)
Heapsort
Max-flow min-cut theorem
Polytope