• Support PF! Buy your school textbooks, materials and every day products Here!

Linear Algebra Invertibility Proof

  • Thread starter Gotejjeken
  • Start date
  • #1
29
0

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?
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
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?
 
  • #3
29
0
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.
 
  • #4
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179

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 [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?
 
  • #5
29
0
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?
 
  • #6
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
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 [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.
 
  • #7
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
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?
 
  • #8
29
0
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.
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?
 
  • #9
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
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 [itex]x[/itex] such that

[tex]Bx = y[/tex]

and you were able to do this precisely because B was assumed to be invertible.
 
  • #10
29
0
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.
 
  • #11
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
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.]
 
  • #12
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
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)
 

Related Threads for: Linear Algebra Invertibility Proof

Replies
2
Views
4K
Replies
1
Views
654
Replies
3
Views
2K
Replies
3
Views
5K
Replies
6
Views
6K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
15K
Top