4
$\begingroup$

Let $\mathbb F$ be a field, and let $r_1, r_2, s_1, s_2$ be positive integers. Consider the matrix $$X:=\left[\begin{array}{cc} A & B \\ C & D \end{array} \right],$$ where $A \in \mathbb F^{r_1 \times s_1}$, $B\in \mathbb F^{r_1\times s_2}$, $C \in \mathbb F^{r_2\times s_1}$ and $D \in \mathbb F^{r_2\times s_2}$.

Q1: Is the following inequality true? $$rank [X] \geq rank \left[\begin{array}{c} B \\ D \end{array} \right]+\max \left\{rank[A\;\; B]- rank[B], rank[C\;\;D]-rank[D] \right\}$$ If so, when does the equality hold?

Q2: Is there some nice formula for $rank[X]$ depending only on the blocks?

Thanks. Alessandro


Edit: The answer to the first question is YES. Is there an elementary proof of it? I can prove it using using results on completions of partial matrices, but I believe there should be an easy way to prove it.

For the equality I suspect that it holds if and only if $$rank \left[\begin{array}{c} A \\ C \end{array} \right]=\max \left\{rank[A],rank[C] \right\},$$ but I'm not sure.

$\endgroup$

2 Answers 2

4
$\begingroup$

Here is a slicker proof for Question 1:

The Frobenius rank inequality says that if $m,k,p,n$ are four nonnegative integers, and if $U\in\mathbb{F}^{m\times k}$, $V\in\mathbb{F}^{k\times p}$ and $W\in\mathbb{F}^{p\times n}$ are three matrices, then

$\operatorname*{rank}\left( UV\right) +\operatorname*{rank}\left( VW\right) \leq\operatorname*{rank}V+\operatorname*{rank}\left( UVW\right) $.

