5

I'm trying to prove that if the systems $AX = 0$ and $BX=0$ are equivalent, then the matrices $A$ and $B$ are row equivalent. Proving the converse was very simple, but this one seems harder. I saw a few answers to similar questions posted here before, but they were done using some higher level concepts which I am unaware of right now (such as orthogonal subspaces etc.). I am familiar with the concepts of linear equations, ranks of matrices, and the basic idea of subspaces(only, definition, dimension, basis etc.)

Any help would be appreciated.........

Quark
  • 1,021

2 Answers2

2

If $X$ is an unknown vector, and so "$AX=0$ and $BX=0$ are equivalent" means a vector is annihilated by $A$ if and only if it is annihilated by $B$, then this whole statement holds if and only if the row spaces of $A$ and $B$ are the same (because $AX=0$ implies that $RX=0$ for every row$~R$ in the row space of $A$, and is in fact equivalenet to that). I suppose the latter is what you mean by "$A$ and $B$ are row equivalent", in which case the answer to your question is affirmative.

On the other hand maybe you mean by $A$ and $B$ are row equivalent then one can be transformed into the other by elementary row operations, and this probably (depending on what operations are allowed precisely) would force $A$ and $B$ to have the same number of rows; that is not implied by "$AX=0$ and $BX=0$ are equivalent".

So with row equivalence defined via elementary transformations that cannot change the number of rows, the statement you are trying to prove strictly speaking does not hold. The obstruction is somewhat trivial though, so one could change the question either by adding adding/removing zero rows to a matrix as additional "elementary operations" in the definition of row equivalence, or add the hypothesis that $A$ and $B$ have the same number of rows to your statement (that they have the same number of columns is implicit in $AX$ and $BX$ both being defined). Then it really amounts to showing that when $A$ and $B$ have equal row spaces they are row equivalent. This is a fairly technical statement, for the proof of which I have little more to suggest than what is indicated here, namely to show that (1)$~$elementary row operations do not change the row space, (2)$~$every matrix is row equivalent to a reduced row echelon matrix, and (3)$~$ two reduced row echelon matrices with the same row space are equal. Point (1) is easy and is more or less what you already proved; points (2) and (3) both require a certain amount of work (though not many original ideas).

Marc van Leeuwen
  • 115,048
  • By row equivalence, I mean matrix A can be transformed to B via elementary row operations. Yes, I'm very sorry, I forgot to mention, A and B are matrices of the same order (mxn) – Quark Aug 26 '13 at 16:02
  • In the first paragraph, the statements (1): "the row spaces are the same" and (2): "the two matrices are row equivalent" do not have the same meaning. (1) is a statement about the solution sets, while (2) is a statement about equivalence under a sequence of tranforms applied to the matrices. Your answer actually doesn't prove that (1) and (2) are equivalent, although they are. – coffeemath Aug 26 '13 at 16:47
  • @coffeemath: Then see my second paragraph. From WP: "In linear algebra, two matrices are row equivalent if one can be changed to the other by a sequence of elementary row operations. Alternatively, two $m\times n$ matrices are row equivalent if and only if they have the same row space." Which confirms my doubt about ambiguity of the definition of the term. But the question does not state that $A$ and $B$ have the same number of rows. – Marc van Leeuwen Aug 26 '13 at 17:06
  • The equivalence is mentioned in the WP link you cite in your last comment. But it still has to be shown. I haven't persued the link to see if they give a proof on that page. But the equivalence of the two is not "by definition". What I think is meant is only that one can use the two interchangeably since it is a theorem they are equivalent. That equivalence theorem needs a proof. [Just checked again WP, and they give a sketch of the fact via row reduced forms.] – coffeemath Aug 26 '13 at 17:23
  • I agree with coffeemath, your solution reduces the question to proving the fact that two mxn matrices are row equivalent if and only if they have equal row spaces – Quark Aug 26 '13 at 17:27
0

If $A$ and $B$ share the same nullspace, then by the rank nullity theorem, they have the same row rank and column rank. This allows us to find a special isomorphism between the two.

Pick a set $\{x_1\dots x_k\}$ such that $\{Bx_i\mid 1\leq i\leq k\}$ is a basis for the columnspace of $B$.

Exercise: prove that the set $\{Ax_i\mid 1\leq i\leq k\}$ is also linearly independent, so that it is a basis for the columnspace of $A$. Now we can complement the $x_i$ we already have by picking $x_{i+1},\dots x_n$ to be a basis for the nullspace of $A$ and $B$, and then $x_1,\dots, x_n$ is a basis for the entire domain $F^n$.

By the mapping property of bases, there exists a unique transformation that sends $Bx_i\mapsto Ax_i$ for all $i\in \{1,\dots,k\}$, and it can be expressed as a nonsingular square matrix $C$, and we have that $CBx_i=Ax_i$. For the $i> k$, $CBx_i=0=Bx_i=Ax_i$. Since $CB$ and $A$ match on a basis, they are actually identical transformations from $F^n\to F^m$.

This shows that $A$ and $B$ are row equivalent, via the nonsingular matrix $C$.

The following example shows that it's important that the entire kernel matches, and not just part:

$X=\begin{bmatrix}0\\0\\1\end{bmatrix}$

$A=\begin{bmatrix}1&0&0\\0&0&0\\0&0&0\end{bmatrix}$

$B=\begin{bmatrix}0&1&0\\0&0&0\\0&0&0\end{bmatrix}$

rschwieb
  • 153,510
  • Here the equation $AX=0$ has general solution $x=0$ while $AY=0$ has general solution $y=0$, if $X=(x,y,z)^t$ is a column vector for the solutions. So these two systems are not equivalent, even though they do have as you note the particular point $(0,0,1)^t$ as a common solution. – coffeemath Aug 26 '13 at 15:21
  • rschweib: I was only guessing that equivalent systems means same solution set. I haven't seen that term used for that either, and have noted to OP to clear up the meaning. – coffeemath Aug 26 '13 at 15:26