# Eigenvectors of regular graph are annihilated by matrix of $1$s

Take a simple $$k-$$regular graph (every vertex has degree $$k$$) $$G$$ and its adyacency matrix $$A$$. Then it's known that $$k$$ is one eigenvalue of $$A$$ with associated eigenvector $$u=\begin{bmatrix}1 & 1 & \cdots & 1\end{bmatrix}^T$$. Let $$\lambda_2,\dots,\lambda_{n}$$ be the remaining eigenvalues.

I want to prove that the complement $$\overline{G}$$ has the same eigenvectors, with corresponding eigenvalues $$n-k-1$$, $$-1-\lambda_2,\dots,-1-\lambda_{n}$$.

Since the adyacency matrix of $$\overline{G}$$ is $$\overline{A}=M-I-A$$ where $$M$$ is a matrix of $$1$$s, then for an eigenvector $$u$$ of $$A$$ with eigenvalue $$\lambda$$, we have $$\overline{A}u=Mu-u-Au=Mu-u-\lambda u=Mu+(-1-\lambda)u.$$

For the eigenvector $$u=\begin{bmatrix}1 & 1 & \cdots & 1\end{bmatrix}^T$$, we have $$\lambda=k$$ and $$Mu=nu$$ so in this case $$\overline{A}u=(n-1-k)u$$, so $$u$$ is also an eigenvector of $$\overline{A}$$.

For the remaining eigenvectors $$u$$, to prove the result I need to prove that $$Mu=0,$$ i.e. the sum of the components of $$u$$ is $$0$$. How can I prove that?

By the way, I found a result in Dragos book about Graph Spectra, in which they prove the characteristic polynomial $$P_{\overline{G}}$$ of $$\overline{G}$$ is $$(-1)^n\frac{x-n+r+1}{x+r+1} P_G(-x-1)$$, and in the proof they use the fact that $$Mu=0$$ for every but one eigenvector (The vector of $$1$$s) without any details, so I think I must be missing a simple argument for that.

The adjacency matrix is symmetric, so it has an orthonormal basis of eigenvectors. The first of these eigenvectors, a multiple of $$[1\;1\;\cdots\;1]$$, is orthogonal to all others, which is just the condition that the entries of any other eigenvector must sum to $$0$$.