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.

Proof

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

Solution

The inversions areSo, there are inversions.

Determine the sign of the permutation

Solution

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.

Solution

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.

The books

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

Featured pages

- Bayes rule
- Multinomial distribution
- Hypothesis testing
- Bernoulli distribution
- Independent events
- F distribution

Explore

Main sections

- Mathematical tools
- Fundamentals of probability
- Probability distributions
- Asymptotic theory
- Fundamentals of statistics
- Glossary

About

Glossary entries

- Distribution function
- Probability mass function
- Precision matrix
- Null hypothesis
- Estimator
- Probability density function

Share

- To enhance your privacy,
- we removed the social buttons,
- but
**don't forget to share**.