Lesson GAUSS ELIMINATION METHOD FOR SOLVING LINEAR EQUATIONS

Source code of 'GAUSS ELIMINATION METHOD FOR SOLVING LINEAR EQUATIONS'

This Lesson (GAUSS ELIMINATION METHOD FOR SOLVING LINEAR EQUATIONS) was created by by Theo(13342)

This lesson provides an overview of the Gauss Elimination Method for solving Linear Equations.

REFERENCES

<a href = "http://ceee.rice.edu/Books/CS/chapter2/linear43.html" target = "_blank">http://ceee.rice.edu/Books/CS/chapter2/linear43.html</a>
<a href = "http://www.mathwords.com/g/gaussian_elimination.htm" target = "_blank">http://www.mathwords.com/g/gaussian_elimination.htm</a>
<a href = "http://www.sosmath.com/matrix/system1/system1.html" target = "_blank">http://www.sosmath.com/matrix/system1/system1.html</a>
<a href = "" target = "_blank"></a>

MECHANIZED TOOLS USING THE GAUSS-JORDAN ELIMINATION METHOD

<a href="http://www.karlscalculus.org/cgi-bin/linear.pl" target="_blank">http://www.karlscalculus.org/cgi-bin/linear.pl</a>
<a href="http://www.gregthatcher.com/Mathematics/GaussJordan.aspx" target="_blank">http://www.gregthatcher.com/Mathematics/GaussJordan.aspx</a>

LINEAR EQUATIONS

A linear equation is an equation with the highest order of exponent equal to 1.
The variables in a linear equation can be raised to the 0 power or to the 1 power.
Since any variable to the 0 power = 1, then the coefficient of that variable becomes a constant and the variable name is not used because the value of that variable has already been defined.
Example:   5x^0 = 5*1 = 5

SOLVING  A SYSTEM OF LINEAR EQUATIONS SIMULTANEOUSLY

When you solve a system of linear equations simultaneously, you have a unique solution for each variable that applies to every equation in the system where the variable is present.

An example:

<pre>
 x + y = 5
 2x + 3y = 13
</pre>
The unique solution to this system of equations is x = 2 and y = 3.

The same value for x is applied to every equation in the system where it is present, and the same value for y is applied to every equation in the system where it is present.

When you substitute 2 for x and 3 for y, then ...

the first equation becomes 2 + 3 = 5 which is true.
the second equation becomes 4 + 9 = 13 which is also true.

Your unique solution for each variable makes all equations in the system true.

Another example:

<pre>
 x + y = 7
 y = 6
</pre>
The unique solution to this system of equations is x = 1 and y = 6.

The same value for x is applied to every equation in the system where it is present, and the same value for y is applied to every equation in the system where it is present.

When you substitute 1 for x and 6 for y, then ...

the first equation becomes 1 + 6 = 7 which is true.
the second equation becomes 6 = 6 which is also true.

Your unique solution for each variable makes all equations in the system true.

STANDARD FORM OF A SYSTEM OF LINEAR EQUATIONS

The standard form of a system of linear equations has the coefficients and the variables on the left side of the equal sign and the constant terms on the right side of the equal side.

An example of the standard form of a system of linear equations in four dimensions could look like this.

<pre>
 4w + 1x + 2y + 3z = 6
 3w - 6x + 5y + 4z = 1
 9w + 7x - 7y + 8z = 4
 1w + 1x + 1y - 1z = 1
 3w + 4x + 3y + 2z = 5
</pre>
w,x,y,z are the variables.
coefficients and variables are on the left side of the equal sign.
constant terms are on the right side of the equal sign.

AUGMENTED MATRIX

From a system of linear equations, we make what is called an augmented matrix.

The augmented matrix has a column for the coefficients of each variable plus a column for the result (constant terms).

The augmented matrix created from the four dimension system of equations above is shown here:

<pre>
 4 1 2 3 | 6
 3 -6 5 4 | 1
 9 7 -7 8 | 4
 1 1 1 -1 | 1
 3 4 3 2 | 5
