Boundaries of the eigenvalues of a symmetric matrix (or of its Lapacian)

Question

Given the adjacency matrix $A_{ij}$ of a graph with $N$ vertices and $M$ links (or any binary symmetric matrix of size $N \times N$), is it possible to establish lower and upper boundaries of its eigenvalues? I mean, do $N$ and $M$ determine the lowest and the largest possible eigenvalues of the matrix?

In other words, let $L$ be the Lapacian of $A_{ij}$. We know that its eigenvalues obbey the following: $\lambda_1 = 0 \leq \lambda_2 \leq \lambda_3 \leq \ldots \leq \lambda_N$. The lowest eigenvalue is always $\lambda_1 = 0$ and hence, the eigenvalues of $L$ have a lower bound. Is there an upper bound for $\lambda_N$ that depends only on the size $N$ of the graph and/or on $M$?

Stated yet in another manner. Does anyone know a graph $G'$ whose $\lambda'_N$ is largest than the $\lambda_N$ of any other graph of the same size $N$ and/or number of links $M$?

Thank you!

Answer 1

There are several notions of Laplacian for graphs. For instance, there is the normalized Laplacian, the classical Laplacian and Laplacians with boundary conditions as the Dirichlet Laplacian and so on. Assuming that you are taking about the classical Laplacian then its eigenvalues are $$ 0=\lambda_1\leq \lambda_2\leq \ldots\leq\lambda_{n} $$ where $n$ is the number of nodes. Typically it is $\lambda_2$ the eigenvalue that gives the most information about the graph (like expanding properties, connectivity, isoperimetric properties, etc). For instance, $\lambda_2>0$ iff the graph is connected.

Here are a few known results:

• [Fiedler] $\lambda_2\leq \frac{n}{n-1}\min\{d(v):v\in V\}$ where $d(v)$ is the degree of the node $v$.

• [Anderson and Moreley] The maximum eigenvalue satisfies $$ \lambda_n\leq\max\{ d(u)+d(v):uv\in E\}. $$ If the graph $G$ is connected then the equality holds iff the graph is bipartite.

• [Kelmans] If the graph is simple (no multiple edges or loops) then $\lambda_n\leq n$ with equality iff the complement of $G$ is not connected.

• $\sum_{i}^{n}{\lambda_i}=2m=\sum_{v}{d(v)}$ where $m$ is the number of edges in $G$.

• [Fiedler] $\lambda_{n}\geq \frac{n}{n-1}\max\{d(v):v\in V\}$.

The second and last bullet give you lower and upper bounds for the maximum eigenvalue in terms of the degree of the nodes. If the graph is regular of course much more can be said.

I hope it helps!

Answer 2

Let $L(G)$ denote the Laplacian of $G$. Then $L(G)$ is positive semidefinite. If $\bar{G}$ denotes the complement of $G$ then $$ L(K_n) = L(\bar{G}) + L(G) $$ and so $L(K_n)-L(G)$ is positive semidefinite. Hence the largest eigenvalue of $L(K_n)$ is an upper bound on the largest eigenvalue of $L(G)$. Since $L(K_n)=nI-J$ (where $J$ is all-ones matrix), the eigenvalues of $L(K_n)$ are $n$ with multiplicity $n-1$ and 0, and so $n$ is a sharp upper bound on the largest eigenvalue of $L(G)$.

Answer 3

Lost of work both for Laplacian an adjacency matrix eigenvalues bound has been done by Vladimir Nikiforov, I suggest to take a look hat his two main papers on arxiv.org

Bounds on graph eigenvalues I and Bounds on graph eigenvalues II

Piero Giacomelli

Answer 4

There's a whole area of algebraic graph theory, but without any information on a the graph, I can't remember anything graph specific right now

What is relevant is Gershgorin circle theorem

Which for example would mean that a undirected graph without loops, the adjacency matrix would have eigenvalues smaller than the maximum degree of a vertex, that is |M-1|. And for the Laplacian we should get something like 2|M|.