Parity of a permutation

The sign, also called Signum, signature or parity, is in combinatorics an important indicator of permutations. The sign of a permutation, the values ​​or accept, where one speaks in the first case of a straight and in the second case of an odd permutation.

There are several ways to characterize even and odd permutations. Such a permutation is exactly then just when the number of failed items in the permutation is even. Every permutation can also be as a concatenation of finitely many transpositions represent and exactly then just when the number of their needed transpositions is even. A permutation may also be divided into cycles, and is then exactly straight when the number of cycles even length is straight. The sign of a permutation is equal to the determinant of the corresponding permutation matrix.

The Signum is as picture is a group homomorphism of the symmetric group of permutations in the multiplicative group over the crowd. An important application example of the sign is the Leibniz formula for determinants.

• 4.1 Presentation of the number of transpositions
• 4.2 Display of the number and length of cycles
• 4.3 Representation of the determinant of the permutation matrix

• 5.1 widths
• 5.2 Inverse permutations
• 5.3 homomorphism

Definition

Is the symmetric group of all permutations of the set, then the sign of a permutation is

, said

The number of missing items of the permutation. If the sign is called the permutation is even, it is they are called odd.

General also permutations of arbitrary finite ordered sets can be considered for the mathematical analysis can, however, on the first natural numbers limit.

Examples

The incorrect readings of the permutation

And are, thus,

And thus the odd permutation. The identity permutation

Is always even, because it has no false stands on. The accompanying table lists all permutations of length three on with their associated signs.

View as product

Product formula

The sign of a permutation of the first natural numbers can also by the product formula

Are shown. Due to the bijectivity of a permutation in this case each term for up occurs where appropriate, the sign once each in the numerator and denominator of a fraction at once. Every unsuccessful state leads to exactly one negative sign.

Example

The sign of the permutation

Is through

Given. The two faulty items and run it to each one sign change.

Concatenation property

For the sign of a concatenation of two permutations is valid based on the product representation:

The last step, it follows that in the product have the same factors, such as occur in the product on, only in a different order. For two, due to reversed figures, while the signs are reversed in both the denominator and the numerator. Accordingly, the composition of two permutations is exactly then just when both permutations have the same Signum.

Further illustrations

Representation of the number of transpositions

A transposition is a permutation of the two numbers and the only switched, that is, as well as maps and to be the other numbers. For the sign of a transposition

Because every transposition can be carried as a concatenation of an odd number of Nachbarvertauschungen the form

Represent. In this case, first, the speed is brought to the site by successively Nachbarvertauschungen and then the number of the place by successive Nachbarvertauschungen to said site. After each of these Nachbarvertauschungen just creates a false state, the total number of incorrect items a transposition

And thus always odd. Every permutation can now be represented as a concatenation of at most transpositions. Each of these transpositions reversed in each case the smallest number for which it holds with that number applies. In this case, the number of required transpositions, then applies a result of the concatenation feature

There are of course other ways to represent a permutation as a concatenation of transpositions. But If it is an even permutation, then the number of required transpositions is always straight, it is an odd permutation always odd.

Example

The permutation

Can be extended by

Pose and is so straight. Another representation of a chain of transpositions would be about.

Representation of the number and length of cycles

A cyclic permutation is a permutation that swaps the numbers cyclically, that is, maps on to up to and to be the other numbers. A cyclic permutation of length two corresponds to just a transposition of two numbers. Each cyclic permutation of the length can be written as a concatenation of transpositions:

Since transpositions are odd, the sign of a cyclic permutation of the length is due to the chaining property

A cyclic permutation is exactly then just when its length is odd. Every permutation can now be uniquely represented as a concatenation of cyclic permutations of pairwise disjoint cycles. Are the lengths of these cycles, then applies due to the chaining property

The Signum can therefore be read directly from the Zykeltyp the permutation. A permutation is accordingly exactly then even if the sum of the lengths of the individual cycles, minus the number of cycles is straight. Since cycles of odd length do not change the sign, a permutation is exactly then just when the number of cycles even length is even. After there is the order of a permutation of the least common multiples of their cycles lengths, is a permutation with odd order is always even.

Example

The permutation

Divided into three disjoint cycles in Zykelschreibweise

Since the sum is odd, the permutation is also odd. To a cycle in Zykelschreibweise and the count also be omitted, without changing the amount and hence the sign.

Representation of the determinant of the permutation matrix

Is the related to the permutation permutation matrix with entries

Then corresponds to the sign of the determinant of straight, so

For the practical calculation of the sign, however, this representation is usually inadequate.

Example

The permutation for

Corresponding permutation matrix is

Whose determinant to the Rule of Sarrus

Results.

Other properties

Widths

There are just different permutations of the set. For the set of all permutations of the even and odd permutations into two equal halves is divided, because there are an equal number of ways to choose the sign in the numerator of the definition of the sign so that the product is positive or negative. Is then valid for the cardinality of these two quantities

For this reason, one speaks here with the Signum also from parity (from the Latin paritas equality ) of a permutation.

Inverse permutations

For the sign of the inverse permutation of the following applies:

By inverting So the sign of a permutation does not change, which is also directly over the concatenation property

Can be seen.

Homomorphism

Due to the chaining property represents the image

A group homomorphism of the symmetric group into the multiplicative group represents (this is just the cyclic group of degree 2 ). This property is used in the theory of determinants, such as the Leibniz formula. The core of the homomorphism, the amount of the straight permutations. It forms a normal subgroup of the alternating group. However, the set of odd permutations does not form a subset of, because the concatenation of two odd permutations results in an even permutation.

Use

The sign of permutations is used inter alia in the following areas:

• In characterization of the determinant of a matrix on the Leibniz formula
• In the definition of antisymmetric functions, such as alternating multilinear forms
• In the determination of the accessible positions in the puzzle 15

Generalization

A generalization of the sign for not necessarily bijective maps is the Levi -Civita symbol, with the notation above for how the sign

Can be defined. However, in contrast to the Signum Levi -Civita symbol can also assume the value, which is exactly the case when the mapping is not bijective. The Levi- Civita symbol is used in particular in the vector and tensor calculus in applications such as the theory of relativity and quantum mechanics.