Linear Algebra/Row Equivalence

From Wikibooks, the open-content textbooks collection

Current revision (unreviewed)

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.

Definition 2.1

A linear combination of $x_1,\ldots,x_m$ is an expression of the form $c_1x_1+c_2x_2+\,\cdots\,+c_mx_m$ where the $c$ '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.

Proof

Given the linear combinations $c_{1,1}x_1+\dots+c_{1,n}x_n$ through $c_{m,1}x_1+\dots+c_{m,n}x_n$ , consider a combination of those

$d_1(c_{1,1}x_1+\dots+c_{1,n}x_n)\,+\dots+\,d_m(c_{m,1}x_1+\dots+c_{m,n}x_n)$

where the $d$ 's are scalars along with the $c$ 's. Distributing those $d$ 's and regrouping gives

$=(d_1c_{1,1}+\dots+d_mc_{m,1})x_1\,+\dots+\,(d_1c_{1,n}+\dots+d_mc_{m,n})x_n$

which is a linear combination of the $x$ '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.

$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}$

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 " $General = Particular + 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.

Proof

We proceed by induction on the minimum number of row operations that take a first matrix $A$ to a second one $B$ .

In the base step, that zero reduction operations suffice, the two matrices are equal and each row of $B$ is obviously a combination of $A$ 's rows: $\vec{\beta}_i =0\cdot\vec{\alpha}_1+\dots+1\cdot\vec{\alpha}_i+\dots+0\cdot\vec{\alpha}_m$ .

For the inductive step, assume the inductive hypothesis: with $t\geq 0$ , if a matrix can be derived from $A$ in $t$ or fewer operations then its rows are linear combinations of the $A$ 's rows. Consider a $B$ that takes $t + 1$ operations. Because there are more than zero operations, there must be a next-to-last matrix $G$ so that $A\longrightarrow\cdots\longrightarrow G\longrightarrow B$ . This $G$ is only $t$ operations away from $A$ and so the inductive hypothesis applies to it, that is, each row of $G$ is a linear combination of the rows of $A$ .

If the last operation, the one from $G$ to $B$ , is a row swap then the rows of $B$ are just the rows of $G$ reordered and thus each row of $B$ is also a linear combination of the rows of $A$ . 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 $B$ being linear combinations of the rows of $G$ . But therefore, by the Linear Combination Lemma, each row of $B$ is a linear combination of the rows of $A$ .

With that, we have both the base step and the inductive step, and so the proposition follows.

Example 2.4

In the reduction

$\begin{pmatrix} 0 &2 \\ 1 &1 \end{pmatrix} \xrightarrow[]{\rho_1\leftrightarrow\rho_2} \begin{pmatrix} 1 &1 \\ 0 &2 \end{pmatrix} \xrightarrow[]{(1/2)\rho_2} \begin{pmatrix} 1 &1 \\ 0 &1 \end{pmatrix} \xrightarrow[]{-\rho_2+\rho_1} \begin{pmatrix} 1 &0 \\ 0 &1 \end{pmatrix}$

call the matrices $A$ , $D$ , $G$ , and $B$ . The methods of the proof show that there are three sets of linear relationships.

$\begin{align} \delta_1 &=0\cdot\alpha_1+1\cdot\alpha_2 \\ \delta_2 &=1\cdot\alpha_1+0\cdot\alpha_2 \end{align} \qquad \begin{align} \gamma_1 &=0\cdot\alpha_1+1\cdot\alpha_2 \\ \gamma_2 &=(1/2)\alpha_1+0\cdot\alpha_2 \end{align} \qquad \begin{align} \beta_1 &=(-1/2)\alpha_1+1\cdot\alpha_2 \\ \beta_2 &=(1/2)\alpha_1+0\cdot\alpha_2 \end{align}$

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 = 2 c 1 + 0 c 2 + 0 c 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 = 7 c 1 + 1 c 2 + 0 c 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 = 8 c 1 + 5 c 2 + 0 c 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.

Lemma 2.5

In an echelon form matrix, no nonzero row is a linear combination of the other rows.

Proof

Let $R$ be in echelon form. Suppose, to obtain a contradiction, that some nonzero row is a linear combination of the others.

$\rho_i=c_1\rho_1+\ldots+c_{i-1}\rho_{i-1}+ c_{i+1}\rho_{i+1}+\ldots+c_m\rho_m$

We will first use induction to show that the coefficients $c 1$ , ..., $c i - 1$ associated with rows above $ρ i$ are all zero. The contradiction will come from consideration of $ρ i$ and the rows below it.