</pre>
The coefficients of each variable have their own column on the left side of the vertical line in the matrix.
The constant terms have their own column on the right side of the vertical line in the matrix.
Each equation has its own row.
In this matrix:
Column 1 is for the coefficients of w.
Column 2 is for the coefficients of x.
Column 3 is for the coefficients of y.
Column 4 is for the coefficients of z.
Column 5 is for the constant terms.
Row 1 contains first equation.
Row 2 contains second equation.
Row 3 contains third equation.
Row 4 contains fourth equation.

The vertical line between the columns containing the coefficient and the column containing the constant term are there to show you that this is an augmented matrix.

If there were only the matrix containing the coefficients without a column showing the constant term, then this would be called a coefficient matrix.

This vertical line should be displayed for clarity, but some mechanized tools may not display it.

As long as you know that you are dealing with an augmented matrix, this is not a problem.

The mechanized tool we will be using will not display it.

Just be aware that if you are showing an augmented matrix, you should have the vertical line separating the coefficient part of the matrix from the results part of the matrix, but you should also be aware that it is not always shown.   Usually you will be told if it is an augmented matrix or not.

MATRIX AND POSITION

The matrix requires that the coefficients of each variable have their own column, and that the constant terms have their own column.

This is easy if all the terms of the system of linear equations are explicit as shown above.

If not, then you have to make sure you place the coefficients of each variable in the proper column and row.

Example:

Here's a system of linear equations where the translation to matrix form requires some adjustment.

<pre>
z = -4
x - y = 3
v + z = 2
7w - 8x = -14
v = 2
</pre>
This system has 5 linear equations with 5 unknowns, so the matrix you will be creating will have 5 rows and 6 columns.

The matrix will look like this:

<pre>
 0 0 0 0 1 | -4
 0 0 1 -1 0 | 3
 1 0 0 0 1 | 2
 0 7 -8 0 0 | -14
 2 0 0 0 0 | 2
</pre>
The variables in this system of equations are v,w,x,y,z.
The columns for each variable have been placed in an alphabetic order in the matrix.
Column 1 contains all the coefficients for v.
Column 2 contains all the coefficients for w.
Column 3 contains all the coefficients for x.
Column 4 contains all the coefficients for y.
Column 5 contains all the coefficients for z.
Column 6 contains all the coefficients for the results (constant terms).
Row 1 contains the first equation.
Row 2 contains the second equation.
Row 3 contains the third equation.
Row 4 contains the fourth equation.
Row 5 contains the fifth equation.

GAUSS ELIMINATION METHOD AND THE AUGMENTED MATRIX

The Gauss Elimination method works with the augmented matrix in order to solve the system of equations.

The goal of the Gauss Elimination method is to convert the matrix into this form (four dimensional matrix is used for demonstration purposes).

<pre>
 p1 c1 c2 c3 | r1
 0 p2 c4 c5 | r2
 0 0 p3 c6 | r3
 0 0 0 p4 | r4
</pre>
p1,p2,p3,p4 represent nonzero coefficients of the variable represented by the column that the coefficient is in. These are the pivot elements that are used to make the coefficients in the row below them equal to 0.
c1,c2,c3,c4,c5,c6 represent coefficients of the variable represented by the column that the coefficient is in.
r1,r2,r3,r4 represent the constant result of each equation.

Once you have the matrix in this form, you are ready for backward processing.

Backward processing starts from the last row in the matrix and works it's way back up to the first row, solving for each variable in turn.

Up until this point you were doing forward processing.

Forward processing is the process that you used to put the matrix in this form.

Forward and Backward Processing for the Gauss Elimination Method will be described in more detail below.

REQUIREMENTS FOR A UNIQUE SOLUTION TO A SYSTEM OF LINEAR EQUATIONS USING THE GAUSS ELIMINATION METHOD

The requirements for a unique solution to a system of linear equations using the Gauss Elimination Method are that the number of unknowns must equal the number of equations.

When the number of equations and the number of unknowns are the same, you will obtain an augmented matrix where the number of columns is equal to the number of rows plus 1.

For example, if you have a system of 4 linear equations in 4 unknowns, then the number of rows must be equal to 4 and the number of columns must be equal to 5 (4 columns for the coefficients and 1 column for the results).

The vertical line between the coefficients part of the matrix and the results part of the matrix does not count as a column.  It's there for display purposes only if you have the capability to display it.

