This activity is designed to help you understand the process of solving systems of equations using Gauss-Jordan Elimination on the augmented coefficient matrix. We will use this process repeatedly throughout the course, not only to solve systems of equations but also to find the optimal solution to linear programming problems. Linear Algebra is often called the arithmetic of higher mathematics, so you will see this process frequently in your mathematical career.
| 1. Form Coefficient Matrix A | Write the coefficients of the equation variables in matrix form. |
| 2. Form Augmented Matrix A|b | Adjoin the column b of constants on the right sides of the equations to the right of the coefficient matrix. |
| 3. Make a11 = 1 | Divide row 1 by a11 or use row operations to make upper left entry 1. |
| 4. Convert column 1 | Use pivot operations to make the rest of the first column of A|b = 0. |
| 5. Convert other columns | Repeat steps 3 and 4 until the first nonzero entry in each row is 1 with its column a unit vector |
| 6. Check Consistency | The converted matrix is inconsistent if it has a row with all zeroes except in the augmented column. |
| 7. Form Equations | If the matrix is consistent, write it in equation format. |
| 8. Add Auxiliary Equations | For each independent variable v write an auxiliary equation in form v = v. |
| 9. Solve Equations | Solve each equation for its first variable. Intersperse auxiliary equations. |
| 10. Write vector form of solution | Rewrite the right side of the step 9 system of equations as linear combination of vectors times the independent variables. |
| 11. Check answer | Assign values to the independent variables, determine dependent variable values, plug in and make sure these values satisfy the original system. |
Solve the system: x + 2y + 3z = 1; 2x + 5y + 8z = 3.
A = 1 2 3
2 5 8
A|b = 1 2 3 | 1
2 5 8 | 3
a11 is already 1.
Multiply the pivot row 1 by -2 and add it to the target row 2 changing row 2 to obtain
1 2 3 | 1
0 1 2 | 1
The first nonzero entry in row 2 is already 1. Multiply the pivot row 2 by -2 and add it to the target row 1 changing row 1 as follows. Since there are no more rows we are finished.
1 0 -1 |-1
0 1 2 | 1
There are no zero rows in the row echelon form so the system is consistent.
x - z = -1
y + 2z = 1
The only independent variable is z so we add the equation z = z.
x = z - 1
y = -2z + 1
z = z
|x| | 1| |-1|
|y| = |-2| z + | 1|
|z| | 1| | 0|
Let z = 1. Then x = 0, y = -1, z = 1. Substituting these values into the original equations we get
0 + 2(-1) + 3(1) = 1 Check
0 + 5(-1) + 8(1) = 3 Check
The variables in a system of equations are just placeholders to identify where the coefficients go. They are not used during the solution of the system. By putting the coefficients in matrix form we can keep them correctly oriented and use linear algebra to simplify the problem.
We are allowed to interchange equations, add multiples of one equation to another, and multiply both sides of an equation by the same constant. These are called elementary row operations when done to the coefficient matrix. Whatever we do to the left side of an equation we have to do to the right side. Adjoining the right side vector to the coefficient matrix ensures that it is not forgotten during the row operations.
The goal matrix for row reduction is the Identity matrix whose columns are unit vectors. We start to transform the first column into the first unit vector by making the top left entry 1. Sometimes this can be done by interchanging rows so that a row whose first entry is already 1 is on top. Other times we can add + or - another row to the first to make its first entry 1. The most straightforward way to make a11 = 1 is to divide the first row by its first element a11 (i.e., multiply the first row by 1/a11).
To make the other entries in the first column 0 using only row operations, we use the first row as the pivot row. If the entry we want to convert to 0 is in the ai1 position then we multiply the first row by -ai1 and add it to the ith row, changing the ith row. This step is repeated for i = 2, 3, ..., m.
This is the key to the entire process and the source of most errors. Remember, we are trying to convert the coefficient matrix as close as possible to an Identity matrix. Ignoring the first row, examine the columns of the matrix, starting from the left, looking for one which has at least one nonzero entry in rows 2 through m. Interchange rows if necessary until the nonzero entry (preferably 1) is in row 2. If this entry is not 1, use the methods in step 3 to make it 1. Then make the rest of the entries in that column zero using step 4 methods. We repeat this process for each row so that its first nonzero entry is 1. This entry is called a pivot. All the columns containing pivots should be unit vectors (columns of an Identity matrix). The columns that don't contain pivots correspond to independent variables and indicate that the system does not have a unique solution. We can assign any value to an independent variable.
A system of equations is consistent if it has a solution. If the reduced augmented matrix has a row of zeroes except for a nonzero final entry, it yields the equation 0 = nonzero which is impossible. When we find that a system is inconsistent, we stop the solution process.
If we substitute the variables back into the equations using the revised coefficients from the reduced matrix constructed in step 5 and set each equation equal to the right hand column entries of the reduced augmented matrix, we derive a system of equations equivalent to the original system in that the solutions to the two systems are the same. We have already verified that elementary row operations do not affect the solution.
To write the solution in vector form we will need an equation for each variable. Since independent variables have no pivot in their columns, they will not appear first in any revised equation. Thus we use the trick of setting each independent variable equal to itself. These new equations are trivially valid.
It is easy to rewrite the equations from steps 7 and 8 as the pivot variable equal to a linear combination of the independent variables and the constant term. If we were to assign arbitrary values to the independent variables, we could evaluate the right side of each revised equation and hence could easily determine the value of each variable on the left.
When we write the general solution to a system in vector form, we can identify basis vectors for the solution space (set of solutions to the corresponding homogeneous system of equations). Note that these are the coefficient vectors of the independent variables. We can also identify the basis for the column space by finding vectors in the original coefficient matrix that correspond to unit vector columns in the row echelon form (REF). There will be as many column space basis vectors as there are non-zero rows in the REF. This number is also the dimension of the column space.
You should always check your answer. It is easy to do in this methodology since the equations are all set up for you.
Solve the system:
x + 2y - z + 3s - 4t = 0
2x + 4y - 2z + 5s - 5t = 0
3x + 6y + 2z + 4s - 2t = 0
The matrix of coefficients of the variables is:
1 2 -1 3 -4
2 4 -2 5 -5
3 6 2 4 -2
1 2 -1 3 -4 | 0
2 4 -2 5 -5 | 0
3 6 2 4 -2 | 0
Because the augmented column is all zeroes, it will never change when using row operations. Thus we can omit it in further computations.
a11 is already 1.
1 2 -1 3 -4 1 2 -1 3 -4 1 2 -1 3 -4 2 4 -2 5 -5 -2R1+R2->R2 0 0 0 -1 3 -3R1+R3->R3 0 0 0 -1 3 3 6 2 4 -2 3 6 2 4 -2 0 0 5 -5 10
The first column with a nonzero entry below the first row is column 3. Since the nonzero entry is the 5 in the third row, we must interchange rows 2 and 3.
1 2 -1 3 -4
0 0 5 -5 10
0 0 0 -1 3
Since the pivot entry in row 2 column 3 is not 1, we must divide row 2 by 5 and then use this pivot to make the entry in row 1 column 3 zero.
1 2 -1 3 -4 1 2 0 2 -2
0 0 1 -1 2 R2+R1->R1 0 0 1 -1 2
0 0 0 -1 3 0 0 0 -1 3
Finally, we need to multiply row 3 by -1 and pivot on the element in row 3 column 4 to make the rest of column 4 zero. Then the matrix will be in row echelon form since every row will have a pivot for its first nonzero entry and each column with a pivot will be a unit vector.
1 2 0 2 -2 1 2 0 2 -2 1 2 0 0 4 0 0 1 -1 2 R3+R2->R2 0 0 1 0 -1 -2R3+R1->R1 0 0 1 0 -1 0 0 0 1 -3 0 0 0 1 -3 0 0 0 1 -3
Since there are no zero rows in the row echelon form, we know that the system is consistent. There will be a solution.
Recall that the right hand side of each equation was zero. Substituting the revised coefficients from the row echelon form back into the equations we obtain the system:
x + 2y + 4t = 0
z - t = 0
s - 3t = 0
Since columns 2 and 5 have no pivot, y and t will be independent variables. Thus we need to add two equations y = y and t = t to the three equations in step 7.
We rewrite the equations with a single variable on the left and the rest on the right as follows:
x = -2y - 4t
y = y
z = t
s = 3t
t = t
|x| |-2| |-4|
|y| | 1| | 0|
|z| = | 0| y + | 1| t
|s| | 0| | 3|
|t| | 0| | 1|
We need to assign values to the independent variables y and t, say let both be 1. Then evaluate the other variables from the equations in step 9 or the vectors in step 10. Thus x = 6, y = 1, z = 1, s = 3, t = 1. Substituting these values into the original equations we get:
-6 + 2 - 1 + 3(3) - 4 = 0 check
2(-6) + 4 - 2 + 5(3) - 5 = 0 check
3(-6) + 6 + 2 + 4(3) - 2 = 0 check
Everything checks out so we are fairly confident that our answer is correct.
These will be provided in class.
See problem 0.24 on page 23 of Strategic Mathematics