# Linear Algebra Invertibility Proof

• Gotejjeken
In summary, without using determinants, it can be proven that if the product of two NxN matrices A and B, denoted as C = AB, is invertible, then both A and B must also be invertible. One way to prove this is by showing that if B is invertible and A is not, then C is not invertible. Another way is to observe that if C is invertible, then there exists a matrix D such that DAB = ABD = I, which immediately implies invertibility of A and B.

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

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.

Gotejjeken said:

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

Gotejjeken said:
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.

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?

jbunniii said:
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?

Gotejjeken said:
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.

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

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)