Take the 2-minute tour ×
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.

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|improve this question

3 Answers 3

up vote 1 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|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|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

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.

share|improve this answer
    
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

Your Answer

 
discard

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.