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: Linear Algebra Invertibility Proof

  1. Mar 24, 2010 #1
    1. The problem statement, all variables and given/known data

    Let A and B be NxN matrices, and assume that their product C = AB is invertible. Without using determinants, prove that A and B must both be invertible.

    2. Relevant equations

    If a NXN matrix A is invertible:

    Ax = 0 has only the trivial solution 0.

    3. The attempt at a solution

    I believe I have this halfway figured out:

    Let's take B to be singular, then there exists an x that is not 0 such that Bx = 0. Thus:

    C = AB => Cx = (AB)x = A(Bx) = 0.

    C would have to be singular, as there exists an x not equal to 0 that makes Cx = 0. This violates the assumption that C is invertible, thus B must be invertible.

    Now, I am not sure where to go with A. I've tried applying the same logic, however:

    C = AB => Cx = (AB)x = (Ax)B = 0

    does not seem to work. Is there some easy way to prove that if B is invertible then A must be also? If not, how can I alter this logic to prove that A is invertible? Can I somehow use the fact that the product of two invertible matrices must be invertible...and if A is not invertible then C cannot be?
     
  2. jcsd
  3. Mar 24, 2010 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, let's take a step back and do some scratch work. If we already know that A and B are invertible, what can we say about their inverses?
     
  4. Mar 24, 2010 #3
    If A and B are invertible, we know their product must also be invertible. Other than that, I'm not too sure unless you are hinting at something involving elementary matrices.
     
  5. Mar 24, 2010 #4

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    This looks fine so far.

    This is false. In fact, the multiplication on the RHS doesn't even make sense: the dimensions aren't compatible.

    You already showed that [itex]B[/itex] must be invertible. So let's suppose that [itex]B[/itex] is invertible and [itex]A[/itex] is not. Then there exists a [itex]y \neq 0[/itex] such that

    [tex]Ay = 0[/tex]

    Now, if you could show that this [itex]y[/itex] must be of the form [itex]Bx[/itex] for some [itex]x \neq 0[/itex], then you'd be done, right?
     
  6. Mar 24, 2010 #5
    I suppose I am a little lost here. I understand how the proof for B works, however A has me stumped. I suppose it is the fact that (AB)x = (Ax)B is illegal, yet (AB)x = A(Bx) is not. I am also confused as to what exactly showing y in the form of Bx means...is there any other way to state this without giving the answer away? Are we saying that we need to use the vector x that we know is not the zero vector (the one that proved B must be invertible) to show that A must be invertible also?
     
  7. Mar 24, 2010 #6

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Here is an attempt at rewording. Hopefully this will be clearer.

    We make the assumption that B is invertible but A is not invertible, and show that this leads to the contradiction that AB is not invertible.

    Proof:

    Since A is not invertible, then there exists [itex]y \neq 0[/itex] such that [itex]Ay = 0[/itex].

    Now, how can I show that AB is not invertible? One way to do so by finding a vector [itex]x \neq 0[/itex] such that [itex]ABx = 0[/itex].

    It would suffice if I could find [itex]x \neq 0[/itex] such that [itex]Bx = y[/itex], because then

    [tex]ABx = A(Bx) = Ay = 0[/tex]

    So, it boils down to this: given [itex]y \neq 0[/itex], how do I find an [itex]x[/itex] such that [itex]Bx = y[/itex]? And if I find such an [itex]x[/itex], I also need to check that it is nonzero.
     
  8. Mar 24, 2010 #7

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    By the way, there's another, more straightforward way to prove this result.

    If AB is invertible, then that means there exists some matrix D such that

    [tex]DAB = ABD = I[/tex]

    Can you see why this immediately implies invertibility of A and B?
     
  9. Mar 24, 2010 #8
    Well, we know that if B is invertible and x is a solution to Bx = y:

    Bx = y => (B-1B)x = B-1y => x = B-1y.

    This x would then have to be nonzero as y is nonzero. Then:

    ABx = A(Bx) = A(BB-1y) = Ay = 0.

    This can't happen though, since C = AB is invertible (and y is not 0), so A has to be invertible. Is that right?
     
  10. Mar 24, 2010 #9

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Right. They key is that you were able to find a solution [itex]x[/itex] such that

    [tex]Bx = y[/tex]

    and you were able to do this precisely because B was assumed to be invertible.
     
  11. Mar 27, 2010 #10
    Alright, I'm going to put this altogether to see if it makes sense:

    Proof:

    Let's take B to be singular, then there exists an x that is not 0 such that Bx = 0. Thus:

    C = AB => Cx = (AB)x = A(Bx) = 0.

    C would have to be singular, as there exists an x not equal to 0 that makes Cx = 0. This violates the assumption that C is invertible, thus B must be invertible.

    As we now know that B is invertible, let us take A to be singular. Then we have a y that is not equal to 0 such that Ay = 0. As B is invertible x is a solution to Bx = y:

    Bx = y => (B-1B)x = B-1y => x = B-1y.

    This x would then have to be nonzero as y is nonzero. Then:

    C = AB => Cx = ABx = A(Bx) = A(BB-1y) = Ay = 0.

    This violates our assumption that C is invertible as there is a y that is not 0 that makes C = 0.

    Therefore, if C = AB and C is invertible, both A and B must be invertible.
     
  12. Mar 27, 2010 #11

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Looks good to me, except the second to last sentence is a bit off. What you have shown is that there is a nonzero x such that Cx = 0, and that contradicts the invertibility of C. [i.e., the vector that is multiplying C is x, not y as your sentence suggests.]
     
  13. Mar 27, 2010 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Since you have a solution more or less figured out, let me point out another way for fun.

    If everything were invertible, you would know that
    C-1 =B-1 A-1
    and so
    A-1 = B C -1
    However, for B C-1 to make sense, you only need to know that C is invertible! So, you could prove A is invertible if you could prove BC-1 is its inverse. (e.g. by plugging into the definition of inverse)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook