Rank of matrix

  • Thread starter D.K.
  • Start date
  • #1
12
0

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.
 

Answers and Replies

  • #2
612
1
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:
  • #3
12
0
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.
 
  • #4
612
1
sorry i'm half asleep, after thinking about it a bit more i'd use the rank-nullity theorem
 
  • #5
12
0
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?
 
  • #6
612
1
you have it backwards:

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

Can you think of why?
 
  • #7
12
0
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.
 
  • #8
612
1
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
12
0
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.
 
  • #10
612
1
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
12
0
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
12
0
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:

Related Threads on Rank of matrix

  • Last Post
Replies
0
Views
838
  • Last Post
Replies
7
Views
772
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
6
Views
23K
Replies
2
Views
10K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
9
Views
17K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
932
  • Last Post
Replies
6
Views
753
Top