• Linear Algebra: #8 Systems of Linear Equations

We now take a small diversion from our idea of linear algebra as being a method of describing geometry, and instead we will consider simple linear equations. In particular, we consider a system of m equations in n unknowns.

We can also think about this as being a vector equation. That is, if

then our system of linear equations is just the single vector equation

A · x = b 

But what is the most obvious way to solve this system of equations? It is a simple matter to write down an algorithm, as follows. The numbers a_ij and b_k are given (as elements of F), and the problem is to find the numbers x_i.

1. Let i : = 1 and j : = 1.
2. if a_ij = 0 then if a_kj = 0 for all i < k ≤ m, set j : = j + 1. Otherwise find the smallest index k > i such that a_kj ≠ 0 and exchange the i-th equation with the k-th equation. kj
3. Multiply both sides of the (possibly new) i-th equation by a_ij^—1. Then for each i < k ≤ m, subtract a_ij times the i-th equation from the k-th equation. Therefore, at this stage, after this operation has been carried out, we will have a_kj = 0, for all k > i. 
4. Set i : = i + 1. If i ≤ n then return to step 2.

So at this stage, we have transformed the system of linear equations into a system in step form.

The next thing is to solve the system of equations in step form. The problem is that perhaps there is no solution, or perhaps there are many solutions. The easiest way to decide which case we have is to reorder the variables — that is the various x_i — so that the steps start in the upper left-hand corner, and they are all one unit wide. That is, things then look like this:

(Note that this reordering of the variables is like our first elementary column operation for matrices.)

So now we observe that:

• If b_l ≠ 0 for some k +1 ≤ l ≤ m, then the system of equations has no solution. 


• Otherwise, if k = n then the system has precisely one single solution. It l is obtained by working backwards through the equations. Namely, the last equation is simply x_n = b_n , so that is clear. But then, substitute b_n for x_n in the n−1-st equation, and we then have x_n-1 = b_n-1 − a_n-1nb_n. By this method, we progress back to the first equation and obtain values for all the x_j, for 1 ≤ j ≤ n. 


• Otherwise, k < n. In this case we can assign arbitrary values to the variables x_k+1, . . . , x_n, and then that fixes the value of x_k. But then, as before, we progressively obtain the values of x_k-1, x_k-2 and so on, back to x₁. 

This algorithm for finding solutions of systems of linear equations is called “Gaussian Elimination”.

All of this can be looked at in terms of our matrix notation. Let us call the following m×n+1 matrix the augmented matrix for our system of linear equations:

Then by means of elementary row and column operations, the matrix is transformed into the new matrix which is in simple step form

Finding the eigenvectors of linear mappings

Definition
Let V be a vector space over a field F, and let f : V → V be a linear mapping of V into itself. An eigenvector of f is a non-zero vector v ∈ V (so we have v ≠ 0) such that there exists some λ ∈ F with f(v) = λv. The scalar λ is then called the eigenvalue associated with this eigenvector.

So if f is represented by the n ×n matrix A (with respect to some given basis of V), then the problem of finding eigenvectors and eigenvalues is simply the problem of solving the equation

Av = λv. 

But here both λ and v are variables. So how should we go about things? Well, as we will see, it is necessary to look at the characteristic polynomial of the matrix, in order to find an eigenvalue λ. Then, once an eigenvalue is found, we can consider it to be a constant in our system of linear equations. And they become the homogeneous system
(That is, all the b_i are zero. Thus a homogeneous system with matrix A has the form Av = 0)

which can be easily solved to give us the (or one of the) eigenvector(s) whose eigenvalue is λ.

Now the n × n identity matrix is

Thus we see that an eigenvalue is any scalar λ ∈ F such that the vector equation (A − λE)v = 0 has a solution vector v ∈ V, such that v ≠ 0.

[Given any solution vector v, then clearly we can multiply it with any scalar κ ∈ F, and we have

(A − λE)(κv) = κ(A − λE)v = κ0 = 0. 

Therefore, as long as κ ≠ 0, we can say that κv is also an eigenvector whose eigenvalue is λ.]