Boundaries of the eigenvalues of a symmetric matrix (or of its Lapacian) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T10:05:53Z http://mathoverflow.net/feeds/question/59450 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59450/boundaries-of-the-eigenvalues-of-a-symmetric-matrix-or-of-its-lapacian Boundaries of the eigenvalues of a symmetric matrix (or of its Lapacian) Gorka Zamora-López 2011-03-24T17:31:45Z 2011-03-25T13:36:03Z <p>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?</p> <p>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$?</p> <p>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$?</p> <p>Thank you!</p> http://mathoverflow.net/questions/59450/boundaries-of-the-eigenvalues-of-a-symmetric-matrix-or-of-its-lapacian/59474#59474 Answer by kastberg for Boundaries of the eigenvalues of a symmetric matrix (or of its Lapacian) kastberg 2011-03-24T20:45:28Z 2011-03-24T22:36:21Z <p>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</p> <p>What is relevant is <a href="http://en.wikipedia.org/wiki/Gershgorin_circle_theorem" rel="nofollow">Gershgorin circle theorem</a></p> <p>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|.</p> http://mathoverflow.net/questions/59450/boundaries-of-the-eigenvalues-of-a-symmetric-matrix-or-of-its-lapacian/59480#59480 Answer by pgiacome for Boundaries of the eigenvalues of a symmetric matrix (or of its Lapacian) pgiacome 2011-03-24T21:01:08Z 2011-03-24T21:01:08Z <p>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</p> <p>Bounds on graph eigenvalues I and Bounds on graph eigenvalues II</p> <p>Piero Giacomelli</p> http://mathoverflow.net/questions/59450/boundaries-of-the-eigenvalues-of-a-symmetric-matrix-or-of-its-lapacian/59502#59502 Answer by Chris Godsil for Boundaries of the eigenvalues of a symmetric matrix (or of its Lapacian) Chris Godsil 2011-03-24T23:24:21Z 2011-03-24T23:24:21Z <p>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)$.</p> http://mathoverflow.net/questions/59450/boundaries-of-the-eigenvalues-of-a-symmetric-matrix-or-of-its-lapacian/59556#59556 Answer by ght for Boundaries of the eigenvalues of a symmetric matrix (or of its Lapacian) ght 2011-03-25T13:36:03Z 2011-03-25T13:36:03Z <p>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.</p> <p>Here are a few known results:</p> <ul> <li><p>[Fiedler] $\lambda_2\leq \frac{n}{n-1}\min\{d(v):v\in V\}$ where $d(v)$ is the degree of the node $v$.</p></li> <li><p>[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.</p></li> <li><p>[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.</p></li> <li><p>$\sum_{i}^{n}{\lambda_i}=2m=\sum_{v}{d(v)}$ where $m$ is the number of edges in $G$.</p></li> <li><p>[Fiedler] $\lambda_{n}\geq \frac{n}{n-1}\max\{d(v):v\in V\}$.</p></li> </ul> <p>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.</p> <p>I hope it helps!</p>