Relación entre el rango de una matriz binaria y el operador NOT

Question

Sea $A$ sea una matriz binaria. Estoy buscando cualquier información sobre la relación entre el rango de $A$ y el rango de NOT $(A)$ donde NOT sustituye a todos $0$ s con $1$ s, y viceversa.

Lo que sé

• En ocasiones, estos rangos pueden ser iguales. Por ejemplo, aplicando el operador NOT a la matriz identidad se obtiene otra matriz de rango completo.

• A veces pueden no ser iguales. Por ejemplo, la matriz \begin{equation*} A= \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} \end{equation*} tiene rango $2$ pero \begin{equation*} \text{NOT}(A)= \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} \end{equation*} tiene rango $1$ .

Mis preguntas

¿Existen relaciones conocidas entre los dos rangos?

Answer 1

Si $E$ es el $n \times n$ matriz de todos los $1$ 's, $NOT(A) = E - A$ . Ahora $E$ tiene rango $1$ y en general $$\text{rank}(A)-\text{rank}(B) \le \text{rank}(A+B) \le \text{rank}(A) + \text{rank}(B)$$ Así, el rango de $NOT(A)$ difiere de la de $A$ como máximo $1$ .

Has dado un ejemplo en el que los rangos son iguales, y otro en el que $\text{rank}(NOT(A)) = \text{rank}(A) - 1$ intercambio $A$ y $NOT(A)$ y tienes un ejemplo donde $\text{rank}(NOT(A)) = \text{rank}(A) + 1$ .

Answer 2

Puede ser útil tener en cuenta que $$ \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} $$

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

desde $\operatorname{rank}(A+ B) \le \operatorname{rank}(A) + \operatorname{rank}(B)$ se puede decir que $$\operatorname{rank}(\operatorname{not}(A)) \le \operatorname{rank}(A) + 1$$ y también $$\operatorname{rank}(A) = \operatorname{rank}(\operatorname{not}(\operatorname{not}(A))) \le \operatorname{rank}(\operatorname{not}(A)) + 1$$ lo que significa $$\operatorname{abs} \left(\ \operatorname{rank}(A) - \operatorname{rank}(\operatorname{not}(A)) \ \right) \le 1$$