Sum of Ranks of Two Complementary Matrices

Question

Suppose we have a binary matrix $A$, i.e, all the elements of $A$ are either $0$ or $1$. Let $B$ be the complementary matrix of $A$, i.e., $$ B_{ij}= \begin{cases} 1,\textrm{ if }A_{ij}=0;\\ 0,\textrm{ if }A_{ij}=1. \end{cases} $$ Then $A+B$ is a matrix with all entries being $1$. Suppose $\textrm{rank}(A)=r$, what is $\textrm{rank}(A)+\textrm{rank}(B)$?

Answer 1

So the question is : what is rank(B) ?

The answer is : we cannot know just from the value of rank(A) .

For example take the following binary matrices :

\begin{pmatrix} 1 & 1 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{pmatrix} And \begin{pmatrix} 1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1 \end{pmatrix}

Both these matrices have rank=1, but their complementary matrices have rank=1 and 0 respectivly.

Answer 2

There is not enough information to tell.

For example, let $s=\operatorname{rank} B$. If $n=2$, we can take

• $A=\begin{bmatrix} 1&1\\0&0\end{bmatrix}$, then $r+s=2$

• $A=\begin{bmatrix} 1&0\\0&0\end{bmatrix}$, then $r+s=3$

• $A=\begin{bmatrix} 1&0\\0&1\end{bmatrix}$, then $r+s=4$

Similarly, with $n=3$:

• $A=\begin{bmatrix} 1&0&0\\0&0&0\\0&0&0\end{bmatrix}$, then $r+s=3$
• $A=\begin{bmatrix} 1&0&1\\0&1&0\\0&0&0\end{bmatrix}$, then $r+s=4$
• $A=\begin{bmatrix} 1&0&0\\0&1&0\\0&0&0\end{bmatrix}$, then $r+s=5$
• $A=\begin{bmatrix} 1&0&0\\0&1&0\\0&0&1\end{bmatrix}$, then $r+s=6$

Answer 3

You can't really say much about it, there is no formula.

Here is why

Consider the case $A = I = \mathbb{1}_{n \times n}$ so that \begin{equation} B_{i,j } = \begin{cases} 0 & \text{if } i =j \\ 1 & \text{if } i \neq j \\ \end{cases} \end{equation}

Then $\text{rank}(A) = \text{rank}(B) = n =$ "full rank."

Likewise consider the case \begin{equation} B_{i,j } = \begin{cases} 1 & \text{if } i =j =1 \\ 0 & \text{o.w. } \\ \end{cases} \end{equation} then both $A$ and $B$ have a really small rank.