# Math 202C: Lecture 11

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 $\mathcal{H}$ be a Hilbert space with finite or countably infinite orthonormal basis $\mathbf{e}_i.$ To make things simpler, let us consider the case where $\dim \mathcal{H}=n < \infty,$ but everything we say below works (or can be made to work) for arbitrary separable Hilbert spaces. Let $\mathbb{C}\Omega$ be a the one-dimensional Hilbert space spanned by a unit vector $\Omega$ which does not belong to $\mathcal{H}.$

Let $d \in \mathbb{N},$ and recall that $\mathcal{H}^{\otimes d}$, the $d$th tensor power of $\mathcal{H},$ is the vector space of degree $d$ tensors

$\mathbf{v}_1 \otimes \dots \otimes \mathbf{v}_d, \quad \mathbf{v}_i \in \mathcal{H},$

and linear combinations thereof. This is again a Hilbert space, with the scalar product defined by

$\langle \mathbf{v}_1 \otimes \dots \otimes \mathbf{v}_d,\mathbf{w}_1,\mathbf{v}_1 \otimes \dots \otimes \mathbf{v}_d \rangle = \prod\limits_{i=1}^d \langle \mathbf{v}_i,\mathbf{w}_i \rangle.$

In particular, an orthonormal basis of $\mathcal{H}^{\otimes d}$ is given by the tensors

$\mathbf{e}_i = \mathbf{e}_{i(1)} \otimes \dots \otimes \mathbf{e}_{i(d)}, \quad i \in \mathrm{Fun}(d,n),$

where $\mathrm{Fun}(d,n)$ is the set of all functions

$\{1,\dots,d\} \longrightarrow \{1,\dots,n\}.$

Thus every tensor $t \in \mathcal{H}^{\otimes d}$ is a linear combination

$\mathbf{t} = \sum\limits_{i \in \mathrm{Fun}(d,n)} a_i \mathbf{e}_i.$

The classical way to think about this is that $\mathcal{H}^{\otimes d}$ is the space of complex-valued functions on $d$-tuples of vertices of a graph $\Gamma$ with vertex set $\{1,\dots,n\}.$ Alternatively, you can think of $\mathcal{H}^{\otimes d}$ as the $d$-particle space corresponding to the one-particle space $\mathcal{H}.$ From this point of view, each function

$i \colon \{1,\dots,d\} \longrightarrow \{1,\dots,n\}$

corresponds to an assignment of $d$ distinguishable particles labeled $1,\dots,d$ to the vertices of $\Gamma.$ If instead we are dealing with $d$ quantum particles, meaning particles whose location cannot be definitely specified, then we instead must deal with a unit tensor

$\mathbf{u}= \sum\limits_{i \in \mathrm{Fun}(d,n)} p_i \mathbf{e}_i$

in $\mathcal{H}^{\otimes d}$, the idea being that

$|p_i|^2 = |\langle \mathbf{e}_i,\mathbf{u}\rangle|^2$

represents the probability to find the distinguishable particles $1,\dots,d$ at vertices $i(1),\dots,i(d),$ respectively. It is convenient to define $\mathcal{H}^{\otimes 0} :=\mathbb{C}\Omega,$ where $\Omega$ is a unit vector not in $\mathcal{H}$ 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 $F(\mathcal{H})$ over $\mathcal{H}$ is the algebraic structure that does this. It is defined as the direct sum of all tensor powers of $\mathcal{H}:$

$F(\mathcal{H}) = \bigoplus\limits_{d=0}^\infty \mathcal{H}^{\otimes d}.$

This is a graded algebra, i.e. we have a natural multiplication of tensors: if $\mathbf{t}_1 \in \mathcal{H}^{\otimes d_1}$ and $\mathbf{t}_2 \in \mathcal{H}^{\otimes d_2},$ then $\mathbf{t_1} \otimes \mathbf{t}_2 \in \mathcal{H}^{\otimes (d_1+d_2)}.$ Note that $F(\mathcal{H})$ is a noncommutative algebra, and it is also infinite-dimensional, even though $\mathcal{H}$ is finite-dimensional.

