# Using the rank of a matrix

• Oct 21st 2013, 04:53 PM
vidomagru
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\$.
• 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 \$\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.
• 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 \$\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?
• 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 \$\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\$.
• 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 \$\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.
• 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.