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

Algebra Notes 2

2.1) Systems of linear equations

$a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1$

$a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2$

$\dots$

$a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m$

This is a system of m linear equations with n unknowns. 

a) The matrix of this system is defined as follows

$$A = \begin{bmatrix}a_{11}&a_{12}&...&a_{1n}\\a_{21}&a_{22}&...&a_{2n}\\...&...&...&...\\a_{m1}&a_{m2}&...&a_{mn}\end{bmatrix}$$

На български: матрица на системата

b) The augmented matrix of this system is defined as follows

$$B = \begin{bmatrix}a_{11}&a_{12}&...&a_{1n}&b_1\\a_{21}&a_{22}&...&a_{2n}&b_2\\...&...&...&...&...\\a_{m1}&a_{m2}&...&a_{mn}&b_m\end{bmatrix}$$

На български: разширена матрица на системата

2.2) Types of systems of linear equations

a) Independent system: has exactly one solution

b) Inconsistent system: has no solutions

c) Consistent system: has at least one solution

d) Dependent system: has infinitely many solutions

a) Определена система: има точно едно решение

b) Несъвместима система: няма решения

c) Съвместима систeмa: има поне едно решение

d) Неопределена система: има безбройно много решения

2.3) Elementary transformations applied to a system of linear equations

a) swapping two rows

b) multiplying a row of the system with a non-zero number

$R := \lambda R$, where $\lambda \neq 0$ 

c) adding to a row another row (multiplied by a number)

$R_2 := R_2 + \lambda R_1$

Note: If we apply (to a given system of linear equations) a finite number of elementary transformations, the resulting system is equivalent to the original system.

2.4) Gaussian elimination - a general method for solving systems of linear equations

Gaussian elimination