The base step of the induction argument is to show that the first coefficient $c 1$ is zero. Let the first row's leading entry be in column number $\ell_1$ and consider the equation of entries in that column.

$\rho_{i,\ell_1}=c_1\rho_{1,\ell_1}+\ldots+c_{i-1}\rho_{i-1,\ell_1} +c_{i+1}\rho_{i+1,\ell_1}+\ldots+c_m\rho_{m,\ell_1}$

The matrix is in echelon form so the entries $\rho_{2,\ell_1}$ , ..., $\rho_{m,\ell_1}$ , including $\rho_{i,\ell_1}$ , are all zero.

$0=c_1\rho_{1,\ell_1}+\dots+c_{i-1}\cdot 0 +c_{i+1}\cdot 0+\dots+c_m\cdot 0$

Because the entry $\rho_{1,\ell_1}$ is nonzero as it leads its row, the coefficient $c 1$ must be zero.

The inductive step is to show that for each row index $k$ between $1$ and $i - 2$ , if the coefficient $c 1$ and the coefficients $c 2$ , ..., $c k$ are all zero then $c k + 1$ is also zero. That argument, and the contradiction that finishes this proof, is saved for Problem 11.

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.

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 $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.

Proof

Let $B$ and $D$ be echelon form matrices that are row equivalent. Because they are row equivalent they must be the same size, say $m \! \times \! n$ . Let the column number of the leading entry in row $i$ of $B$ be $\ell_i$ and let the column number of the leading entry in row $j$ of $D$ be $k j$ . We will show that $\ell_1=k_1$ , that $\ell_2=k_2$ , 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 $B$ is a linear combination of the rows of $D$ and vice versa:

$\beta_i=s_{i,1}\delta_1+s_{i,2}\delta_2+\dots+s_{i,m}\delta_m \quad\text{and}\quad \delta_j=t_{j,1}\beta_1+t_{j,2}\beta_2+\dots+t_{j,m}\beta_m$

where the $s$ 's and $t$ '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 $\ell_1=k_1$ . 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 $\ell_1$ and $k 1$ are $\infty$ . For the case where neither $β 1$ nor $δ 1$ is a zero row, consider the $i = 1$ instance of the linear relationship above.

$\begin{array}{rl} \beta_1 &=s_{1,1}\delta_1+s_{1,2}\delta_2+\dots+s_{1,m}\delta_m \\ \begin{pmatrix} 0 &\cdots &b_{1,\ell_1} &\cdots & \end{pmatrix} &=s_{1,1}\begin{pmatrix} 0 &\cdots &d_{1,k_1} &\cdots & \end{pmatrix} \\ &\quad+s_{1,2}\begin{pmatrix} 0 &\cdots &0 &\cdots & \end{pmatrix} \\ &\quad \vdots \\ &\quad+s_{1,m}\begin{pmatrix} 0 &\cdots &0 &\cdots & \end{pmatrix} \end{array}$

First, note that $\ell_1<k_1$ is impossible: in the columns of $D$ to the left of column $k 1$ the entries are all zeroes (as $d_{1,k_1}$ leads the first row) and so if $\ell_1<k_1$ then the equation of entries from column $\ell_1$ would be $b_{1,\ell_1}=s_{1,1}\cdot 0+\dots+s_{1,m}\cdot 0$ , but $b_{1,\ell_1}$ isn't zero since it leads its row and so this is an impossibility. Next, a symmetric argument shows that $k_1<\ell_1$ also is impossible. Thus the $\ell_1=k_1$ base case holds.

The inductive step is to show that if $\ell_1=k_1$ , and $\ell_2=k_2$ , ..., and $\ell_r=k_r$ , then also $\ell_{r+1}=k_{r+1}$ (for $r$ in the interval $1\,..\,m-1$ ). 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 $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.

Theorem 2.7

Each matrix is row equivalent to a unique reduced echelon form matrix.

Proof

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 $B$ and $D$ , which are therefore row equivalent to each other. The Linear Combination Lemma and its corollary allow us to write the rows of one, say $B$ , as a linear combination of the rows of the other $\beta_i=c_{i,1}\delta_1+\cdots+c_{i,m}\delta_m$ . The preliminary result, Lemma 2.6, says that in the two matrices, the same collection of rows are nonzero. Thus, if $β 1$ through $β r$ are the nonzero rows of $B$ then the nonzero rows of $D$ are $δ 1$ through $δ r$ . Zero rows don't contribute to the sum so we can rewrite the relationship to include just the nonzero rows.

$\beta_i =c_{i,1}\delta_1+\dots+c_{i,r}\delta_r \qquad(*)$

