Here is a problem listed on a book 'Algebraic Combinatorics' by Richard P.Stanley.
Let $G$ be a finite graph with at least two vertices. Suppose that for some $l \ge 1$, the number of walks of length $l$ between any two vertices $u, v$(including $u=v$) is odd.
Show that there is a nonempty subset $S$ of the vertices such that $S$ has an even number of elements and such that every vertex $v$ of $G$ is adjacent to an even number of vertices in $S$. (A vertex is adjacent to itself if and only if there is a loop at $v$.)
I really couldn't get the gist of it, so the title became quite vague as well.
What I got from it was that if $A$ is the adjacency matrix of $G$, then all components of $A^l$ is odd. I tried induction, proving the contraposition but I just got baffled. I also could understand that a graph derived from $S$ has an adjacency matrix that can fit inside $A$, but I don't know what to do afterwards.
Maybe I have to use more linear algebraic stuff or turn to combinatorial way?
Look at everything modulo $2$. The matrix $A^l$ is singular, and so for some $v$, $Av=0$. This gives the second property. The first one follows from $A^lv=0$.