Rank of matrix

1. Sep 13, 2010

D.K.

1. The problem statement, all variables and given/known data

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)

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

2. Sep 13, 2010

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.

Last edited: Sep 13, 2010
3. Sep 13, 2010

D.K.

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.

4. Sep 13, 2010

JonF

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

5. Sep 13, 2010

D.K.

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?

6. Sep 13, 2010

JonF

you have it backwards:

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

Can you think of why?

7. Sep 13, 2010

D.K.

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.

8. Sep 13, 2010

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)

9. Sep 13, 2010

D.K.

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.

10. Sep 13, 2010

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.

11. Sep 13, 2010

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.

12. Sep 13, 2010

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.

Last edited: Sep 13, 2010