When you create your matrix, just make sure that the number of columns is equal to 1 plus the number of rows.

Note that it is possible to get a unique solution to a system of linear equations where the number of equations is greater than the number of unknowns.

An example of that would be 5 lines in a plane all intersecting in the same point.   There is a unique solution for the x and y variables that makes all the equations in the system true.   This type of situation, however, is not conducive to solving using the Gauss Elimination Method since that method requires the number of equations and the number of unknowns to be the same.

Note also that it is not possible to get a unique solution to a system of linear equations where the number of equations is less than the number of unknowns.

If you use the Gauss Elimination Method, just make sure that the number of equations is equal to the number of unknowns and the method will work just fine.

ROW OPERATIONS ON A MATRIX

You are allowed to do the following without changing the equality of any equation in the matrix and without impacting the solution to the system of linear equations:

<pre>
-----------------------------------------------------------------------------------------------
> YOU CAN SWAP ANY ROW IN THE MATRIX WITH ANY OTHER ROW IN THE MATRIX.
 Example:
 Old row 1 equals: 0 5 3 2 | 1
 Old row 3 equals: 0 -2 2 3 | -3
 SWAP ROW 3 WITH ROW 1 --------------------------------
 New row 1 equals: 0 -2 2 3 | -3 (equals old row 3)
 New row 3 equals: 0 5 3 2 | 1 (equals old row 1)
-----------------------------------------------------------------------------------------------
> YOU CAN MULTIPLY OR DIVIDE ANY ROW IN THE MATRIX BY ANY CONSTANT.
 Example:
 Old row 3 equals: 0 5 3 2 | 1
 MULTIPLY ROW 3 BY 5 ----------------------------------
 New row 3 equals: 0 25 15 10 | 5 (equals old row 3 * 5)
-----------------------------------------------------------------------------------------------
> YOU CAN ADD OR SUBTRACT ANY ROW FROM ANY OTHER ROW IN THE MATRIX.
 Example: 
 Old row 1 equals: 0 5 3 2 | 1
 Old row 3 equals: 0 -2 2 3 | -3
 ADD ROW 1 TO ROW 3 -----------------------------------
 New row 1 equals: 0 5 3 2 | 1 (equals old row 1 unchanged)
 New row 3 equals: 0 3 5 5 | -2 (equals old row 1 + old row 3)
-----------------------------------------------------------------------------------------------
> YOU CAN MULTIPLY OR DIVIDE ANY ROW BY ANY CONSTANT AND THEN ADD OR SUBTRACT THAT ROW FROM 
ANY OTHER ROW IN THE MATRIX. (This is the next to last rule referenced below).
 Example:
 Old row 1 equals: 0 5 3 2 | 1
 Old row 3 equals: 0 -2 2 3 | -3
 MULTIPLY ROW 1 BY 2 AND ADD IT TO ROW 3 --------------
 New row 1 equals: 0 10 6 4 | 2 (equals old row 1 * 2)
 New row 3 equals: 0 8 8 7 | -1 (equals old row 3 + new row 1)
-----------------------------------------------------------------------------------------------
> YOU CAN ADD OR SUBTRACT ANY ROW IN THE MATRIX MULTIPLIED OR DIVIDED BY ANY CONSTANT FROM ANY 
OTHER ROW IN THE MATRIX. (This is the last rule referenced below).
 Example:
 Old row 1 equals: 0 5 3 2 | 1
 Old row 3 equals: 0 -2 2 3 | -3
 ADD 2 * ROW 1 TO ROW 3 -------------------------------
 New row 1 equals: 0 5 3 2 | 1 (equals old row 1 unchanged)
 New row 3 equals: 0 8 8 7 | -1 (equals old row 3 + old row 1 * 2)
-----------------------------------------------------------------------------------------------
</pre>
The last two rules give you the same result for the new row 3 but provide different results for the new row 1.

MULTIPLY ROW 1 BY 2 AND ADD IT TO ROW 3 (next to last rule shown above) makes new row 1 different from old row 1 (changes row 1).

ADD 2 * ROW 1 TO ROW 3 (last rule shown above) makes new row 1 the same as old row 1 (leaves row 1 unchanged).

