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$
  • $\begingroup$ What is the NOT operator? $\endgroup$ – Dzoooks Jun 5 '18 at 18:35
  • $\begingroup$ @Dzoooks Sorry about that, I've clarified this in the first paragraph. It flips $0$s and $1$s. $\endgroup$ – Alex Jun 5 '18 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 '18 at 18:40
  • $\begingroup$ I'm discussing binary matrices, so only $0$ and $1$. $\endgroup$ – Alex Jun 5 '18 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 '18 at 18:42
5
$\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$
  • $\begingroup$ This makes sense. Very clever! Thank you for your answer. $\endgroup$ – Alex Jun 6 '18 at 13:37
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.