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

Thread: 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 $\displaystyle A$ be an $\displaystyle m x n$ matrix of rank $\displaystyle r$. Prove that every $\displaystyle s$ rows of $\displaystyle A$ form a matrix whose rank is greater than or equal to $\displaystyle r+s-m$.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,462
    Thanks
    1374

    Re: Using the rank of a matrix

    Prove it by induction on r. Start with r=0. Then any $\displaystyle s$ rows form a matrix whose rank is 0. Since $\displaystyle s \le m$, it is trivially true that $\displaystyle 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 $\displaystyle s$ rows form a matrix whose rank is 0. Since $\displaystyle s \le m$, it is trivially true that $\displaystyle 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 $\displaystyle r=0$. If $\displaystyle r=0$, then any $\displaystyle s$ rows of $\displaystyle A$ form a matrix $\displaystyle A_o$ whose rank is 0. So $\displaystyle r+s-m=0+s-m \le m-m=0$. So this holds for $\displaystyle r=0$.
    Now we assume $\displaystyle r=k$, and show that it holds for $\displaystyle r=k+1$.
    $\displaystyle r=0$ implies that any $\displaystyle s$ rows of $\displaystyle A$ form a matrix $\displaystyle A_k$ whose rank is $\displaystyle rank(A_k)$. Therefore we have $\displaystyle rank(A_k) \ge r + s - m = k + s - m$.
    So we need to show that $\displaystyle 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
    3,462
    Thanks
    1374

    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 $\displaystyle m$ rows and the rank is $\displaystyle r$, that tells you that at least $\displaystyle r$ rows are nonzero. Suppose the rest are all zero rows. Then there are $\displaystyle m-r$ zero rows. So, if $\displaystyle s\le m-r$, and you just happen to choose all zero rows, then the rank of the matrix you chose would be $\displaystyle r+s-m \le r+(m-r)-m = 0$, which is true. If $\displaystyle s>m-r$, then by the pigeonhole principle, you must have chosen at least $\displaystyle s-(m-r)$ independent rows, so the rank is a minimum of $\displaystyle 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 $\displaystyle m$ rows and the rank is $\displaystyle r$, that tells you that at least $\displaystyle r$ rows are nonzero. Suppose the rest are all zero rows. Then there are $\displaystyle m-r$ zero rows. So, if $\displaystyle s\le m-r$, and you just happen to choose all zero rows, then the rank of the matrix you chose would be $\displaystyle r+s-m \le r+(m-r)-m = 0$, which is true. If $\displaystyle s>m-r$, then by the pigeonhole principle, you must have chosen at least $\displaystyle s-(m-r)$ independent rows, so the rank is a minimum of $\displaystyle 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,577
    Thanks
    790

    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: Oct 7th 2012, 02:14 PM
  2. Matrix Rank
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Oct 19th 2010, 04:26 AM
  3. Replies: 3
    Last Post: Aug 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: Jul 27th 2010, 04:40 AM
  5. Replies: 1
    Last Post: Apr 1st 2010, 08:34 AM

Search Tags


/mathhelpforum @mathhelpforum