EXAMPLE OF SOLVING A 4 DIMENSIONAL SYSTEM OF LINEAR EQUATIONS USING THE GAUSS ELIMINATION METHOD

The system of linear equations that we want to solve is shown below:

<pre>
 4z = 5
 3y = 4
 5w + 6x + 7y + 8z = 9
 4x + 3y + 2z = 1
</pre>
From this system of linear equations, we create our augmented matrix as shown below:

<pre>
 0 0 0 4 | 5
 0 0 3 0 | 4
 5 6 7 8 | 9
 0 4 3 2 | 1
</pre>
Column 1 contains all the coefficients of w.
Column 2 contains all the coefficients of x.
Column 3 contains all the coefficients of y.
Column 4 contains all the coefficients of z.
Column 5 contains all the results (constant terms).
Row 1 contains the first equation.
Row 2 contains the second equation.
Row 3 contains the third equation.
Row 4 contains the fourth equation.

Our goal is to get the matrix into the following final form and then to solve for each of the variables starting from the last row and working back towards the first row.

The final form of the Gauss Elimination Method that we are using in this lesson requires that:

<pre>
> Row 1 column 1 contains a nonzero coefficient in it.
 All coefficients in column 1 below row 1 are equal to 0.
> Row 2 column 2 contains a nonzero coefficient in it.
 All coefficients in column 2 below row 2 are equal to 0.
> Row 3 column 3 contains a nonzero coefficient in it.
 All coefficients in column 3 below row 3 are equal to 0.
> Row 4 column 4 contains a nonzero coefficient in it.
 Since row 4 is the last row, there are no further requirements.
</pre>
When the matrix is in this form, forward processing is complete and backward processing begins.

Backward processing means starting from the last row and working your way back up to the first row, solving for each variable in turn along the way.

Here's the general strategy:

Column 1 forward processing:
<1.1> Start from row 1 column 1.
<1.2> Check to see if the coefficient of column 1 of row 1 is not zero.
<1.3> If it is not zero then go to step 1.6. If it is zero, then go to step 1.4.
<1.4> Look for any row below row 1 that contains a nonzero value in column 1.
<1.5> When found, swap that row with row 1. Row 1 now contains a nonzero value in column 1.
<1.6> Use row 1 to make all the coefficients of column 1 equal to zero in all rows that are below row 1.
<1.7> When row 1 contains a nonzero coefficient in column 1 and all the other rows below it contain a zero coefficient in column 1, then you are done with column 1 forward processing and can move on to column 2 forward processing.

Column 2 forward processing:
<2.1> Start from row 2 column 2.
<2.2> Check to see if the coefficient of column 2 of row 2 is not zero.
<2.3> If it is not zero then go to step 2.6. If it is zero, then go to step 2.4.
<2.4> Look for any row below row 2 that contains a nonzero value in column 2.
<2.5> When found, swap that row with row 2. Row 2 now contains a nonzero value in column 2.
<2.6> Use row 2 to make all the coefficients of column 2 equal to zero in all rows that are below row 2.
<2.7> When row 2 contains a nonzero coefficient in column 2 and all the other rows below it contain a zero coefficient in column 2, then you are done with column 2 forward processing and can move on to column 3 forward processing.

Column 3 forward processing:
<3.1> Start from row 3 column 3.
<3.2> Check to see if the coefficient of column 3 of row 3 is not zero.
<3.3> If it is not zero then go to step 3.6. If it is zero, then go to step 3.4.
<3.4> Look for any row below row 3 that contains a nonzero value in column 3.
<3.5> When found, swap that row with row 3. Row 3 now contains a nonzero value in column 3.
<3.6> Use row 3 to make all the coefficients of column 3 equal to zero in all rows that are below row 3.
<3.7> When row 3 contains a nonzero coefficient in column 3 and all the other rows below it contain a zero coefficient in column 3, then you are done with column 3 forward processing and can move on to column 4 forward processing.

Column 4 forward processing:
<4.1> Start from row 4 column 4.
<4.2> Row 4 column 4 should have a nonzero coefficient in it. 
<4.3> You are done with column 4 forward processing and can move on to solving for each of the variables in turn, starting from the last row in the matrix and working your way back up to the first row.

