This lecture introduces the concept of sign (or signature) of a permutation of a set of natural numbers. The concept will be used in the definition of the determinant of a matrix.
We are going to assume that the reader is already familiar with the concept of permutation.
We are going to deal with permutations of the set of the first natural numbers
Remember that a permutation is one of the possible ways to order the elements of a set.
We will denote a permutation by where is the first element of the permutation, is the second, and so on.
Example Consider the set of the first four natural numbersThen,is a permutation. Its elements can be denoted as follows:Another permutation isand we write
Also remember that the number of all possible permutations of the first natural numbers is the factorial of :
Example There arepossible permutations of the first three natural numbers. They are
An important concept is that of inversion.
Definition A couple of elements of a permutation and is said to be an inversion if and only ifbut
In other words, two elements are an inversion if their natural order is inverted.
Example Consider the following permutation of the first five natural numbers:It contains the following inversions:
We now define the parity of a permutation.
Definition A permutation is said to be even if and only if the total number of inversions it contains is even. Otherwise, it is said to be odd.
In the previous example there were inversions. So, the parity of the permutation in that example was odd.
Here is another example.
Example Consider the following permutation of the first four natural numbers:Its inversions areThus, there are a total of inversions. As a consequence, the permutation is even.
We are now ready to define the concept of sign (or signature).
Definition The sign of a permutation , denoted by is a function defined as follows:
Example The permutationdefined in the previous example was even. Therefore, .
We are now going to analyze how simple changes in the order of the elements of a permutation affect its sign.
Definition The operation of interchanging any two distinct elements of a permutation is called a transposition. If the elements are adjacent, then it is called an adjacent transposition.
Example Consider the following permutation of the first five natural numbers:The operation of interchanging its second and fourth element so as to obtain the new permutationis a transposition. If we now interchange the first and second elementwe are performing an adjacent transposition.
The effect of transpositions on parity is characterized as follows.
Proposition If a permutation is odd, a transposition makes it even.
Proposition If a permutation is even, a transposition makes it odd.
Let us start from the simpler case of an adjacent transposition. Let and be the two elements involved in the transposition. If and are not an inversion, then they become an inversion. No other inversions are affected by the transposition. As a consequence, the total number of inversions in the permutation increases by one unit. On the contrary, if and are an inversion, then by interchanging them we remove the inversion and the total number of inversions decreases by one unit. Thus, the number of inversions either decreases or increases by one unit. If it is odd, it becomes even. If it is even, it becomes odd. In other words, the two propositions above hold for adjacent transpositions. Let us now tackle the case in which the transposition is not adjacent. Let and be two elements involved in the transposition. We perform adjacent transpositions to move to position (we always interchange with the nearest element on its right). After performing these adjacent transpositions, is in the right position (), while is in position . We now perform adjacent transpositions to move to position . Therefore, we perform an odd number () of adjacent transpositions. Since each adjacent transposition changes the parity of the permutation, an odd number of them changes the parity (even becomes odd and vice-versa).
Below you can find some exercises with explained solutions.
Find the number of inversions in the permutation
The inversions areSo, there are inversions.
Determine the sign of the permutation
The inversions areSo there are inversions, the parity is odd, and the sign of the permutation is .
Consider the permutationand the transposition of its first and fourth element, giving
Write down a sequence of adjacent transpositions that allows you to obtain the same result.
We first move the first element to the last position by adjacent transpositions:The element is now in the penultimate position and we move it backwards:
Please cite as:
Taboga, Marco (2021). "Sign of a permutation", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/sign-of-a-permutation.
Most of the learning materials found on this website are now available in a traditional textbook format.