Submatrix formed from independent rows and columns

Question

Suppose matrix A has rank r. Pick any r independent rows and r independent columns from A. Must the submatrix formed from these rows and columns be invertible?

Answer 1

Let

• $\,A\,$ be an $\,m{\,\times\,}n\,$ matrix of rank $r$.$\\[3pt]$
• $\,R\,$ be an $\,r{\,\times\,}\,n$ submatrix of $A$ with $r$ linearly independent rows.$\\[3pt]$
• $\,C\,$ be an $\,m{\,\times\,}r\,$ submatrix of $A$ with $r$ linearly independent columns.$\\[3pt]$
• $\,B\,$ be the $\,r{\,\times\,}r\,$ submatrix of $A$ formed by intersecting the rows of $R$ with the columns of $C$.

Claim $B$ is invertible.

Since $B$ is a submatrix of $A$, $\text{rank}(B) \le r$.

By construction, $R$ has rank $r$, as does $C$.

If row $i$ of A is not one of the rows from $R$, then it must be linearly dependent on the rows from $R$, hence row $i$ of $C$ is linearly dependent on those rows from $C$ which are in $B$.

It follows that $\text{rank}(C) \le \text{rank}(B)$, hence $r \le \text{rank}(B)$.

Thus, $r \le \text{rank}(B) \le r$, so $\text{rank}(B) = r$.

It follows that $B$ is invertible, as claimed.