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

— Q.E.D.

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.

## 2 Comments