Math 202C: Lecture 3

*** All problems in this lecture due April 12 at 23:59 ***

We return to the general setting of a finite, connected, simple graph G=\mathrm{Cay}(S,T), and as before \mathcal{C}(S) the Hilbert space with orthonormal basis |\pi\rangle, |\rho\rangle,|\sigma\rangle,\dots. In Lecture 1 we introduced the metrics level set linear operators L_0,L_1,L_2,\dots in \mathrm{End}\mathcal{C}(S) which act on vertices according to

L_r|\rho\rangle = \sum\limits_{\substack{\sigma \in S \\ \mathrm{d}(\rho,\sigma)=r}} |\sigma\rangle.

We argued the case that these operators are quite fundamental: L_0=I is the identity operator, L_1=K is the adjacency operator,

D = \sum\limits_{r=0}^\infty rL_r

is the distance operator,

\Omega_q=\sum\limits_{r=0}^\infty q^r L_r

is the exponential distance operator. However, the selfadjoint operators L_0,L_1,L_2,\dots and the subalgebra of \mathrm{End}\mathcal{C}(S) they generate are not easy to understand.

Problem 3.1. Show that \langle \sigma|L_sL_r|\rho\rangle is the cardinality of the intersection of the sphere of radius r centered at \rho with the sphere of radius s centered at \sigma.

So, the matrix elements of the commutator

[L_s,L_r]=L_sL_r - L_rL_s

are differences of intersection numbers,

\langle \sigma | [L_s,L_r] |\rho\rangle = |S_\rho(r) \cap S_\sigma(s)|-|S_\rho(s) \cap S_\rho(r)|,

and if it seems difficult to characterize graphs for which all such differences are zero, that’s because it is. There is one much-studied class of graphs which does have the property that metric level set operators L_0,L_1,L_2,\dots commute.

Problem 3.2. Show that if G is a distance regular graph, then [L_r,L_s]=0.

The following is the only restricted situation in which I personally know a simple combinatorial characterization of commutativity of the metric level set operators (it is likely that an actual graph theorist would know more).

Problem 3.3. Suppose G has diameter 2. Prove that the metric level set operators on G commute if and only if G is a regular graph. (Hint: the basic reason behind this is that in a graph of diameter 2, the metric does not contain any more information than the adjacency relation).

I am torturing you (us, really) with these combinatorial considerations because I want to further hammer home the point that Cayley graphs are much easier to understand than general graphs due to the underlying group structure, which is reflected in the behavior of linear operators acting on the vertices of the graph.

Suppose that S=\{\pi,\rho,\sigma,\dots\} is a finite group, so that \mathcal{C}(S) is the convolution algebra of this group. For any arbitrary subset A \subseteq S, we write

|A\rangle=\sum\limits_{\pi \in A}|\pi\rangle,

which is simply the indicator function of the set A. It is a very convenient abuse of notation to also simply write A for the image of |A\rangle in the right regular representation, i.e. we identity the set A \subseteq S with the operator A \in \mathrm{End}\mathcal{C}(S) defined by

A|\rho\rangle = |\rho\rangle|A\rangle=\sum\limits_{\pi \in A} |\rho\pi\rangle.

Recall from Math 202B that we have a tracial state

\langle \cdot \rangle \colon \mathcal{C}(S) \longrightarrow \mathbb{C}

on the convolution algebra of S defined by

\langle A \rangle := \langle \iota |A\rangle,

where \iota \in S is the group identity. In other words, \langle A \rangle is the coefficient of the vector |A\rangle in the group basis |\pi\rangle, which is the same thing as the value of the function A at the point \pi=\iota. Here is a second under-appreciated characterization of this important functional, which is often referred to as the canonical group trace.

Problem 3.4. Prove that all diagonal matrix elements \langle \pi | A |\pi\rangle of the image A \in \mathrm{End}\mathcal{C}(S) of |A\rangle\in \mathcal{C}(S) in the regular representation are equal to the same number, and that that number is \langle A \rangle. Hence conclude (as was already shown in Math 202B) that the \langle A \rangle =\frac{1}{|S|}\mathrm{Tr} A.

Now to Cayley graphs. We continue with a finite group S and select inside it a symmetric set of generators T, giving us the Cayley graph G = \mathrm{Cay}(S,T). As discussed above, we may also view T \in \mathrm{End}\mathcal{C}(S) as the adjacency operator on G.

Problem 3.5. Show that \langle T^r\rangle is the number of length r loops based at the identity element (or any other specified point) in S.

Now specialize to the case where S=\mathrm{Aut}\{1,\dots,n\} is the symmetric group and T is the full conjugacy class of transpositions. The metric level set operators L_0,L_1,L_2,\dots \in \mathrm{End}\mathcal{C}(S) commute for a very simple reason: they are the images of the vectors

|L_r \rangle = \sum\limits_{\substack{\pi \in S \\ |\pi|=r}} |\pi\rangle, \quad r=0,1,2,\dots,

and these vectors lie in the center of the convolution algebra \mathcal{C}(S). Indeed, the center of \mathcal{C}(S) is spanned by the conjugacy classes

|C_\alpha\rangle = \sum\limits_{\pi \in C_\alpha} |\pi\rangle, \quad \alpha \in \Lambda,

and

|L_r\rangle = \sum\limits_{\substack{\alpha \vdash n \\ \ell(\alpha)=n-r}} |C_\alpha\rangle

is simply the sum of all conjugacy classes corresponding to partitions of n with n-r parts.

