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 ?



migrated from cs.stackexchange.com Nov 8 '15 at 17:15

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

  • 2
    $\begingroup$ 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? $\endgroup$ – David Richerby Nov 8 '15 at 10:28
  • $\begingroup$ 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. $\endgroup$ – D.W. Nov 8 '15 at 17:14
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ 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$ $\endgroup$ – penguina Nov 7 '15 at 12:07
  • $\begingroup$ @penguina That's for you to answer. $\endgroup$ – Yuval Filmus Nov 7 '15 at 12:43

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

  • $\begingroup$ 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. $\endgroup$ – Morgan Rodgers Nov 9 '15 at 17:28

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.