The essence of linear algebra # 1 — start with the determinant

This post was originally posted on my public account: TechFlow

Linear algebra is a very important basic knowledge in the field of machine learning, but it is a pity that few people can realize the importance of it before the real introduction, to learn it solid, after the introduction, to realize that it is not easy to make up the lessons. I myself was the same. I only dabbled in the course during university, but I didn’t remember much later. As a result, it was very difficult to read many papers and materials. Many formulas were difficult to understand, and even if they were understood, they were easy to forget.

There’s a lot of linear algebra out there, a lot of it really deep, and we’re just going to extract the key points here. For those of you who haven’t studied it, it can be very easy to get the essence, and for those of you who have studied it, it can be used as a review.

Definition of the determinant

The definition in Wikipedia is that a determinant is a function that maps an n by n matrix to a scalar. This scalar represents the change in the “volume” of the matrix in space after the linear variation of what the matrix represents.

In other words, the input of the determinant is an n by n square matrix, and the output is a concrete number. Let’s write the determinant in terms of the determinant, so if A is some n by n matrix, then the determinant of A is the determinant of that matrix.

Calculation of the determinant

Second order determinant

make

thenIs the difference of the diagonal product.

Third order determinant

Let’s look at the third order:

make

then

The formula is very complicated in light, and if we take the product of all the positive terms and connect it with the red line, and the product of the negative terms and connect it with the blue line, then we get the following graph.

It’s essentially the product of the diagonal, the sum of the products of all the positive (top left, bottom right) diagonals minus the product of the opposite (top right, bottom left) diagonals.

We’ve listed binomial and triadic determinants, and naturally, we’re going to write the n determinant. But before we do that, we’ll introduce another related concept — inverse numbers.

Reverse order number

Inversions themselves are primarily used in determining determinants, but they are often used in interview questions, many of which ask candidates to write or dictate the algorithm for calculating inversions. This will be covered separately in a future algorithm column.

Let’s say we have an array A that has n different elements. In an ideal world, everything in A should be ordered. Let’s say they’re all in order from smallest to largest, but ideally that rarely happens. In most cases, the elements of an array are unordered.

Suppose we want to know how far the array’s current sort is from the ideal ascending order. And it’s perfectly normal to think that we can go through all of this arrayandTo see how few of them are out of order. The total number of combinations of all pairs of elements in the sequence that are out of order is called the inverse number.

The concept is a bit of a mouthful, but looking at the code is actually quite simple:

reverse = 0
for i in range(n):
  for j in range(i):
    if A[i] < A[j]:
      reverse += 1
Copy the code

That is, for each element in the array, we counted the number of elements that came before it and were larger than it. Let’s think about the general case, and let’s say that the array A is 1, 2, 3For each of themLet’s figure out the number of elements that precede it, and let’s define it as zero, then the sum of all inverse numbers:

The determinant of order n

Let’s go back to the NTH order determinant, and once we understand the concept of inverse numbers, we can easily write the formula for the NTH order determinant.

First, the matrix D is defined as a square matrix of order N:

Assumed natural numbersA permutation of isThe number of inversions of this permutation is t. So we can write the determinant of D:

Because all permutations of a sequence of length n are commonSo the determinant of the square matrix of order n containsItems.

But there’s another way to calculate the determinant.

In the NTH determinant, let’s take theAfter all the elements in the row and column of the element are removed, the new determinant of order N-1 is calledThe algebraic cofactor of the element is written as

Included in the 4th-order determinant:

Among themThe algebraic cofactor of the element is:

The cofactor can be used to express the determinant:

The determinant of a matrix can be written as:

And the proof is easy, but this is just a variation of the determinant. Let’s use the third order determinant as an example:

Let’s express these values in terms of cofactors:

If we simplify this, this is obviously the result of the formula above.

Cramer’s rule

The definition and calculation of a determinant are not very intuitive, so what is the use of such a relatively complicated concept?

In addition to being used in machine learning models, another very classic use is to determine whether linear equations have solutions.

For n systems of linear equations with n unknowns

Its solution can be expressed in terms of the determinant of order n.

If the determinant of order n is not equal to 0, that is:

Then the system of n-order equations has a unique solution, and its solution is:

Among themIs the new determinant obtained by replacing the JTH column in D with the constant term of the equation:

In addition to the above, there are a number of very useful properties and some variations of the determinant. However, there is not much help for the algorithm field, so there is not much enumeration here, interested students can refer to the relevant information.

Geometric meaning of the determinant

In addition to its algebraic function, the determinant also has its geometric meaning.

So let’s take the second order determinant, let’s say we have two vectors, A and B, where vector A is written asB vectorThe matrix composed of two vectors AB can be written as follows:

And if we were to draw it, it would actually represent the parallelogram area of these two vectors

So, when we multiply a row or a column of the determinant by a coefficient k, its determinant increases by k.

The code to calculate

From the above definition of determinant, it is easy to conclude that the calculation of determinant is complicated, and if we implement it by ourselves, we need at least 100 lines of code. However, the Python Numpy library provides us with a very rich matrix related operations, including determinant calculation, so we can implement determinant calculation very easily.

If Numpy is not installed, it can be easily installed by PIP:

pip install numpy
Copy the code

We can directly evaluate the determinant of a matrix by calling the det function in numpy.linalg.

The resources

wikipedia

Linear Algebra 5th Edition (Shanghai Jiaotong University Press)

www.cnblogs.com/andyjee/p/3…