Linear Algebra/Row Equivalence/Solutions

Solutions

This exercise is recommended for all readers.

Problem 1

Decide if the matrices are row equivalent.

1. ${\begin{pmatrix}1&2\\4&8\end{pmatrix}},{\begin{pmatrix}0&1\\1&2\end{pmatrix}}$
2. ${\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}}$
3. ${\begin{pmatrix}2&1&-1\\1&1&0\\4&3&-1\end{pmatrix}},{\begin{pmatrix}1&0&2\\0&2&10\\\end{pmatrix}}$
4. ${\begin{pmatrix}1&1&1\\-1&2&2\end{pmatrix}},{\begin{pmatrix}0&3&-1\\2&2&5\end{pmatrix}}$
5. ${\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.

1. 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.
2. 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.
3. These two are not row equivalent because they have different sizes.
4. 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.
5. 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.

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

Answer

1. They have the form

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

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

   ${\begin{pmatrix}1a&2a\\1b&2b\end{pmatrix}}$

3. 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?

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

Answer

1. A row operation on a zero matrix has no effect. Thus each zero matrix is alone in its row equivalence class.
2. 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.

1. $2\!\times \!2$ matrices
2. $2\!\times \!3$ matrices
3. $3\!\times \!2$ matrices
4. $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

1. 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.)
2. Use that to simplify the proof of Lemma 2.5.

Answer

1. 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}$.
2. 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.

1. First illustrate the inductive step by showing that $c_{2}=0$.
2. 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.
3. Find the contradiction.

Answer

1. 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$.
2. 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$.
3. 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.

1. State the inductive hypothesis, Also state what must be shown to follow from that hypothesis.
2. 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.
3. 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

1. 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$).
2. 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 $\beta _{r+1}$ has a zero in entry $\ell _{1}$ (the matrix $B$ is in echelon form). But the row $\delta _{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.)
3. 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 $\delta _{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 $4s+c+10d=8.45$ and that $3s+c+7d=6.30$, and we'd like to know what $s+c+d$ is. Fortunately, $s+c+d$ is a linear combination of $4s+c+10d$ and $3s+c+7d$. 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.

1. Produce an equation not implied by this system.

   ${\begin{array}{*{2}{rc}r}3x&+&4y&=&8\\2x&+&y&=&3\end{array}}$

2. Can any equation be derived from an inconsistent system?

Answer

1. 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., $5x+5y=3$.
2. Every equation can be derived from an inconsistent system. For instance, here is how to derive "$3x+2y=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=2y$. Ditto for $0=4$. But now, $0+0=0$ gives $3x+2y=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.

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

Answer

1. The three possible row swaps are easy, as are the three possible rescalings. One of the six possible pivots is $k\rho _{1}+\rho _{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.
2. The obvious conjecture is that row operations do not change linear relationships among columns.
3. A case-by-case proof follows the sketch given in the first item.

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