Given a symmetric $n\times n$ matrix $A$ where each element is either 1 or 0, and all diagonal elements are 1, I'm trying to find whether there is an $n$ dimensional vector $x$ whose elements are 0 or 1 such that all elements of $Ax$ are equivalent to $1$ modulo 2.
My initial guess is that such vector should exist for any matrix $A$, but I'm unable to prove it. I'm also curious which of the requirements on $A$ (if any) can be removed.
The answer is that yes, every matrix $A$ as such has a solution as desired, I have found the solution with a short and nice proof in Arxiv: https://arxiv.org/abs/1206.2973
What's interesting, is that the context in which the proof is given is the same context which brought me to this question at first, which is to solve the lights out puzzle for a general graph.
In the article they prove the following claim: Given a symmetric $n\times n$ matrix $A$ over $\mathbb{F}_2$ then the diagonal of the matrix is in the range of the matrix. As the diagonal elements are all $1$ this exactly solves our problem.
The proof is as follow: It works by showing that $d$, the vector of diagonal elements, is orthogonal to all vectors in the null space of $A$. Given an element $x$ such that $Ax=0$, it assumes without loss of generality that $x=(1,\dots,1,0,\dots,0)$ where $1$ appears $m+1$ times, and then as the result is $0$, the $m+1$th row must be the sum of the first $m$, this gives the equalities for $1\leq j \leq m$
$$a_{jj}+\sum_{i=1,i\neq j}^ma_ij=a_{j,m+1}$$
where then
$$a_{m+1,m+1}=\sum_{i=1}^ma_{m+1,i}$$
and from symmetry
$$\sum_{i=1}^ma_{m+1,i} = \sum_{j=1}^ma_{j,m+1}=\sum_{j=1}^{m}a_{jj}+\sum_{j,i=1,j\neq i}^ma_{ij}$$
where the second summand is 0 as each element cancels out with it's transpose (again from symmetry), showing us that
$$a_{m+1,m+1} = \sum_{j=1}^{m}a_{jj}$$
but this exactly means that $x\cdot d = \sum_{j=1}^{m+1}a_{jj}=0$ as we required.