That's the essence of the Gauss Elimination Process.

Forward processing to get your matrix into the final form required by the Gauss Elimination Method.

Once it's in the final form, then backward processing to solve for each variable in turn.

NOTE:

You might get a situation like shown below:

<pre>
 c1 c2 c3 | r1
 c4 0 0 | r2
 0 0 c5 | r3
</pre>
You might think that, using the process described above, you can't get the matrix into the final form required for Gauss Elimination Processing.
A closer inspection, however, shows that if you swap row 1 with row 2, you will then have the final form you are looking for as shown below:

<pre>
 c4 0 0 | r2
 c1 c2 c3 | r1
 0 0 c5 | r3
</pre>
Now c4 becomes p1, c2 becomes p2, c5 becomes p3 and your matrix is in the final form required for processing the Gauss Elimination Method as shown below:

<pre>
 p1 0 0 | r2
 c1 p2 c3 | r1
 0 0 p3 | r3
</pre>
This is just a little wrinkle in the process that you need to be aware of. If you can't get your matrix into the final form for Gauss Elimination Processing, check that first row to see if you can't swap rows to make the problem go away.

We will now go through the details for the problem we want to solve.

The system of linear equations that we want to solve is shown below:

Our goal is to get the matrix into the following final form and then to solve for each of the variables starting from the last row and working back towards the first row.

We start with the original matrix created from the system of equations.

<pre>
 0 0 0 4 | 5
 0 0 3 0 | 4
 5 6 7 8 | 9
 0 4 3 2 | 1
</pre>
We start with Column 1 forward processing.

We start with row 1 column 1.
We see that row 1 column 1 does not have a nonzero coefficient in it, so we scan down column 1 until we find a row that has a nonzero coefficient in it.
We see that row 3 has a nonzero coefficient in column 1, so we swap row 3 with row 1 to make our matrix look like this:

<pre>
 5 6 7 8 | 9
 0 0 3 0 | 4
 0 0 0 4 | 5
 0 4 3 2 | 1
</pre>
Since column 1 row 1 has a nonzero coefficient in it, and all the other rows below row 1 have a zero coefficient in column 1, we are done with column 1 forward processing and can proceed with column 2 forward processing.

We see that column 2 row 2 does not have a nonzero coefficient in it, so we scan down column 2 until we find a row that has a nonzero coefficient in it.
We see that row 4 has a nonzero coefficient in column 2, so we swap row 4 with row 2 to make our matrix look like this:

<pre>
 5 6 7 8 | 9
 0 4 3 2 | 1
 0 0 0 4 | 5
 0 0 3 0 | 4
</pre>
Since column 2 row 2 has a nonzero coefficient in it, and all the other rows below row 2 have a zero coefficient in them, we are done with column 2 forward processing and can proceed with column 3 forward processing.

We start with row 3 column 3.
We see that column 3 row 3 does not have a nonzero coefficient in it, so we scan down column 3 until we find a row that has a nonzero coefficient in it.
We see that row 4 has a nonzero coefficient in column 3, so we swap row 4 with row 3 to make our matrix look like this:

<pre>
 5 6 7 8 | 9
 0 4 3 2 | 1
 0 0 3 0 | 4
 0 0 0 4 | 5
</pre>
Our matrix is now in the final form required by the Gauss Elimination Method.

Column 1 has a nonzero coefficient in row 1 and zero coefficients in all the rows below it.
Column 2 has a nonzero coefficient in row 2 and zero coefficients in all the rows below it.
Column 3 has a nonzero coefficient in row 3 and zero coefficients in all the rows below it.
Column 4 has a nonzero coefficient in row 4.   
Since row 4 is the last row, there are no further requirements and we are ready to start backward processing.

Backward processing involves starting from the last row and working our way back up to the first row, solving for each variable in turn.

Remember that, for this problem, column 4 contains the coefficients of the z variable and column 3 contains the coefficients of the y variable and column 2 contains the coefficients of the x variable and column 1 contains the coefficients for the w variable and column 5 contains the constant results.

We start with row 4.
The equation generated from row 4 is:
4z = 5
We divide both sides of this equation by 4 to get:
z = 5/4

