Proving Rank Relationship Between Matrices A and B

[D.K.]

Homework Statement

Prove that for any m x s matrix A and any s x n matrix B it holds that:

rank(A) + rank(B) - s
is less or equal to:
rank(AB)

The Attempt at a Solution

Obviously, the following are true:

- rank(A) is less or equal to s,
- rank(B) is less or equal to s,
- rank(AB) is less or equal to both rank(A) and rank(B).

So it is possible to prove:

rank(A) + rank(B) - 2s is less or equal to rank(AB).

Really don't know what can be done next. Thanks for any help on this.

 

[JonF]

These should be easy to prove:
Rank(A) <= min(m,s,)
Rank(B) <= min(s,n)
Rank(AB) <= min (m,n)

and put you in the right direction

edit: If you have to prove these cause you haven’t proven it in class, just prove the general form of:
Rank(A) <= min (m,n) where A is a m x n matrix.

 

[D.K.]

These should be easy to prove:
Rank(A) <= min(m,s,)
Rank(B) <= min(s,n)
Rank(AB) <= min (m,n)

and put you in the right direction

I'm afraid that doesn't suffice.

For suppose that m <= n < = s, e.g. m = 4, n = 4, s = 5. Then:

rank(A) <= 4,
rank(B) <= 4,
rank(AB) <= 4.

That, however, doesn't make rule out as impossible following:

rank(A) = 4,
rank(B) = 4,
rank(AB) = 2,

which would make the statement:

rank(A) + rank(B) - s <= rank(AB)

entirely false.

 

[JonF]

sorry I'm half asleep, after thinking about it a bit more i'd use the rank-nullity theorem

 

[D.K.]

sorry I'm half asleep, after thinking about it a bit more i'd use the rank-nullity theorem

Well, I see a way to use the rank-nullity theorem here successfully provided it is known that:

for any A, B, AB it is the case that: nullity A + nullity B <= nullity AB.

But is the above true?

 

[JonF]

you have it backwards:

nullity(AB) <= nullity(A) + nullity(B)

Can you think of why?

 

[D.K.]

you have it backwards:

nullity(AB) <= nullity(A) + nullity(B)

Can you think of why?

Sorry, I've meant to write it the way you did. I'm aware that it'll do the trick but don't know why is it true.

 

[JonF]

sorry it took me so long to respond, I'm at work and didn’t have a chance to get back to you.

Do you know Rank(AB) <= min(Rank(A),Rank(B))? If so:
Since Null(A) >= 0, Rank(AB) >=0, if we use the rank-nullity theorem a few times we get:

Null(A) + Null(B) =
Null(A) + n – Rank(B) =
Null(A) + Rank (AB) + Null(AB) – Rank(B) >=
Rank (AB) + Null(AB) – Rank(B) >=
Rank(B) – Rank(B) + Null(AB) =
Null(AB)

 

[D.K.]

sorry it took me so long to respond, I'm at work and didn’t have a chance to get back to you.

Do you know Rank(AB) <= min(Rank(A),Rank(B))? If so:
Since Null(A) >= 0, Rank(AB) >=0, if we use the rank-nullity theorem a few times we get:

Null(A) + Null(B) =
Null(A) + n – Rank(B) =
Null(A) + Rank (AB) + Null(AB) – Rank(B) >=
Rank (AB) + Null(AB) – Rank(B) >=
Rank(B) – Rank(B) + Null(AB) =
Null(AB)

Would you be so kind as to explain how did you get

Rank (AB) + Null(AB) – Rank(B) >= Rank(B) – Rank(B) + Null(AB)?

The rest - including Rank(AB) <= min(Rank(A),Rank(B)) - is perfectly clear to me.

 

[JonF]

With an inequality error, sigh I’m doing poorly with this problem and algebraic manipulation tonight.

I know: nullity(AB) <= nullity(A) + nullity(B) is true. I can't for the life of me remember why.

 

[D.K.]

For sure the inequality holds:

max(null(A), null(B)) <= null(AB).

Oh, and null(A) + null(B) >= null(AB) turns out to be simply equivalent to the statement we were trying to prove from the beginning.

 

[D.K.]

I found it easy to prove:

null(A) + null(B) >= null(AB),

using maps instead of matrices. Indeed, take /phi_A, /phi_B and /phi_AB defined by matrices A, B and AB respectively.

If we restrict the domain of /phi_AB to just those vectors X of which images \phi_B(X) lies in the Ker(A), it's not hard to apply rank-null theorem in it's full generality once again and get:

null(AB) = rank C + null(B), where C \in null(A).

That concludes the proof.