Take the 2-minute tour ×
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|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
add comment

2 Answers 2

up vote 4 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, the singular values of a product obey the exponentiated version of Horn's inequalities.

share|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
add comment

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|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
add comment

Your Answer

 
discard

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.