Relationship between rank of binary matrix and the NOT operator

Question

Let $A$ be a binary matrix. I'm looking for any information about the relationship between the rank of $A$ and the rank of NOT$(A)$, where NOT replaces all $0$s with $1$s, and vice-versa.

What I know

• These ranks can sometimes be equal. For example, applying the NOT operator to the identity matrix returns another full rank matrix.

• They can sometimes not be equal. For example, the matrix \begin{equation*} A= \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \end{equation*} has rank $2$, but \begin{equation*} \text{NOT}(A)= \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} \end{equation*} has rank $1$.

My questions

Are there known relationships between the two ranks?

Answer 1

If $E$ is the $n \times n$ matrix of all $1$'s, $NOT(A) = E - A$. Now $E$ has rank $1$, and in general $$\text{rank}(A)-\text{rank}(B) \le \text{rank}(A+B) \le \text{rank}(A) + \text{rank}(B)$$ Thus the rank of $NOT(A)$ differs from that of $A$ by at most $1$.

You gave an example where the ranks are equal, and one where $\text{rank}(NOT(A)) = \text{rank}(A) - 1$; interchange $A$ and $NOT(A)$ and you have an example where $\text{rank}(NOT(A)) = \text{rank}(A) + 1$.

Answer 2

It may help to notice that $$ \operatorname{not} \begin{bmatrix} x_{11} & x_{12}\\ x_{21} & x_{22}\\ \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 1\\ \end{bmatrix} - \begin{bmatrix} x_{11} & x_{12}\\ x_{21} & x_{22}\\ \end{bmatrix} $$

and $\operatorname{rank}\begin{bmatrix}1\end{bmatrix}_{nn} = 1$.

since $\operatorname{rank}(A+ B) \le \operatorname{rank}(A) + \operatorname{rank}(B)$, you can tell that $$\operatorname{rank}(\operatorname{not}(A)) \le \operatorname{rank}(A) + 1$$ and also $$\operatorname{rank}(A) = \operatorname{rank}(\operatorname{not}(\operatorname{not}(A))) \le \operatorname{rank}(\operatorname{not}(A)) + 1$$ which means $$\operatorname{abs} \left(\ \operatorname{rank}(A) - \operatorname{rank}(\operatorname{not}(A)) \ \right) \le 1$$