# Eigenvalues of adjacency matrix of a k-regular graph

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!

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.

• Thanks! So the key is J ,in general, has a common set of eigenvectors with any matrix, right? – RayyyyySun Mar 27 at 16:17
• @RayyyyySun Not with every matrix, just with those for which $(1,...,1)$ is an eigenvector, and all other eigenvectors are perpendicular to $(1,...,1)$. – M. Winter Mar 27 at 16:19
• I see, Thanks! really appreciate :) – RayyyyySun Mar 27 at 16:20