Prove "If $\text{rank } A = k$ with $A\in R^{n\times m},\ \ m>n$, there is a $k\times k$ submatrix with rank $k$"

Question

How to prove the title?

My work:

1. The title implies there exists $k$ independent columns in $A$.
2. Delete other $m-k$ columns.
3. By elementary row operation, we can obtain a reduced-row-echelon form.
   There must be a $k\times k$ identity matrix. (This is just by rref form)
4. So there should exist $k \times k$ submatrix with rank $k$.

---

However, it still seems shaky to me that what I obtain is a matrix after doing row operation, which is not really $A$ itself.

How should I say more to strengthen this proof or use other method?

Answer 1

After you throw away the $m-k$ columns that don't work, you can just use a dimensionality argument. Notice now that by deleting those $m-k$ columns, we now obtain an $n\times k$ matrix $\tilde{A}$ which is of rank $k$. Notice however that it is impossible for $k >n$ since $k \leq \min\{n,m\}$. In the case that $k=n$ we are done since $\tilde{A}$ is of rank $k$. If $k <n$ then we know there are linearly dependent rows in our matrix $\tilde{A}$. We can repeat the same operation as in the first step by deleting an appropriate $n-k$ rows of $\tilde{A}$.