Understanding the properties and use of the Laplacian matrix (and its norm)

The Laplacian is a discrete analogue of the Laplacian $\sum \frac{\partial^2 f}{\partial x_i^2}$ in multivariable calculus, and it serves a similar purpose: it measures to what extent a function differs at a point from its values at nearby points. The Laplacian appears in the analysis of random walks and electrical networks on a graph (the standard reference here being Doyle and Snell), and so it is not surprising that it encodes some of its structural properties: as I described in this blog post, it can be used to set up three differential equations on a graph (the wave equation, the heat equation, and the Schrödinger equation).

(To be totally clear, when you're using this interpretation you should think of the Laplacian, not as a matrix, but as an operator acting on functions $f : V \to \mathbb{R}$. In this setting there is a discrete notion of gradient (which sends a function $f$ to a function $\text{grad } f : E \to \mathbb{R}$) and a discrete notion of divergence (which sends a function $g : E \to \mathbb{R}$ to a function $\text{div } g : V \to \mathbb{R}$), and the divergence of the gradient is the Laplacian - just like in the infinitary case. So the Laplacian defines a certain analogy between graphs and Riemannian manifolds.)

The quadratic form defined by the Laplacian appears, for example, as the power running through a circuit with given voltages at each point and unit resistances on each edge. It is the discrete analogue of the Dirichlet energy.

The Laplacian appears in the matrix-tree theorem: the determinant of the Laplacian (with a bit removed) counts the number of spanning trees. This is related to its appearance in the study of electrical networks and is still totally mysterious to me. The group $\mathbb{Z}^n / L$ where $L$ is the Laplacian has rank $1$, and its torsion subgroup is the critical group of the graph, which has size the number of spanning trees. The critical group appears in the description of chip-firing games on the graph (another name for this is the abelian sandpile model), and is an interesting invariant of graphs.

There is some evidence that finite graphs are analogous to curves over finite fields, and in this analogy the critical group appears to be analogous to the ideal class group (that is, the Jacobian). Its size even appears in a class number formula for graphs coming from the Ihara zeta function (the analogue of the Dedekind zeta function). Again, all of this is totally mysterious to me.

Here is a nice survey paper by Mohar on what graph theorists actually use the Laplacian for. In the literature there are several different normalizations; they correspond to either using a different preferred basis for the space of functions $f : V \to \mathbb{R}$ or varying physical properties of the graph (e.g. changing resistances, adding a potential).

Laplacian matrices are important objects in the field of Spectral Graph Theory.

Many properties of the graph can be read off easily from the properties of the corresponding Laplacian Matrix.

For instance:

• The multiplicity of the eigenvalue zero gives the number of connected components of the graph.
• The largest eigenvalue is 2 if and only if a connected component of the graph is a non-trivial bipartite graph.

There are plenty more results like these.

I would recommend you try the book by Fan Chung (Ronald Graham's wife, I believe) conveniently titled Spectral Graph Theory. Here is a link to the book page: http://www.math.ucsd.edu/~fan/research/revised.html

An explanation of the possible motivation for using the Laplacian (and it's normalized form, which is what you seem to be talking about, when you say norm) appears in the first chapter of that book: http://www.math.ucsd.edu/~fan/research/cb/ch1.pdf

Also search the web for a linear algebra proof of Friendship theorem, which uses matrices. Even though Laplacian matrices are not used, I would still recommend you read that, as it will give you an idea about the power of spectral methods in graph theory.

Hope that helps.