4
$\begingroup$

Let $A$ and $B$ be $2\times 3$ matrices. For which $A$ and $B$ does the following equation hold?

$$\operatorname{rref}(A)+ \operatorname{rref}(B) = \operatorname{rref}(A+B)$$

($\operatorname{rref}$ is the operation that makes a matrix in reduced row echelon form.)

This problem is from Strang's Introduction to Linear Algebra book, and he says about this problem in the book that, it is silly. I don't know why he said that but I couldn't figure this out for a while. I'd appreciate your help. Thanks from now.

$\endgroup$
3
  • $\begingroup$ Could you add what rref of a matrix is? And what exactly is silly about the problem? $\endgroup$ – Dietrich Burde Dec 23 '20 at 15:49
  • $\begingroup$ Oh, I am sorry. Rref operation makes a matrix echelon form. It is used in some math programs so It somehow stayed in my mind as formal name. I am fixing it $\endgroup$ – Bora Dec 23 '20 at 15:53
  • 1
    $\begingroup$ An example of such a pair of matrices: $$ A = \pmatrix{1&0\\2&0}, \quad B = \pmatrix{0&1\\0&2}. $$ $\endgroup$ – Ben Grossmann Dec 23 '20 at 16:47
1
$\begingroup$

In equational terms, there are elementary matrices $E,F,G$ such that each of the following terms are in rref, $$EA+FB=G(A+B)\tag{1}.$$ The key is that the sum of two rrefs is not usually an rref.

If $A=0$ or $B=0$ then the problem is trivial. So suppose $A,B\ne0$ and suppose wolog that $B$'s first non-zero column is at or to the right of $A$'s.

Facts

  1. The first row operation on $A$ reduces its first non-zero column to $(1,0)^\top$. The same column of $B$ cannot be non-zero as well, for otherwise its first row operation would also reduce it to $(1,0)^\top$ and the sum of both rrefs would have a column of $(2,0)^\top$. Hence $B$'s first non-zero column is after $A$'s; so $A$ can have at most one leading zero column, and $B$ must have a leading zero column.
  2. The first non-zero column of $A+B$ is identical to that of $A$.
  3. The first $(1,0)^\top$ in rref$(A+B)$ occurs at the same column as $A$'s and must be produced by the same row operations as those for $A$.
  4. Any column $v$ of $A$ is reduced to $Ev=(r,0)^\top$ iff $v$ is a multiple $r$ of the first non-zero column of $A$.

Case 1. A second row operation is needed on $A$, by multiplying the second row by a constant to reduce some column to $(0,1)^\top$ and then reduce the component above it to $0$. For the same reason as above, this same column of $B$ must be $(0,0)^\top$. Thus, two columns of $A+B$ agree with those of $A$, and so exactly the same row operations have to be used to reduce $A+B$ to an rref. Thus $E=G$, so $FB=GB=EB$ by (1), which means that the same row operations $E$ can be used on $B$ to reduce it to rref.

Case 2. It can happen that after this one row operation, the result is a rref, i.e., $\begin{pmatrix}1&*&*\\0&0&0\end{pmatrix}$. So all three columns of $A$ are multiples of the first one. This operation also reduces the first column of $A+B$ to $(1,0)^\top$, and it does not affect $B$'s first column. More operations may be needed on $B$ to reduce it to rref, and these are precisely the ones needed to reduce $A+B$ to rref. Thus $G=F$, so $EA=GA=FA$, and once again we can assume $E=F=G$.

Thus in both cases, $E=F=G$. This forces some columns of $B$ to be the same as $A$'s. For example, since $B$ has rref with a $(1,0)^\top$, then that column must be the same as $A$'s first non-zero column (by fact 4.).

Using the facts above, one can see that $B$ must have one or two zero columns, one column that agrees with the first non-zero column of $A$, and possibly a third non-zero column. Here are the five possibilities for $A+B$ and their reduced forms:

\begin{align} \begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\end{pmatrix} +\begin{pmatrix}0&0&a_{11}\\0&0&a_{21}\end{pmatrix}&\stackrel{rref}{\mapsto}\begin{pmatrix}1&0&*\\0&1&*\end{pmatrix}\\ \begin{pmatrix}a_{11}&ca_{11}&a_{13}\\a_{21}&ca_{21}&a_{23}\end{pmatrix} +\begin{pmatrix}0&a_{11}&0\\0&a_{21}&0\end{pmatrix}&\stackrel{rref}{\mapsto}\begin{pmatrix}1&*&0\\0&0&1\end{pmatrix}\\ \begin{pmatrix}a_{11}&ca_{11}&0\\a_{21}&ca_{21}&0\end{pmatrix} +\begin{pmatrix}0&a_{11}&a_{13}\\0&a_{21}&a_{23}\end{pmatrix}&\stackrel{rref}{\mapsto}\begin{pmatrix}1&*&0\\0&0&1\end{pmatrix}\\ \begin{pmatrix}a_{11}&ca_{11}&da_{11}\\a_{21}&ca_{21}&da_{21}\end{pmatrix} +\begin{pmatrix}0&a_{11}&ba_{11}\\0&a_{21}&ba_{21}\end{pmatrix}&\stackrel{rref}{\mapsto}\begin{pmatrix}1&*&*\\0&0&0\end{pmatrix}\\ \begin{pmatrix}0&a_{12}&a_{13}\\0&a_{22}&a_{23}\end{pmatrix} +\begin{pmatrix}0&0&a_{12}\\0&0&a_{22}\end{pmatrix}&\stackrel{rref}{\mapsto}\begin{pmatrix}0&1&*\\0&0&0\end{pmatrix}\\ \end{align} (The third possibility needs a bit more argumentation, which I've skipped.)

Silly? Well, almost an hour writing an answer for what? a silly (+1)...maybe :)

$\endgroup$
2
  • $\begingroup$ Thanks a lot, it makes sense. I wonder ,with small changes, can we find rref(AB) = rref(A+B). But ,frankly, I won't try it because it is too long but not too complicated. Similarly i think such rref problems are long. Nevermind, thanks a lot again. $\endgroup$ – Bora Dec 25 '20 at 16:43
  • $\begingroup$ @Bora $AB$ is not even defined. $\endgroup$ – Chrystomath Dec 26 '20 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.