Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

I forgot how to prove the following inequality. Could anybody help?

Let $A, B, C$ be matrices of appropriate dimensions: $$rank\left( \left[\begin{array}{rr} A & 0\\ C & B \end{array}\right]\right)\ge rank\left( \left[\begin{array}{rr} A & 0\\ 0 & B \end{array}\right]\right).$$

share|cite|improve this question
What does rank-nullity imply? – Ehsan M. Kermani Apr 15 '11 at 16:13
@ehsanmo: does rank-nullity imply this directly? If so, please post an answer with such reasoning. I do not see this argument. – Qiang Li Apr 19 '11 at 0:14

If you apply the elementary row operations that bring the right-hand matrix into row echelon form to both matrices, the result is the same on both sides except in the $C$ block, which may have additional non-zero entries. Then all rows that are linearly independent on the right-hand side are also linearly independent on the left-hand side, and possibly more.

share|cite|improve this answer
I think it would just be somewhat difficult to write down the detailed proof. I guess we should separately bring $A$ and $B$ to row echelon form, rather than bringing the whole matrix to its row echelon form, to give the argument, correct? – Qiang Li Apr 15 '11 at 20:03

Let $A \in M_{p\times q}(\mathbb K)$, $C \in M_{(n-p)\times q}(\mathbb K)$ and $B \in M_{(n-p)\times (n-q)}(\mathbb K)$. We may decompose $\mathbb K^n=\mathbb K^p\times 0 \oplus 0 \times \mathbb K^(n-p)$ and consider $$\{a_1,\dots,a_q\} \subset \mathbb K^p\times 0$$ the set of columms of $A$, $$\{b_1,\dots,b_q\} \subset 0 \times \mathbb K^{n-p}$$ the set of columms of $B$ and $$\{c_1,\dots,c_q\} \subset 0 \times \mathbb K^{n-p}$$ the set of columms of $C$.

So, it suffices to show that given an LI subset $$\{a_{i_1},\dots,a_{i_s},b_{j_1},\dots,b_{j_r}\}$$ of $$\{a_1,\dots,a_q,b_1,\dots,b_{n-q}\}$$ we have that $$\{a_{i_1}+c_{i_1},\dots,a_{i_s}+c_{i_s},b_{j_1},\dots,b_{j_r}\}$$ is a LI subset of $$\{a_1+c_1,\dots,a_q+c_q,b_1,\dots,b_{n-q}\}.$$ In fact, if $$\alpha_{i_1}(a_{i_1}+c_{i_1})+\dots+\alpha_{i_s}(a_{i_s}+c_{i_s})+\beta_{j_1}b_{j_1},\dots,\beta_{j_r}b_{j_r} = 0$$ for some $\alpha$s and $\beta$s \in $\mathbb K$, we must have that $$\mathbb K^p \times 0 \ni \alpha_{i_1}a_{i_1} +\dots+\alpha_{i_s}a_{i_s} = 0$$ and $$0 \times \mathbb K^{n-p} \ni \alpha_{i_1}c_{i_1}+\dots+\alpha_{i_s}c_{i_s}+\beta_{j_1}b_{j_1},\dots,\beta_{j_r}b_{j_r} = 0.$$ By the linear independence of $$\{a_{i_1},\dots,a_{i_s}\} \subset \{a_{i_1},\dots,a_{i_s},b_{j_1},\dots,b_{j_r}\}$$ we must have that $$\alpha_{i_1}=\dots=\alpha_{i_s}=0$$ and, hence, $$\beta_{j_1}b_{j_1}+\dots+\beta_{j_r}b_{j_r} = 0.$$ Again, $$\{b_{j_1},\dots,b_{j_r}\}\subset \{a_{i_1},\dots,a_{i_s},b_{j_1},\dots,b_{j_r}\}$$ implies that $$\beta_{j_1}=\dots=\beta_{j_r}=0.$$ Therefore, we conclude that $$\{a_{i_1}+c_{i_1},\dots,a_{i_s}+c_{i_s},b_{j_1},\dots,b_{j_r}\}$$ is a LI set.

share|cite|improve this answer

Let $c'_1,..., c'_n$ be the columns of

$$\left( \left[\begin{array}{rr} A & 0\\ C & B \end{array}\right]\right)$$

and $c_1,..., c_n$ be the colums of

$$\left( \left[\begin{array}{rr} A & 0\\ 0 & B \end{array}\right]\right)$$

If $c_{i_1},..., c_{i_j}$ are linearly independent and

$$k_1c'_{i_1}+...+ k_jc'_{i_j} =0 \,.$$

then, it follows immediately by writing explicitely the columns that $k_1=..=k_j=0$.

Hence if we pick a basis in the column space of $\left( \left[\begin{array}{rr} A & 0\\ 0 & B \end{array}\right]\right)$, the correcponding colums are linearly independent in $\left( \left[\begin{array}{rr} A & 0\\ C & B \end{array}\right]\right)$, which proves the inequality.

share|cite|improve this answer

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.