# Lin Alg - Matrix multiplication (Proof by contrapositive)

1. Mar 1, 2006

### mattmns

Hello, here is the question my book is asking:

Let A, B be two m x n matricies. Assume that AX = BX for all n-tuples X. Show that A = B.
-------

So I decided to try and prove the contrapositive, which is (unless I am mistaken): If $A \neq B$, then there is some X such that $AX \neq BX$

Proof:

Assume $A \neq B$
Then $A^j \neq B^j$ for some j, where $A^j, B^j$ are the j-th columns of A and B.
Then, let $X = E^j$ be the unit vector with 1 in the j-th spot, the same j where $A^j \neq B^j$
So $AX = AE^j = A^j$ and
$BX = BE^j = B^j$
and so $AX \neq BX$ for $X = E^j$ as $A^j \neq B^j$

Thus if $A \neq B$ there is some X such that $AX \neq BX$
So, as the contrapositive is logically equivalent, we have just showed that if AX = BX for all X, then A = B. Where A, B are two m x n matricies, and X is an n-tuple.
------

First, is the contrapositive correct, and if so then is the proof correct. The whole thing looks perfectly sufficient to me. Thanks!!

Also, I just realized that it is very easy to just prove it directly, but I am still curious to see if this is a sufficient proof. Thanks!

2. Mar 1, 2006

### AKG

$$test\pi$$ $$test\pi$$

3. Mar 1, 2006

### 0rthodontist

I would call that sufficient.

4. Mar 2, 2006

### Galileo

The proof is good. Proving directly might be more transparant though. You already noted the crucial $AE^j=A^j$, so if $AX=BX$ for all X, then $A^j=AE^j=BE^j=B^j$ for j=1,2,...,n. So A=B.

5. Mar 2, 2006

### mattmns

Yep, I saw that just as I was posting my proof. Thanks.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook