Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By SlipEternal

Math Help - Using the rank of a matrix

  1. #1
    Member
    Joined
    Oct 2013
    From
    Washington state
    Posts
    77
    Thanks
    1

    Using the rank of a matrix

    Let A be an m x n matrix of rank r. Prove that every s rows of A form a matrix whose rank is greater than or equal to r+s-m.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,866
    Thanks
    729

    Re: Using the rank of a matrix

    Prove it by induction on r. Start with r=0. Then any s rows form a matrix whose rank is 0. Since s \le m, it is trivially true that r+s-m = 0+s-m \le m-m = 0.

    Next, make the induction hypothesis and prove the induction step.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2013
    From
    Washington state
    Posts
    77
    Thanks
    1

    Re: Using the rank of a matrix

    Quote Originally Posted by SlipEternal View Post
    Prove it by induction on r. Start with r=0. Then any s rows form a matrix whose rank is 0. Since s \le m, it is trivially true that r+s-m = 0+s-m \le m-m = 0.

    Next, make the induction hypothesis and prove the induction step.
    We prove this by induction. First we show this hold for r=0. If r=0, then any s rows of A form a matrix A_o whose rank is 0. So r+s-m=0+s-m \le m-m=0. So this holds for r=0.
    Now we assume r=k, and show that it holds for r=k+1.
    r=0 implies that any s rows of A form a matrix A_k whose rank is rank(A_k). Therefore we have rank(A_k) \ge r + s - m = k + s - m.
    So we need to show that rank(A_{k+1}) \ge r + s - m = k+1 +s-m = (k+s-m)+1 = rank(A_k) + 1.

    Is this on the right track? I am not sure where to go from here?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,866
    Thanks
    729

    Re: Using the rank of a matrix

    Actually, induction might not be the best way to prove this. Perhaps a direct proof would be more efficient. If you have m rows and the rank is r, that tells you that at least r rows are nonzero. Suppose the rest are all zero rows. Then there are m-r zero rows. So, if s\le m-r, and you just happen to choose all zero rows, then the rank of the matrix you chose would be r+s-m \le r+(m-r)-m = 0, which is true. If s>m-r, then by the pigeonhole principle, you must have chosen at least s-(m-r) independent rows, so the rank is a minimum of r+s-m.
    Thanks from vidomagru
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2013
    From
    Washington state
    Posts
    77
    Thanks
    1

    Re: Using the rank of a matrix

    Quote Originally Posted by SlipEternal View Post
    Actually, induction might not be the best way to prove this. Perhaps a direct proof would be more efficient. If you have m rows and the rank is r, that tells you that at least r rows are nonzero. Suppose the rest are all zero rows. Then there are m-r zero rows. So, if s\le m-r, and you just happen to choose all zero rows, then the rank of the matrix you chose would be r+s-m \le r+(m-r)-m = 0, which is true. If s>m-r, then by the pigeonhole principle, you must have chosen at least s-(m-r) independent rows, so the rank is a minimum of r+s-m.
    Ok, I read the wikipedia page on the "pigeonhole principle," but I am not sure I understand its implications.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Using the rank of a matrix

    You can use the fact that if a row is added to a matrix, its rank cannot increase by more than 1. So, if the rank of the chosen s rows is < r + s - m = r - (m - s), then adding the rest (m - s) rows will not restore the rank of the matrix to r.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Matrix Rank
    Posted in the Peer Math Review Forum
    Replies: 1
    Last Post: October 7th 2012, 02:14 PM
  2. Matrix Rank
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 19th 2010, 04:26 AM
  3. Replies: 3
    Last Post: August 20th 2010, 05:32 AM
  4. Is the rank of a 3x3 matrix all 0 .....
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: July 27th 2010, 04:40 AM
  5. Replies: 1
    Last Post: April 1st 2010, 08:34 AM

Search Tags


/mathhelpforum @mathhelpforum