06 Reduced Echelon Form and Row Equivalence
We have used Gauss's Method to solve linear systems of equations. This method uses row operations to put a linear system or matrix into echelon form. [From now on, I will just talk in terms of matrices.] Chapter 1, Section III covers reduced echelon form. In an echelon form matrix, any all-zero row is at the bottom, and for rows that are not all-zero (after the first row), the leading entry in that row lies to the right of the leading entry in the previous row. A reduced echelon form matrix has the additional properties that (1) every leading entry is a 1 and (2) in any column that contains a leading entry, that leading entry is the only non-zero entry in that column.
After a matrix has been put into echelon form, it is easy to apply
additional row operations to put the matrix into reduced echelon form.
Just divide each non-zero row by the leading entry in that row, making
the leading entry equal to one. Then, for any column that contains a
leading entry for row
But the more interesting aspect of Section 1.III is
the definition of row equivalence of matrices,
the proof that row equivalence is an equivalence relation
on the set of all
The really important consequence of all this is that no matter what specific sequence of row operations that you apply to a matrix to put it into reduced echelon form, you will always end up with the same reduced echelon form matrix.
We defined free variables and leading variables for echelon form matrices.
But starting from a matrix,
Finally, there is result stated as a Lemma in Section 1.III.2 that will be important for us later: In an echelon form matrix, a non-zero row cannot be a linear combination of the other non-zero rows. Another way of saying this is that the non-zero rows in an echelon form matrix are linearly independent.
There is some fairly sophisticated mathematics in Section 1.III that will require some work to understand, especially for people who have not taken Math 135.
There is the idea of "equivalence relation" on a set. A relation on a set is
an operation that takes any two elements of the set and tells you whether or
not they are related in the sense defined by that relation. If I say that
An equivalence relation is a type of relation that
breaks up a set into non-empty subsets, where the intersection of any two subsets
is empty. This is called a partition of the set.
All of the elements a given subset are related to each other, and two elements
from different subsets are not related. Given a relation, you can show that
it is an equivalence relation by showing that it has certain properties—reflexive,
symmetric, and transitive—but usually we are most interested in the way
the relation partitions the set. (For the record, a relation
Two matrices
The most difficult theorem we have encountered so far (Theorem 2.6 in Section 1.III.2) says that each of those subsets contains exactly one reduced echelon form matrix. Since two matrices are row equivalent if and only if they are in the same subset, this means that every matrix is row equivalent to one and only one reduced echelon form matrix. Furthermore, two matrices are row equivalent if and only if they reduce to the same reduced echelon form matrix. The proof of the theorem uses proof by mathematical induction.
Proof by induction is actually very natural. It amounts to showing that
something is true for
- Base case: Prove that the statement is true for
. - Inductive case: Prove that whenever the statement is
true for some positive integer
, then it is also true for .
The inductive case takes care of proving all of the infinitely
many individual steps—from 1 to 2, from 2 to 3, from 3 to 4, from 4 to 5, and so on—all
at once. (Sometimes, the induction starts with a base case other than
A typical first example of induction is to prove that
- For
, . ✓ - For
, . ✓ - For
, . ✓ - For
, . ✓ - For
, . ✓
Or I might give a formal proof by induction, which should be easier to understand and absolutely convincing:
Base Case: For
Inductive Case: Suppose that