The preliminary result also says that for each row $j$ between $1$ and $r$ , the leading entries of the $j$ -th row of $B$ and $D$ appear in the same column, denoted $\ell_j$ . Rewriting the above relationship to focus on the entries in the $\ell_j$ -th column

$\begin{array}{rl} \begin{pmatrix} &\cdots &b_{i,\ell_j} &\cdots & \end{pmatrix} &=c_{i,1}\begin{pmatrix} &\cdots &d_{1,\ell_j} &\cdots & \end{pmatrix} \\ &\quad+c_{i,2}\begin{pmatrix} &\cdots &d_{2,\ell_j} &\cdots & \end{pmatrix} \\ &\quad\vdots \\ &\quad+c_{i,r}\begin{pmatrix} &\cdots &d_{r,\ell_j} &\cdots & \end{pmatrix} \end{array}$

gives this set of equations for $i = 1$ up to $i = r$ .

$\begin{array}{rl} b_{1,\ell_j} &=c_{1,1}d_{1,\ell_j} +\cdots+c_{1,j}d_{j,\ell_j}+\cdots +c_{1,r}d_{r,\ell_j} \\ &\vdots \\ b_{j,\ell_j} &=c_{j,1}d_{1,\ell_j} +\cdots+c_{j,j}d_{j,\ell_j}+\cdots +c_{j,r}d_{r,\ell_j} \\ &\vdots \\ b_{r,\ell_j} &=c_{r,1}d_{1,\ell_j} +\cdots+c_{r,j}d_{j,\ell_j}+\cdots +c_{r,r}d_{r,\ell_j} \end{array}$

Since $D$ is in reduced echelon form, all of the $d$ 's in column $\ell_j$ are zero except for $d_{j,\ell_j}$ , which is $1$ . Thus each equation above simplifies to $b_{i,\ell_j}=c_{i,j}d_{j,\ell_j}=c_{i,j}\cdot 1$ . But $B$ is also in reduced echelon form and so all of the $b$ 's in column $\ell_j$ are zero except for $b_{j,\ell_j}$ , which is $1$ . Therefore, each $c i, j$ is zero, except that $c 1,1 = 1$ , and $c 2,2 = 1$ , ..., and $c r, r = 1$ .

We have shown that the only nonzero coefficient in the linear combination labelled ( $*$ ) is $c j, j$ , which is $1$ . Therefore $β j = δ j$ . Because this holds for all nonzero rows, $B = D$ .

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 canonical form^[2] 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

$\begin{pmatrix} 1 &-3 \\ -2 &6 \end{pmatrix} \qquad \begin{pmatrix} 1 &-3 \\ -2 &5 \end{pmatrix}$

because their reduced echelon forms are not equal.

$\begin{pmatrix} 1 &-3 \\ 0 &0 \end{pmatrix} \qquad \begin{pmatrix} 1 &0 \\ 0 &1 \end{pmatrix}$

Example 2.9

Any nonsingular $3 \! \times \! 3$ matrix Gauss-Jordan reduces to this.

$\begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{pmatrix}$

Example 2.10

We can describe the classes by listing all possible reduced echelon form matrices. Any $2 \! \times \! 2$ matrix lies in one of these: the class of matrices row equivalent to this,

$\begin{pmatrix} 0 &0 \\ 0 &0 \end{pmatrix}$

the infinitely many classes of matrices row equivalent to one of this type

$\begin{pmatrix} 1 &a \\ 0 &0 \end{pmatrix}$

where $a\in\mathbb{R}$ (including $a = 0$ ), the class of matrices row equivalent to this,

$\begin{pmatrix} 0 &1 \\ 0 &0 \end{pmatrix}$

and the class of matrices row equivalent to this

$\begin{pmatrix} 1 &0 \\ 0 &1 \end{pmatrix}$

(this is the class of nonsingular $2 \! \times \! 2$ matrices).

[edit] Exercises

This exercise is recommended for all readers.

Problem 1

Decide if the matrices are row equivalent.

