Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
I still don't get it. I've tried to understand your post, but keep failing. – Enjoys Math Apr 21 '13 at 19:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.