(This is proven in the answer to question #497830 in the case when $\mathbb{F}=\mathbb{C}$ (notice that the matrices $U$, $V$ and $W$ are denoted by $A$, $B$ and $C$ in said question); the same proof applies for arbitrary $\mathbb{F}$.)

For any $n\in\mathbb{N}$, we let $I_{n}$ denote the $n\times n$ identity matrix. For any $n\in\mathbb{N}$ and $m\in\mathbb{N}$, we let $0_{n\times m}$ denote the $n\times m$ zero matrix.

Now, if we set $m=r_{1}$, $k=r_{1}+r_{2}$, $p=s_{1}+s_{2}$, $n=s_{2}$, $U=\left[ \begin{array} [c]{cc} I_{r_{1}} & 0_{r_{1}\times r_{2}} \end{array} \right] $, $V=X$ and $W=\left[ \begin{array} [c]{c} 0_{s_{1}\times s_{2}}\\ I_{s_{2}} \end{array} \right] $, then it is easy to see that $UV=\left[ \begin{array} [c]{cc} A & B \end{array} \right] $, $VW=\left[ \begin{array} [c]{c} B\\ D \end{array} \right] $ and $UVW=B$; therefore, the Frobenius rank inequality (applied to these $m,k,p,n,U,V,W$) yields

$\operatorname*{rank}\left[ \begin{array} [c]{cc} A & B \end{array} \right] +\operatorname*{rank}\left[ \begin{array} [c]{c} B\\ D \end{array} \right] \leq\operatorname*{rank}X+\operatorname*{rank}B$.

Hence,

(1) $\operatorname*{rank}X-\operatorname*{rank}\left[ \begin{array} [c]{c} B\\ D \end{array} \right] \geq\operatorname*{rank}\left[ \begin{array} [c]{cc} A & B \end{array} \right] -\operatorname*{rank}B$.

On the other hand, if we set $m=r_{2}$, $k=r_{1}+r_{2}$, $p=s_{1}+s_{2}$, $n=s_{2}$, $U=\left[ \begin{array} [c]{cc} 0_{r_{2}\times r_{1}} & I_{r_{2}} \end{array} \right] $, $V=X$ and $W=\left[ \begin{array} [c]{c} 0_{s_{1}\times s_{2}}\\ I_{s_{2}} \end{array} \right] $, then it is easy to see that $UV=\left[ \begin{array} [c]{cc} C & D \end{array} \right] $, $VW=\left[ \begin{array} [c]{c} B\\ D \end{array} \right] $ and $UVW=D$; therefore, the Frobenius rank inequality (applied to these $m,k,p,n,U,V,W$) yields

$\operatorname*{rank}\left[ \begin{array} [c]{cc} C & D \end{array} \right] +\operatorname*{rank}\left[ \begin{array} [c]{c} B\\ D \end{array} \right] \leq\operatorname*{rank}X+\operatorname*{rank}D$.

Hence,

(2) $\operatorname*{rank}X-\operatorname*{rank}\left[ \begin{array} [c]{c} B\\ D \end{array} \right] \geq\operatorname*{rank}\left[ \begin{array} [c]{cc} C & D \end{array} \right] -\operatorname*{rank}D$.

Combining (1) with (2), we obtain

$\operatorname*{rank}X-\operatorname*{rank}\left[ \begin{array} [c]{c} B\\ D \end{array} \right] $

$\geq\max\left\{ \operatorname*{rank}\left[ \begin{array} [c]{cc} A & B \end{array} \right] -\operatorname*{rank}B,\operatorname*{rank}\left[ \begin{array} [c]{cc} C & D \end{array} \right] -\operatorname*{rank}D\right\} $.

This answers your Q1.

As for Question 2, here is a pretty comprehensive negative answer: In general, the rank of the block matrix $X$ is not uniquely determined from the ranks of $A$, $B$, $C$, $D$ and of the $1\times 2$ and $2\times 1$-block submatrices of $X$. This is probably easiest to check in the case of $r_1 = s_1 = r_2 = s_2 = 1$ and $A, B, C, D \neq 0$ (in this case, all nontrivial submatrices of $X$ have rank $1$, but $X$ itself can have either rank $1$ or rank $2$).

$\endgroup$
2
$\begingroup$

You can arrange row reduction of a block matrix $\left[ \matrix{A\cr B\cr} \right]$ so that you get a set of $\text{rank} \left[\matrix{A\cr B\cr}\right] - \text{rank}(A)$ rows of $B$ that are linearly independent of the rows of $A$, i.e. the only linear combination of these rows of $B$ that is in the row space of $A$ has all coefficients $0$. Taking transposes and interchanging $A$ and $B$, we have a similar result for columns: there is a set of $\text{rank}[A\ B] - \text{rank}(B)$ columns of $A$ that are linearly independent of the columns of $B$. Now for any $C$ and $D$, the corresponding columns of $\left[\matrix{A\cr C\cr}\right]$ are linearly independent of the columns of $\left[\matrix{B\cr D\cr}\right]$.

Thus $\text{rank}\left[\matrix{B\cr D\cr}\right]$ linearly independent columns of $\left[\matrix{B\cr D\cr}\right]$ together with those $\text{rank}[A\ B] - \text{rank}(B)$ columns of $\left[\matrix{A\cr C\cr}\right]$ form a linearly independent set, which says $$\text{rank}(X) \ge \text{rank}\left[\matrix{B\cr D\cr}\right] + \text{rank}[A\ B] - \text{rank}(B)$$ Similarly for $\text{rank}\left[\matrix{B\cr D\cr}\right] + \text{rank}[C\ D] - \text{rank}(D)$.

EDIT: Your suspicion is incorrect in both directions. Try

$$ \eqalign{A = \pmatrix{0 & 1\cr 0 & 1\cr},\ & B = \pmatrix{0 & 1\cr 1 & 1\cr}\cr C = \pmatrix{0 & 1\cr 1 & 1\cr},\ & D = \pmatrix{0 & 0\cr 1 & 1\cr}}$$ Then $X$ has rank $4$, while $\text{rank}\left[\matrix{B\cr D\cr}\right] = 2$, $\max(\text{rank}[A\ B] - \text{rank}(B), \text{rank}[C\ D] - \text{rank}(D)) = 1$, and $\text{rank} \left[ \matrix{A\cr C\cr} \right] = \max\{\text{rank}[A],\text{rank}[C]\} = 2$.

In the other direction, try $$ \eqalign{A = \pmatrix{0 & 0\cr 1 & 1\cr}, \ &B = \pmatrix{1 & 1\cr 0 & 0\cr}\cr C = \pmatrix{0 & 1\cr 0 & 1\cr}, \ &D = \pmatrix{1 & 0\cr 1 & 0\cr}}$$ Here $\text{rank}(X) = 3$, $\text{rank}\left[\matrix{B\cr D\cr}\right] = 2$, $\max(\text{rank}[A\ B] - \text{rank}(B), \text{rank}[C\ D] - \text{rank}(D)) = 1$, but $\text{rank} \left[ \matrix{A\cr C\cr} \right] =2 \ne \max\{\text{rank}[A],\text{rank}[C]\} = 1$.

$\endgroup$
3
  • $\begingroup$ Very good answer. Thank you! Do you have any idea about the equality? $\endgroup$
    – Sfarla
    Feb 9, 2016 at 22:00
  • $\begingroup$ btw the notation $R(M)$ for the column space was absolutely necessary! $\endgroup$
    – Sfarla
    Feb 9, 2016 at 22:02
  • $\begingroup$ Sorry, that $R(M)$ was the remains of a previous version of the answer. $\endgroup$ Feb 9, 2016 at 23:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .