So I have encountered the following fact:
Let $G$ be a $d$-regular graph with adjacency eigenvalues $\lambda_1\geq…\geq\lambda_n$. Then its complement graph $\bar{G}$ has eigenvalues $n-1-\lambda_1,-(\lambda_2+1),…,-(\lambda_n+1)$.
The proof uses the fact that $A(\bar{G})=J-A(G)-I$, where $J$ is the matrix with all ones. So if $v_i$ is an eigenvector of $\lambda_i$, then $A(\bar{G})v_i=Jv_i-A(G)v_i-v_i$. If $i=1$, then since $G$ is regular, $v_1$ must be the vector of all ones, hence $Jv_1=nv_1$.
But for $i>1$, then does the equation $A(\bar{G})v_i=Jv_i-A(G)v_i-v_i=Jv_i-\lambda_iv_i-v_i=-(\lambda_i+1)v_i$ imply that $Jv_i=0$? If it does, then I can't see why it is true.
Best Answer
Yes, $Jv_i=0$ for all $i>1$. This is because, the matrix of $1$s has only one nonzero eigenvalue, $n$. Thus, since we have already covered its eigenvalue in $v_1$, and since a symmetric matrix has all independent eigenvectors, which are orthogonal to each other, therefore the vectors $v_i$ for $i>1$ are in the null space of $A(\overline{G})$, whence $Jv_i=0$.