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!



Eigenvalues of adjacency matrix of a k-regular graph
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.


