Sunday, June 8, 2014

Linear Algebra: #8 Systems of Linear Equations

  • 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.

Linear Algebra: #8 Systems of Linear Equations pic 1

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

Linear Algebra: #8 Systems of Linear Equations pic 2

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 aij and bk are given (as elements of F), and the problem is to find the numbers xi.
  1. Let i : = 1 and j : = 1.
  2. if aij = 0 then if akj = 0 for all i < k ≤ m, set j : = j + 1. Otherwise find the smallest index k > i such that akj ≠ 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 aij—1. Then for each i < k ≤ m, subtract aij times the i-th equation from the k-th equation. Therefore, at this stage, after this operation has been carried out, we will have akj = 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 xi — 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:

Linear Algebra: #8 Systems of Linear Equations pic 3

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

So now we observe that:
  • If bl ≠ 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 xn = bn , so that is clear. But then, substitute bn for xn in the n−1-st equation, and we then have xn-1 = bn-1 − an-1nbn. By this method, we progress back to the first equation and obtain values for all the xj, for 1 ≤ j ≤ n. 

  • Otherwise, k < n. In this case we can assign arbitrary values to the variables xk+1, . . . , xn, and then that fixes the value of xk. But then, as before, we progressively obtain the values of xk-1, xk-2 and so on, back to x1
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:

Linear Algebra: #8 Systems of Linear Equations pic 4

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

Linear Algebra: #8 Systems of Linear Equations pic 5

Finding the eigenvectors of linear mappings

Let V be a vector space over a field F, and let f : VV be a linear mapping of V into itself. An eigenvector of f is a non-zero vector vV (so we have v0) 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 bi are zero. Thus a homogeneous system with matrix A has the form Av = 0)

Linear Algebra: #8 Systems of Linear Equations pic 6

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

Linear Algebra: #8 Systems of Linear Equations pic 7

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 v0.

[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 λ.]

No comments:

Post a Comment

If it's a past exam question, do not include links to the paper. Only the reference.
Comments will only be published after moderation

Currently Viewing: Physics Reference | Linear Algebra: #8 Systems of Linear Equations