10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is the significance of $LS^{-1}$? Does it have any graph-theoretic interpretation? $\endgroup$ – PrimeNumber Feb 4 '11 at 0:13
  • $\begingroup$ 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$ $\endgroup$ – Lagerbaer Feb 4 '11 at 0:52
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. :) $\endgroup$ – Lagerbaer Feb 4 '11 at 0:55
  • $\begingroup$ 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? $\endgroup$ – Nathaniel Nov 26 '15 at 3:49
  • $\begingroup$ @Nathaniel Thanks for pointing it out. Added both, though the link may paywall for some people. $\endgroup$ – David E Speyer Nov 27 '15 at 15:57
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. :) $\endgroup$ – Lagerbaer Feb 4 '11 at 0:51

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.