# Rank of matrix a submatrix $B$ from $A$

Question:

A submatrix $B$ consisting of "s" rows of $A$ is selected from an n-square matrix $A$ of rank $r_{A}$. prove that the rank of $B$ is equal to or greater than $r_{A}+s-n$.

My thoughts:

I start with an easy case, says $A=I_4$. Then, by selecting 2 first rows of $A$. We obtain a matrix $B$:$$\begin{pmatrix} 1 &0 &0 &0 \\ 0&1 &0 &0 \end{pmatrix}$$ So, the rank of $B=4+2-4=2$. At least, I know the statement is true for this trivial situation. But can anyone help me to figure out the general situation about the problem? Thanks in advance.

Hint: Note the following: $$r_A\leq n$$ and $$r_B\leq s$$. With this in mind, instead of trying to prove that $$r_B\ge r_A+s-n$$ try to prove an equivalent inequality that has $$r_B, r_A$$ one one side and $$n,s$$ on the other.

As was pointed out below, my hint has issues and I don't see a way to salvage it. I am unable to delete this answer, so, for self-containment, I'm copying Leon Sot's answer:

Rearrange to get $$r_A-r_B\leq n-s.$$ So the difference in rank is less than the difference in rows. There are $$r_A-r_B$$ 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 $$n-s$$ rows not in $$B$$. The inequality follows.

• Thank you for your hint so much. It helps me to work it out. =)
– nam
Apr 11, 2014 at 16:31
• @nam I'm glad.${}$ Apr 11, 2014 at 16:31
• Kindly provide hint 2. Nov 24, 2019 at 7:20
• @ChandramauliChakraborty Subtract the two first inequalities in my answer. Nov 24, 2019 at 21:32
• @GitGud, then I would get $r_A-s \leq n-r_B$. Nov 25, 2019 at 13:42

Here $$A$$ is $$n\times n$$ matrix and $$r_A$$ be the rank of $$A$$. Now we need to eliminate $$n-s$$ rows from $$n$$ rows. Let $$C=\{A_{i_k*}:1\leq k\leq r_A\}$$, be the set of basis of row space of A , i.e , $$\mathcal{R}(A)$$, where $$A_{i_k*}$$ denote the $$i_k\textit{-th}$$ row of the matrix A.

Now choose any row $$A_{j_m*}$$, there would be two possibilities, i.e. either $$A_{j_m*}\in C$$ or $$A_{j_m*}\not\in C$$.If $$A_{j_m*}\in C$$, then the new matrix is of order $$(n-1)\times n$$ has rank $$r_A-1$$, while in the other case, $$r_B=r_A$$, since $$A_{j_m*}\in span(C)$$.

Hence if we want the minimum of $$r_B$$, then it should be the worst case where all the $$n-s$$ rows belong to $$C$$. Hence $$r_B\geq r_A-(n-s)$$.