The fact that the level set operators L_0,L_1,L_2,\dots on a graph G commute is equivalent to saying that they are simultaneously diagonalizable. However, in the group-theoretic setting this statement can be refined. Let us stick with the case where S=\mathrm{Aut}\{1,\dots,n\} is the symmetric group, noting that what follows is true for the Cayley graph G=\mathrm{Cay}(S,T) of any finite group S with generating set T \subseteq S such that |T\rangle is a central element in the convolution algebra \mathcal{C}(S). Let \Lambda be a set indexing the conjugacy classes in S, so for the symmetric group \Lambda is the set of partitions of n. Then \Lambda also indexes isomorphism classes of irreducible unitary representations of S, or equivalently irreducible linear representations of \mathcal{C}(S). For each \lambda \in \Lambda, choose a representative (V^\lambda,\Phi^\lambda) of the corresponding isomorphism class. By Schur’s Lemma, any central element |A\rangle \in \mathcal{C}(S) acts in each irrep (V^\lambda,\Phi^\lambda) as a scalar operator: we have

\Phi^\lambda|A\rangle = \widehat{A}(\lambda) I_{V^\lambda}, \quad \widehat{A}(\lambda) \in \mathbb{C}.

Let us apply this to the adjacency operator on the all-transpositions Cayley graph G=\mathrm{Cay}(S,T) of the symmetric group, which is the image of the central element

|T\rangle = \sum\limits_{\tau \in T} |\tau\rangle= \sum\limits_{1 \leq s<t \leq n} |s\ t\rangle.

The eigenvalues of the adjacency operator T \in \mathrm{End}\mathcal{C}(S) are the numbers

\widehat{T}(\lambda) = {n \choose 2} \frac{\chi^\lambda(\tau)}{\dim V^\lambda}, \quad \lambda \in \Lambda,

where \tau \in T is any transposition. Moreover, where the multiplicity of \widehat{T}(\lambda) is (\dim V^\lambda)^2 because the isotypic decomposition of the regular representation is

\mathcal{C}(S) = \bigoplus\limits_{\lambda \in \Lambda} (\dim V^\lambda)V^\lambda.

Thus, in a sense, we completely know the spectrum of the adjacency operator on the all-transpositions Cayley graph of the symmetric group. However, to actually compute these numbers explicitly, we need to know both the dimension

\dim V^\lambda = \chi^\lambda(\iota) = \mathrm{Tr}\varphi^\lambda(\iota)

of every irreducible unitary representation (V^\lambda,\varphi^\lambda) of S, as well as the character

\chi^\lambda(\tau) = \mathrm{Tr} \varphi^\lambda(\tau)

of a transposition in each representation.

This highlights the fact that we really only know the irreducible unitary representations (V^\lambda,\varphi^\lambda) of S=\mathrm{Aut}\{1,\dots,n\} abstractly. In particular, while we know that the irreducible representations of S are (up to isomorphism) in bijection with the conjugacy classes in S, we have not explicitly selected such a bijection and it is not at all clear how best to do so.

Nevertheless, there are a few things we can say concretely at this stage. First, as with every group, S has the trivial representation (V^\mathsf{triv},\varphi^\mathsf{triv}) in which V^\mathsf{triv} is a one-dimensional Hilbert space and \varphi^\mathsf{triv} sends every \sigma \in S to the identity operator on this space. For this representation, we have

\widehat{T}^\mathsf{triv}={n \choose 2} \frac{\chi^\mathsf{triv}(\tau)}{\dim V^\mathsf{triv}}= {n \choose 2},

and we have reproduced the fact that the degree of the regular graph G=\mathrm{Cay}(S,T) is an eigenvalue of its adjacency operator.

Second, the symmetric group S has a second one-dimensional representation (V^\mathsf{alt},\varphi^\mathsf{alt}) in which

\varphi^\mathsf{alt} = (-1)^{|\sigma|}I.

This gives the eigenvalue

\widehat{T}^\mathsf{alt}={n \choose 2} \frac{\chi^\mathsf{alt}(\tau)}{\dim V^\mathsf{alt}}=- {n \choose 2},

which could also be deduced from the fact that the spectrum of the adjacency operator on a bipartite graph is symmetric about zero.

We can compute a third eigenvalue of the adjacency operator on the all-transpositions Cayley graph which is not directly accessible without representation-theoretic methods. To do so, we start with the permutation representation (V^\mathsf{perm},\varphi^\mathsf{perm}), in which V is the Hilbert space with orthonormal basis |1\rangle,\dots,|n\rangle and \varphi^\mathrm{perm}(\sigma)|i\rangle=|\sigma(i)\rangle. The character of this representation is

\chi^\mathsf{perm}(\sigma) = \sum\limits_{i=1}^n \langle i | \varphi^\mathsf{perm}(\sigma) | i\rangle = \sum\limits_{i=1}^n \langle i|\sigma(i)\rangle=\mathsf{fix}(\sigma),

the number of fixed points of the permutation \sigma. However, the permutation representation is not irreducible, as it has a one-dimensional invariant subspace spanned by the vector

|w\rangle = |1\rangle + \dots + |n\rangle.

The orthogonal complement of this vector gives an (n-1)-dimensional representation (V^\mathsf{std},\varphi^\mathsf{std}) of S called the standard representation, whose character satisfies

\chi^\mathsf{std}+\chi^\mathsf{triv}=\chi^\mathsf{perm}

and is therefore given by

\chi^\mathsf{std}(\sigma)=\mathsf{fix}(\sigma)-1.

Problem 3.6. Prove that the standard representation of S=\mathrm{Aut}\{1,\dots,n\} is irreducible, and give a third eigenvalue of the adjacency operator on the all-transpositions Cayley graph G=\mathrm{Cay}(S,T).

Published by Jonathan Novak

Mathematician at UC San Diego.

Leave a Reply