5
$\begingroup$

The adjacency matrix of a nonempty (undirected) graph has a strictly positive largest eigenvalue $\lambda_\max$. A very easy upper estimate for it can be obtained directly by Gershgorin's theorem: $$ \lambda_{\max}\le \Delta\ , $$ where $\Delta$ is the maximal degree of the graph. Are any further estimates known?

And are there known lower estimates on the lowest eigenvalue $\lambda_\min$?

$\endgroup$
  • $\begingroup$ Just making sure: are you interested in lower bounds for $\lambda_{\min}$ or for $|\lambda_{\min}|$? $\endgroup$ – Felix Goldberg Oct 9 '14 at 9:15
  • $\begingroup$ $\lambda_\min $ $\endgroup$ – Delio Mugnolo Oct 9 '14 at 9:24
5
$\begingroup$

A classic estimate is due to Constantine:

$$ \lambda_{\min} \geq -\sqrt{\lceil \frac{n}{2} \rceil \lfloor \frac{n}{2} \rfloor}. $$

If $m$ is the number of edges, then $$ \lambda_{\min} \geq - \sqrt{m}. $$

A common generalization is $$ \lambda_{\min} \geq -\sqrt{MaxCut(G)}, $$ where $MaxCut(G)$ is the size of a maximal bipartite subgraph.

You can find these results, with references, in the 2008 paper by Bell et al.. There are more complicated results as well, in particular using the eigenvector.

If you would like to discuss such topics, I am always interested.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks a lot! by now i have found a further upper estimate in a paper by brualdi and hoffman, but i am still quite surprised that so little is known about the adjacency matrix - as opposite to the laplacian, in particular. $\endgroup$ – Delio Mugnolo Oct 10 '14 at 11:27
  • $\begingroup$ @DelioMugnolo Which paper would that be? Thanks. $\endgroup$ – Felix Goldberg Oct 12 '14 at 14:17
  • $\begingroup$ On the Spectral Radius of (0,1)-Matrices, LAA 1985 $\endgroup$ – Delio Mugnolo Oct 13 '14 at 10:55
  • $\begingroup$ 2½ years have gone and I've learned a bit on this topic. Now I've started working myself on a related topic (arxiv.org/abs/1702.05253) and can appreciate better your suggestions. In particular, I was wondering whether any of your suggested estimates can be tuned a bit in the specific case of line graphs, where $\lambda_{\rm min}\ge 2$ anyway. $\endgroup$ – Delio Mugnolo Apr 27 '17 at 7:34
0
$\begingroup$

Not very different, but another possible estimate is the following: if you know that $Av\leq tv$ (elementwise) for some nonnegative (elementwise) vector $v$ and real $t$, then $\lambda_\max \leq t$ (proof: left-multiply by the left Perron vector. Irreducibility is needed, otherwise you need $v>0$). This is essentially a "weighted Gershgorin estimate", since Gershgorin's theorem corresponds to the version with $v$ the vector of all ones.

Note that both estimates can be tight, if $v$ is the Perron eigenvector.

You may get other estimates via matrix norms: $\lambda_\max \leq ||A||$. Computing the Euclidean norm is as difficult as computing the maximum eigenvalue, so it is probably unhelpful. This leaves as candidates the Frobenius norm (which is always larger than the Euclidean norm, but at least it is easily computable) and the $1$ norm (which is the Gershgorin bound on $A^T$ --- so yes, I am basically just stating Gershgorin variants and easy stuff in this answer, sorry).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ plus, $A^T=A$ anyway :) $\endgroup$ – Delio Mugnolo Oct 9 '14 at 9:13
  • $\begingroup$ Hmm, right. :) What I wrote applies to a generic nonsymmetric nonnegative matrix. Then, in your case, moreover, the 2-norm bound is even more useless, since the 2-norm is $\lambda_\max$. $\endgroup$ – Federico Poloni Oct 9 '14 at 9:20

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.