You are about to erase your work on this activity. Are you sure you want to do this?
Updated Version Available
There is an updated version of this activity. If you update to the most recent version of this activity, then your current progress on this activity will be erased. Regardless, your record of completion will remain. How would you like to proceed?
Mathematical Expression Editor
We introduce Gaussian elimination and Gauss-Jordan elimination algorithms, and
define the rank of a matrix.
SYS-0030: Gaussian Elimination and Rank
Row Echelon and Reduced Row Echelon Forms
In module SYS-0020, we learned to write linear systems in augmented matrix
form and use elementary row operations to carry an augmented matrix to
row-echelon form and the reduced row-echelon form in order to solve linear
systems.
Recall that a matrix (or augmented matrix) is in row-echelon form if:
All entries below each leading entry are .
Each leading entry is in a column to the right of the leading entries in the
rows above it.
All rows of zeros, if there are any, are located below non-zero rows.
A matrix in row-echelon form is said to be in reduced row-echelon form if it has the
following additional properties
Each leading entry is a
All entries above each leading are
Matrices in row-echelon form and reduced row-echelon form are “convenient” because
their corresponding systems of equations are easy to solve.
In this module we turn to the question of existence and uniqueness of the two echelon
forms. Can every matrix (augmented matrix) be carried to a row-echelon form? If so,
is the row-echelon form unique? Can every matrix be reduced to a reduced
row-echelon form? If so, is the reduced row-echelon form unique? The answers we find
will have long-lasting implications.
Solve the following system of equations.
We create an augmented matrix corresponding to the system and apply row
operations until the matrix is in row-echelon form.
Note that the elementary row operations that lead to (eq:ref1) were not prescribed. We may
employ row-operations in a different manner and obtain a different matrix in
row-echelon form. For example, suppose for some reason we had begun by switching
the first and third rows.
Next we would reduce this matrix to row-echelon form, perhaps in this way:
The augmented matrices in (eq:ref1) and (eq:ref2) are clearly not the same, but both are in
row-echelon form.
If we write the systems of equations corresponding to (eq:ref1) and (eq:ref2), we can employ back
substitution to solve them. The matrix in (eq:ref1) corresponds to
Because both systems are equivalent to the original system, it is not surprising that
back substitution yields the same solution for both systems.
It is clear from Exploration init:gaussianelim1 that a row-echelon form corresponding to a matrix is not
unique. But what about the reduced row-echelon form?
In this problem we revisit the system
Following the steps we took to get (eq:ref1), but taking the process a little further, we get
the reduced row-echelon form.
Do you think it is possible to start with (eq:ref2) and obtain the same reduced row-echelon
form? Try to justify your response. If possible, find the elementary row operations
that take (eq:ref2) to the reduced row-echelon form in (eq:rref3).
Our observations in Exploration init:gaussianelim2 are summarized in the following diagram.
We observed that a row-echelon form associated with a matrix is not unique. In
contrast, we also saw how different sequences of elementary row operations lead to
the same solution set and the same reduced row-echelon form. It turns out that the
reduced row-echelon form of a matrix is unique.
The reduced row-echelon form of a matrix is unique.
A proof of this result can be found in [Yuster].
The reduced row-echelon form of a matrix is an instance of a row-echelon form of the
matrix. While a given matrix may have multiple row-echelon forms, all row-echelon
forms will share one characteristic: the number of nonzero rows in a row-echelon form
of the given matrix will be the same. We will prove this result in Theorem th:samenumberofnonzerorows of
VSP-0040.
Gaussian and Gauss-Jordan Elimination
Gaussian Elimination The process of using the elementary row operations on a
matrix to transform it into row-echelon form is called Gaussian Elimination.
As we saw in the previous section, it is possible to follow different sequences of row
operations to arrive at various row-echelon forms. However, it was not clear whether
it is always possible to find a row-echelon form. The following algorithm takes any
matrix (or augmented matrix) and transforms it into row-echelon form:
Gaussian
Algorithm Let be an matrix.
Set initially.
Step 1. If consists entirely of zeros, stop; is already in row-echelon form.
Step 2. Otherwise, find the first column from the left containing a nonzero
entry in row or below row . This column will be called a pivot column.
Scan the pivot column from top to bottom, starting with row . Pick the
topmost nonzero entry and call it . Switch rows, if necessary, to move the
row containing to row . Now is the leading entry in its row. We will also
refer to as a pivot.
Step 3. By subtracting multiples of the row containing from rows below
it, make each entry below zero.
Step 4. Set . If then stop; is in row-echelon form.
Repeat steps 1–4 on the matrix consisting of the remaining rows. When the process
stops, will be in row echelon form.
Gaussian Algorithm guarantees that every matrix will have a row-echelon
form.
Use the Gaussian Algorithm to find a row-echelon form of if
Following Step 2, we choose the first entry, , as our pivot. We then perform step 3,
using the top row to get zeros in all entries below the .
The first row is now complete, and we repeat the process on the rows below it. We
identify as a pivot entry in the second column and move the row containing to be
directly below the first completed row. We then use the to make each entry below
the a zero.
This time the algorithm terminates since row 3 and row 4 are zero rows.
Gauss-Jordan Elimination The process of using the elementary row operations on a
matrix to transform it into reduced row-echelon form is called Gauss-Jordan
elimination.
Given a matrix in row-echelon form, it is easy to bring it the reduced row-echelon
form. For example, continuing with Example ex:non-augmented, we can start where we left off and
compute . From our earlier computations we have:
Now we create leading and use them to to wipe out all non-zero entries above
them.
The following modification to the Gaussian Algorithm produces the reduced
row-echelon form of a matrix. This algorithm guarantees the existence of the reduced
row-echelon form.
Gauss-Jordan Algorithm Let be an matrix. Follow the steps of the Gaussian
Algorithm but modify Step 2 to create leading by multiplying the row containing by
.
When the Gaussian Algorithm terminates, subtract multiples of the rows
containing leading from the rows above to make all entries above the pivots
zero.
Use the Gauss-Jordan Algorithm to solve the system
We convert the reduced row-echelon form to a system of equations and find the
solution. The last equation contributes nothing to the system so we omit writing it
down.
The solution is
The Gauss-Jordan Algorithm guarantees the existence of the reduced row-echelon
form for all matrices. When doing computations by hand, however, the algorithm
may not always be the optimal method of finding a row-echelon form or the reduced
row-echelon form because the procedure often leads to fractions early in
the process. The following video shows how to arrive at the same reduced
row-echelon form for the matrix in Example ex:gaussjordanalg without doing any fraction
arithmetic. You will see that we still employ the row operations, but in a different
order.
_
The video, again, highlights the fact that regardless of what sequence of elementary
row operations we take to arrive at the reduced row-echelon form, the end result is
the same.
Rank
As stated in Theorem th:uniquenessofrref, the reduced row-echelon form of a matrix is uniquely
determined by . That is, no matter which series of row operations is used to carry to
a reduced row-echelon matrix, the result will always be the same matrix. By contrast,
this is not true for row-echelon matrices: Different sequences of row operations can
carry the same matrix to different row-echelon matrices. However, it is
true that the number of nonzero rows must be the same in each of these
row-echelon matrices, as we will see in Theorem th:dimofrowA of VSP-0040. Hence, the number
depends only on and not on the way in which is carried to row-echelon
form.
Matrices (eq:ref1) and (eq:ref2) of Exploration init:gaussianelim1 are both row-echelon forms of . Both matrices
have three nonzero rows. The same is true for .
The rank of matrix is the number of nonzero rows in any row-echelon matrix to
which can be carried by elementary row operations.
Compute the rank of
A reduction of to row-echelon form is
Because the row-echelon form has two nonzero rows, .
Suppose a system of equations in variables is consistent, and that the rank of the
coefficient matrix is .
(a)
The set of solutions involves exactly parameters, corresponding to free
variables.
(b)
If , the system has infinitely many solutions.
(c)
If , the system has a unique solution.
Proof
The fact that the rank of the coefficient matrix is means that there are
exactly leading variables in the coefficient matrix, and hence exactly nonleading
variables. The nonleading variables are called free variables. All free variables
are assigned parameters, so the set of solutions involves exactly parameters.
Hence if , there is at least one parameter, and so infinitely many solutions. If ,
there are no parameters and the resulting solution is unique.
Theorem th:rankandsolutions shows that, for any system of linear equations, exactly three possibilities
exist:
(a)
Unique solution. This occurs when every variable is a leading variable.
(b)
Infinitely many solutions. This occurs when the system is consistent and
there is at least one nonleading variable, so at least one parameter is
involved.
(c)
No solution. This occurs when a row appears in the row-echelon form.
Such a row corresponds to an equation with no solutions. (See Example ex:nosolutionssys
of SYS-0020.)
Practice Problems
Show that applying Gauss-Jordan elimination to the matrix in Exploration init:gaussianelim2 yields
the same matrix in reduced row-echelon form that we got in Exploration
init:gaussianelim1.
In this problem you will be asked to bring an augmented matrix to its reduced
row-echelon form using two different sets of steps.
Follow the indicated steps of
the Gauss-Jordan algorithm to carry the matrix to its reduced row-echelon
form.
Your entries must be fractions or integers - no decimals.
The following reduction steps do not follow the algorithm but are easier for a human
to carry out because they use fewer fractions. Follow the indicated steps to carry the
matrix to its reduced row-echelon form.
Your entries must be fractions or integers - no decimals.
Find the rank of each matrix.
Answer:
Answer:
Answer:
Answer:
Suppose is a matrix. Which of the following can be true?
All of the
above
Suppose a linear system has equations and unknowns. Which of the following is
NOT a possibility?
The system has a unique solutionThe system has no
solutionsThe system has infinitely many solutions
Suppose is a matrix such that has leading . What do we know to be true about
has at least entriesAny row-echelon form of will have exactly nonzero rowsAny row-echelon form of will have at least nonzero rowsAny row-echelon form of
will have at most nonzero rows
In this problem we will discuss how the rank of the coefficient matrix associated with
a linear system compares to the rank of the augmented matrix associated with the
system.
(a)
Explain why the rank of the augmented matrix has to be greater than or
equal to the rank of the coefficient matrix.
(b)
Prove that for a consistent system the rank of the coefficient matrix will
be the same as the rank of the augmented matrix.
(c)
Give an example of an inconsistent system for which the rank of the
augmented matrix is greater than the rank of the coefficient matrix.
(d)
Can the rank of an augmented matrix be greater than the number of
variables?
(e)
Is the following statement true?
“If the rank of the augmented matrix associated with a linear system
is greater than the rank of the coefficient matrix, then the system is
inconsistent.”
W. Keith Nicholson, Linear Algebra with Applications, Lyryx 2018, Open Edition, p
15-17.
Bibliography
[Yuster] Thomas Yuster, The Reduced Row Echelon Form of a Matrix is Unique: a
Simple Proof, Mathematics Magazine, vol. 57, no. 2 (Mar. 1984), pp. 93-94.