We move up to row 3.
The equation generated from row 3 is:
3y = 4
We divide both sides of this equation by 3 to get:
y = 4/3

We move up to row 2.
The equation generated from row 2 is:
4x + 3y + 2z = 1
We substitute 4/3 for y, and 5/4 for z to get:
4x + 3*(4/3) + 2*(5/4) = 1
We simplify this equation to get:
4x + 4 + (5/2) = 1
We multiply both sides of this equation by 2 to get:
8x + 8 + 5 = 2
We combine like terms to get:
8x + 13 = 2
We subtract 13 from both sides of this equation to get:
8x = -11
We divide both sides of this equation by 8 to get:
x = -11/8

We move up to row 1.
The equation generated from row 1 is:
5w + 6x + 7y + 8z = 9
We substitute (-11/8) for x, and (4/3) for y, and (5/4) for z to get:
5w + 6*(-11/8) + 7*(4/3) + 8*(5/4) = 9
We simplify to get:
5w - (66/8 + (28/3) + (40/4) = 9
We multiply both sides of the equation by 8 to get:
40w - 66 + (28*8)/3 + (40*8)/4 = 72
We simplify further to get:
40w - 66 + (224/3) + 80 = 72
We multiply both sides of this equation by 3 to get
120w - 198 + 224 + 240 = 216
We combine like terms to get:
120w + 266 = 216
We subtract 266 from both sides of this equation to get:
120w = -50
We divide both sides of this equation by 120 to get:
w = -5/12

Our solution to this system of equations is:

w = -5/12
x = -11/8
y = 4/3
z = 5/4

We can use the Gauss-Jordan Mechanized Tool referenced below to confirm that we solved this problem correctly.

<a href="http://www.gregthatcher.com/Mathematics/GaussJordan.aspx" target="_blank">http://www.gregthatcher.com/Mathematics/GaussJordan.aspx</a>.

Results from the execution of that tool are shown below:

The results from the execution of this tool are the same as the results we got manually, confirming that we processed this system of linear equations properly using the Gauss Elimination Method.

From the fourth row, you see that z = 5/4.
From the third row, you see that y = 4/3
From the second row, you see that x = -11/8
From the first row, you see that w = -5/12

UNIQUE SOLUTIONS TO A SYSTEM OF LINEAR EQUATIONS

Using the Gauss Elimination method, if your matrix is in the final form shown below, then you have a unique solution to the system of linear equations and all you have to do is solve for each of the variables in turn.

If your matrix cannot be placed in the final form shown above, then you do not have a unique solution to your system of linear equations.

PROCESSING CLUES TO WHETHER OR NOT YOU WILL HAVE A UNIQUE SOLUTION TO YOUR SYSTEM OF EQUATIONS

As you progress through the steps of your matrix, if you encounter a row that has all zeroes in the coefficient part of the matrix, that's a clue that tells you that you will not have a unique solution to your matrix.

Here's an example of a system of linear equations that does not have a unique solution.

Your equations are:

<pre>
 x + y + z = 5
 3x + 3y + 3z = 20
 2x - 3y - 4z = 6
</pre>
Your matrix looks like this:

<pre>
 1 1 1 | 5
 3 3 3 | 20
 2 -3 -4 | 6
</pre>
You start column 1 processing by subtracting 3 * the first row from the second row to get:

<pre>
 1 1 1 | 5
 0 0 0 | 5
 2 -3 -4 | 6
</pre>
This is your first clue that this system of equations will not have a unique solution.

You can actually stop processing here because it will not get any better.   Once all the coefficients in a row are all zero, there is no unique solution to the system of equations.

I confirmed this by using the mechanized tools at my disposal to see what they would come up with.

The first tool was <a href="http://www.karlscalculus.org/cgi-bin/linear.pl" target="_blank">http://www.karlscalculus.org/cgi-bin/linear.pl</a>

It stopped the processing once it generated a row with all zero coefficients.

A display of the results from that tool are shown below:

The second tool was <a href="http://www.gregthatcher.com/Mathematics/GaussJordan.aspx" target="_blank">http://www.gregthatcher.com/Mathematics/GaussJordan.aspx</a>

It did not stop the processing, but the results clearly showed that there was no unique solution to the problem.

A display of the results from that tool are shown below: