# Relationship between rank of binary matrix and the NOT operator

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?

• What is the NOT operator? – Dzoooks Jun 5 '18 at 18:35
• @Dzoooks Sorry about that, I've clarified this in the first paragraph. It flips $0$s and $1$s. – Alex Jun 5 '18 at 18:38
• What does it do to numbers which are not 0 or 1? Are entries of the matrices you're considering only 0 or 1? There are only 16 2 $\times$ 2 matrices with entries as 0's or 1's. Write them down! – Dzoooks Jun 5 '18 at 18:40
• I'm discussing binary matrices, so only $0$ and $1$. – Alex Jun 5 '18 at 18:42
• The sum is rank 1, so you can shift the rank by 1 or have it the same, but that's it. – fedja Jun 5 '18 at 18:42

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$.
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$$