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$.

Printable View

- Oct 21st 2013, 04:53 PMvidomagruUsing 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 PMSlipEternalRe: 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 PMvidomagruRe: Using the rank of a matrix
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 PMSlipEternalRe: 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 PMvidomagruRe: Using the rank of a matrix
- Oct 23rd 2013, 12:24 AMemakarovRe: 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.