$\begin{pmatrix} 1 &2 \\ 4 &8 \end{pmatrix}, \begin{pmatrix} 0 &1 \\ 1 &2 \end{pmatrix}$
$\begin{pmatrix} 1 &0 &2 \\ 3 &-1 &1 \\ 5 &-1 &5 \end{pmatrix}, \begin{pmatrix} 1 &0 &2 \\ 0 &2 &10 \\ 2 &0 &4 \end{pmatrix}$
$\begin{pmatrix} 2 &1 &-1 \\ 1 &1 &0 \\ 4 &3 &-1 \end{pmatrix}, \begin{pmatrix} 1 &0 &2 \\ 0 &2 &10 \\ \end{pmatrix}$
$\begin{pmatrix} 1 &1 &1 \\ -1 &2 &2 \end{pmatrix}, \begin{pmatrix} 0 &3 &-1 \\ 2 &2 &5 \end{pmatrix}$
$\begin{pmatrix} 1 &1 &1 \\ 0 &0 &3 \end{pmatrix}, \begin{pmatrix} 0 &1 &2 \\ 1 &-1 &1 \end{pmatrix}$

Answer

Bring each to reduced echelon form and compare.

The first gives

$\xrightarrow[]{-4\rho_1+\rho_2} \begin{pmatrix} 1 &2 \\ 0 &0 \end{pmatrix}$

while the second gives

$\xrightarrow[]{\rho_1\leftrightarrow\rho_2} \begin{pmatrix} 1 &2 \\ 0 &1 \end{pmatrix} \xrightarrow[]{-2\rho_2+\rho_1} \begin{pmatrix} 1 &0 \\ 0 &1 \end{pmatrix}$

The two reduced echelon form matrices are not identical, and so the original matrices are not row equivalent.
The first is this.

$\xrightarrow[-5\rho_1+\rho_3]{-3\rho_1+\rho_2} \begin{pmatrix} 1 &0 &2 \\ 0 &-1 &-5 \\ 0 &-1 &-5 \end{pmatrix} \xrightarrow[]{-\rho_2+\rho_3} \begin{pmatrix} 1 &0 &2 \\ 0 &-1 &-5 \\ 0 &0 &0 \end{pmatrix} \xrightarrow[]{-\rho_2} \begin{pmatrix} 1 &0 &2 \\ 0 &1 &5 \\ 0 &0 &0 \end{pmatrix}$

The second is this.

$\xrightarrow[]{-2\rho_1+\rho_3} \begin{pmatrix} 1 &0 &2 \\ 0 &2 &10 \\ 0 &0 &0 \end{pmatrix} \xrightarrow[]{(1/2)\rho_2} \begin{pmatrix} 1 &0 &2 \\ 0 &1 &5 \\ 0 &0 &0 \end{pmatrix}$

These two are row equivalent.
These two are not row equivalent because they have different sizes.
The first,

$\xrightarrow[]{\rho_1+\rho_2} \begin{pmatrix} 1 &1 &1 \\ 0 &3 &3 \end{pmatrix} \xrightarrow[]{(1/3)\rho_2} \begin{pmatrix} 1 &1 &1 \\ 0 &1 &1 \end{pmatrix} \xrightarrow[]{-\rho_2+\rho_1} \begin{pmatrix} 1 &0 &0 \\ 0 &1 &1 \end{pmatrix}$

and the second.

$\xrightarrow[]{\rho_1\leftrightarrow\rho_2} \begin{pmatrix} 2 &2 &5 \\ 0 &3 &-1 \end{pmatrix} \xrightarrow[(1/3)\rho_2]{(1/2)\rho_1} \begin{pmatrix} 1 &1 &5/2 \\ 0 &1 &-1/3 \end{pmatrix} \xrightarrow[]{-\rho_2+\rho_1} \begin{pmatrix} 1 &0 &17/6 \\ 0 &1 &-1/3 \end{pmatrix}$

These are not row equivalent.
Here the first is

$\xrightarrow[]{(1/3)\rho_2} \begin{pmatrix} 1 &1 &1 \\ 0 &0 &1 \end{pmatrix} \xrightarrow[]{-\rho_2+\rho_1} \begin{pmatrix} 1 &1 &0 \\ 0 &0 &1 \end{pmatrix}$

while this is the second.

$\xrightarrow[]{\rho_1\leftrightarrow\rho_2} \begin{pmatrix} 1 &-1 &1 \\ 0 &1 &2 \end{pmatrix} \xrightarrow[]{\rho_2+\rho_1} \begin{pmatrix} 1 &0 &3 \\ 0 &1 &2 \end{pmatrix}$

These are not row equivalent.

Problem 2

Describe the matrices in each of the classes represented in Example 2.10.

Answer

First, the only matrix row equivalent to the matrix of all $0$ 's is itself (since row operations have no effect).

Second, the matrices that reduce to

$\begin{pmatrix} 1 &a \\ 0 &0 \end{pmatrix}$

have the form

$\begin{pmatrix} b &ba \\ c &ca \end{pmatrix}$

(where $a,b,c\in\mathbb{R}$ , and $b$ and $c$ are not both zero).

