Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Sign of a permutation

by , PhD

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.

Table of Contents

Permutations of the first n natural numbers

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 n natural numbers[eq1]

Remember that a permutation is one of the possible ways to order the elements of a set.

We will denote a permutation by [eq2]where [eq3] is the first element of the permutation, [eq4] is the second, and so on.

Example Consider the set of the first four natural numbers[eq5]Then,[eq6]is a permutation. Its elements can be denoted as follows:[eq7]Another permutation is[eq8]and we write[eq9]

Also remember that the number of all possible permutations of the first n natural numbers is the factorial of n: [eq10]

Example There are[eq11]possible permutations of the first three natural numbers. They are[eq12]

Inversions

An important concept is that of inversion.

Definition A couple of elements of a permutation [eq13] and [eq14] is said to be an inversion if and only if[eq15]but[eq16]

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:[eq17]It contains the following inversions:[eq18]

Parity of a permutation

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 $7$ 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:[eq19]Its inversions are[eq20]Thus, there are a total of $4$ inversions. As a consequence, the permutation is even.

Definition of sign

We are now ready to define the concept of sign (or signature).

Definition The sign of a permutation $pi $, denoted by [eq21] is a function defined as follows:[eq22]

Example The permutation[eq23]defined in the previous example was even. Therefore, [eq24].

Transpositions

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:[eq25]The operation of interchanging its second and fourth element so as to obtain the new permutation[eq26]is a transposition. If we now interchange the first and second element[eq27]we 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.

Proof

Let us start from the simpler case of an adjacent transposition. Let [eq28] and [eq29] be the two elements involved in the transposition. If [eq30] and [eq29] 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 [eq32] and [eq29] 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 [eq30] and [eq35] be two elements involved in the transposition. We perform $m$ adjacent transpositions to move [eq30] to position $i+m$ (we always interchange [eq30] with the nearest element on its right). After performing these $m$ adjacent transpositions, [eq38] is in the right position ($i+m$), while [eq39] is in position $i+m-1$. We now perform $m-1$ adjacent transpositions to move [eq40] to position i. Therefore, we perform an odd number ($2m-1$) 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).

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Find the number of inversions in the permutation[eq41]

Solution

The inversions are[eq42]So, there are $5$ inversions.

Exercise 2

Determine the sign of the permutation[eq43]

Solution

The inversions are[eq44]So there are $3$ inversions, the parity is odd, and the sign of the permutation is $-1$.

Exercise 3

Consider the permutation[eq45]and the transposition of its first and fourth element, giving[eq46]

Write down a sequence of adjacent transpositions that allows you to obtain the same result.

Solution

We first move the first element to the last position by adjacent transpositions:[eq47]The element [eq48] is now in the penultimate position and we move it backwards:[eq49]

How to cite

Please cite as:

Taboga, Marco (2021). "Sign of a permutation", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/sign-of-a-permutation.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.

Featured pages
Explore
Main sections
About
Glossary entries
Share
  • To enhance your privacy,
  • we removed the social buttons,
  • but don't forget to share.