# Surprising connection between linear algebra and graph theory

What is the intuition for linear algebra being such an effective tool to resolve questions regarding graphs?

For example, one can determine if a given graph is connected by computing its Laplacian and checking if the second smallest eigenvalue is greater than zero (the so called Fiedler's eigenvalue).

It seems surprising to me that some questions about graphs, which are inherently discrete combinatorial structures, can be resolved by means of linear algebra. What is the intuition behind this connection?

-
A graph is a $(0,1)$-matrix, after all. No wonder that linear algebra provides a natural language, and tools, to deal with it. – Pietro Majer Jul 9 '14 at 13:07
Granted that the adjacency matrix of an undirected graph can be coded as a $(0, 1)$-matrix. But why should the eigenvalues of the Laplacian have anything to do with connectivity? Why should the spectrum of the Laplacian tell you so much about the graph? It seems surprising to me. – rnegrinho Jul 9 '14 at 13:23
I would be interested myself to learn when it was realized that Fiedler's eigenvalue reflects connectivity. Perhaps the history is recounted in Fan Chung's book on Spectral Graph Theory. – Joseph O'Rourke Jul 9 '14 at 14:14
A graph $(V,E)$ can be identified with its adjacency operator, which is the linear operator defined on the set of all complex-valued functions on $V$ sending a function $f\colon V\to{\mathbb C}$ to the function $v\mapsto\sum_{uv\in E} f(u)$. From this viewpoint, a graph is a linear algebraic object, and linear algebra is the tool to study graphs. – Seva Jul 9 '14 at 14:19
Linear algebra is so powerful that we use it to study all other mathematical objects (de Rham cohomology comes to mind), graphs just being one example. – Allen Knutson Jul 9 '14 at 20:34

I think the basic point of contact between graph theory and linear algebra is the notion of a random walk. Given an initial probability distribution $p$ on the vertex set $V$ of a graph (though of as a vector in $\mathbb{R}^{|V|}$), the probabilities of hitting different vertices after $k$ steps of a random walk are given by $W^k p$ where $W = A D^{-1}$ (with $A$ the adjacency matrix and $D$ the degree matrix). This suggests that the spectral theory of $W$ is going to be relevant to dynamical questions on graphs, and the (normalized) Laplacian is just $D^{-1/2}(I - W)D^{1/2}$. (The point of the normalization is so that eigenvalues for different graphs can be compared).

You ask specifically why spectral theory for the Laplacian helps measure the connectivity of a graph. Let's first note that it is possible to use random walks to answer this question. Suppose a graph is very loosely connected, meaning it can be divided into two pieces which each have many internal connections but very few external connections. Pick any vertex and start doing random walks of various lengths starting at that vertex. Intuitively, you expect that these random walks will be much more likely to visit vertices in the same piece as the starting vertex and much less likely to visit vertices in the other piece, and this intuition can be made precise.

Of course you will still probably see vertices with high degree more often then you will see vertices with low degree, so you should compare the random walk probabilities to the degree vector of the graph (normalized so that it is a probability distribution). The normalized degree vector is an eigenvector for $W$ with eigenvalue $1$, so it is not unreasonable to expect that the small eigenvalues of the Laplacian (which is conjugate to $I - W$) will carry similar information.

A question you might ask is: why use the Laplacian at all if the intuition comes from random walks? The first answer is historical: the theorem relating the connectivity of graphs to the spectral theory of the Laplacian began as the Cheeger inequality, a theorem relating connectivity of Riemannian manifolds to the spectral theory of the Riemannian Laplacian operator (the two theorems have nearly identical proofs). A more substantive answer is that for any vector $f \in \mathbb{R}^{|V|}$ we have: $$\langle Lf, f \rangle = \sum_{u \sim v} (f(u) - f(v))^2$$ which is a particularly simple quadratic form on the graph, and thus linear algebra and spectral theory for $L$ is quite simple (and the estimates are pretty sharp).

-
Thanks. Very interesting. I've have Spectral Graph Theory by Fan R. K. Chung to read when I find the time. What about the eigenvectors of the Laplacian? Do they have any interpretation? I know that the eigenvector of matrix $W$ associated with eigenvalue $1$ is the stationary distribution of a random walk of the graph (the graph has to satisfy some conditions; see Peron-Frobenius theorem). What about the other eigenvectors? – rnegrinho Jul 9 '14 at 14:53
The eigenvector $e_2$ of the Laplacian whose eigenvalue is $\lambda_2$ actually gives an algorithm for partitioning a graph: order the vertices so that $\frac{e_2(v_i)}{deg(v_i)}$ is a decreasing function of $i$, let $S_i = \{v_1, \ldots, v_i\}$, and let $\alpha_G$ be the minimal isoperimetric ratio of the $S_i$'s. Then $\lambda_2 \geq \frac{\alpha_G^2}{2}$. This in fact proves the Cheeger inequality (and it is the proof in Fan Chung's book). – Paul Siegel Jul 9 '14 at 19:05
For the other eigenvectors of the Laplacian, one buzzword to Google is "spectral embedding". Roughly, the eigenvectors for the dominant eigenvalues give a good algorithm for embedding your graph in small dimensional Euclidean space. – Paul Siegel Jul 9 '14 at 19:06
here is a question related to the other eigenvalues/eigenvectors – amakelov May 7 at 16:49