# Eigenvalues of product of a matrix and a diagonal matrix

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.

-
What is the significance of $LS^{-1}$? Does it have any graph-theoretic interpretation? –  PEV Feb 4 '11 at 0:13
The $1/s_i$ are node-weights. A well-known property of $L$ is that $x^T L x = \sum_{(i,j)\in E} (x_i - x_j)^2$. You can define a generalized scalar product $\langle x, y \rangle = \sum_i x_i y_i/s_i$ and then you have $\langle x, LS^{-1} x \rangle = \sum_{(i,j)\in E} (x_i/s_i - x_j/x_j)^2$ –  Lagerbaer Feb 4 '11 at 0:52

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, the singular values of a product obey the exponentiated version of Horn's inequalities.
If you are interested in the second smallest eigenvalue $\lambda_2$ of $L$, then this is just the algebraic connectivity of $G$ (i.e. $\mu = \mu(G)$). Also this paper and MO question might be relevant.
I know about $\lambda_2$ of $L$, and have a lot of interesting papers about it relating it to various properties of the graph such as its diameter or its isoperimetric number. But how does it change when I look at $L S^{-1}$? That's my question. :) –  Lagerbaer Feb 4 '11 at 0:51