Welcome to MathOverflow

Question

2

I have a weighted Laplacian matrix $L$ of a strongly connected directed graph and a diagonal matrix $D$ with positive entries. Since the graph is directed, $L$ is non-symmetric real. Further, since the graph is strongly connected, $L$ has a simple zero eigenvalue and all its nonzero eigenvalues have positive real part. Is it possible to establish a relation e.g., a bound, between the eigenvalues of $L$ and those of the product $DL$?

Thanks a lot!

edited Mar 3 at 14:12

asked Mar 3 at 14:03

FS
21●2

1

hardly, it seems. Think of the Laplacian of the oriented 2-cycle, i.e., $L:=\begin{pmatrix}1 & 1\\ 1 & 1\end{pmatrix}$ and take any diagonal matrix $D:=\begin{pmatrix}a & 0\\ 0 & b\end{pmatrix}$. Then $L$ will always have eigenvalues $0,2$, but the eigenvalues of $D\cdot A$ are $0,a+b$. – Delio Mugnolo Mar 3 at 17:10

Sorry, I meant −1 on the off-diagonal entries of L, but my computations still hold. So, do you possibly want to make more precise what kind of estimates are you hoping for? – Delio Mugnolo Mar 3 at 17:57

Hi Delio, thanks for the reply. Let $\sigma(L)$ respectively $\sigma(DL)$ denote the spectrum of $L$ respectively $DL$. Let $D_{ii}$ denote the positive diagonal entries of $D$. I am hoping for an estimate of the form $\sigma(DL)\leq max_i(D_{ii})\sigma(L)$. – FS Mar 3 at 18:12

I see. So my example would indeed fit your scheme. – Delio Mugnolo Mar 3 at 18:31

Yes, absolutely. – FS Mar 3 at 19:47

show 1 more comment

Felix Goldberg · Answer 1 · 2013-03-04 10:52:14Z UTC

1

For undirected graphs, Theorem 2.2 in this paper might help a bit.

UPDT: Let $G$ be a weighted undirected graph with Laplacian matrix $L$. Let $D$ be a positive diagonal matrix. Let $d=min(diag(D))$ and let $\Delta$ be the maximum diagonal entry of $L$. Let $i$ be the weighted isoperimetric number of $G$. Then: $$ \lambda_{2}(DL) \geq d (\Delta-\sqrt{\Delta^{2}-i^{2}}) $$

edited Mar 4 at 10:52

answered Mar 4 at 0:21

Felix Goldberg
2,385●5●12

	Hi Felix, could you summarize the result for those who do not have access to scidirect? Thanx! – S. Sra Mar 4 at 0:28
	Isn't that paper on graphs - as opposed to digraphs? – Delio Mugnolo Mar 4 at 1:45
	@DelioMugnolo: Indeed, and I indicated so in my answer. However, perhaps the OP could still derive some insights from it. – Felix Goldberg Mar 4 at 10:47
	@Suvrit: I added the statement of the theorem. But actually - sciderect have recently put all the old paper of many journals, including LAA, online for free - just try it :) – Felix Goldberg Mar 4 at 11:20

Eigenvalues of directed Laplacian matrix $L$ and $DL$, where $D$ is a diagonal matrix with positive entries

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.