Algebra Notes 3

3.1) Permutations

Every ordering of the first n natural numbers $1,2,\dots,n$ is called a permutation.

There are $n!$ permutations of the first n natural numbers.

3.2) Inversions

If we have the permutation $i_1, i_2, \dots i_n$ (of the first n natural numbers) then the numbers $i_k$ and $i_s$ are said to form an inversion if $k \lt s$ but $i_k > i_s$

In other words, an inversion in a permutation is a pair of numbers such that the larger number appears to the left of the smaller one in the permutation. The inversion number of a permutation is the total number of inversions. The inversion number of the permutation $i_1, i_2, \dots i_n$ is denoted by $[i_1, i_2, \dots ,i_n]$.

3.3) Parity of a permutation

Odd permutations - the inversion number is odd

Even permutations - the inversion number is even

3.4) Sign of a permutation

The sign of a permutation $i_1, i_2, \dots i_n$ is defined as $(-1)^{[i_1, i_2, \dots ,i_n]}$, where $[i_1, i_2, \dots ,i_n]$ is the inversion number of the permutation. It is obvious that the sign is $+1$ for even permutations and $-1$ for odd permutations.

3.5) Transposition

We say that we have applied a transposition if in a permutation P we swap the order of any two elements and the other elements we leave in place. When we do this, we get (from P) a new permutation R.

Lemma 1: The permutations P and R are of different parity.

Lemma 2: When $n \ge 2$, the number of the even permutations is equal to the number of the odd permutations.

3.6) Determinant

The concepts introduced here are important building blocks for introducing the concept of determinant (of a square matrix). The concept of determinant is usually defined using the Leibniz formula for determinants