An $r\times r$ submatrix of independent rows and independent columns is invertible (Michael Artin's book).

Question

Let $A$ be an $m \times n$ matrix of rank $r$, let $I$ be a set of row indices such that the corresponding rows of $A$ are independent and let $J$ be a set of $r$ column indices such that the corresponding columns of $A$ are independent. Let $M$ denote the $r \times r$ submatrix obtained by taking rows from $I$ and columns from $J$. Then $M$ is invertible.

So far I've got: Let $B$ be the $m \times r$ matrix obtain from taking the rows from $J$. $B$ is row-reducible to having a pivot in each column or else $Ax = 0$ has more than one solution, a contradiction. Also, the dimension of the row space of $B$ equals $r$ as well.

Answer 1

We may pre- and post- multiply by permutation matrices, so without loss assume that $I=J=\{1,2,\ldots, r\}$. Because the row-rank of the first $r$ rows is $r$, and the row-rank of $A$ is also $r$, all other rows of $A$ are linear combinations of the first $r$ rows. Suppose by way of contradiction that $M$ is not invertible; then its row rank is less than $r$. Hence we may do elementary row operations on the first $r$ rows, making an all-zero row within $M$.

Now we turn our attention to the columns. Because the column-rank of the first $r$ columns is $r$, and the column-rank of $A$ is also $r$, all other columns of $A$ are linear combinations of the first $r$ columns. None of this is disturbed by the elementary row operations done in the previous paragraph. But now all linear combinations of the all-zero row remain zero, so in fact $A$ has an all-zero row among the first $r$ rows (after the work in the previous paragraph). This is a contradiction.

Answer 2

Do you know that row rank is equal to column rank, and invertible is equivalent to full rank?

We want to assume $M$ is not invertible and get a contradiction. If $M$ is not invertible then it doesn't have rank $r$, but $M$ sits inside of $B$ which does have rank $r$. This means there is a column of $B$ that cannot be written as a linear combination of the columns in $M$. But this contradicts the fact that the columns of $A$ that contain $M$ form a matrix of rank $r$, so any other column of $A$ can be written as a linear combination of these columns.