Solving Ax = b

Goals: Know how to solve Ax=b by 1) x=A^-1 b
2) by factoring A = PLU and 3) Using Lsolve(A,b).

We are now prepared to recast the fundamental problem of linear algebra using matrix notation as: Solve Ax = b. We will find the matrix representations for row echelon, Gaussian elimination, and reduced row echelon, Gauss-Jordan reduction methods for solving linear systems of equations.

I. The Algebraic Solution x = A^-1b

If a solution to A x = b exists, then we would like solve the matrix equation by

For the last equation to be a solution we must know if the matrix multiplication by gives an equivalent solution.

Before we begin solving matrix equations, we need to know if and when the operation of matrix multiplication produces an equivalent system. This question is answered by the following theorem.

Theorem 1.4.1: If represents an m x n linear system, then given any m x m nonsigular matrix M,
is an equivalent system.

Proof: If x is a solution to A x = b, then it will also
be a solution to M A x = M b.

If x is a solution to M A x = M b,
M^-1(M A x) = M^-1(M b)
A x = b
Thus the systems are equivalent. q.e.d.

(This is not a convincing proof, why? Because we don't know enough about nonsingular matrices)

In theory, all that we need in order to solve the matrix equation
Ax = b is to find A^-1 and perform the multiplication A^-1b.

In practice, it may not be possible to calculate A^-1 even if it exists, in which case, other methods of solution are needed. More important, the algebraic method generally does not provide the most efficient algorithm for solving a linear system.
All of that aside, how do we find ?

II. The Elementary Matrices

Our goal now is to show that each of the elementary row operations can be described by a corresponding Elementary Matrix. Thus we can represent any sequence of elemenatry row operations on a linear system as a product of Elementary Matrices on the augmented matrix, and in particular we can accomplish the steps of Gaussian Elimination or Gauss-Jordan Reduction by matrix multiplication.

The E1 elementary row operation

Consider a Permutation matrix

and

If the matrix S is the augmented matrix for a system of linear equations, then the product,

is the matrix representation of an E1 elementary row operation on the system S.

In general, any E1 type of row operation can be accomplished by the product of a permutation matrix and the augmented matrix.

Try to figure out how the other elementary row operations can be written in matrix form.

Hint: Change an element in the identity matrix.

The E2 elementary row operation

An E2 row operation is represented by the matrix

How would you alter E2 so that the second row of S was multiplied by 2?

The E3 elementary row operation

Determine the matrix form of the E3 elementary row operation.

A Summary

An E1 Type elementary row operation is a Permutation matrix P.

An E2 Type elementary row operation is obtained by multiplying a row of the identity matrix I by a nonzero constant.

An E3 type elementary row operation is a matrix obtained from I by multiplying a row by a constant and adding it to another row.

In order to use the elementary matrices to solve linear systems, we need to be sure that they produce equivalent systems, that is by our theorem, they must be nonsingular.

Theorem 1.4.2: If is an nxn elementary matrix, then is nonsingular and is an elementary matrix of the same type.

Proof: Construct an for each type.

III. Gaussian Elimination -- Row Echelon Form Revisited

Now we show that any sequence of elementary row operations that puts a system of linear equations into Row Echelon Form is equivalent to a sequence of elementary matrix multiplications on the augmented system. Also, this sequence of multiplications may be written as a single matrix.

A. Determine the sequence of elementary row operations used to put the following system into row echelon form.

The Algorithm

Step #

Type

Description

Purpose

S1 E1 Interchange rows 1 and 2.

Get a nonzero pivot.

S2 E3 -2*R1 + R3 a R3

Put zeros below the pivot

S3 E3 -3*R1 + R4 a R4

S4 ? ?

Now for the matrix representation of these steps.

B. Write an elementary matrix for each of the previous steps. Show the effect of each step on S. (In all of its hideous detail)

Step 1

The effect on S

Step 2

Step 3

Step 4

The equivalent system

Moving to the a₂₂ pivot, we put zeros below this pivot using:

Step 5

Step 6

Continuing...

Step 7

Step 8

Step 9

The sequence of matrix multiplications is:

This is the row echelon form of S.

Let's look at the product of these elementary matrices:

This matrix is Lower Triangular.

How do we know this matrix product is nonsingular?
This is necessary to obtain an equivalent system.

We could use a threorem:

Theorem 1.4.3: If A and B are nonsingular nxn matrices, then AB is also nonsingular and (AB)^-1 = B^-1 A^-1.

Proof:
(B^-1 A^-1) AB = B^-1 (A^-1A) B = B^-1 B = I

(AB) (B^-1 A^-1) = A (B B^-1)A^-1 = AA^-1 = I
q.e.d.

IV. Gauss-Jordan Reduction -- RREF Revisited

If we continue with the backward pass (back-substitution) on the previous system S, we may put it into reduced row echelon form. We will now see that this can be accomplished by further multiplications of elementary matrices.

Akamai: The coefficient matrix in rref form is the identity matrix I.
Read -- Unique Solution.

Write out the elementary matrices used to put U into Reduced Row Echelon Form.

Hmm, I need some matrices that work above the diagonal to do this. Any Ideas?

Hint 1: Use as for the pivot.

Hint 2:

Akamai: Notice that the B1, B2, ... matrices are elementary matrices.

Write out , a matrix that eliminates the 2,4 entry in .

V. The Inverse Matrix A^-1

Akamai: We have just discovered an algorithm for computing A^-1!

If we consider just the coefficient matrix A for the previous system of linear equations S, then putting S into reduced row echelon form by a series of elementary matrix multiplications is equivalent to A^-1A = I.

Find the inverse of A.

As before we write out:

and

Therefore

We can use this idea to compute A^-1 by hand. First, we augment the coefficient matrix A with the identity matrix I and then put the augmented matrix into Reduced Row Echelon Form.

Use your CAS to find the inverses for the following Matirces.

Definition: A matrix B is row equivalent to A if there exists a finite sequence of elementary matrices E_i such that

Theorem : If A is an nxn matrix, then the following are equivalent statements:

(a) A is nonsingular
(b) Ax = 0 has only the trivial solution
(c) A is row equivalent to I.

Proof: (Circle of Implications)

One more time:

Corollary 1.4.4: The system of n linear equations in n unkowns Ax = b has a unique solution if and only if A is nonsingular.

Proof: (IFF If and only if)

Solve the system by x = A^-1 b.

The Linear System:

Given

and

After a bit of work, we find:

We compute

to find that

.

Although it seems that we should be done with this problem, things are not so simple as we would like, since as we mentioned earlier, often we cannot compute A^-1, even if it exists! Other methods are needed.

VI. The Triangular Factorization A = PLU

Many of the key ideas of linear algebra may be viewed as a factoring of a given matrix. Factoring the coefficient matrix A into a product of a permutation matrix with a lower triangular matrix and upper triangular matrix is important in practice.

Gaussian Elimination, which we have seen puts the coefficient matrix for the related linear system into an upper triangular form (if there is a unique solution), may viewed as factoring the matrix A.

In section 1 we saw that

If we solve this for A, we get:

But this product is a lower triangular matrix:

Let

and let

Then we obtain the matrix factoriztion:

P is a permutation matrix.

If no row exchanges are necessary then the matrix factorization is

Experiment with Factorizations of A.

P

L

U

We have seen that if a pivot is 0 then a row exchange is necessary resulting in a nontrivial permutation matrix P. Another reason for exchanging rows is to minimize the errors generated by computer computations.

VI. Lsolve(A)

The computer algebra systems have subroutinues for solving systems of linear equations.

To use Mathcad to solve a linear system of the form A x = b, we can use the command lsolve(A,b).

Define

and

Write

The solution is

Lecture 3 Notes