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$.

  • $\begingroup$ That's just it. Thanks. $\endgroup$ – David Molano Jan 27 at 21:34

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.