Parity of a permutation

but it is impossible to write it as a product of an even number of transpositions.

A cycle is even if and only if its length is odd. This follows from formulas like

In practice, in order to determine whether a given permutation is even or odd, one writes the permutation as a product of disjoint cycles. The permutation is odd if and only if this factorization contains an odd number of even-length cycles.

Another method for determining whether a given permutation is even or odd is to construct the corresponding permutation matrix and compute its determinant. The value of the determinant is the same as the parity of the permutation.

This section presents proofs that the parity of a permutation σ can be defined in two equivalent ways:

Every transposition can be written as a product of an odd number of transpositions of adjacent elements, e.g.

Consider the elements that are sandwiched by the two elements of a transposition. Each one lies above completely above, completely below or between the two transposition elements.