Si el factor determinante de esta matriz no es nulo:

Question

Que sea $D=(V,E)$. Ser el factor determinante de su matriz de adyacencia, $det(A) = 0$ $\iff$ $\exists S \subseteq V $ (no vacío) tal que $|v_{ext} \cap S|$ es un número par, $\forall $v $\in V$. $v_{ext}$ indica el % de nodos $u$tal que $vu \in E$. También, D puede tiene lazos (i.e $\exists$ $A_{uu} =1$). Todas las operaciones se realizan en $GF(2)$.

He probado la implicación directa de esta manera: Si $det(A) = 0$, que significa que los vectores de $A$ no son linealmente independientes. Pero, ¿cuál es el siguiente paso?

¡Gracias!

Answer 1

Sugerencia: El determinante de la $A$ desaparece iff hay un vector distinto de cero $x$ tal que $Ax=0$.

Answer 2

Otra sugerencia: considerar el caso especial $S=\emptyset$.

Answer 3

Algunos consejos:

1. El factor determinante es $0$, por lo que hay algunos vectores $\mathbf{x}$$A \mathbf{x} = 0$.
2. Ya que todos sus cálculos se hacen a $\bmod{2}$, su vector de $\mathbf{x}$ puede ser asumida como un $0/1$ vector.
3. De nuevo, ya que los cálculos se realizan $\bmod{2}$, $A \mathbf{x} = 0$ significa que, si se multiplica $A$ veces este vector usando números enteros (todos los números en la matriz y vector son o $0$ o $1$), obtendrá un número par.
4. Desde $\mathbf{x}$ contiene $0$ $1$s, y tiene el mismo número de entradas que su gráfica tiene vértices, se puede considerar una relación de buques entre el $\mathbf{x}$ y un subconjunto $S \subset V$ mediante la interpretación de su $0$s y $1$s de una cierta manera.
5. Las entradas de $A \mathbf{x}$ son los productos de las filas de $A$$\mathbf{x}$; las filas de $A$ cada uno asociado con un vértice $v \in V$ de una manera natural.