A submatrix $B$ of rank $q$ consisting of $s$ rows of $A$ is selected from an $m$-square matrix $A$ of rank $r$. Prove that $q$ is equal to or greater than $r+s−m$.

My thoughts:

I should start by getting $0 \leq q \leq r \leq m$ and $0 \leq q \leq s \leq m$. Can anyone give me guidance on how to proceed?

Note: There was a similar question that has been asked here, but the hint did not help me.


Note that this is equivalent to $$m-r \geq s-q, $$ the difference between rows and rank of $A$ is greater than in $B$. Now, suppose $A: k^n\to k^m$ where $k$ is your favourite field. Let $U\subseteq k^m$ be the subspace given by the first $s$ coordinates. Then $im(B)=U\cap im(A)$ under the natural embedding.

Let $V=im(A)+U$, then from the second isomorphism theorem we have $$V/im(A) \cong U/im(B) $$ and upon taking dimensions we get $$dim(V) -r = s-q. $$ The inequality follows.

Edit: Here is a simpler solution,

rearrange to get $$r-q\leq m-s. $$ So the difference in rank is less than the difference in rows. There are $r-q$ rows that add the the rank of $A$ but not to the rank of $B$. These rows cannot be in the $s$ selected rows since then this would increase the rank of $B$. Therefore, they are one of the $m-s$ rows not in $B$. The inequality follows.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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