# proof of one matrix rank inequality

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

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

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

-

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.

-