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 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 at 13:23
A link that may be interesting. I have not looked into it in great detail. orion.math.iastate.edu/butler/PDF/dissertation.pdf –  rnegrinho Jul 9 at 13:25
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 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 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).
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 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 at 19:05