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$ Commented 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$ Commented 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$ Commented Jun 5, 2018 at 18:40
  • $\begingroup$ I'm discussing binary matrices, so only $0$ and $1$. $\endgroup$ Commented 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$ Commented Jun 5, 2018 at 18:42

2 Answers 2

Reset to default
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$ Commented 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.