Math 202C: Lecture 3

In Lecture 2, we showed that the problem of computing the number W^r(i,j) of r-step walks on finite undirected graph \mathrm{G} with vertex set \{1,\dots,n\} is equivalent to computing the matrix elements \langle \mathbf{e}_i,A^r \mathbf{e}_j \rangle of the rth power of the adjacency operator A \in \mathrm{End}\ \mathbb{C}\mathrm{G} relative to the vertex basis \{\mathbf{e}_1,\dots,\mathbf{e}_n\} of the Hilbert space \mathbb{C}\mathrm{G}. This translates the combinatorial problem of counting walks into the algebraic problem of computing the matrix elements of an operator in a specified basis. We now give this problem the Math 202A treatment.

Consider linear operators A_1,\dots,A_r acting in a finite-dimensional Hilbert space \mathcal{H}. Recall the following theorem from Math 202A.

Theorem 1: The operators A_1,\dots,A_r admit a common orthonormal basis if and only if \{A_1,A_1^*,\dots,A_r,A_r^*\} is a commutative family. In particular, a single operator admits an orthonormal eigenbasis if and only if it commutes with its adjoint, i.e. is a normal operator.

Now let \{\mathbf{e}_1,\dots,\mathbf{e}_n\} be a given orthonormal basis of \mathcal{H}, let A \in \mathrm{End}\mathcal{H} be a normal operator, let \{\mathbf{f}_1,\dots,\mathbf{f}_n\} be an orthonormal basis of \mathcal{H} such that

A \mathbf{f}_j = \lambda_j \mathbf{f}_j \quad 1 \leq j \leq n,

and let U \in \mathrm{Aut}\mathcal{H} be the automorphism of \mathcal{H} defined by

U\mathbf{f}_j = \mathbf{e}_j, \quad 1 \leq j \leq n,

i.e. U is the unitary operator which transforms the eigenvectors of A into our preferred basis of \mathcal{H}.

Problem 3.1: Prove that the operator U above is indeed unitary, which by definition means that it is invertible and preserves the scalar product.

Problem 3.2: Prove that U \in \mathrm{End} \mathcal{H} is unitary if and only if it is invertible and satisfies \langle \mathbf{v},U\mathbf{w}\rangle = \langle U^{-1}\mathbf{v},\mathbf{w} \rangle for all \mathbf{v},\mathbf{w} \in \mathcal{H}.

We now compute the matrix elements of a power A^r in the initial basis as follows:

\langle \mathbf{e}_i,A^r\mathbf{e}_j \rangle = \langle U\mathbf{f}_i,A^rU\mathbf{f}_j \rangle \\=\left\langle \sum\limits_{k=1}^n \langle \mathbf{f}_k,U\mathbf{f}_i\rangle \mathbf{f}_k,A^r\sum\limits_{l=1}^n \langle \mathbf{f}_l,U\mathbf{f}_j\rangle \mathbf{f}_l \right\rangle \\=\sum\limits_{k=1}^n\sum\limits_{l=1}^n \overline{\langle \mathbf{f}_k,U\mathbf{f}_i\rangle}\langle \mathbf{f}_l,U\mathbf{f}_j\rangle \langle \mathbf{f}_k,A^r\mathbf{f}_l\rangle \\ =\sum\limits_{k=1}^n\sum\limits_{l=1}^n \overline{\langle \mathbf{f}_k,U\mathbf{f}_i\rangle} \lambda_k^r \langle \mathbf{f}_l,U\mathbf{f}_j\rangle \langle \mathbf{f}_k,\mathbf{f}_l\rangle \\ =\sum\limits_{k=1}^n \overline{\langle \mathbf{f}_k,U\mathbf{f}_i\rangle} \lambda_k^r \langle \mathbf{f}_k,U\mathbf{f}_j\rangle \\ = \sum\limits_{k=1}^n \overline{\langle \mathbf{f}_k,\mathbf{e}_i\rangle} \lambda_k^r \langle \mathbf{f}_k,\mathbf{e}_j\rangle \\ =  \sum\limits_{k=1}^n \langle \mathbf{e}_i,\mathbf{f}_k\rangle \lambda_k^r \overline{\langle \mathbf{e}_j,\mathbf{f}_k\rangle}.

In particular, noting that the adjacency operator of a given undirected graph \mathrm{G} is selfadjoint and hence normal, we combine the above with Theorem 1 from Lecture 2 to obtain the following result.

Theorem 2: The number of r-step walks from vertex i to vertex j in \mathrm{G} is

W^r(i,j) = \sum\limits_{k=1}^n \langle \mathbf{e}_i,\mathbf{f}_k\rangle \lambda_k^r \overline{\langle \mathbf{e}_j,\mathbf{f}_k\rangle},

where \mathbf{f}_1,\dots,\mathbf{f}_n is an orthonormal basis of the Hilbert space \mathbb{C}\mathrm{G} consisting of eigenvectors of the adjacency operator, A\mathbf{f}_j=\lambda_j\mathbf{f}_j.

Remark: The adjacency operator A of a graph \mathrm{G} is not only selfadjoint, but symmetric. Consequently, the complex conjugate can be omitted from the formula.

Theorem 2 is a conceptually clear result, but actually applying it to a particular graph could be difficult, since one must find all spectral information, i.e. both the eigenvectors and the eigenvalues of the adjacency operator. For some “easy” graphs, this procedure is straightforward.

Problem 3.3: Find the eigenvalues and eigenvectors of the complete graph \mathrm{K}(n) on \{1,\dots,n\}, and use Theorem 2 to recover the formulas W^r(1,1) and W^r(1,2) previously derived using combinatorics and commutative algebra.

In order to make progress on the question of card shuffling as discussed in Lecture 1, we need to do two things. First, we need a version of Theorem 2 for random walks, and second we need to implement this for \mathrm{S}(n) rather than \mathrm{K}(n). Concerning the first point, this is trivial for regular graphs, being an instance the following principle:

Probability is just combinatorics divided by n.

Gian-Carlo Rota

For non-regular graphs Rota’s principle fails there are some additional complications, which we will deal with next week. A more serious obstacle is that the Cayley graph of \mathrm{S}(n) as generated by the conjugacy class \mathrm{T} of transpositions is enormous and complicated: compared to \mathrm{K}(n), the number of vertices goes up from quadratic to factorial, and the edge structure is far more involved as well. It may thus seem impossible to implement Theorem 2 for \mathrm{S}(n). The reason it’s not impossible is that, unlike \{1,\dots,n\}, the vertex set \mathrm{S}(n) is not just a set but a group.

Indeed, the perspective that we are developing is that the representation theory of finite groups is the subject that one must invent in order to successfully use spectral graph theory to analyze Cayley graphs. It is not entirely historical fiction to say that this was one of the main motivations for the development of the theory: in the late 1800s, Adolf Hurwitz wanted to count walks on the Cayley graph of \mathrm{S}(n) as generated by the conjugacy class of transpositions in order to solve a problem in enumerative geometry, and he was able to make progress in doing this using the Fourier transform on \mathrm{S}(n). So, after a necessarily brief discussion about the linear-algebraic approach to random walks on finite graphs, we will begin developing Fourier analysis on groups, which is just representation theory viewed a little differently. We’ll start with some easy abelian groups, like the discrete circle (aka the subgroup \mathrm{C}(n) of \mathrm{S}(n) generated by the full forward cycle \gamma = (1\ 2\ \dots\ n), and go from there.

Leave a Reply