Problem 11.1: Show that $F(\mathcal{H})$ is (non-canonically) isomorphic to the free algebra $\mathbb{C}\langle x_1,\dots,x_n\rangle$ of rank $n,$ which consists of polynomials in $n$ noncommutative indeterminates.

Returning to the viewpoint that $\mathcal{H}=\bigoplus_{i=1}^n\mathbf{e}_i$ is the one-particle space corresponding to a graph $\Gamma$ with vertex set $\{1,\dots,n\},$ we encode the edge structure of $\Gamma$ using the adjacency operator $A \in \mathrm{End}\mathcal{H}$ defined by

$A\mathbf{e}_i = \sum\limits_{j=1}^n m(i,j) \mathbf{e}_j,$

where $m(i,j)$ is the multiplicity of the edge $\{i,j\}$ in $\Gamma.$ As we have discussed, the matrix elements of $A^r$ then count $r$-step walks in $\Gamma,$ i.e.

$\langle A^r\mathbf{e}_i,\mathbf{e}_j \rangle$

is the number of $r$-step walks from vertex $i$ to vertex $j$ in $\Gamma.$ Let us now observe that this naturally extends to any finite number of particles. Namely, for any $d \in \mathbb{N},$ we have the operator $A^{\otimes d} \in \mathrm{End} \mathcal{H}^{\otimes d}$ with action defined by

$A^{\otimes d} \mathbf{e}_i = A\mathbf{e}_{i(1)} \otimes \dots \otimes A\mathbf{e}_{i(d)}, \quad i \in \mathrm{Fun}(d,n).$

Proposition 1: For any $d \in \mathbb{N},$ any $i,j \in \mathrm{Fun}(d,n),$ and any $r \in \mathbb{N} \cup \{0\},$ the number of ways in which $d$ distinguishable particles on $\Gamma$ can move from positions $i(1),\dots,i(d)$ to positions $j(1),\dots,j(d)$ in $r$ instants of time, where at each instant each particle jumps to an adjacent vertex, is given by the scalar product

$\langle (A^r)^{\otimes d} \mathbf{e}_i,\mathbf{e}_j \rangle.$

Proof: We have that

$\langle (A^r)^{\otimes d} \mathbf{e}_i,\mathbf{e}_j \rangle = \langle A^r\mathbf{e}_{i(1)} \otimes \dots \otimes A^r\mathbf{e}_{i(d)},\mathbf{e}_{j(1)} \otimes \dots \otimes \mathbf{e}_{j(d)} \rangle = \prod\limits_{x=1}^d \langle A^r\mathbf{e}_{i(x)},\mathbf{e}_{j(x)} \rangle.$

The $x$th factor $\langle A^r\mathbf{e}_{i(x)},\mathbf{e}_{j(x)} \rangle$ in the product counts the number of ways in which particle $x$ can travel from vertex $i(x)$ to vertex $j(x)$ in $r$ jumps along the edges of $\Gamma.$ 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 $i$ to state $j$ in time $r.$

— Q.E.D.

Now suppose that $\mathbf{f}_1,\dots,\mathbf{f}_n$ is an orthonormal basis of $\mathcal{H}$ consisting of eigenvectors of $A:$

$A\mathbf{f}_1 = \lambda_1 \mathbf{f}_1,\dots,A \mathbf{f}_n = \lambda_n\mathbf{f}_n.$

Then, the tensors

$\mathbf{f}_i = \mathbf{f}_{i(1)} \otimes \dots \otimes \mathbf{f}_{i(d)}, \quad i \in \mathrm{Fun}(d,n)$

are an orthonormal basis of $\mathcal{H}^{\otimes d}$ consisting of eigenvectors of $A^{\otimes d}:$

$A^{\otimes d}\mathbf{f}_i = A\mathbf{f}_{i(1)} \otimes \dots\otimes A\mathbf{f}_{i(d)} = \lambda_{i(1)} \dots \lambda_{i(d)} \mathbf{f}_i, \quad i \in \mathrm{Fun}(d,n).$

If we agree to use the multi-index notation

$\lambda_i := \lambda_{i(1)} \dots \lambda_{i(d)},$

$A^{\otimes d} \mathbf{f}_i = \lambda_i \mathbf{f}_i, \quad i \in \mathrm{Fun}(d,n).$

We then have the following.

Corollary 1: For any $d \in \mathbb{N},$ any $i,j \in \mathrm{Fun}(d,n),$ and any $r \in \mathbb{N} \cup \{0\},$ the number of ways in which $d$ distinguishable particles on $\Gamma$ can move from positions $i(1),\dots,i(d)$ to positions $j(1),\dots,j(d)$ in $r$ instants of time, where at each instant each particle jumps to an adjacent vertex, is given by

$W^r(i,j) = \sum\limits_{k \in \mathrm{Fun}(d,n)} \overline{\langle \mathbf{f}_k,\mathbf{e}_i\rangle} \lambda_i^r \mathbf{f}_k,\mathbf{e}_j \rangle.$

The point of the above discussion is that, associated to every graph $\Gamma$ is not just a Hilbert space $\mathcal{H}$ encoding the vertices and an operator $A \in \mathrm{End}\mathcal{H}$ encoding the edges, but an infinite dimensional noncommutative algebra $F(\mathcal{H})$ encoding $\mathbb{C}$-valued functions on ordered tuples of vertices of arbitrary finite length, and an operator $F(A) \in \mathrm{End} F(\mathcal{H})$ acting on these functions in a manner determined by the adjacency structure of $\Gamma.$ 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 $\Gamma$ is not an inert finite set, but rather a finite set $\mathrm{G}$ 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 $\mathcal{H}$ with orthonormal basis $\mathbf{e}_\pi$ indexed by the group elements $\pi \in \mathrm{G}$ (which may or may not have a natural linear order), but it is more appropriate to denote this space $\mathcal{A}$ since it is already an a unital, associative, and finite-dimensional algebra via bilinear extension of

$\mathbf{e}_\pi \mathbf{e}_\sigma := \mathbf{e}_{\pi\sigma}.$

We can still of course form the tensor algebra $F(\mathcal{A}),$ but there is a natural map from $F(\mathcal{A})$ to its degree one component $\mathcal{A}$ given by evaluation:

$\mathbf{e}_{i(1)} \otimes \mathbf{e}_{i(2)} \otimes \dots \otimes \mathbf{e}_{i(d)} \to \mathbf{e}_{i(1)i(2)\dots i(d)}, \quad i \in \mathrm{Fun}(\{1,\dots,d\},\mathrm{G}),\ d \in \mathbb{N}.$

Moreover, it is not only $\mathcal{A}$ which is naturally a finite-dimensional algebra, but all of its tensor powers $\mathcal{A}^{\otimes d},$ via

$(\mathbf{e}_{i(1)} \otimes \dots \otimes \mathbf{e}_{i(d)})( (\mathbf{e}_{j(1)} \otimes \dots \otimes \mathbf{e}_{j(d)}) = e_{i(1)j(1)} \otimes \dots \otimes \mathbf{e}_{i(d)j(d)},$

which in multi-index notation we can succinctly write as $\mathbf{e}_i\mathbf{e}_j = \mathbf{e}_{ij}.$ Moreover, if $\mathrm{G}$ 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 $A$ and all of its tensor powers.

One demerit of the above is that the tensor algebra $F(\mathcal{H})$ 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 $\Gamma.$ This can be accomplished by letting the adjacency operator $A$ act not on the tensor powers of the one-particle space $\mathcal{H},$ but rather on its symmetric and antisymmetric tensors powers. We will discuss this next time.