Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Rank of matrix

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

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

    Can you think of why?
     
  8. Sep 13, 2010 #7

    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.
     
  9. Sep 13, 2010 #8
    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)
     
  10. Sep 13, 2010 #9
    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.
     
  11. Sep 13, 2010 #10
    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.
     
  12. Sep 13, 2010 #11
    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.
     
  13. Sep 13, 2010 #12
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook