It is no secret that one can encode a finite undirected graph as a finite-dimensional Hilbert space together with a self-adjoint operator on that space. There are two ways to implement this: functional and formal. Suppose the vertex set of is The functional implementation is to take the Hilbert space to be
the space of complex-valued functions on the vertex set of the graph equipped with the scalar product
and the self-adjoint operator to be the adjacency operator defined by
where is the indicator function
The formal implementation is to take the Hilbert space to be
where is an orthonormal set of abstract vectors indexed by the vertices of and define the adjacency operator by
Both implementations are useful, and it’s wise to stay flexible and not be too wedded to either one. For the time being, we’ll go with the formal one.
The purpose of the above trade-off is to replace combinatorial questions about graphs with algebraic questions about linear operators: since linear algebra is such a powerful tool, this is often very helpful, and is an instructive example of how helpful it can be to “linearize” a problem. In particular, let us consider the problem of counting walks in graphs.
Definition 1: Given a graph on , a pair of vertices and a nonnegative integer an -step walk from to in is a function such that and are adjacent vertices for all in the domain of We write for the set of all such functions, and set
Let us take the case of the complete graph on , as a case study.
First, it is possible to count walks in the complete graph by direct combinatorial reasoning, without using any fancy linear algebra: thinking about the problem carefully reduces it to solving a system of two linear equations in two unknowns. Pick an arbitrary vertex of say the vertex Observe that
since the sum on the left hand side counts all -step walks beginning at while the right hand side reflects the fact that such a walk amounts to choosing between options times. Thinking about the left hand side a bit more, we realize that its terms are really only of two types: there’s the term which counts loops of length based at and then there are terms of the form with corresponding to -step walks which aren’t loops. Moreover, for any two vertices both of which are distinct from we have that because is “everywhere the same.” More precisely, verify the following.
Problem 2.1: The map
defined by where is the transposition is a bijection.
In view Problem 2.1, the above summation identity simplifies to
We thus have a linear equation with two unknowns: if we can find one more equation we’re done. Looking at small values of one observes that the relation
appears to hold, and this can be verified by induction. Indeed, for the inductive step, we write
since the th step of an -step walk from to can land anywhere but the target vertex on its penultimate step, and also
for exactly the same reason. Subtracting, we get
by the induction hypothesis. Thus we obtain the formula
for loops and I leave it to you to complete the mission and obtain the formula for .
To solve the above problem through the systematic use of linear algebra rather than combinatorial reasoning, we can make use of the following general result.
Theorem 1: Let be a finite undirected graph on and let be its adjacency operator. Then for any and we have
Proof: For this is obvious: since is the identity operator, we have and clearly For the result follows from (a special case of) the formula for the matrix elements of a product of linear operators relative to a preferred basis:
In the particular case at hand, we have the adjacency operator, so that for any the scalar product equal to zero unless and are adjacent, in which case it is equal to . Thus we have
I’m sure you think you know what’s coming next: an invocation of the Spectral Theorem. However, let’s leave that for next lecture, and end this one by observing that sometimes Theorem 1 is useful simply because of the efficacy of algebraic operations with linear operators. In particular, in the case of we have where are operators
Clearly, these operators commute, so we can compute by means of the binomial theorem:
Problem 2.2: Prove that
Using Problem 2.2, we can continue our above computation to
and using the binomial theorem again (in the other direction), this is
In particular, we can compute the missing quantity from the combinatorial argument above as the scalar product
Of course, all of this follows from the decomposition of the adjacency operator, which is a special feature of For general graphs, we really do have to resort to spectral theory, and we will start down this road next lecture.