Gaussian Elimination And Matrix Equations

Matrix Equations

A matrix equation is just what it sounds like - it is an equation involving matrices.  Usually, if we are given a matrix called A and a vector called b, then an equation Ax = b seeks to find a vector x that makes the equation true.  Here is an example:

If you know how to multiply matrices and vectors, then by multiplying the x vector times the matrix A, you will arrive at a linear system for the entries of b.  Suffice it to say, solving the above matrix equation amounts to the same thing as solving this linear system:

For the methods we will use in this lesson, it is more convenient to dispense with the variables altogether, treating them more as place holders.   In order to do this we augment the matrix A by the vector b like this:

The above augmented matrix form turns out to be extremely useful for solving and classifying linear systems. If we still want to think of this matrix as representing a linear system, then we can.  We simply associate the columns with variables of our system and the rows with the system's equations.  

Just to recap, here is how to translate a matrix equation into both a linear system and an augmented matrix.

Row Echelon Form

Often when working with augmented matrices, we recognize that certain matrices are more interesting than others.  When a matrix has only zeros below its diagonal entries, then it is said to be in echelon form, or row echelon form.

Here is an example

Echelon form is interesting because it allows us to more easily solve the system using a technique called back-substitution.  Assuming that the above matrix is an augmented matrix, then each of the first five columns represents a variable, say a, b, c, d ,e.  This means that, by looking at the last column, we immediately see that 4e = 1 so that e = 1/4.  Now we can substitute in for e in the second to last row. Doing so gives us d + 7e = 5 so that d + 7/4 = 5 so that d = 27/4.  Now we can substitute both d and e into the third row, and so on, until we have values for all five variables.

Reduced Row Echelon Form

Another form, similar to echelon form, is reduced row echelon form.  For any matrix, the first non-zero entry in a row is called a pivot. A matrix is in reduced row echelon form when every pivot is a 1, and the pivot is the only non-zero entry in its column. Here is an ideal example: 

Given a matrix in reduced row echelon form, if there is a pivot in every column, we can simply read the solutions by looking at the final column.  So, if we again were to assume that the first five columns corresponded to variables a, b, c, d, and e, then a = 3, b = 1, c = 2, d = 5, and e = 2.

Shortly, we will see a technique that takes any matrix and puts it into reduced row echelon form, thereby solving whatever equation or system it represents.  Here is another example that shows how solutions relate to reduced row echelon form. 

The Idea

This is really the meat of this lesson, here we learn a technique for solving large linear systems.  Gaussian elimination is a step-by-step procedure that starts with  a system of linear equations, or an augmented matrix, and transforms it into another system which is easier to solve.  Usually, we end up being able to easily determine the value of one of our variables, and, using that variable we can apply back-substitution to solve the rest of the system.  

When the equations are represented by an augmented matrix, the process of Gaussian elimination puts the matrix into echelon form.  As we have seen, once we have a matrix in echelon form we can determine the solutions to the matrix equation it represents.

An Aside: Gauss-Jordan Elimination

Gauss-Jordan elimination is exactly like Gaussian elimination except that the goal is to put a matrix into reduced row echelon form rather than simple row echelon form.  It requires more work, but will make seeing the solutions rather simple. Now for the technique.

Row operations

Gaussian and Gauss-Jordan elimination work by applying row operations to matrices.  A row operation is a way to simplify the presentation of a matrix while keeping its solution the same.  The following row operations are allowed:

1. You may swap the positions of any two rows
2. You may multiply any row by a non-zero scalar value
3. You may add a scalar multiple of any one row to another row

Example: Swapping Rows

Example: Multiply by a non-zero scalar value

Example: Add a multiple of one row to another

Now lets apply these rules in an example.

Lets start with a simple linear system

x + 2y = 4

2x + y = 1

We can form an augmented matrix and perform row operations until we have a matrix in row echelon form.  Because this is such a small system, this only requires one step:

We see that the entries below the diagonal are all zero (there is only one in this example), so that the matrix is in row echelon form.  From here, we can look at the final row to see that -3y = -6, which gives y = 2.  Now we can substitute this into our first equation to find the x value:

x + 2y = 4

x + 2(2) = 4

x + 4 = 4

x = 0

So a solution to the system is given by x=0, y=2.