Suppose you have a real positive definite matrix $A$ who eigenvalues are $\lambda_{1} \leq \lambda_{2} \leq \ldots \leq \lambda_{n}$. I am interested in bounding from below $\lambda_{2}-\lambda_{1}$. (It is known that $\lambda_{1}$ is simple). Are there any known methods for this kind of problem?
$\begingroup$
$\endgroup$
5
asked Oct 22, 2012 at 10:36
-
$\begingroup$ Do you have any other information about A? As stated, the difference that you want to bound can be made arbitrarily small. $\endgroup$– Vidit NandaCommented Oct 22, 2012 at 11:19
-
$\begingroup$ Well, $A$ is in fact a signless Laplacian of a graph. $\endgroup$– Felix GoldbergCommented Oct 22, 2012 at 11:37
-
1$\begingroup$ Searching google for "arbitrarily small spectral gap" produces this paper: <www.mis.mpg.de/fileadmin/jjost/abj21-6-04.pdf> which claims to construct graphs of arbitrarily small spectral gap given mild conditions on the degrees of the vertices. What is your starting point? If you know each entry of $A$ then you can presumably compute the eigenvalues and hence the gap. On the other hand if you want a theorem that bounds the gap for some general $A$, then there is no hope without more assumptions on the graph. $\endgroup$– Vidit NandaCommented Oct 22, 2012 at 12:43
-
1$\begingroup$ One could get bounds depending on some feature of $A$. For instance, we all know that $a^2+b^2$ can get arbitrarily small for positive $a$ and $b$, but nevertheless it is interesting to discover the bound $2ab\leq a^2+b^2$. $\endgroup$– Federico PoloniCommented Oct 22, 2012 at 13:50
-
$\begingroup$ Vidit Nanda, OP is talking about the signless Laplacian, you are talking about the usual Laplacian, it seems. Their spectrum is quite different. For instance, it is known that the multiplicity of 0 as an eigenvalue of the signless Laplacian agrees with the number of connected components that are bipartite. In other words, if the graph is bipartite and connected, then OP's question simply reads: "Are there bounds on the second smallest eigenvalue?" $\endgroup$– Delio MugnoloCommented Oct 25, 2013 at 9:13
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
You mention that $A$ is the Laplacian of a graph. The field of spectral graph theory is well established, and I think there are several techniques that can be used to bound the spectral gap of a graph Laplacian for an undirected weighted graph.
Perhaps the most straightforward is known as Cheeger's inequality which controls the spectral gap, $\lambda_2 - \lambda_1$ by the Cheeger constant of the graph. See the wikipedia entry for Cheeger constant: http://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory)
If you might also consider trying a Log sobolev inequality: http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aoap/1034968224
I hope this helps.
-
$\begingroup$ But I am interested in the signless Laplacian - there is a Cheeger-type result for them (Desai & Rao, 1994) but I haven't seen anything for the gap. Thanks anyway! $\endgroup$ Commented Oct 25, 2013 at 12:32
$\begingroup$
$\endgroup$
1
There are many articles on spectral theory for signless Laplacians $Q$, but the most complete is as far as I know Towards a spectral theory of graphs based on the signless Laplacian, II
In that paper, which is three years old, Cvetkovic and Simic point out why in their opinion not the second smallest is important, but the second largest $Q$-eigenvalue is important (hint: it corresponds to the spectral gap). Most researchers seem to share their opinion, because as far as I know the answer to your question is unknown.
The best available piece of information is, to my knowledge, the bound on the smallest $Q$-eigenvalues based on the largest (signed) Laplacian eigenvalue and the maximal and minimal degrees of the graph that is presented in Bipartite subgraphs and the signless laplacian matrix.
-
$\begingroup$ Thanks - I am familiar with these papers, though, and with this one too: arxiv.org/abs/1307.7749 :) $\endgroup$ Commented Oct 25, 2013 at 12:30