A less cumbersome way to represent a linear system is to write it as an augmented matrix. For example
the linear system, 4.4 can be written as
( )
1 3 6 |25
|( 2 7 14 |58 |) .
0 2 5 |19
It has exactly the same information as the original system but here it is understood there is an x
column,
( )
1
|( 2 |)
0
, a y column,
( )
3
|( 7 |)
2
and a z column,
( )
6
|( 14 |)
5
. The rows correspond to
the equations in the system. Thus the top row in the augmented matrix corresponds to the
equation,
x+ 3y +6z = 25.
Now when you replace an equation with a multiple of another equation added to itself, you are just taking
a row of this augmented matrix and replacing it with a multiple of another row added to it. Thus the first
step in solving 4.4 would be to take
(− 2)
times the first row of the augmented matrix above and add it to
the second row,
Changes to the system of equations in 4.7 as a result of an elementary operations translate into changes of
the augmented matrix resulting from a row operation. Note that Theorem 4.1.4 implies that the row
operations deliver an augmented matrix for a system of equations which has the same solution set as the
original system.
Definition 4.1.6The row operations consist of the following
Switch two rows.
Multiply a row by a nonzero number.
Replace a row by a multiple of another row added to it.
Gauss eliminationis a systematic procedure to simplify an augmented matrix to a reduced form. In
the following definition, the term “leading entry” refers to the first nonzero entry of a row when scanning
the row from left to right.
Definition 4.1.7An augmented matrix isin echelon form if
All nonzero rows are above any rows of zeros.
Each leading entry of a row is in a column to the right of the leading entries of any rows aboveit.
How do you know when to stop doing row operations? You might stop when you have obtained an
echelon form as described above, but you certainly should stop doing row operations if you have gotten a
matrix in row reduced echelon form described next.
Definition 4.1.8An augmentedmatrix is in row reduced echelon formif
All nonzero rows are above any rows of zeros.
Each leading entry of a row is in a column to the right of the leading entries of any rows aboveit.
All entries in a column above and below a leading entry are zero.
Each leading entry is a 1, the only nonzero entry in its column.
Example 4.1.9Here are some matrices which are in row reduced echelon form.
Definition 4.1.12A pivot positionin a matrix is the location of a leading entry in an echelonform resulting from the application of row operations to the matrix. A pivot columnis a columnthat contains a pivot position.
For example consider the following.
Example 4.1.13Suppose
( )
| 1 2 3 4 |
A = ( 3 2 1 6 )
4 4 4 10
Where are the pivot positionsand pivot columns?
Replace the second row by −3 times the first added to the second. This yields
( )
1 2 3 4
|( 0 − 4 − 8 − 6 |) .
4 4 4 10
This is not in reduced echelon form so replace the bottom row by −4 times the top row added to the
bottom. This yields
( )
1 2 3 4
|( 0 − 4 − 8 − 6 |) .
0 − 4 − 8 − 6
This is still not in reduced echelon form. Replace the bottom row by −1 times the middle row added to the
bottom. This yields
( )
| 1 2 3 4 |
( 0 − 4 − 8 − 6 )
0 0 0 0
which is in echelon form, although not in reduced echelon form. Therefore, the pivot positions in the
original matrix are the locations corresponding to the first row and first column and the second row and
second columns as shown in the following:
( |--| )
-1-| 2-| 3 4
|( 3 2 | 1 6 |)
4 4-- 4 10
Thus the pivot columns in the matrix are the first two columns.
The following is the algorithm for obtaining a matrix which is in row reduced echelon form.
Algorithm 4.1.14
This algorithm tells how to start with a matrix and do row operations on it in such a way as to end up
with a matrix in row reduced echelon form.
Find the first nonzero column from the left. This is the first pivot column. The position at
the top of the first pivot column is the first pivot position. Switch rows if necessary to place a
nonzero number in the first pivot position.
Use row operations to zero out the entries below the first pivot position.
Ignore the row containing the most recent pivot position identified and the rows above it.
Repeat steps 1 and 2 to the remaining sub-matrix, the rectangular array of numbers obtained
from the original matrix by deleting the rows you just ignored. Repeat the process until there
are no more rows to modify. The matrix will then be in echelon form.
Moving from right to left, use the nonzero elements in the pivot positions to zero out the
elements in the pivot columns which are above the pivots.
Divide each nonzero row by the value of the leading entry. The result will be a matrix in row
reduced echelon form.
This row reduction procedure applies to both augmented matrices and non augmented
matrices. There is nothing special about the augmented column with respect to the row reduction
procedure.
Do row reductions till you obtain a matrix in echelon form. Then complete the process by producing one inrow reduced echelon form.
The pivot column is the second. Hence the pivot position is the one in the first row and second column.
Switch the first two rows to obtain a nonzero entry in this pivot position.
Step two is not necessary because all the entries below the first pivot position in the resulting matrix are
zero. Now ignore the top row and the columns to the left of this first pivot position. Thus you apply the
same operations to the smaller matrix
( )
| 2 3 2 |
|| 1 2 2 || .
( 0 0 0 )
0 2 1
The next pivot column is the third corresponding to the first in this smaller matrix and the second pivot
position is therefore, the one which is in the second row and third column. In this case it is not necessary to
switch any rows to place a nonzero entry in this position because there is already a nonzero entry there.
Multiply the third row of the original matrix by −2 and then add the second row to it. This
yields
The next matrix the steps in the algorithm are applied to is
( )
− 1 − 2
|( 0 0 |) .
2 1
The first pivot column is the first column in this case and no switching of rows is necessary because
there is a nonzero entry in the first pivot position. Therefore, the algorithm yields for the next
step
There is only one column and it is nonzero so this single column is the pivot column. Therefore, the
algorithm yields the following matrix for the echelon form.
The above algorithm is the way a computer would obtain a reduced echelon form for a given matrix. It
is not necessary for you to pretend you are a computer but if you like to do so, the algorithm described
above will work. The main idea is to do row operations in such a way as to end up with a
matrix in echelon form or row reduced echelon form because when this has been done, the
resulting augmented matrix will allow you to describe the solutions to the linear system of
equations in a meaningful way. When you do row operations until you obtain row reduced
echelon form, the process is called the Gauss Jordan method. Otherwise, it is called Gauss
elimination.
Example 4.1.16Give the complete solution to the system of equations, 5x + 10y − 7z = −2,
2x + 4y − 3z = −1, and 3x + 6y + 5z = 9.
The augmented matrix for this system is
( )
2 4 − 3 − 1
|( 5 10 − 7 − 2 |)
3 6 5 9
Multiply the second row by 2, the first row by 5, and then take
(− 1)
times the first row and add to the
second. Then multiply the first row by 1/5. This yields
( )
| 2 4 − 3 − 1 |
( 0 0 1 1 )
3 6 5 9
Now, combining some row operations, take
(− 3)
times the first row and add this to 2 times the last row
and replace the last row with this. This yields.
( )
2 4 − 3 − 1
|( 0 0 1 1 |) .
0 0 1 21
One more row operation, taking
(− 1)
times the second row and adding to the bottom yields.
( )
| 2 4 − 3 − 1 |
( 0 0 1 1 ) .
0 0 0 20
This is impossible because the last row indicates the need for a solution to the equation
0x+ 0y+ 0z = 20
and there is no such thing because 0≠20. This shows there is no solution to the three given equations.
When this happens, the system is called inconsistent. In this case it is very easy to describe the solution
set. The system has no solution.
Here is another example based on the use of row operations.
Example 4.1.17Give the complete solution to the system of equations, 3x−y−5z = 9, y−10z = 0,and −2x + y = −6.
The augmented matrix of this system is
( )
| 3 − 1 − 5 9 |
( 0 1 − 10 0 )
− 2 1 0 − 6
Replace the last row with 2 times the top row added to 3 times the bottom row combining two row
operations. This gives
( )
3 − 1 − 5 9
|( 0 1 − 10 0 |) .
0 1 − 10 0
The entry, 3 in this sequence of row operations is called thepivot. It is used to create zeros in the other
places of the column. Next take −1 times the middle row and add to the bottom. Here the 1 in the second
row is the pivot.
( )
| 3 − 1 − 5 9 |
( 0 1 − 10 0 )
0 0 0 0
Take the middle row and add to the top and then divide the top row which results by 3.
( )
1 0 − 5 3
|( 0 1 − 10 0 |) .
0 0 0 0
This is in reduced echelon form. The equations corresponding to this reduced echelon form
are y = 10z and x = 3 + 5z. Apparently z can equal any number. Lets call this number t.^{1}Therefore,
the solution set of this system is x = 3 + 5t,y = 10t, and z = t where t is completely arbitrary. The system
has an infinite set of solutions which are given in the above simple way. This is what it is all about, finding
the solutions to the system.
There is some terminology connected to this which is useful. Recall how each column corresponds to a
variable in the original system of equations. The variables corresponding to a pivot column are called basicvariables. The other variables are called free variables.In Example 4.1.17 there was one free variable, z,
and two basic variables, x and y. In describing the solution to the system of equations, the free
variables are assigned a parameter. In Example 4.1.17 this parameter was t. Sometimes there are
many free variables and in these cases, you need to use many parameters. Here is another
example.
Example 4.1.18Find the solution to the system
x + 2y− z + w = 3
x+ y− z + w = 1
x + 3y− z + w = 5
The augmented matrix is
( )
1 2 − 1 1 3
|( 1 1 − 1 1 1 |) .
1 3 − 1 1 5
Take −1 times the first row and add to the second. Then take −1 times the first row and add to the third.
This yields
This matrix is in echelon form and you see the basic variables are x and y while the free variables are z and
w. Assign s to z and t to w. Then the second row yields the equation, y = 2 while the top
equation yields the equation, x + 2y − s + t = 3 and so since y = 2, this gives x + 4 − s + t = 3
showing that x = −1 + s − t,y = 2,z = s, and w = t. It is customary to write this in the
form
( ) ( )
x − 1 + s− t
|| y || || 2 ||
|( z |) = |( s |) . (4.10)
w t
(4.10)
This is another example of a system which has an infinite solution set but this time the solution set
depends on two parameters, not one. Most people find it less confusing in the case of an infinite solution
set to first place the augmented matrix in row reduced echelon form rather than just echelon
form before seeking to write down the description of the solution. In the above, this means
we don’t stop with the echelon form 4.9. Instead we first place it in reduced echelon form as
follows.
( 1 0 − 1 1 − 1 )
| |
( 0 1 0 0 2 ) .
0 0 0 0 0
Then the solution is y = 2 from the second row and x = −1 + z −w from the first. Thus letting z = s and
w = t, the solution is given in 4.10.
The number of free variables is always equal to the number of different parameters used to describe
the solution. If there are no free variables, then either there is no solution as in the case where row
operations yield an echelon form like
( )
1 2 3
|( 0 4 − 2 |)
0 0 1
or there is a unique solution as in the case where row operations yield an echelon form like
( )
| 1 2 2 3 |
( 0 4 3 − 2 ) .
0 0 4 1
Also, sometimes there are free variables and no solution as in the following:
( )
1 2 2 3
|( 0 4 3 − 2 |) .
0 0 0 1
There are a lot of cases to consider but it is not necessary to make a major production of this. Do row
operations till you obtain a matrix in echelon form or reduced echelon form and determine whether there is
a solution. If there is, see if there are free variables. In this case, there will be infinitely many solutions.
Find them by assigning different parameters to the free variables and obtain the solution. If there are no
free variables, then there will be a unique solution which is easily determined once the augmented matrix is
in echelon or row reduced echelon form. In every case, the process yields a straightforward way to describe
the solutions to the linear system. As indicated above, you are probably less likely to become
confused if you place the augmented matrix in row reduced echelon form rather than just echelon
form.
In summary,
Definition 4.1.19A system of linear equations is a list of equations,
where a_{ij}are numbers, and b_{j}is a number. The above is a system of m equations in the n variables,x_{1},x_{2}
⋅⋅⋅
,x_{n}. Nothing is said about the relative size of m and n. Written more simply in terms ofsummation notation, the above can be written in the form
n
∑ aijxj = fi, i = 1,2,3,⋅⋅⋅,m
j=1
It is desired to find
(x ,⋅⋅⋅,x )
1 n
solving each of the equations listed.
As illustrated above, such a system of linear equations may have a unique solution, no solution, or
infinitely many solutions and these are the only three cases which can occur for any linear system.
Furthermore, you do exactly the same things to solve any linear system. You write the augmented matrix
and do row operations until you get a simpler system in which it is possible to see the solution, usually
obtaining a matrix in echelon or reduced echelon form. All is based on the observation that the row
operations do not change the solution set. You can have more equations than variables, fewer equations
than variables, etc. It doesn’t matter. You always set up the augmented matrix and go to work on it.
Definition 4.1.20A system of linear equations is calledconsistent if there exists a solution. Itis calledinconsistent if there is no solution.
These are reasonable words to describe the situations of having or not having a solution. If you think of
each equation as a condition which must be satisfied by the variables, consistent would mean there is some
choice of variables which can satisfy all the conditions. Inconsistent would mean there is no choice of the
variables which can satisfy each of the conditions.