# Linear Algebra/Row Equivalence

|current=Row Equivalence
|previous=Gauss-Jordan Reduction
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
next chapter.

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.

(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.)

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.

$$A=
\begin{pmatrix}
\cdots \alpha_1 \cdots \\
\cdots \alpha_2 \cdots \\
\vdots                 \\
\cdots \alpha_m \cdots  
\end{pmatrix}
\qquad
B=
\begin{pmatrix}
\cdots \beta_1 \cdots \\
\cdots \beta_2 \cdots \\
\vdots                \\
\cdots \beta_m\cdots 
\end{pmatrix}$$

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
\"$\text{General}=\text{Particular}+\text{Homogeneous}$\" proof).[^1]
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 $t\geq 0$ 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 $t+1$ 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.

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

$$R=\begin{pmatrix}
2  &3  &7  &8  &0  &0  \\
0  &0  &1  &5  &1  &1  \\
0  &0  &0  &3  &3  &0  \\
0  &0  &0  &0  &2  &1
\end{pmatrix}$$

$x_1$ has been removed from $x_5$\'s equation. That is, Gauss\' method
has made $x_5$\'s row independent of $x_1$\'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
$\rho_3\neq c_1\rho_1+c_2\rho_2+c_4\rho_4$. For, suppose that there are
scalars $c_1$, $c_2$, and $c_4$ such that this relationship holds.

$$\begin{array}{rl}
\begin{pmatrix} 0  &0  &0  &3  &3  &0 \end{pmatrix}
&=c_1\begin{pmatrix} 2 &3 &7 &8 &0 &0 \end{pmatrix}             \\
&\quad+c_2\begin{pmatrix} 0 &0 &1 &5 &1 &1 \end{pmatrix} \\
&\quad+c_4\begin{pmatrix} 0 &0 &0 &0 &2 &1 \end{pmatrix}
\end{array}$$

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 $0=2c_1+0c_2+0c_4$ gives that $c_1=0$. The
second row\'s leading entry is in the third column and the equation of
entries in that column $0=7c_1+1c_2+0c_4$, along with the knowledge that
$c_1=0$, gives that $c_2=0$. Now, to finish, the third row\'s leading
entry is in the fourth column and the equation of entries in that column
$3=8c_1+5c_2+0c_4$, along with $c_1=0$ and $c_2=0$, 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.

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 preliminary lemma. For one thing, it
holds for any echelon form whatever, not just reduced echelon form.

For the proof we rephrase the result in more technical terms.
Define the **form** of an
$m \! \times \! n$ matrix to be the sequence
$\langle \ell_1,\ell_2,\ldots\,,\ell_m \rangle$ where $\ell_i$ is the
column number of the leading entry in row $i$ and $\ell_i=\infty$ 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.

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 $y$ and $z$ free but solve it another way and get $y$ and $w$ 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.

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.

```{=html}
<center>
```
![](Linalg_reduced_echelon_form_equiv_classes.png "Linalg_reduced_echelon_form_equiv_classes.png"){width=""
height="200"}

```{=html}
</center>
```
(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
*canonical form*[^2] for row equivalence: the reduced echelon form
matrices are representatives of the classes.

```{=html}
<center>
```
![](Linalg_reduced_echelon_form_equiv_classes_2.png "Linalg_reduced_echelon_form_equiv_classes_2.png"){width=""
height="200"}

```{=html}
</center>
```
We can answer questions about the classes by translating them into
questions about the representatives.

## Exercises


## Footnotes

```{=html}
<references/>
```

## References

-   
-   

[^1]: More information on mathematical induction is in the appendix.

[^2]: More information on canonical representatives is in the appendix.
