On Graphs and Matrices

Warning: Everything here is probably either wrong or obvious. It is about an epiphany I had today, and nothing more. It has been almost a year since I have blogged, and I want to get back into it.

A student in my office today was asking about graphs. It is easy to prove that the nth power of an adjacency matrix is counts the number of paths of length n. Proving this was enough to placate me as an undergrad, but today for some reason showing this result got me thinking. The "matrix" is not an arbitrary notion. Matrix multiplication isn't just some arcane ritual that happens to have useful properties. Rather, matrices are a computationally efficient implementation for a certain class of functions--namely, linear transformation. Matrix multiplication is just function composition.

So that lead me to thinking--is there a way to view adjacency matrices (and graphs) as linear transformation? The answer is that: of course there is.

One can think of an element in a set $S$ as being a function $S \to \mathbb{Z}_2$ that is $1$ at the point and $0$ everywhere else. In fact, one can generalize this to work in any ring, not just $\mathbb{Z}_2$.

This then produces a notion of "super position." A subset of a set $S$ can be seen as an arbitrary function $S \to \mathbb{Z}_2$, while a general notion of super position is achieved using other rings. In the integers we get multi-sets, while if we use something like real numbers we get a more general notion where we can include fractions of elements...

All of these notions define "K-modules" for what ever ring $K$ we use. If $K$ is a field we get vector spaces. For example: given a set $S$, the set of subsets of $S$ form a $\mathbb{Z}_2$-vector space. Bizarre, but true.

What does this fave to do with graphs? Well recall that a graph is usually defined as a tuple $(V,E)$ of the vertices and edges. Usually $E$ is thought of as a subset of $V \otimes V$. Equivalently, we could, using the construction above, express $E : (V \otimes V) \to \mathbb{Z}_2$.

And this motivates the adjacency matrix representation. For each pair of vertices, we assign a zero if there is not an edge between them, and a one if there is.

This though was the unsatisfying position I was in at the beginning. The question is can we do better.

Here is the trick though, we define the function $A : (V \to \mathbb{Z}_2) \to (V \to \mathbb{Z}_2)$ as $A(f)(y) = \Sigma_{x \in V}f(x)E(x,y)$. Why this odd function? Well, we know that for any particular vertex $v$, there exists a function $\bar{v}$ that is $1$ at $v$ and zero everywhere else. Observe that $A(\bar{v})(y) = E(v,y)$, and thus we can recover $E$ from $A$. In this respect, $A$ is just a very odd way of writing $E$.

More importantly, we can observe two things about $A$

1. $A$ is linear.
2. The matrix representation of $A$ is exactly the adjacency matrix.

We can further generalize. If we replace $\mathbb{Z}_2$ with the integers, then a function $V \to \mathbb{Z}$ assigns an integer "weight" to each element in $V$. While the function $A$ produces a new assignment, copying the weight to each adjacent vertex, and then summing. If we let this weight be the number of ways to get from some starting positions $s$ to each position in $V$ using $n$ steps, then it should be obvious that the action of $A$ is to compute the number of ways to get from $s$ to each position in $V$ using $n+1$ steps.

Whats more, we have a natural way of encoding multigraphs--instead of the adjacency matrix consisting of elements from $\mathbb{Z}_2$, it consists of elements from $\mathbb{Z}$ encoding the number of edges between two vertices. From the linear algebra perspective, $A$ is precisely the linear operator that given a vector of paths from some $s$ to each position in $V$ using $n$ steps, returns a vector of paths from $s$ to each vertex in $V$ using $n+1$ steps.

In fact, it seems to me that switching to integers makes everything more logical, not less. The idea that $A^n$ is the number of paths of length $n$ should be obvious in this framework.

I don't know why I didn't learn this as an undergrad, but it seems to me now that graph theory is really just linear algebra in disguise.