You can navigate through this E-Book using the menu to the left. For E-Books that have a Chapter/Section organization each option in the menu to the left indicates a chapter and will open a menu showing the sections in that chapter. Alternatively, you can navigate to the next/previous section or chapter by clicking the links in the boxes at the very top and bottom of the material.
Also, depending upon the E-Book, it will be possible to download the complete E-Book, the chapter containing the current section and/or the current section. You can do this be clicking on the E-Book, Chapter, and/or the Section link provided below.
For those pages with mathematics on them you can, in most cases, enlarge the mathematics portion by clicking on the equation. Click the enlarged version to hide it.
Solving Systems of
Equations
In this section we are going to take a look at using linear
algebra techniques to solve a system of linear equations. Once we have a couple of definitions out of
the way we’ll see that the process is a fairly simple one. Well, it’s fairly simple to write down the
process anyway. Applying the process is
fairly simple as well but for large systems can take quite a few steps. So, let’s get the definitions out of the way.
A matrix (any matrix, not just an augmented matrix) is said
to be in reduced row-echelon form if
it satisfies all four of the following conditions.
- If
there are any rows of all zeros then they are at the bottom of the matrix.
- If a
row does not consist of all zeros then its first non-zero entry (i.e. the left most non-zero entry)
is a 1. This 1 is called a leading 1.
- In any
two successive rows, neither of which consists of all zeroes, the leading
1 of the lower row is to the right of the leading 1 of the higher row.
- If a
column contains a leading 1 then all the other entries of that column are
zero.
A matrix (again any matrix) is said to be in row-echelon form if it satisfies items
1 
3 of the reduced row-echelon form definition.
Notice from these definitions that a matrix that is in
reduced row-echelon form is also in row-echelon form while a matrix in
row-echelon form may or may not be in reduced row-echelon form.
|
Example 1 The
following matrices are all in row-echelon form.
|
None of the matrices in the previous example are in reduced
row-echelon form. The entries that are
preventing these matrices from being in reduced row-echelon form are
highlighted in red and underlined (for those without color printers...). In order for these matrices to be in reduced
row-echelon form all of these highlighted entries would need to be zeroes.
Notice that we didn’t highlight the entries above the 1 in
the fifth column of the third matrix.
Since this 1 is not a leading 1 (i.e.
the leftmost non-zero entry) we don’t need the numbers above it to be zero in
order for the matrix to be in reduced row-echelon form.
|
Example 2 The
following matrices are all in reduced row-echelon form.
|
In the second matrix on the first row we have all zeroes in
the entries. This is perfectly
acceptable and so don’t worry about it.
This matrix is in reduced row-echelon form, the fact that it doesn’t
have any non-zero entries does not change that fact since it satisfies the
conditions. Also, in the second matrix
of the second row notice that the last column does not have zeroes above the 1
in that column. That is perfectly
acceptable since the 1 in that column is not a leading 1 for the fourth row.
Notice from Examples 1 and 2 that the only real difference
between row-echelon form and reduced row-echelon form is that a matrix in
row-echelon form is only required to have zeroes below a leading 1 while a
matrix in reduced row-echelon from must have zeroes both below and above a
leading 1.
Okay, let’s now start thinking about how to use linear
algebra techniques to solve systems of linear equations. The process is actually quite simple. To solve a system of equations we will first
write down the augmented matrix for the system.
We will then use elementary row
operations to reduce the augmented matrix to either row-echelon form or to
reduced row-echelon form. Any further
work that we’ll need to do will depend upon where we stop.
If we go all the way to reduced row-echelon form then in
many cases we will not need to do any further work to get the solution and in
those times where we do need to do more work we will generally not need to do
much more work. Reducing the augmented
matrix to reduced row-echelon form is called Gauss-Jordan Elimination.
If we stop at row-echelon form we will have a little more
work to do in order to get the solution, but it is generally fairly simple
arithmetic. Reducing the augmented
matrix to row-echelon form and then stopping is called Gaussian Elimination.
At this point we should work a couple of examples.
|
Example 3 Use
Gaussian Elimination and Gauss-Jordan Elimination to solve the following
system of linear equations.
Solution
Since we’re asked to use both solution methods on this
system and in order for a matrix to be in reduced row-echelon form the matrix
must also be in row-echelon form.
Therefore, we’ll start off by putting the augmented matrix in
row-echelon form, then stop to find the solution. This will be Gaussian Elimination. After doing that we’ll go back and pick up
from row-echelon form and further reduce the matrix to reduced row echelon
form and at this point we’ll have performed Gauss-Jordan Elimination.
So, let’s start off by getting the augmented matrix for
this system.
As we go through the steps in this first example we’ll
mark the entry(s) that we’re going to be looking at in each step in red so
that we don’t lose track of what we’re doing.
We should also point out that there are many different paths that we
can take to get this matrix into row-echelon form and each path may well
produce a different row-echelon form of the matrix. Keep this in mind as you work these
problems. The path that you take to
get this matrix into row-echelon form should be the one that you find the
easiest and that may not be the one that the person next to you finds the
easiest. Regardless of which path you
take you are only allowed to use the three elementary row operations that we
looked in the previous section.
So, with that out of the way we need to make the leftmost
non-zero entry in the top row a one.
In this case we could use any three of the possible row
operations. We could divide the top
row by -2 and this would certainly change the red “-2” into a one. However, this will also introduce fractions
into the matrix and while we often can’t avoid them let’s not put them in
before we need to.
Next, we could take row three and add it to row one, or we
could take three times row 2 and add it to row one. Either of these would also change the red
“-2” into a one. However, this row
operation is the one that is most prone to arithmetic errors so while it
would work let’s not use it unless we need to.
This leaves interchanging any two rows. This is an operation that won’t always work
here to get a 1 into the spot we want, but when it does it will usually be
the easiest operation to use. In this
case we’ve already got a one in the leftmost entry of the second row so let’s
just interchange the first and second rows and we’ll get a one in the
leftmost spot of the first row pretty much for free. Here is this operation.
Now, the next step we’ll need to take is changing the two
numbers in the first column under the leading 1 into zeroes. Recall that as we move down the rows the
leading 1 MUST move off to the right.
This means that the two numbers under the leading 1 in the first
column will need to become zeroes. Again,
there are often several row operations that can be done to do this. However, in most cases adding multiples of
the row containing the leading 1 (the first row in this case) onto the rows
we need to have zeroes is often the easiest.
Here are the two row operations that we’ll do in this step.
Notice that since each operation changed a different row
we went ahead and performed both of them at the same time. We will often do this when multiple
operations will all change different rows.
We now need to change the red “5” into a one. In this case we’ll go ahead and divide the
second row by 5 since this won’t introduce any fractions into the matrix and
it will give us the number we’re looking for.
Next, we’ll use the third row operation to change the red
“-6” into a zero so the leading 1 of the third row will move to the right of
the leading 1 in the second row. This
time we’ll be using a multiple of the second row to do this. Here is the work in this step.
Notice that in both steps were we needed to get zeroes
below a leading 1 we added multiples of the row containing the leading 1 to
the rows in which we wanted zeroes.
This will always work in this case.
It may be possible to use other row operations, but the third can
always be used in these cases.
The final step we need to get the matrix into row-echelon
form is to change the red “-2” into a one.
To do this we don’t really have a choice here. Since we need the leading one in the third
row to be in the third or fourth column (i.e.
to the right of the leading one in the second column) we MUST retain the
zeroes in the first and second column of the third row.
Interchanging the second and third row would definitely
put a one in the third column of the third row, however, it would also change
the zero in the second column which we can’t allow. Likewise we could add the first row to the
third row and again this would put a one in the third column of the third
row, but this operation would also change both of the zeroes in front of it
which can’t be allowed.
Therefore, our only real choice in this case is to divide
the third row by -2. This will retain
the zeroes in the first and second column and change the entry in the third
column into a one. Note that this step
will often introduce fractions into the matrix, but at this point that can’t
be avoided. Here is the work for this
step.
At this point the augmented matrix is in row-echelon
form. So if we’re going to perform
Gaussian Elimination on this matrix we’ll stop and go back to equations. Doing this gives,
At this point solving is quite simple. In fact we can see from this that . Plugging this into the second equation
gives . Finally, plugging both of these into the
first equation gives . Summarizing up the solution to the system
is,
This substitution process is called back substitution.
Now, let’s pick back up at the row-echelon form of the
matrix and further reduce the matrix into reduced row-echelon form. The first step in doing this will be to
change the numbers above the leading 1 in the third row into zeroes. Here are the operations that will do that
for us.
The final step is then to change the red “2” above the
leading one in the second row into a zero.
Here is this operation.
We are now in reduced row-echelon form so all we need to
do to perform Gauss-Jordan Elimination is to go back to equations.
We can see from this that one of the nice consequences to
Gauss-Jordan Elimination is that when there is a single solution to the
system there is no work to be done to find the solution. It is generally given to us for free. Note as well that it is the same solution
as the one that we got by using Gaussian Elimination as we should expect.
|
Before we proceed with another example we need to give a
quick fact. As was pointed out in this
example there are many paths we could take to do this problem. It was also noted that the path we chose
would affect the row-echelon form of the matrix. This will not be true for the reduced
row-echelon form however. There is only
one reduced row-echelon form of a given matrix no matter what path we chose to
take to get to that point.
If we know ahead of time that we are going to go to reduced
row-echelon form for a matrix we will often take a different path than the one
used in the previous example. In the
previous example we first got the matrix in row-echelon form by getting zeroes
under the leading 1’s and then went back and put the matrix in reduced
row-echelon form by getting zeroes above the leading 1’s. If we know ahead of time that we’re going to
want reduced row-echelon form we can just take care of the matrix in a column
by column basis in the following manner.
We first get a leading 1 in the correct column then instead of using
this to convert only the numbers below it to zero we can use it to convert the
numbers both above and below to zero. In
this way once we reach the last column and take care of it of course we will be
in reduced row-echelon form.
We should also point out the differences between
Gauss-Jordan Elimination and Gaussian Elimination. With Gauss-Jordan Elimination there is more
matrix work that needs to be performed in order to get the augmented matrix
into reduced row-echelon form, but there will be less work required in order to
get the solution. In fact, if there’s a
single solution then the solution will be given to us for free. We will see however, that if there are
infinitely many solutions we will still have a little work to do in order to
arrive at the solution. With Gaussian
Elimination we have less matrix work to do since we are only reducing the
augmented matrix to row-echelon form.
However, we will always need to perform back substitution in order to
get the solution. Which method you use
will probably depend on which you find easier.
Okay let’s do some more examples. Since we’ve done one example in excruciating
detail we won’t be bothering to put as much detail into the remaining
examples. All operations will be shown, but
the explanations of each operation will not be given.
|
Example 4 Solve
the following system of linear equations.
Solution
First, the instructions to this problem did not specify
which method to use so we’ll need to make a decision. No matter which method we chose we will
need to get the augmented matrix down to row-echelon form so let’s get to
that point and then see what we’ve got.
If we’ve got something easy to work with we’ll stop and do Gaussian
Elimination and if not we’ll proceed to reduced row-echelon form and do
Gauss-Jordan Elimination.
So, let’s start with the augmented matrix and then proceed
to put it into row-echelon form and again we’re not going to put in quite the
detail in this example as we did with the first one. So, here is the augmented matrix for this
system.
and here is the work to put it into row-echelon form.
Okay, we’re now in row-echelon form. Let’s go back to equation and see what
we’ve got.
Hmmmm. That last
equation doesn’t look correct. We’ve
got a couple of possibilities here.
We’ve either just managed to prove that 0=1 (and we know that’s not
true), we’ve made a mistake (always possible, but we haven’t in this case) or
there’s another possibility we haven’t thought of yet.
Recall from Theorem
1 in the previous section that a system has one of three possibilities
for a solution. Either there is no
solution, one solution or infinitely many solutions. In this case we’ve got no solution. When we go back to equations and we get an
equation that just clearly can’t be true such as the third equation above
then we know that we’ve got not solution.
Note as well that we didn’t really need to do the last
step above. We could have just as
easily arrived at this conclusion by looking at the second to last matrix
since 0=8 is just as incorrect as 0=1.
So, to close out this problem, the official answer that
there is no solution to this system.
|
In order to see how a simple change in a system can lead to
a totally different type of solution let’s take a look at the following
example.
|
Example 5 Solve
the following system of linear equations.
Solution
The only difference between this system and the previous one
is the -7 in the third equation. In
the previous example this was a 1.
Here is the augmented matrix for this system.
Now, since this is essentially the same augmented matrix
as the previous example the first few steps are identical and so there is no
reason to show them here. After taking
the same steps as above (we won’t need the last step this time) here is what
we arrive at.
For some good practice you should go through the steps
above and make sure you arrive at this matrix.
In this case the last line converts to the equation
and this is a perfectly acceptable equation because after
all zero is in fact equal to zero! In
other words, we shouldn’t get excited about it.
At this point we could stop convert the first two lines of
the matrix to equations and find a solution.
However, in this case it will actually be easier to do the one final
step to go to reduced row-echelon form.
Here is that step.
We are now in reduced row-echelon form so let’s convert to
equations and see what we’ve got.
Okay, we’ve got more unknowns than equations and in many
cases this will mean that we have infinitely many solutions. To see if this is the case for this example
let’s notice that each of the equations has an in it and so we can solve each equation for
the remaining variable in terms of as follows.
So, we can choose to be any value we want to, and hence it is
a free variable (recall we saw these in the
previous section), and each choice of will give us a different solution to the
system. So, just like in the previous
section when we’ll rename the and write the solution as follows,
We therefore get infinitely many solutions, one for each
possible value of t and since t can be any real number there are
infinitely many choices for t.
|
Before moving on let’s first address the issue of why we
used Gauss-Jordan Elimination in the previous example. If we’d used Gaussian Elimination (which we
definitely could have used) the system of equations would have been.
To arrive at the solution we’d have to solve the second
equation for first and then substitute this into the first
equation before solving for . In my mind this is more work and work that
I’m more likely to make an arithmetic mistake than if we’d just gone to reduced
row-echelon form in the first place as we did in the solution.
There is nothing wrong with using Gaussian Elimination on a
problem like this, but the back substitution is definitely more work when we’ve
got infinitely many solutions than when we’ve got a single solution.
Okay, to this point we’ve worked nothing but systems with
the same number of equations and unknowns.
We need to work a couple of other examples where this isn’t the case so
we don’t get too locked into this kind of system.
|
Example 6 Solve
the following system of linear equations.
Solution
So, let’s start with the augmented matrix and reduce it to
row-echelon form and see if what we’ve got is nice enough to work with or if
we should go the extra step(s) to get to reduced row-echelon form. Let’s start with the augmented matrix.
Notice that this time in order to get the leading 1 in the
upper left corner we’re probably going to just have to divide the row by 3
and deal with the fractions that will arise.
Do not go to great lengths to avoid fractions, they are a fact of life
with these problems and so while it’s okay to try to avoid them, sometimes
it’s just going to be easier to deal with it and work with them.
So, here’s the work for reducing the matrix to row-echelon
form.
Okay, we’re in row-echelon form and it looks like if we go
back to equations at this point we’ll need to do one quick back substitution
involving numbers and so we’ll go ahead and stop here at this point and do
Gaussian Elimination.
Here are the equations we get from the row-echelon form of
the matrix and the back substitution.
So, the solution to this system is,
|