In Lecture 2, we showed that the problem of computing the number of -step walks on finite undirected graph with vertex set is equivalent to computing the matrix elements of the th power of the adjacency operator relative to the vertex basis of the Hilbert space . 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 acting in a finite-dimensional Hilbert space Recall the following theorem from Math 202A.
Theorem 1: The operators admit a common orthonormal basis if and only if 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 be a given orthonormal basis of let be a normal operator, let be an orthonormal basis of such that
and let be the automorphism of defined by
i.e. is the unitary operator which transforms the eigenvectors of into our preferred basis of .
Problem 3.1: Prove that the operator above is indeed unitary, which by definition means that it is invertible and preserves the scalar product.
Problem 3.2: Prove that is unitary if and only if it is invertible and satisfies for all
We now compute the matrix elements of a power in the initial basis as follows:
In particular, noting that the adjacency operator of a given undirected graph 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 -step walks from vertex to vertex in is
where is an orthonormal basis of the Hilbert space consisting of eigenvectors of the adjacency operator,
Remark: The adjacency operator of a graph 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 on and use Theorem 2 to recover the formulas and 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 rather than Concerning the first point, this is trivial for regular graphs, being an instance the following principle:
Probability is just combinatorics divided byGian-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 as generated by the conjugacy class of transpositions is enormous and complicated: compared to 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 The reason it’s not impossible is that, unlike the vertex set 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 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 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 of generated by the full forward cycle and go from there.