Let be an matrix of rank . Prove that every rows of form a matrix whose rank is greater than or equal to .

Printable View

- October 21st 2013, 04:53 PMvidomagruUsing the rank of a matrix
Let be an matrix of rank . Prove that every rows of form a matrix whose rank is greater than or equal to .

- October 21st 2013, 08:11 PMSlipEternalRe: Using the rank of a matrix
Prove it by induction on r. Start with r=0. Then any rows form a matrix whose rank is 0. Since , it is trivially true that .

Next, make the induction hypothesis and prove the induction step. - October 22nd 2013, 01:49 PMvidomagruRe: Using the rank of a matrix
We prove this by induction. First we show this hold for . If , then any rows of form a matrix whose rank is 0. So . So this holds for .

Now we assume , and show that it holds for .

implies that any rows of form a matrix whose rank is . Therefore we have .

So we need to show that .

**Is this on the right track? I am not sure where to go from here?** - October 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 rows and the rank is , that tells you that at least rows are nonzero. Suppose the rest are all zero rows. Then there are zero rows. So, if , and you just happen to choose all zero rows, then the rank of the matrix you chose would be , which is true. If , then by the pigeonhole principle, you must have chosen at least independent rows, so the rank is a minimum of .

- October 22nd 2013, 07:53 PMvidomagruRe: Using the rank of a matrix
- October 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.