Determinant of Adjacency Matrix is null Let be $D=(V,E)$ . Prove the determinant of its adjacency matrix , $det(A) = 0$ $\iff$ $\exists S \subseteq V $ (nonempty) such that $|v_{ext} \cap S|$ is an even number , $\forall $ v $\in V$ . $v_{ext}$ denotes the nodes $u$ such that $vu \in E$.
Also , D may have loops (i.e $\exists$ $A_{uu} =1$). All operations are made in $GF(2)$.
I have tried the direct implication in this way : if $det(A) = 0$ , it means that the vectors of $A$ are not linearly independents. But what`s the next step ?
Thanks!
 A: Hint: The determinant of $A$ vanishes iff there is a non-zero vector $x$ such that $Ax=0$.
A: Another hint: consider the special case $S=\emptyset$.
A: Some hints: 


*

*The determinant is $0$, so there is some vector $\mathbf{x}$ with $A \mathbf{x} = 0$.  

*Since all of your calculations are done $\bmod{2}$, your vector $\mathbf{x}$ can be assumed to be a $0/1$ vector.

*Again, since your calculations are done $\bmod{2}$, $A \mathbf{x} = 0$ means that, if you multiply $A$ times this vector using integers (all numbers in the matrix and vector are either $0$ or $1$), you will get an even number.

*Since $\mathbf{x}$ contains $0$ and $1$s, and has the same number of entries as your graph has vertices, you can consider a relation ship between $\mathbf{x}$ and a subset $S \subset V$ by interpreting your $0$s and $1$s in a certain way.

*The entries of $A \mathbf{x}$ are the products of the rows of $A$ with $\mathbf{x}$; the rows of $A$ are each associated with a vertex $v \in V$ in a natural way.

