My situation is as follows: I have a symmetric positive semi-definite matrix L (the Laplacian matrix of a graph) and a diagonal matrix S with positive entries $s_i$.
There's plenty of literature on the spectrum of $L$, and I'm most interested in bounds on the second-lowest eigenvalue, $\lambda_2$.
Now the thing is that I'm not using the Laplacian $L$ itself, but rather the 'generalized' Laplacian $L S^{-1}$. I still need results on its second lowest eigenvalue $\lambda_2$ (note that the lowest eigenvalue of the Laplacian, both the normal and the generalized, is 0).
My question is: Are there some readily available theorems/lemmata that allow me to relate the spectra of $L$ and $L S^{-1}$?
EDIT: Of course, $LS^{-1}$ is not a symmetric matrix any more, so I'm talking about its right-eigenvectors. The eigenvalues of $LS^{-1}$ are the same as those of
$S^{-1/2} L S^{-1/2}$ which again is a symmetric positive semi-definite matrix, so I know an eigenbasis actually exists.
Best Answer
Let $\mu_i$ be the eigenvalues of $L S^{-1}$. Then $(\lambda_i, \mu_i, s_i)$ obey the multiplicative version of Horn's inequalities. The most basic of these, if $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$ and $s_1^{-1} \geq \cdots \geq s_n^{-1}$ and $\mu_1 \geq \mu_2 \geq \cdots \geq \mu_n$ is that $$\mu_{i+j-1} \leq \lambda_i s_j^{-1} \ \mbox{and}\ \mu_{i+j-n} \geq \lambda_i s_j^{-1}.$$
Proof: Let $X=\sqrt{L}$ and $T=\sqrt{S^{-1}}$. So the singular values of $X$ and $T$ are $\sqrt{\lambda_i}$ and $\sqrt{s_i^{-1}}$. Then $\sqrt{\mu_i}$ are the singular values of $XT$. By a result of Klyachko (Random walks on symmetric spaces and inequalities for matrix spectra, Linear Algebra and its Applications, Volume 319, Issues 1–3, 1 November 2000, Pages 37–59), the singular values of a product obey the exponentiated version of Horn's inequalities.