2
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

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

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)$.

$\endgroup$

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.