Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Lin Alg - Matrix multiplication (Proof by contrapositive)

  1. Mar 1, 2006 #1
    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 [itex]A \neq B[/itex], then there is some X such that [itex]AX \neq BX[/itex]


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

    Thus if [itex]A \neq B[/itex] there is some X such that [itex]AX \neq BX[/itex]
    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. jcsd
  3. Mar 1, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper

    [tex]test\pi[/tex] [tex]$test\pi$[/tex]
  4. Mar 1, 2006 #3


    User Avatar
    Science Advisor

    I would call that sufficient.
  5. Mar 2, 2006 #4


    User Avatar
    Science Advisor
    Homework Helper

    The proof is good. Proving directly might be more transparant though. You already noted the crucial [itex]AE^j=A^j[/itex], so if [itex]AX=BX[/itex] for all X, then [itex]A^j=AE^j=BE^j=B^j[/itex] for j=1,2,...,n. So A=B.
  6. Mar 2, 2006 #5
    Yep, I saw that just as I was posting my proof. Thanks.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook