# 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!

## migrated from cs.stackexchange.comNov 8 '15 at 17:15

This question came from our site for students, researchers and practitioners of computer science.

• This looks like a question of pure mathematics. What insight do you expect computer scientists to have on this question that a mathematician wouldn't have? – David Richerby Nov 8 '15 at 10:28
• As David Richerby says, this looks like a pure math question. While we don't have an absolute policy against pure math questions, we do expect that if they're asked here they should have a good reason why they need to be answered from a computer science perspective and should explain in the question what that is, and I'm not seeing any of that here. – D.W. Nov 8 '15 at 17:14
• I think you want to require that your set $S$ is not empty, otherwise you will not be able to have this as an $\iff$ statement. – Morgan Rodgers Nov 9 '15 at 15:09

Some hints:

1. The determinant is $0$, so there is some vector $\mathbf{x}$ with $A \mathbf{x} = 0$.
2. Since all of your calculations are done $\bmod{2}$, your vector $\mathbf{x}$ can be assumed to be a $0/1$ vector.
3. 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.
4. 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.
5. 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.

Hint: The determinant of $A$ vanishes iff there is a non-zero vector $x$ such that $Ax=0$.

• Ok , but who is this vector $x$ and how could this helps me in proving that $\exists S \subseteq V$ such that $|v_{ext} \cap S|$ is an even number , $\forall$ v $\in V$ – penguina Nov 7 '15 at 12:07
• @penguina That's for you to answer. – Yuval Filmus Nov 7 '15 at 12:43

Another hint: consider the special case $S=\emptyset$.

• Doesn't $S = \emptyset$ provide a counterexample to the claim (when paired with a nonsingular $A$)? My guess was that $S = \emptyset$ needed to be excluded in the statement. – Morgan Rodgers Nov 9 '15 at 17:28