Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|cite|improve this question
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

2 Answers 2

up vote 6 down vote accepted

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.

share|cite|improve this answer
This looks like what I'm after. I'll give it a bit more thought and maybe come back with more questions :) EDIT: Yes, exactly what I'm after. Thanks very much. :) – Lagerbaer Feb 4 '11 at 0:55
Hi, this is an old post I know, but the link to Klyachko's paper is dead - is there any chance of an updated link, or a bibliographic reference? – Nathaniel Nov 26 at 3:49
@Nathaniel Thanks for pointing it out. Added both, though the link may paywall for some people. – David Speyer yesterday

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.