# Finding the rank of sub-matrix

A Boolean matrix $M$, of rank $r$, is of the form

$$\begin{bmatrix} A & B \\ C & D \\ \end{bmatrix}$$

where the sub-matrix $A$ is a all zero matrix or all one matrix (i.e. $A$ is monochromatic). So $\text{rank}(A)$ is at most $1$.

Then a typical upper bound on $\text{rank}(B) + \text{rank}(C)$ is $2r$.

Can we have anything better than that? Can we say $\text{rank}(B) + \text{rank}(C) \le r+1$ ? How?

First, argue that the matrix $M'=\pmatrix{0 & B \\ C & D}$ has rank at least $\text{rank}(B)+\text{rank}(C)$: Let $U$ be the space spanned by the columns of $\pmatrix{0 \\ C}$. Then $\text{dim}(U)=\text{rank}(C)$. Next, choose a set of columns of $B$ forming a basis for the span of the columns of $B$, and let $V$ be the space spanned by the corresponding columns of $\pmatrix{B \\ D}$. Then $\text{dim}(V)=\text{rank}(B)$, and $U\cap V=0$. Therefore $\text{dim}(U+V)=\text{rank}(B)+\text{rank}(C)$, and since $\text{rank}(M')\geq \text{dim}(U+V)$, it follows that $\text{rank}(M')\geq\text{rank}(B)+\text{rank}(C)$.
Now, $M$ differs from $M'$ by a matrix of rank at most 1, and the result follows.
• Let's say there are $b$ basis vectors for the span of the columns of B. Then these $b$ vectors remain linearly independent when we extend them with additional components coming from the corresponding columns in $D$, and there still remain just $b$ of them; therefore they span a space of dimension $b$. The way I have defined $V$, $\text{dim}(V)$ will always be $b$, regardless of what the rank of $D$ is. Feb 28, 2015 at 7:25