Next, the matrices that reduce to

$\begin{pmatrix} 0 &1 \\ 0 &0 \end{pmatrix}$

have the form

$\begin{pmatrix} 0 &a \\ 0 &b \end{pmatrix}$

(where $a,b\in\mathbb{R}$ , and not both are zero).

Finally, the matrices that reduce to

$\begin{pmatrix} 1 &0 \\ 0 &1 \end{pmatrix}$

are the nonsingular matrices. That's because a linear system for which this is the matrix of coefficients will have a unique solution, and that is the definition of nonsingular. (Another way to say the same thing is to say that they fall into none of the above classes.)

Problem 3

Describe all matrices in the row equivalence class of these.

$\begin{pmatrix} 1 &0 \\ 0 &0 \end{pmatrix}$
$\begin{pmatrix} 1 &2 \\ 2 &4 \end{pmatrix}$
$\begin{pmatrix} 1 &1 \\ 1 &3 \end{pmatrix}$

Answer

They have the form

$\begin{pmatrix} a &0 \\ b &0 \end{pmatrix}$

where $a,b\in\mathbb{R}$ .
They have this form (for $a,b\in\mathbb{R}$ ).

$\begin{pmatrix} 1a &2a \\ 1b &2b \end{pmatrix}$
They have the form

$\begin{pmatrix} a &b \\ c &d \end{pmatrix}$

(for $a,b,c,d\in\mathbb{R}$ ) where $ad-bc\neq 0$ . (This is the formula that determines when a $2 \! \times \! 2$ matrix is nonsingular.)

Problem 4

How many row equivalence classes are there?

Answer

Infinitely many. For instance, in

$\begin{pmatrix} 1 &k \\ 0 &0 \end{pmatrix}$

each $k\in\mathbb{R}$ gives a different class.

Problem 5

Can row equivalence classes contain different-sized matrices?

Answer

No. Row operations do not change the size of a matrix.

Problem 6

How big are the row equivalence classes?

Show that the class of any zero matrix is finite.
Do any other classes contain only finitely many members?

Answer

A row operation on a zero matrix has no effect. Thus each zero matrix is alone in its row equivalence class.
No. Any nonzero entry can be rescaled.

This exercise is recommended for all readers.

Problem 7

Give two reduced echelon form matrices that have their leading entries in the same columns, but that are not row equivalent.

Answer

Here are two.

$\begin{pmatrix} 1 &1 &0 \\ 0 &0 &1 \end{pmatrix} \quad\text{and}\quad \begin{pmatrix} 1 &0 &0 \\ 0 &0 &1 \end{pmatrix}$

This exercise is recommended for all readers.

Problem 8

Show that any two $n \! \times \! n$ nonsingular matrices are row equivalent. Are any two singular matrices row equivalent?

Answer

Any two $n \! \times \! n$ nonsingular matrices have the same reduced echelon form, namely the matrix with all $0$ 's except for $1$ 's down the diagonal.

$\begin{pmatrix} 1 &0 & &0 \\ 0 &1 & &0 \\ & &\ddots & \\ 0 &0 & &1 \end{pmatrix}$

Two same-sized singular matrices need not be row equivalent. For example, these two $2 \! \times \! 2$ singular matrices are not row equivalent.

$\begin{pmatrix} 1 &1 \\ 0 &0 \end{pmatrix} \quad\text{and}\quad \begin{pmatrix} 1 &0 \\ 0 &0 \end{pmatrix}$

This exercise is recommended for all readers.

Problem 9

Describe all of the row equivalence classes containing these.

$2 \! \times \! 2$ matrices
$2 \! \times \! 3$ matrices
$3 \! \times \! 2$ matrices
$3 \! \times \! 3$ matrices

Answer

Since there is one and only one reduced echelon form matrix in each class, we can just list the possible reduced echelon form matrices.

For that list, see the answer for Problem 1.5.

Problem 10

Show that a vector $\vec{\beta}_0$ is a linear combination of members of the set $\{\vec{\beta}_1,\ldots,\vec{\beta}_n\}$ if and only if there is a linear relationship $\vec{0}=c_0\vec{\beta}_0+\cdots+c_n\vec{\beta}_n$ where $c 0$ is not zero. (Hint. Watch out for the $\vec{\beta}_0=\vec{0}$ case.)
Use that to simplify the proof of Lemma 2.5.

Answer

If there is a linear relationship where $c 0$ is not zero then we can subtract $c_0\vec{\beta}_0$ from both sides and divide by $- c 0$ to get $\vec{\beta}_0$ as a linear combination of the others. (Remark: if there are no other vectors in the set— if the relationship is, say, $\vec{0}=3\cdot\vec{0}$ — then the statement is still true because the zero vector is by definition the sum of the empty set of vectors.) Conversely, if $\vec{\beta}_0$ is a combination of the others $\vec{\beta}_0=c_1\vec{\beta}_1+\dots+c_n\vec{\beta}_n$ then subtracting $\vec{\beta}_0$ from both sides gives a relationship where at least one of the coefficients is nonzero; namely, the $- 1$ in front of $\vec{\beta}_0$ .
The first row is not a linear combination of the others for the reason given in the proof: in the equation of components from the column containing the leading entry of the first row, the only nonzero entry is the leading entry from the first row, so its coefficient must be zero. Thus, from the prior part of this exercise, the first row is in no linear relationship with the other rows. Thus, when considering whether the second row can be in a linear relationship with the other rows, we can leave the first row out. But now the argument just applied to the first row will apply to the second row. (That is, we are arguing here by induction.)

This exercise is recommended for all readers.

Problem 11

Finish the proof of Lemma 2.5.

First illustrate the inductive step by showing that $c 2 = 0$ .
Do the full inductive step: where $1\leq n<i-1$ , assume that $c k = 0$ for $1 < k < n$ and deduce that $c n + 1 = 0$ also.
Find the contradiction.

Answer

In the equation

$\rho_i=c_1\rho_1+c_2\rho_2+\ldots+c_{i-1}\rho_{i-1}+ c_{i+1}\rho_{i+1}+\ldots+c_m\rho_m$

we already know that $c 1 = 0$ . Let $\ell_2$ be the column number of the leading entry of the second row. Consider the prior equation on entries in that column.

$\rho_{i,\ell_1}=c_2\rho_{2,\ell_2}+\ldots+c_{i-1}\rho_{i-1,\ell_2} +c_{i+1}\rho_{i+1,\ell_2}+\ldots+c_m\rho_{m,\ell_2}$

Because $\ell_2$ is the column of the leading entry in the second row, $\rho_{i,\ell_2}=0$ for $i > 2$ . Thus the equation reduces to

$0=c_2\rho_{2,\ell_2}+0+\ldots+0$

and since $\rho_{2,\ell_2}$ is not $0$ we have that $c 2 = 0$ .
In the equation

$\rho_i=c_1\rho_1+c_2\rho_2+\ldots+c_{i-1}\rho_{i-1}+ c_{i+1}\rho_{i+1}+\ldots+c_m\rho_m$

we already know that $0=c_1=c_2=\dots =c_n$ . Let $\ell_{n+1}$ be the column number of the leading entry of row $n + 1$ . Consider the above equation on entries in that column.

$\rho_{i,\ell_{n+1}}=c_{n+1}\rho_{n+1,\ell_{n+1}}+\ldots +c_{i-1}\rho_{i-1,\ell_{n+1}} +c_{i+1}\rho_{i+1,\ell_{n+1}} +\dots+c_m\rho_{m,\ell_{n+1}}$

Because $\ell_{n+1}$ is the column of the leading entry in the row $n + 1$ , we have that $\rho_{j,\ell_{n+1}}=0$ for $j > n + 1$ . Thus the equation reduces to

$0=c_{n+1}\rho_{n+1,\ell_{n+1}}+0+\ldots+0$

and since $\rho_{n+1,\ell_{n+1}}$ is not $0$ we have that $c n + 1 = 0$ .
From the prior item in this exercise we know that in the equation

$\rho_i=c_1\rho_1+c_2\rho_2+\ldots+c_{i-1}\rho_{i-1}+ c_{i+1}\rho_{i+1}+\ldots+c_m\rho_m$

we already know that $0=c_1=c_2=\dots =c_{i-1}$ . Let $\ell_{i}$ be the column number of the leading entry of row $i$ . Rewrite the above equation on entries in that column.

$\rho_{i,\ell_{i}}=c_{i+1}\rho_{i+1,\ell_{i}} +\dots+c_m\rho_{m,\ell_{i}}$

Because $\ell_{i}$ is the column of the leading entry in the row $i$ , we have that $\rho_{j,\ell_{i}}=0$ for $j > i$ . That makes the right side of the equation sum to $0$ , but the left side is not $0$ since it is the leading entry of the row. That's the contradiction.

Problem 12

Finish the induction argument in Lemma 2.6.

