1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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