Linear Algebra Invertibility Proof

[Gotejjeken]

Homework Statement

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.

Homework Equations

If a NXN matrix A is invertible:

Ax = 0 has only the trivial solution 0.

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?

 

[Hurkyl]

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?

 

[Gotejjeken]

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.

 

[jbunniii]

Homework Statement

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.

Homework Equations

If a NXN matrix A is invertible:

Ax = 0 has only the trivial solution 0.

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.

This looks fine so far.

(AB)x = (Ax)B

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

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

Ay = 0

Now, if you could show that this y must be of the form Bx for some x \neq 0, then you'd be done, right?

 

[Gotejjeken]

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?

 

[jbunniii]

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?

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 y \neq 0 such that Ay = 0.

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

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

ABx = A(Bx) = Ay = 0

So, it boils down to this: given y \neq 0, how do I find an x such that Bx = y? And if I find such an x, I also need to check that it is nonzero.

 

[jbunniii]

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

DAB = ABD = I

Can you see why this immediately implies invertibility of A and B?

 

[Gotejjeken]

So, it boils down to this: given y \neq 0, how do I find an x such that Bx = y? And if I find such an x, I also need to check that it is nonzero.

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?

 

[jbunniii]

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?

Right. They key is that you were able to find a solution x such that

Bx = y

and you were able to do this precisely because B was assumed to be invertible.

 

[Gotejjeken]

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.

 

[jbunniii]

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.]

 

[Hurkyl]

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)