Sign (permutation)
The sign , also known as the sign , signature or parity , is an important number of permutations in combinatorics . The sign of a permutation can take the values or , in the first case one speaks of an even and in the second case of an odd permutation.
There are several ways to characterize even and odd permutations. A permutation is even if the number of errors in the permutation is even . Each permutation can also be represented as a concatenation of a finite number of transpositions and is even if the number of transpositions required is even. A permutation can also be broken down into cycles and is even if the number of cycles of even length is even. The sign of a permutation is also equal to the determinant of the associated permutation matrix .
As a mapping, the sign is a group homomorphism from the symmetrical group of permutations into the multiplicative group above the set . An important application example of the sign is the Leibniz formula for determinants .
definition
If the set is the symmetric group of all permutations , then the sign of a permutation is given by
defined, where
is the set of permutation errors .
stands for the thickness (number of elements) of .
If the sign is called the permutation even, if it is , it is called odd.
In a more general way, permutations of any finite ordered sets can be considered, but the mathematical analysis can be limited to the first natural numbers.
Examples
permutation | Deficiencies | Signum |
---|---|---|
- | +1 | |
(2.3) | −1 | |
(1.2) | −1 | |
(1.3), (2.3) | +1 | |
(1.2), (1.3) | +1 | |
(1.3) | −1 |
The imperfections of the permutation
are and , thus is
and thus the permutation is odd. The identical permutation
is always straight because it has no defects. The table opposite lists all permutations of length three with their associated signs.
Presentation as a product
Product formula
The sign of a permutation of the first natural numbers can also be given by the product formula
being represented. Due to the bijectivity a permutation this case each term occurs for the exception of possibly sign denominator once each in the numerator and once a fracture on. Each deficit leads to exactly one negative sign.
example
The sign of the permutation
is through
given. The two faulty items and lead it to each one sign change.
Concatenation property
The following applies to the sign of a concatenation of two permutations due to the product representation:
The last step follows from the fact that the same factors appear in the product as in the product above , only in a different order. For two numbers that have been swapped , the sign is reversed in both the denominator and the numerator. Accordingly, the concatenation of two permutations is even if and only if both permutations have the same sign.
Further representations
Representation of the number of transpositions
A transposition with is a permutation that only swaps the two numbers and , that is, maps onto and onto and leaves the other numbers fixed. The following applies to the sign of a transposition
- ,
because every transposition can be an odd number of Nachbarvertauschungen the mold as the concatenation by
represent. Here, the number is first by successive Nachbarvertauschungen the place taken and then the number of the place by successive Nachbarvertauschungen the place . Since each of these neighboring swaps produces exactly one missing position, the total number of missing positions is a transposition
and therefore always odd. Each permutation can now be represented as a chain of at most transpositions. Each of these transpositions swaps the smallest number for which applies with the number for which applies. If the number of transpositions required is then the following applies due to the chaining property
- .
There are of course other ways of representing a permutation as a chain of transpositions. However, if the permutation is even, then the number of transpositions required is always even; if the permutation is odd, it is always odd.
example
The permutation
lets through
represent and is thus straight. Another representation of as a chain of transpositions would be .
Representation of the number and length of the cycles
A cyclic permutation is a permutation that the numbers cyclically changed over , that is, on maps, on to on and to be the other numbers. A cyclic permutation of length two corresponds to a transposition of two numbers. Every cyclic permutation of length can be written as a chain of transpositions:
- .
Since transpositions are odd, the sign of a cyclic permutation is length due to the concatenation property
- .
A cyclic permutation is even if and only if its length is odd. Each permutation can now be clearly represented as a concatenation of cyclic permutations with pairwise disjoint cycles. If the lengths of these cycles are, then due to the chaining property
- .
The sign can therefore be read directly from the cycle type of the permutation. Accordingly, a permutation is even if the sum of the lengths of the individual cycles minus the number of cycles is even. Since cycles of odd length do not change the sign, a permutation is even if the number of cycles of even length is even. Since the order of a permutation results from the smallest common multiple of its cycle length, a permutation with an odd order is always even.
example
The permutation
splits into three disjoint cycles, in cycle notation
- .
Since the sum is odd, the permutation is also odd. Single cycles can also be omitted in the cycle notation and in the counting without changing the sum and thus the sign.
Representation via the determinant of the permutation matrix
Is the permutation matrix with entries belonging to the permutation
then corresponds to the sign of just the determinant of so
- .
However, this representation is mostly unsuitable for the practical calculation of the sign.
example
The one for permutation
associated permutation matrix is
- ,
whose determinant after the rule of sarrus to
results.
Other properties
Powers
There are exactly different permutations of the set . For , the set of all permutations is divided into two equally large halves by the even and odd permutations, because there are equally many possibilities to choose the sign in the numerator of the product formula so that the product is positive or negative. The following applies to the power of these two sets
- .
For this reason, in addition to the sign, one speaks here of the parity (from Latin paritas , equality ) of a permutation.
Inverse permutations
For the sign of the inverse permutation of :
- .
Inverting does not change the sign of a permutation, which is also directly related to the concatenation property
can be seen.
Signum homomorphism
Due to the chaining property, the figure represents
represent a group homomorphism from the symmetric group to the multiplicative group (this is precisely the cyclic group of degree 2 ). This property is used in the theory of determinants, for example the Leibniz formula . The core of this homomorphism is the set of even permutations. It forms a normal divisor of , the alternating group . However, the set of odd permutations does not form a subgroup of , because the concatenation of two odd permutations results in an even permutation.
Conjugated permutations have the same sign as follows from the properties of sign homomorphism. Is namely , then applies to everyone
- .
use
The sign of permutations is used in the following areas, among others:
- when characterizing the determinant of a matrix using the Leibniz formula
- in the definition of antisymmetric functions , e.g. alternating multilinear forms
- in Zolotareff's lemma to represent the Legendre symbol
- in determining the achievable positions in the 15 puzzle
A very clear example can be found in the Futurama episode " In the body of the friend ". The character "Professor Farnsworth" invents a machine that swaps the souls of two people (so that the soul of person A is in the body of person B and the soul of person B is in the body of person A). Regardless of the number of exchanges made (and how many people were involved), an odd number of permutations is always necessary so that everyone is back in their own body.
generalization
A generalization of the signum for not necessarily bijective representations is the Levi-Civita symbol , which starts with the notation for like the signum about
can be defined. In contrast to the Signum, the Levi-Civita-Symbol can also take on the value , which is exactly the case when the image is not bijective. The Levi-Civita symbol is used in particular in vector and tensor calculus in applications such as relativity and quantum mechanics .
literature
- Albrecht Beutelspacher : Linear Algebra. An introduction to the science of vectors, maps, and matrices . 6th edition. Vieweg, 2009, ISBN 3-528-56508-X .
- Siegfried Bosch : Linear Algebra . Springer, 2009, ISBN 3-540-76437-2 .
Web links
- Eric W. Weisstein : Even Permutation . In: MathWorld (English).
- Eric W. Weisstein : Odd Permutation . In: MathWorld (English).
- Raymond Puzio, Larry Hammick, Pedro Sanchez: Signature of a permutation . In: PlanetMath . (English)
Individual evidence
- ^ Burkard Polster: The parity of permutations and the Futurama theorem. Retrieved June 21, 2019 .