0

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?

grg
  • 1,017
TCS-user-23
  • 3

1 Answers1

0

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.

Brent Kerby
  • 5,539
  • Hi Brent thanks for your answer. Can you please elaborate on why dim(V)=rank(B)? I understand that set of basis for the span of columns of B counts as rank of B. But what if rank of D is more than rank of B? then should not dim(V) be equal to rank(D)? Or may be I am missing something trivial here. – TCS-user-23 Feb 28 '15 at 07:19
  • 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. – Brent Kerby Feb 28 '15 at 07:25