Another matrix rank proof

  1. radou

    radou 3,215
    Homework Helper

    Let A and B me matrices such that the product AB is defined. One has to proove that r(AB) <= r(A) and r(AB) <= r(B).

    My first thoughts are: let A be 'mxn' and B be 'nxp', so AB is 'mxp'. Further on, we know that r(A) <= min{m, n}, r(B) <= min{n, p} and r(AB) <= min{m, p}. I'm stuck here, although I tried to work something out with the inequalities, but without success. Any hints would be appreciated.
     
  2. jcsd
  3. you should look on the vector space of the homogenous solutions of Bx=0.
    and use the fact that dim of this space equals n-rankB, also you should look on ABx=0.
    from this you can easily prove that rank(AB)<=rank(B).
    now i forgot how to prove the second inequality.
     
  4. radou

    radou 3,215
    Homework Helper

    Hm, I can't exactly say I follow.

    The only way that r(AB) <= r(A) would follow from this is that d2 >= d1, where d2 is the dimension of the vector space of solutions to ABx=0, and d1 the dimension of the vector space of solutions to Ax=0. But why would I conclude that d2>=d1?
     
  5. ok, you need to show that U={x|Bx=0} is a subset of V={x|ABx=0}, then
    dim U<=dim V
    and dim U=n-rankB and dimV=n-rankAB, n is the number of columns of the matrix, the number of columns of AB is the same as of B.
    the same way you can prove that rankAB<=rankA, with the use of rankAB=rank(AB)^t=rank(B^tA^t).
    and rankA=rankA^t.
     
  6. if you ask why dimU<=dimV, then it follow from a thoerem that if U is subspace of V then (and V is finite) the inequality holds.
     
  7. radou

    radou 3,215
    Homework Helper

    Ok, I got a grip on it now. Thanks! :wink:
     
  8. matt grime

    matt grime 9,395
    Science Advisor
    Homework Helper

    Woah, boys, you're making this way way to complicated. What is the rank? Just the dimension of the image. This is cleary a submultiplicative function (take some linearly independent vectors, applying a linear map can only make it more dependent).
     
  9. radou

    radou 3,215
    Homework Helper

    Ok, the definition of the rank of a mxn matrix A is r(A) = dim [{C1, ..., Cn}], where C1, ..., Cn are the columns of the matrix. What exactly does it mean 'to be a submultiplicative function' and how exactly do I apply this to the problem?
     
  10. morphism

    morphism 2,020
    Science Advisor
    Homework Helper

    The image of AB is a subet of the image of A. So r(AB) <= r(A).

    The second inequality follows from the first, as
    r(AB) = r((AB)^t) = r(B^t A^t) <= r(B^t) = r(B)
     
  11. radou

    radou 3,215
    Homework Helper

    How is the image of a matrix defined?
     
  12. morphism

    morphism 2,020
    Science Advisor
    Homework Helper

    The set { Av in R^m : v is in R^n }, if A is mxn, which is the same as the image of the linear transformation T : R^n -> R^m given by Tv = Av. So a matrix can simply be thought of as a linear transformation.
     
  13. matt grime

    matt grime 9,395
    Science Advisor
    Homework Helper

    Forget it: it wasn't important, and wasn't used in the technical sense, just a suggestive one.
     
    Last edited: Feb 5, 2007
  14. radou

    radou 3,215
    Homework Helper

    Yes, perhaps a bit too nonsuggestive for my level (no offence, of course). :smile:
     
  15. solution :

    let C=AB [ A=m*k , B= k*n, C= m*n]
    now let the rows be C and B be: {c[1],c[2],....c[m]} , { b[1],b[2]....b[k]
    thus we can write :
    c= A[1]*b[1] + A[2]*b[2] +...+ A[m]*b[m]

    therefore the row space of C is a subspace of row space of B
    therefre Rowrank(C)=rank(C) <= Rank (B)
    similarly proceed wid column rank argument for
    Column rank (C)=Rank(C) <= Colum rank (A)=Rank(A)
    hence Rank(C)<= {Rank(A),Rank(B)}
     
  16. You can think this as ''how can the dimension of the nullspace of the product increase ?" For a little intuition, think about how can (AB)x = 0 be satisfied with a nonzero x vector, either it is because x is in the nullspace of B or (Bx) is in the nullspace in A. It is very useful to experiment these kind of stuff with full rank rectangular matrices...
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?
Similar discussions for: Another matrix rank proof
Loading...