If I was to start this course over again, I would not have limited the opening act to a discussion of the relationship between linear algebra and graph theory, but with a more general discussion of the relations between multilinear algebra and graph theory. Since I sketched this briefly in our last in-person lecture, I will record what was said here in more precise detail.
Let be a Hilbert space with finite or countably infinite orthonormal basis To make things simpler, let us consider the case where but everything we say below works (or can be made to work) for arbitrary separable Hilbert spaces. Let be a the one-dimensional Hilbert space spanned by a unit vector which does not belong to
Let and recall that , the th tensor power of is the vector space of degree tensors
and linear combinations thereof. This is again a Hilbert space, with the scalar product defined by
In particular, an orthonormal basis of is given by the tensors
where is the set of all functions
Thus every tensor is a linear combination
The classical way to think about this is that is the space of complex-valued functions on -tuples of vertices of a graph with vertex set Alternatively, you can think of as the -particle space corresponding to the one-particle space From this point of view, each function
corresponds to an assignment of distinguishable particles labeled to the vertices of If instead we are dealing with quantum particles, meaning particles whose location cannot be definitely specified, then we instead must deal with a unit tensor
in , the idea being that
represents the probability to find the distinguishable particles at vertices respectively. It is convenient to define where is a unit vector not in called the “vacuum vector,” which corresponds to no particles, i.e. a vacuum.
Now suppose that one would like to deal with a variable (but finite) number of particles: the tensor algebra over is the algebraic structure that does this. It is defined as the direct sum of all tensor powers of
This is a graded algebra, i.e. we have a natural multiplication of tensors: if and then Note that is a noncommutative algebra, and it is also infinite-dimensional, even though is finite-dimensional.
Returning to the viewpoint that is the one-particle space corresponding to a graph with vertex set we encode the edge structure of using the adjacency operator defined by
where is the multiplicity of the edge in As we have discussed, the matrix elements of then count -step walks in i.e.
is the number of -step walks from vertex to vertex in Let us now observe that this naturally extends to any finite number of particles. Namely, for any we have the operator with action defined by
Proposition 1: For any any and any the number of ways in which distinguishable particles on can move from positions to positions in instants of time, where at each instant each particle jumps to an adjacent vertex, is given by the scalar product
Proof: We have that
The th factor in the product counts the number of ways in which particle can travel from vertex to vertex in jumps along the edges of Since the particles are non-interacting, the product of these numbers is the number of possible histories corresponding to the evolution of the particle system from initial state to state in time
Now suppose that is an orthonormal basis of consisting of eigenvectors of
Then, the tensors
are an orthonormal basis of consisting of eigenvectors of
If we agree to use the multi-index notation
then this simply reads
We then have the following.
Corollary 1: For any any and any the number of ways in which distinguishable particles on can move from positions to positions in instants of time, where at each instant each particle jumps to an adjacent vertex, is given by
The point of the above discussion is that, associated to every graph is not just a Hilbert space encoding the vertices and an operator encoding the edges, but an infinite dimensional noncommutative algebra encoding -valued functions on ordered tuples of vertices of arbitrary finite length, and an operator acting on these functions in a manner determined by the adjacency structure of Moreover, the variable multi-particle construction is not really any different from the one-particle construction: all the formulas are the same up to replacing indices with multi-indices.
The reason that we are discussing the above is that it gives a nice conceptual understanding of why the spectral analysis of Cayley graphs is so much more accessible than the spectral analysis of arbitrary graphs. In the group case the vertex set of is not an inert finite set, but rather a finite set which comes to us with a group law. Since this is a special case of the above, we can of course still form the corresponding one-particle space with orthonormal basis indexed by the group elements (which may or may not have a natural linear order), but it is more appropriate to denote this space since it is already an a unital, associative, and finite-dimensional algebra via bilinear extension of
We can still of course form the tensor algebra but there is a natural map from to its degree one component given by evaluation:
Moreover, it is not only which is naturally a finite-dimensional algebra, but all of its tensor powers via
which in multi-index notation we can succinctly write as Moreover, if is an abelian group, things get even simpler and all these finite-dimensional algebras are commutative, and character theory gives a universal method to construct the eigenvalues and eigenvectors of the adjacency operator and all of its tensor powers.
One demerit of the above is that the tensor algebra is “unphysical,” in the sense that if we were dealing with natural particles they would not be distinguishable. Moreover, we would want to classify them as either interacting or not, so decide between bosons and fermions populating the vertices of our graph This can be accomplished by letting the adjacency operator act not on the tensor powers of the one-particle space but rather on its symmetric and antisymmetric tensors powers. We will discuss this next time.