Today I'd like to share an idea. It's a very simple idea. It's not fancy and it's certainly not new. In fact, I'm sure many of you have thought about it already. But if you haven't—and even if you have!—I hope you'll take a few minutes to enjoy it with me. Here's the idea:
So simple! But we can get a lot of mileage out of it.
To start, I'll be a little more precise: every matrix corresponds to a weighted bipartite graph. By "graph" I mean a collection of vertices (dots) and edges; by "bipartite" I mean that the dots come in two different types/colors; by "weighted" I mean each edge is labeled with a number.
The graph above corresponds to a 3×2 matrix M. You'll notice I've drawn three green dots—one for each row of M—and two pink dots—one for each column of M. I've also drawn an edge between a green dot and a pink dot if the corresponding entry in M is non-zero.
For example, there's an edge between the second green dot and the first pink dot because M21=4, the entry in the second row, first column of M, is not zero. Moreover, I've labeled that edge by that non-zero number. On the other hand, there is no edge between the first green dot and the second pink dot because M12, the entry in the first row, second column of the matrix, is zero.
Allow me to describe the general set-up a little more explicitly.
Any matrix M is an array of n×m numbers. That's old news, of course. But such an array can also be viewed as a function M:X×Y→R where X={x1,…,xn} is a set of n elements and Y={y1,…,ym} is a set of m elements. Indeed, if I want to describe the matrix M to you, then I need to tell you what each of its ijth entries are. In other words, for each pair of indices (i,j), I need to give you a real number Mij. But that's precisely what a function does! A function M:X×Y→R associates for every pair (xi,yj) (if you like, just drop the letters and think of this as (i,j)) a real number M(xi,yj). So simply write Mij for M(xi,yj).
Et voila. A matrix is a function.
As suggested, let's further think of X's elements as being green and Y's elements as being pink. Then a matrix M corresponds to a weighted bipartite graph in the following way: the vertices of the graph have two different colors provided by X and Y, and there is an edge between every xi and yj which is labeled by the number Mij. But if this number is zero, then simply omit that edge.
Et voila. Every matrix corresponds to a graph.
Nice things happen when we visualize matrices in this way. For instance...
Given two matrices (graphs) M:X×Y→R and N:Y×Z→R, we can multiply them by sticking their graphs together and traveling along paths: the ijth entry of MN, i.e. the value of the edge connecting xi to zj, is obtained by multiplying the edges along each path from xi to zj and adding them together. For example:
Symmetric matrices correspond to symmetric graphs.
A matrix is symmetric if it is equal to its transpose. That symmetry is always seen by reflecting across the diagonal of the matrix. But you can also see the symmetry in the graph. In particular, the graph makes it visually intuitive why MM⊤ and M⊤M are always symmetric, for any M!
