# Linear Algebra Invertibility Proof

## 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
Staff Emeritus
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?

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 Helper
Gold Member

## 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?

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
Homework Helper
Gold Member
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
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

$$DAB = ABD = I$$

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

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
Homework Helper
Gold Member
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.

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

Hurkyl
Staff Emeritus