38

This question already has a number of nice answers; I want to emphasize the breadth of this topic. Graphs can be represented by matrices - adjacency matrices and various flavours of Laplacian matrices. This almost immediately raises the question as to what are the connections between the spectra of these matrices and the properties of the graphs. Let's call ...


29

I can't speak much to what traditional Spectral Graph Theory is about, but my personal research has included the study of what I call "Spectral Realizations" of graphs. A spectral realization is a special geometric realization (vertices are not-necessarily-distinct points, edges are not-necessarily-non-degenerate line segments, in some $\mathbb{R}^n$) ...


24

Spectral graph theory is a discrete analogue of spectral geometry, with the Laplacian on a graph being a discrete analogue of the Laplace-Beltrami operator on a Riemannian manifold. The Laplacian $\Delta$ can be used to write down three important differential equations, both on a graph and a Riemannian manifold: The heat equation $\frac{\partial u}{\partial ...


18

It is possible to give a lower bound on the multiplicities of the eigenvalues of the adjacency or Laplacian matrix of a graph $G$ using representation theory. Namely, the vector space of functions $G \to \mathbb{C}$ is a representation of the symmetry group, and both the adjacency and Laplacian matrix respect this group action. It follows that each ...


17

The second eigenvalue of a markov chain has meaning, and it affects (for example) the convergence and stability of algorithms that find the equilibrium distribution. See The second eigenvalue of the Google matrix, by Haveliwala and Kamvar for a discussion on how to compute its value. The second eigenvector, however, has to be something more complex. Given ...


16

It's completely known. I prefer to define the Laplacian as $A - D$. This more closely imitates the behavior of the continuous Laplacian, which is negative-semidefinite. Let $G, H$ be two locally finite graphs with Laplacians $L_G, L_H$. The Cartesian product $G \Box H$ is again locally finite and has Laplacian the Kronecker sum $L_G \otimes I + I \otimes ...


14

Some random facts: The largest eigenvalue $\lambda_1$ is closely related to average degree. The second largest eigenvalue $\lambda_2$ is closely related to connectivity, that is graphs with small $\lambda_2$ have small diameter. A graph $G$ is bipartite if and only if for every eigenvalue $\lambda$, $-\lambda$ is also an eigenvalue. For connected $G$, the ...


10

Yes! Perhaps the easiest way is to obtain the Laplacian matrix and find a basis of its kernel. In words, call $A$ your adjacency matrix. Obtain the diagonal matrix $D$ of the degrees of each vertex. Set $L=D-A$. Now $\dim \ker L = $ number of connected components. Moreover, the kernel of $L$ is spanned by vectors constant on each connected component. For ...


9

The smallest (in absolute value) eigenvalue $\lambda_1$ of the Laplacian (I don't know if this agrees with your definition of $\lambda_1$; I recall not liking Chung's definitions) measures how fast heat dissipates on the graph. More precisely, for a (finite, for simplicity) graph $G = (V, E)$ with Laplacian $\Delta$ (regarded as an operator acting on ...


9

If $G = (V, E)$ is a graph, then the adjacency matrix is an operator which acts on the space of functions $V \to \mathbb{R}$ (say) via $$A(f)(v) = \sum_{v \to w} f(w).$$ Constructing the adjacency matrix is therefore a form of linearization. Note that this description of the adjacency matrix makes the connection between powers of the adjacency matrix and ...


9

Expanding on a random fact mentioned by dtldarek: People frequently use spectral graph theory in clustering. The general situation is that you have a collection of data points $x_1, \dots x_n$, that belong to some unknown clusters $A_1, \dots, A_k$. You want to identify which points lie in which cluster. You have some sort of connection graph, and the ...


8

As far as I know, there is no "simple" necessary and sufficient condition of $G$ for an invertible adjacency matrix. A few comments: A necessary condition that generalizes your "each vertex needs at least one connection" condition is that if $S$ is any subset of vertices of the graph, there are at least $|S|$ vertices in the graph having at least one ...


8

About your reference request, presumably you know Chung's book Spectral Graph Theory. To my knowledge this is the only reference dedicated to spectral methods; however, most major books on graph theory have sections on spectral methods. There seem to be scattered notes on the internet, but I don't know about those. Edit: the recent book 'Graphs and ...


7

I would expect many of your graphs to not have distinct eigenvalues. Here's one reason: They have a very large number of degree $1$ vertices. Enough, in fact, that there will probably be a decent number of degree $1$ vertices which share a common neighbor with another degree $1$ vertex. These will give rise to many independent vectors in the nullspace ...


7

What does it mean "orthogonal eigenvectors of eigenvalue zero"? Are those eigenvalues really equal 0? Eigenvector for eigenvalue zero is a vector $\mathbf{a}$ such that $L\mathbf{a}=\mathbf{0}$. In this case $$\begin{bmatrix} L_{G_{1}} & 0\\ 0 & L_{G_{2}} \end{bmatrix} \begin{bmatrix} 0\\ 1 \end{bmatrix} = \begin{bmatrix} 0\\ 0 \end{...


7

Suppose that $G$ is $d$-regular. Then every vertex of $G$ is adjacent to $d$ other vertices, so each row of its adjacency matrix $A$ will have $d$ $1$’s and $n-d$ $0$’s. Let $$A=\pmatrix{a_{11}&a_{12}&\dots&a_{1n}\\ a_{21}&a_{22}&\dots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\dots&a_{nn}}\;,$$ ...


7

The characteristic polynomial of an integer matrix is a monic integer polynomial. The product of the non-zero eigenvalues is thus equal to a non-zero integer, so the only way for $\rho(A) < 1$ is for this to be an empty product, that is if $\rho(A) = 0$ and all eigenvalues are zero. This is equivalent to the property that $A$ is nilpotent, i.e. $A^n = 0$...


6

As Colin noted in a comment, you need to assume that $G$ is connected. For a $k$-regular graph, $\mathbf A/k$ is the transition matrix of a random walk that uniformly selects one of the $k$ neighbours in each step. If $\mathbf A$ has eigenvalue $-k$, then $\mathbf A/k$ has eigenvalue $-1$. Thus the random walk does not necessarily converge to a stationary ...


6

Your $C_n$ is a circulant matrix. All $n\times n$ complex circulant matrices share a common set of eigenvectors, and there is an explicit formula for their eigenvalues (see Wikipedia). In your specific case, the eigenvalues are $\omega_j+\omega_j^{n-1}$ for $j=0,1,2,\ldots,n-1$, where $\omega_j=e^{2\pi ij/n}$.


6

Your graph is the Cartesian product of the cycle $C_n$ and the complete graph $K_2$. So its adjacency matrix is $$ A(C_n) \otimes I +I \otimes A(K_2) $$ and hence its eigenvalues are the numbers $\theta\pm1$, where $\theta$ runs over the eigenvalues of the cycle. (Here $\otimes$ is the Kronecker product of matrices.)


6

There is no simple relation. The rank of Laplacian of a graph is number of vertices minus number of components. There is no simple formula for the rank of the adjacency matrix. It is generally equal to the number of vertices but for complete bipartite graphs it is two. If $\nu(G)$ is the maximum number of edges in a matching, then the adjacency matrix of a ...


6

I think a general set of conditions will be hard to come by. To substantiate this claim I make the following negative observation. The adjacency matrix of any bipartite graph with an odd number of vertices is not invertible. This follows since the eigenvalues of a bipartite graph are symmetric about $0$, and since there are an odd number of eigenvalues (if ...


6

Intro I'll present an incomplete interpretation framework. Let's being by considering two points in one dimension. We can easily generalize the results to more than one dimension. Our matrix is given by, $$M=\begin{bmatrix} 0 & |x_1-x_2| \\ |x_1-x_2| & 0 \end{bmatrix}$$ The eigenvalues are given by $$\lambda_1=-\lambda_2=|x_1-x_2|$$ The ...


6

An easy way to obtain this result from Kirchhoffs Theorem is the following (following "Biggs, Algebraic graph theory"): Step 1 (Temperley 1964) For a graph $X$ with $n$ vertices and its Laplacian $L=L(X)$ it holds that $$ \tau(X) = n^{-2} \text{det}(J + L),$$ where $J$ is the matrix with all entries equal to $1$ and $\tau(X)$ is the number of spanning trees....


6

This is not even close to true. The eigenvalues of the Petersen graph are integers, but it contains 5-cycles as induced subgraphs and these do not have integer eigenvalues. Or the eigenvalues of a 4-cycle are integers, but this contains paths on three vertices, which have non-integral eigenvalues. More generally note that the eigenvalues of the complete ...


6

The fact that the path graph $P_n$ minimizes algebraic connectivity among all connected graphs with $n$ vertices follows from proposition 4.3 in Fiedler's paper. This proposition states (among other things) that the algebraic connectivity of a graph $G$ is at least $2 e(G) (1-\cos(\pi/n))$, where $e(G)$ is the edge-connectivity of $G$, i.e. the minimum ...


5

Your intuition is totally correct. $v = \mathbf{1}$ is an eigenvector to eigenvalue $k$, since $A \mathbf{1} = k \mathbf{1}$. Now, let $v_i$ denote the characteristic function of the $i$'th connected component, i.e., $v_i(x)$ is $1$ for all vertices $x$ within the $i$'th component and $0$ else, thus, it is $\mathbf{1} = \sum_{i=1}^t v_i$. For any $i = 1, \...


5

$A$ is symmetric, nonnegative, and irreducible. By a theorem of Perron and Frobenius, $k$ is a simple eigenvalue with a positive eigenvector $u$. Now with componentwise absolute value, $k|x|=|-kx|=|Ax|\le A|x|$. Multiplication with $u^T$ shows that we must have equality. Hence $|x|$ is an eigenvector, hence a multiple of $u$. Therefore $x$ has no zero ...


5

Let $G$ have $\ell$ components $C_1$, $\ldots\,$, $C_{\ell}$. For $i = 1$, $\ldots\,$, $\ell$, define the vector $x^{(i)}$ by $x^{(i)}_j = \chi_{v_j \in C_i}$. Since the different $x^{(i)}$s are orthogonal, in order to show that the multiplicity of $k$ is $\ell$, it is enough to show that each $x^{(i)}$ is an eigenvector with eigenvalue $k$ and that if $x$ ...


5

I'm a little confused by your series of questions. If we "know" something, as in your first sentence, that by definition means we know it works "in reality," and also means we have a proof of that result. In any case, the key step in the intuition is understanding how the Laplacian matrix acts on a graph, which is probably too long to fully develop here. ...


Only top voted, non community-wiki answers of a minimum length are eligible