Let $A$ be a symmetric $(0,1)$-matrix whose row sum is $r.$ Suppose I have a $(0,1)$ vector $v$ such that $$Av = \vec{1} - v.$$
By taking the vector $$u = \vec{1} - (r+1)v$$ we see that $$Au = A (\vec{1} - (r+1)v) = r\vec{1} - (r+1)(\vec{1} - v) = -1u,$$ thus implying that $-1$ is an eigenvalue of $A.$
This is of course easy to understand but I am having a subtle mental block in understanding what lead to the choice of $u?$ It seems to me that there has to be a more general idea following the above choice. Hence my question is
Is there another way to look at this? Is there a more general trick that, given some identity for $Av$ allows one to construct an eigenvector for $A$ in terms of $v.$
Note. The above argument shows that a $r$-regular graph with a perfect code (aka efficient dominating set) has $-1$ as the eigenvalue of its adjacency matrix, hence why the graph theory tag.
You know that $$ Ae = re $$ with $e=(1,\dots,1)^T$. And there is $v$ such that $$ Av = e - v. $$ So $v$ is almost an eigenvector. It seems that $v$ differs from an eigenvector by a multiple of $e$: $$ A(v + se) = e-v + sre, \quad s\in \mathbb R. $$ Now adjust $s$ such that $$ v+se = \lambda (e-v+sre) $$ with $\lambda\in\mathbb R$ being the unknown eigenvalue. The assumptions imply $v\ne e$. From inspection (look at the factors in front of $v$) it follows that $\lambda=-1$.
The we can compute $s=-\frac1{r+1}$. This implies $$ v - \frac1{1+r}e$$ or equivalently $$ e-(1+r) v$$ are eigenvectors of $A$.
So the intuition about $v+se$ being an eigenvector is justified.