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

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.

-

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.

-

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.

-
I still don't get it. I've tried to understand your post, but keep failing. –  Enjoys Math Apr 21 '13 at 19:57
I'm not sure how advanced you are, so this proof might be too "high-level". It's clear by construction that $rank(M) = r$. But a square matrix has full rank iff it is invertible. This is clear if we view a matrix as a linear transformation $T:\mathbb{R}^r \rightarrow \mathbb{R}^r$; the rank is the dimension of the image, and then $dim(Im(T)) = dim(V)$ means that $T$ is an isomorphism.
Sorry, why is it clear that $rank(M)=r$? –  vadim123 Apr 21 '13 at 18:24
@vadim123 Because we have chosen linearly independent columns of $A$ to form columns of $M$. So all the $r$ columns of $M$ are linearly independent, i.e. $rank(M) = r$. –  A.P. Apr 21 '13 at 18:56
What about the block matrix $A=\left(\begin{smallmatrix}0&I\\I&I\end{smallmatrix}\right)$, where each block is $2\times 2$. The first two columns of $A$ are linearly independent, and of rank 2, but the submatrix $M=0$. –  vadim123 Apr 21 '13 at 18:58
@vadim123 The first two columns of $A$ are the same, so they're definitely not linearly independent. –  A.P. Apr 21 '13 at 19:00
The first column of A is $(0,0,1,0)^T$, while the second column is $(0,0,0,1)^T$. $I=\left(\begin{smallmatrix}1&0\\0&1\end{smallmatrix}\right)$. –  vadim123 Apr 21 '13 at 19:01