Eigenvalues of adjacency matrix of a k-regular graph

Question

If $A_G$ is the adjacency matrix of a k-regular graph, let $B = J+xA_G$, where J is the matrix whose elements are all 1s and $x\in R$ is a scalar. If $\lambda_1\geq\lambda_2\geq \dots \geq \lambda_n$ are eigenvalues of $A_G$, how do we prove that $\underset{x\in R}{\min} \lambda_{max}(J+xA_G) = \frac{n\lambda_n}{\lambda_n-\lambda_1}$?

I know that e (the vector of all 1s) is an eigenvector of B with eigenvalue $n+x\lambda_1$, but what about the other eigenvectors? If we know other eigenvectors of B, then we can compare among them and pick the maximum. Thanks!

Answer 1

If $G$ is regular, then $J$ and $A_G$ are simultaneously diagonalizable (i.e. they have a common set of eigenvectors).

That is, the eigenvalues of $xA_G$ and $J$ (to the same eigenvectors) just add up to the eigenvalues of $B=J+xA_G$. Note that the spectrum of $J$ is $\{0^{n-1}, n^1\}$, and that the eigenvalue $n$ corresponds to the eigenvector $(1,...,1)$. The corresponding eigenvalue of $A_G$ is $k=\lambda_1$.

If $x$ is positive or only a little bit negative, then the largest eigenvalue of $B$ is $n+x\lambda_1$. But if $x$ is more negative, then at some point the largest eigenvalue of $B$ will be $0+x\lambda_n$ (note that $\lambda_n<0$). So the moment when these two values coincide is when the minimum is attained:

$$n+x\lambda_1 = x\lambda_n \quad\implies\quad x=\frac{n}{\lambda_n-\lambda_1}.$$

If you plug this into $\lambda_n x$ you found the desired value.