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$?

Improve this question
$\endgroup$
2
  • $\begingroup$ Just making sure: are you interested in lower bounds for $\lambda_{\min}$ or for $|\lambda_{\min}|$? $\endgroup$
    – Felix Goldberg
    Oct 9, 2014 at 9:15
  • $\begingroup$ $\lambda_\min $ $\endgroup$
    – Delio Mugnolo
    Oct 9, 2014 at 9:24

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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, 2014 at 11:27
  • $\begingroup$ @DelioMugnolo Which paper would that be? Thanks. $\endgroup$
    – Felix Goldberg
    Oct 12, 2014 at 14:17
  • $\begingroup$ On the Spectral Radius of (0,1)-Matrices, LAA 1985 $\endgroup$
    – Delio Mugnolo
    Oct 13, 2014 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, 2017 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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ plus, $A^T=A$ anyway :) $\endgroup$
    – Delio Mugnolo
    Oct 9, 2014 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, 2014 at 9:20

Your Answer

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

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