We will close this section and this chapter by proving
that every matrix is row equivalent to one
and only one reduced echelon form matrix.
The ideas that appear here will reappear, and be further developed, in the
The underlying theme here is that one way to understand a
mathematical situation is by being able to classify the cases that can happen.
We have met this theme several times already.
We have classified solution sets of linear systems into the no-elements,
one-element, and infinitely-many elements cases.
We have also classified linear systems with the same number of equations
as unknowns into the nonsingular and singular cases.
We adopted these classifications because they give us a way to understand
the situations that we were investigating.
Here, where we are investigating row equivalence, we know that the set of all
matrices breaks into the row equivalence classes.
When we finish the proof here, we will have a way to understand each of those
classes— its matrices can be thought of as derived by row operations from the
unique reduced echelon form matrix in that class.
To understand how row operations act to transform one matrix into another,
we consider the effect that they have on the parts of a matrix.
The crucial observation is that row operations combine the rows linearly.
- Definition 2.1
A linear combination of
is an expression of the form
where the 's are scalars.
(We have already used the phrase
"linear combination" in this book.
The meaning is unchanged, but the next result's statement makes
a more formal definition in order.)
- Lemma 2.2 (Linear Combination Lemma)
A linear combination of linear combinations is a linear combination.
Given the linear combinations
consider a combination of those
where the 's are scalars along with the 's.
Distributing those 's and regrouping gives
which is a linear combination of the 's.
In this subsection we will use the convention
that, where a matrix is named with an upper case roman letter,
the matching lower-case greek letter names the rows.
- Corollary 2.3
Where one matrix reduces to another, each row of the second
is a linear combination of the rows of the first.
The proof below uses induction on the number of row operations used to
reduce one matrix to the other.
Before we proceed, here is an outline of the argument
(readers unfamiliar with induction may want to compare this argument with the
one used in the
First, for the base step of the argument, we
will verify that the proposition is true when reduction
can be done in zero row operations.
Second, for the inductive step, we will
argue that if being able to reduce the first matrix to the second in some
number of operations implies that each row of the second is a linear
combination of the rows of the first, then being able to reduce the first to
the second in operations implies the same thing.
Together, this base step and induction step prove this result because by the
base step the proposition is true in the zero operations case,
and by the inductive step the fact that it is true in the zero operations case
implies that it is true in the one operation case, and the inductive step
applied again gives that it is therefore true in the two operations case, etc.
We proceed by induction on the minimum number of row operations that take a
first matrix to a second one .
In the base step, that
zero reduction operations suffice, the two matrices are equal and each
row of is obviously a combination of
's rows: .
For the inductive step, assume the inductive hypothesis: with ,
if a matrix can be derived from in or fewer operations
then its rows are linear combinations of the 's rows.
Consider a that takes operations.
Because there are more than zero operations,
there must be a next-to-last matrix
so that .
This is only operations away from and so the inductive
hypothesis applies to it, that is, each row of
is a linear combination of the rows of .
If the last operation, the one from to , is a row swap then
the rows of are just the rows of reordered and thus each row of
is also a linear combination of the rows of .
The other two possibilities for this last operation, that it multiplies a
row by a scalar and that it adds a multiple of one row to another, both result
in the rows of being linear combinations of the rows of .
But therefore, by the Linear Combination Lemma, each row of is a linear
combination of the rows of .
With that, we have both the base step and the inductive step, and
so the proposition follows.
- Example 2.4
In the reduction
call the matrices , , , and .
The methods of the proof show that there are three sets of linear
The prior result gives us the insight that Gauss' method works by taking
linear combinations of the rows.
But to what end; why do we go to echelon form as a particularly simple, or
basic, version of a linear system?
The answer, of course, is that echelon form is suitable for back substitution,
because we have isolated the variables.
For instance, in this matrix
has been removed from 's equation.
That is, Gauss' method has made 's row independent of 's row.
Independence of a collection of row vectors, or of any kind of vectors,
will be precisely defined and explored in the next chapter.
But a first take on it is that we can show that, say, the third row above
is not comprised of the other rows, that
For, suppose that there are scalars , , and such that this
The first row's leading entry is in the first column and narrowing our
consideration of the above relationship to consideration only of the entries
from the first column gives that .
The second row's leading entry is in the third column and the equation of
entries in that column , along with the knowledge that
, gives that .
Now, to finish, the third row's leading entry is in the fourth column and the
equation of entries in that column , along with and
, gives an impossibility.
The following result shows that this effect always holds.
It shows that what Gauss' linear elimination method eliminates is linear
relationships among the rows.
- Lemma 2.5
In an echelon form matrix,
no nonzero row is a linear combination of the other rows.
Let be in echelon form.
Suppose, to obtain a contradiction, that some nonzero row is a linear
combination of the others.
We will first use induction to show that the coefficients
, ..., associated with rows above are all zero.
The contradiction will come from consideration of and the rows below
The base step of the induction argument
is to show that the first coefficient is zero.
Let the first row's leading entry be in column number
and consider the equation of entries in that column.
The matrix is in echelon form so the entries
, ..., , including
, are all zero.
Because the entry is nonzero as it leads its row,
the coefficient must be zero.
The inductive step is to show that
for each row index between and ,
if the coefficient and the
coefficients , ..., are all zero
then is also zero.
and the contradiction that finishes this proof, is saved for
We can now prove that each matrix is row equivalent to one and only one
reduced echelon form matrix.
We will find it convenient to break the first half of the argument off as a
For one thing, it holds for any echelon form whatever, not just
reduced echelon form.
- Lemma 2.6
If two echelon form matrices are row equivalent then the leading entries in
their first rows lie in the same column.
The same is true of all the nonzero rows— the leading entries in their
second rows lie in the same column, etc.
For the proof we rephrase the result in more technical terms.
Define the form
of an matrix to be the sequence
where is the column number of the leading entry in row
and if there is no leading entry in that row.
The lemma says that if two echelon form matrices are row equivalent
then their forms are equal sequences.
Let and be echelon form matrices that are row equivalent.
Because they are row equivalent they must be the same size, say
Let the column number of the leading entry in row of be and
let the column number of the leading entry in row of be .
We will show that , that , etc., by induction.
This induction argument relies on the fact that the matrices are row
equivalent, because the Linear Combination Lemma and its corollary therefore
give that each row of is a linear combination of the rows of
and vice versa:
where the 's and 's are scalars.
The base step of the induction is to verify the lemma for the
first rows of the matrices, that is, to verify that .
If either row is a zero row then the entire matrix is a zero matrix since it
is in echelon form, and therefore both matrices are zero matrices
(by Corollary 2.3), and so both
and are .
For the case where neither nor is a zero row,
consider the instance of the linear relationship above.
First, note that is impossible: in the columns of to the left
of column the entries are all zeroes
(as leads the first row) and
so if then the equation of entries from column would be
but isn't zero since it leads its row and so this is
Next, a symmetric argument
shows that also is impossible.
Thus the base case holds.
The inductive step is to show that
if , and
, ..., and , then also
(for in the interval ).
This argument is saved for Problem 12.
That lemma answers two of the questions that we have posed: (i) any
two echelon form versions of a matrix have the same free variables,
and consequently, and (ii) any two echelon form versions have the same number
of free variables.
There is no linear system and no combination of row operations such
that, say, we could solve the system
one way and get and free but solve it
another way and get and free, or solve it one way and get two free
variables while solving it another way yields three.
We finish now by specializing to the case of reduced echelon form matrices.
- Theorem 2.7
Each matrix is row equivalent to a unique reduced echelon form matrix.
Clearly any matrix is row equivalent to at least
one reduced echelon form matrix, via Gauss-Jordan reduction.
For the other half, that any matrix is equivalent to at most one
reduced echelon form matrix, we will show that
if a matrix Gauss-Jordan reduces to each of two others then those
two are equal.
Suppose that a matrix is row equivalent to two reduced echelon form matrices
and , which are therefore row equivalent to each other.
The Linear Combination Lemma and its corollary allow us to
write the rows of one, say , as a linear combination
of the rows of the other
The preliminary result, Lemma 2.6, says that
in the two matrices, the same collection of rows are nonzero.
Thus, if through are the nonzero rows of then
the nonzero rows of are through .
Zero rows don't contribute to the sum so we can rewrite the relationship
to include just the nonzero rows.
The preliminary result also says that for
each row between and , the leading entries
of the -th row of and appear in the same column,
Rewriting the above relationship to focus on the entries in the
gives this set of equations for up to .
Since is in reduced echelon form,
all of the 's in column are zero except
for , which is .
Thus each equation above simplifies to
But is also in reduced echelon form and so all of the 's
in column are zero
except for , which is .
Therefore, each is zero, except that
, and , ..., and .
We have shown that the only nonzero coefficient
in the linear combination labelled () is , which is .
Because this holds for all nonzero rows, .
We end with a recap.
In Gauss' method we start with a matrix and then
derive a sequence of other matrices.
We defined two matrices to be related if one can be derived from the other.
That relation is an equivalence relation,
called row equivalence, and
so partitions the set of all matrices into row equivalence classes.
(There are infinitely many matrices in the pictured class, but we've only
got room to show two.)
We have proved there is one and only one reduced echelon form matrix in
each row equivalence class.
So the reduced echelon form is a
for row equivalence:
the reduced echelon form matrices are
representatives of the classes.
We can answer questions about the classes by translating them
into questions about the representatives.
- Example 2.8
We can decide if matrices are interreducible
by seeing if Gauss-Jordan reduction produces the same
reduced echelon form result.
Thus, these are not row equivalent
because their reduced echelon forms are not equal.
- Example 2.9
Any nonsingular matrix Gauss-Jordan reduces to this.
- Example 2.10
We can describe the classes by listing all possible
reduced echelon form matrices.
Any matrix lies in one of these: the class of matrices
row equivalent to this,
the infinitely many classes of matrices row equivalent to one of this type
where (including ),
the class of matrices row equivalent to this,
and the class of matrices row equivalent to this
(this is the class of nonsingular matrices).