2
$\begingroup$

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!

$\endgroup$
6
  • 1
    $\begingroup$ 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$. $\endgroup$ Mar 3, 2013 at 17:10
  • $\begingroup$ 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? $\endgroup$ Mar 3, 2013 at 17:57
  • $\begingroup$ 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)$. $\endgroup$
    – user31905
    Mar 3, 2013 at 18:12
  • $\begingroup$ I see. So my example would indeed fit your scheme. $\endgroup$ Mar 3, 2013 at 18:31
  • $\begingroup$ Yes, absolutely. $\endgroup$
    – user31905
    Mar 3, 2013 at 19:47

1 Answer 1

1
$\begingroup$

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(\operatorname{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 \left(\Delta-\sqrt{\Delta^{2}-i^{2}}\right) $$

$\endgroup$
4
  • $\begingroup$ Hi Felix, could you summarize the result for those who do not have access to scidirect? Thanx! $\endgroup$
    – Suvrit
    Mar 4, 2013 at 0:28
  • $\begingroup$ Isn't that paper on graphs - as opposed to digraphs? $\endgroup$ Mar 4, 2013 at 1:45
  • $\begingroup$ @DelioMugnolo: Indeed, and I indicated so in my answer. However, perhaps the OP could still derive some insights from it. $\endgroup$ Mar 4, 2013 at 10:47
  • $\begingroup$ @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 :) $\endgroup$ Mar 4, 2013 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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