5
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ What is the NOT operator? $\endgroup$
    – Dzoooks
    Jun 5, 2018 at 18:35
  • $\begingroup$ @Dzoooks Sorry about that, I've clarified this in the first paragraph. It flips $0$s and $1$s. $\endgroup$
    – NNN
    Jun 5, 2018 at 18:38
  • $\begingroup$ 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! $\endgroup$
    – Dzoooks
    Jun 5, 2018 at 18:40
  • $\begingroup$ I'm discussing binary matrices, so only $0$ and $1$. $\endgroup$
    – NNN
    Jun 5, 2018 at 18:42
  • 1
    $\begingroup$ The sum is rank 1, so you can shift the rank by 1 or have it the same, but that's it. $\endgroup$
    – fedja
    Jun 5, 2018 at 18:42

2 Answers 2

6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This makes sense. Very clever! Thank you for your answer. $\endgroup$
    – NNN
    Jun 6, 2018 at 13:37
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .