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.

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

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.