What’s up with the Graph Laplacian?

This is a guest post written by my friend, Jeremy Kun! He’s the author of the popular blog Math ∩ Programming, your go-to site for learning about algorithms, machine learning, cryptography, and so much more.

There’s a deep connection in mathematics between a graph (a set of vertices and edges), and the algebraic properties of special matrices associated with that graph.

Here’s the simplest example of this phenomenon. Say you take an undirected graph G = (V, E) and you let A = (a_{i,j}) be its adjacency matrix, where a_{i,j} = 1 if (i,j) \in E is an edge, and a_{i,j} = 0 otherwise. The matrix A is an n \times n square matrix with n = |V|. The remarkable fact is that the i,j entry of A^k contains the number of walks of length k from i to j.


In this example, the cube of the adjacency matrix counts the number of length-3 walks (paths where you can repeat vertices/edges) between all pairs of nodes. So there is one walk from 5 to 3, and four walks from 1 to 4.

Continue reading