Using the rank of a matrix

• Oct 21st 2013, 04:53 PM
vidomagru
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$.
• Oct 21st 2013, 08:11 PM
SlipEternal
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.
• Oct 22nd 2013, 01:49 PM
vidomagru
Re: Using the rank of a matrix
Quote:

Originally Posted by SlipEternal
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?
• Oct 22nd 2013, 03:23 PM
SlipEternal
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$.
• Oct 22nd 2013, 07:53 PM
vidomagru
Re: Using the rank of a matrix
Quote:

Originally Posted by SlipEternal
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.
• Oct 23rd 2013, 12:24 AM
emakarov
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.