State the inductive hypothesis, Also state what must be shown to follow from that hypothesis.
Check that the inductive hypothesis implies that in the relationship $\beta_{r+1}=s_{r+1,1}\delta_1+s_{r+2,2}\delta_2 +\dots+s_{r+1,m}\delta_m$ the coefficients $s_{r+1,1},\,\ldots\,,s_{r+1,r}$ are each zero.
Finish the inductive step by arguing, as in the base case, that $\ell_{r+1}<k_{r+1}$ and $k_{r+1}<\ell_{r+1}$ are impossible.

Answer

The inductive step is to show that if the statement holds on rows $1$ through $r$ then it also holds on row $r + 1$ . That is, we assume that $\ell_1=k_1$ , and $\ell_2=k_2$ , ..., and $\ell_r=k_r$ , and we will show that $\ell_{r+1}=k_{r+1}$ also holds (for $r$ in $1\;..\;m-1$ ).
Corollary 2.3 gives the relationship $\beta_{r+1}=s_{r+1,1}\delta_1+s_{r+2,2}\delta_2 +\dots+s_{r+1,m}\delta_m$ between rows. Inside of those row vectors, consider the relationship between the entries in the column $\ell_1=k_1$ . Because by the induction hypothesis this is a row greater than the first $r + 1 > 1$ , the row $β r + 1$ has a zero in entry $\ell_1$ (the matrix $B$ is in echelon form). But the row $δ 1$ has a nonzero entry in column $k 1$ ; by definition of $k 1$ it is the leading entry in the first row of $D$ . Thus, in that column, the above relationship among rows resolves to this equation among numbers: $0=s_{r+1,1}\cdot d_{1,k_1}$ , with $d_{1,k_1}\neq 0$ . Therefore $s r + 1,1 = 0$ . With $s r + 1,1 = 0$ , a similar argument shows that $s r + 1,2 = 0$ . With those two, another turn gives that $s r + 1,3 = 0$ . That is, inside of the larger induction argument used to prove the entire lemma, here is an subargument by induction that shows $s r + 1, j = 0$ for all $j$ in $1\,..\,r$ . (We won't write out the details since it is just like the induction done in Problem 11.)
Note that the prior item of this exercise shows that the relationship between rows $\beta_{r+1}=s_{r+1,1}\delta_1+s_{r+2,2}\delta_2 +\dots+s_{r+1,m}\delta_m$ reduces to $\beta_{r+1}=s_{r+1,r+1}\delta_{r+1}+\dots+s_{r+1,m}\delta_m$ . Consider the column $\ell_{r+1}$ entries in this equation. By definition of $k r + 1$ as the column number of the leading entry of $δ r + 1$ , the entries in this column of the other rows $\delta_{r+2}\;\;\delta_{m}$ are zeros. Now if $\ell_{r+1}<k_{r+1}$ then the equation of entries from column $\ell_{k+1}$ would be $b_{r+1,\ell_{r+1}}=s_{r+1,1}\cdot 0+\dots+s_{r+1,m}\cdot 0$ , which is impossible as $b_{r+1,\ell_{r+1}}$ isn't zero as it leads its row. A symmetric argument shows that $k_{r+1}<\ell_{r+1}$ also is impossible.

Problem 13

Why, in the proof of Theorem 2.7, do we bother to restrict to the nonzero rows? Why not just stick to the relationship that we began with, $\beta_i=c_{i,1}\delta_1+\dots+c_{i,m}\delta_m$ , with $m$ instead of $r$ , and argue using it that the only nonzero coefficient is $c i, i$ , which is $1$ ?

Answer

The zero rows could have nonzero coefficients, and so the statement would not be true.

This exercise is recommended for all readers.

Problem 14

Three truck drivers went into a roadside cafe. One truck driver purchased four sandwiches, a cup of coffee, and ten doughnuts for $ $8.45$ . Another driver purchased three sandwiches, a cup of coffee, and seven doughnuts for $ $6.30$ . What did the third truck driver pay for a sandwich, a cup of coffee, and a doughnut? (Trono 1991)

Answer

We know that $4 s + c + 10 d = 8.45$ and that $3 s + c + 7 d = 6.30$ , and we'd like to know what $s + c + d$ is. Fortunately, $s + c + d$ is a linear combination of $4 s + c + 10 d$ and $3 s + c + 7 d$ . Calling the unknown price $p$ , we have this reduction.

$\left(\begin{array}{*{3}{c}|c} 4 &1 &10 &8.45 \\ 3 &1 &7 &6.30 \\ 1 &1 &1 &p \end{array}\right) \xrightarrow[-(1/4)\rho_1+\rho_3]{-(3/4)\rho_1+\rho_2} \left(\begin{array}{*{3}{c}|c} 4 &1 &10 &8.45 \\ 0 &1/4 &-1/2 &-0.037\,5 \\ 0 &3/4 &-3/2 &p-2.112\,5 \end{array}\right) \xrightarrow[]{-3\rho_2+\rho_3} \left(\begin{array}{*{3}{c}|c} 4 &1 &10 &8.45 \\ 0 &1/4 &-1/2 &-0.037\,5 \\ 0 &0 &0 &p-2.00 \end{array}\right)$

The price paid is $ $2.00$ .

Problem 15

The fact that Gaussian reduction disallows multiplication of a row by zero is needed for the proof of uniqueness of reduced echelon form, or else every matrix would be row equivalent to a matrix of all zeros. Where is it used?

Answer

If multiplication of a row by zero were allowed then Lemma 2.6 would not hold. That is, where

$\begin{pmatrix} 1 &3 \\ 2 &1 \end{pmatrix} \xrightarrow[]{0\rho_2} \begin{pmatrix} 1 &3 \\ 0 &0 \end{pmatrix}$

all the rows of the second matrix can be expressed as linear combinations of the rows of the first, but the converse does not hold. The second row of the first matrix is not a linear combination of the rows of the second matrix.

This exercise is recommended for all readers.

Problem 16

The Linear Combination Lemma says which equations can be gotten from Gaussian reduction from a given linear system.

Produce an equation not implied by this system.

$\begin{array}{*{2}{rc}r} 3x &+ &4y &= &8 \\ 2x &+ & y &= &3 \end{array}$
Can any equation be derived from an inconsistent system?

Answer

An easy answer is this:

$0 = 3.$

For a less wise-guy-ish answer, solve the system:

$\left(\begin{array}{*{2}{c}|c} 3 &-1 &8 \\ 2 &1 &3 \end{array}\right) \xrightarrow[]{-(2/3)\rho_1+\rho_2} \left(\begin{array}{*{2}{c}|c} 3 &-1 &8 \\ 0 &5/3 &-7/3 \end{array}\right)$

gives $y = - 7 / 5$ and $x = 11 / 5$ . Now any equation not satisfied by $( - 7 / 5,11 / 5)$ will do, e.g., $5 x + 5 y = 3$ .
Every equation can be derived from an inconsistent system. For instance, here is how to derive " $3 x + 2 y = 4$ " from " $0 = 5$ ". First,

$0=5 \xrightarrow[]{(3/5)\rho_1} 0=3 \xrightarrow[]{x\rho_1} 0=3x$

(validity of the $x = 0$ case is separate but clear). Similarly, $0 = 2 y$ . Ditto for $0 = 4$ . But now, $0 + 0 = 0$ gives $3 x + 2 y = 4$ .

Problem 17

Extend the definition of row equivalence to linear systems. Under your definition, do equivalent systems have the same solution set? (Hoffman & Kunze 1971)

Answer

Define linear systems to be equivalent if their augmented matrices are row equivalent. The proof that equivalent systems have the same solution set is easy.

This exercise is recommended for all readers.

Problem 18

In this matrix

$\begin{pmatrix} 1 &2 &3 \\ 3 &0 &3 \\ 1 &4 &5 \end{pmatrix}$

the first and second columns add to the third.

Show that remains true under any row operation.
Make a conjecture.
Prove that it holds.

Answer

The three possible row swaps are easy, as are the three possible rescalings. One of the six possible pivots is $k ρ 1 + ρ 2$ :

$\begin{pmatrix} 1 &2 &3 \\ k\cdot 1+3 &k\cdot 2+0 &k\cdot 3+3 \\ 1 &4 &5 \end{pmatrix}$

and again the first and second columns add to the third. The other five pivots are similar.
The obvious conjecture is that row operations do not change linear relationships among columns.
A case-by-case proof follows the sketch given in the first item.

[edit] Footnotes

↑ More information on mathematical induction is in the appendix.
↑ More information on canonical representatives is in the appendix.

[edit] References

Hoffman, Kenneth; Kunze, Ray (1971), Linear Algebra (Second ed.), Prentice Hall
Trono, Tony (compilier) (1991), University of Vermont Mathematics Department High School Prize Examinations 1958-1991, mimeograhed printing

[0] More information on mathematical induction is in the appendix.

[1] More information on canonical representatives is in the appendix.

[1]

[2]

Linear Algebra/Row Equivalence

From Wikibooks, the open-content textbooks collection

[edit] Exercises

[edit] Footnotes

[edit] References

Views

Personal tools

Navigation

Search

community

Print/export

Toolbox