1. Not finding help here? Sign up for a free 30min 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!

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]

    Proof:

    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

    AKG

    User Avatar
    Science Advisor
    Homework Helper

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

    0rthodontist

    User Avatar
    Science Advisor

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

    Galileo

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Lin Alg - Matrix multiplication (Proof by contrapositive)
  1. Lin Alg proof problem (Replies: 1)

  2. Lin. Alg. Invertility (Replies: 1)

Loading...