Math 202C: Lecture 9

*** Problems due April 26 at 23:59 ***

Week Four review and preview.

We began with the algebraic approach to graphs, which you can think of as a natural road to go down after Math 202A. Given a finite, connected, simple graph $G=(S,T)$ with vertex set $S=\{\pi,\rho,\sigma,\dots\}$ , we pass to the Hilbert space $\mathcal{C}(S)$ with orthonormal basis $|\pi\rangle,|\rho\rangle,|\sigma\rangle,\dots.$ We encode the edge set $T$ as a linear transformation of $\mathcal{C}(S),$ which by abuse of notation we also denote $T \in \mathrm{End}\mathcal{C}(S)$ because it contains exactly the same information. That is, we define the adjacency operator by

$T|\rho\rangle = \sum\limits_{\sigma} |\sigma\rangle,$

where the sum is over all $\sigma \in S$ such that $\{\rho,\sigma\} \in T.$ The adjacency operator is self-adjoint, and we could equally well define it by

$\langle \sigma |T = \sum\limits_{\rho} \langle \rho|,$

where the sum is over all $\rho \in S$ such that $\{\rho,\sigma\} \in T.$ Either definition of $T$ is consistent with

$\langle \sigma | T |\rho\rangle = \begin{cases} 1, \text{ if } \rho,\sigma \text{ adjacent }\\ 0, \text{ otherwise}\end{cases}.$

More generally, for any nonnegative integer $r$ the matrix element $\langle \sigma |T^r |\rho\rangle$ equals the number of $r$ -step walks $\rho \to \sigma$ in the graph $G=(S,T)$ . The linear algebraic approach is to find an orthonormal basis $B \subset \mathcal{C}(S)$ such that $T$ belongs to the maximal commutative subalgebra $\mathcal{D}(B) \leq \mathrm{End}\mathcal{C}(S)$ consisting of operators which act diagonally on $B.$

We also observed that the adjacency operator $T$ is the first member of a sequence $T=L_1,L_2,L_3,\dots$ of selfjadoint linear operators on $\mathcal{C}(S)$ which we called the level operators of the graph $G=(S,T).$ These operators encode not just adjacency in $G=(S,T),$ but its complete structure as a finite connected metric space. By definition,

$L_r|\rho\rangle = \sum\limits_{\mathrm{d}(\rho,\sigma)=r} |\sigma\rangle,$

where $\mathrm{d}$ is geodesic distance in $G=(S,T)$ . That is, $L_r$ acts on an input vertex $|\rho\rangle$ by summing all vertices $|\sigma\rangle$ in the sphere of radius $r$ centered at $\rho$ . Equivalently,

$\langle \sigma | L_r |\rho\rangle = \begin{cases} 1, \text{ if } \mathrm{d}(\rho,\sigma)=r\\ 0, \text{ otherwise}\end{cases}.$

We noted that although $T=L_1,L_2,L_3,\dots$ is a finite family of selfadjoint operators in $\mathrm{End}\mathcal{C}(S)$ , it may not be a commutative family. Indeed, we have

$\langle \sigma | L_sL_r |\rho\rangle = |S_r(\rho) \cap S_s(\sigma)|,$

where $S_r(\rho)$ and $S_s(\sigma)$ are the spheres of radii $r$ and $s$ centered at the vertices $\rho$ and $\sigma,$ respectively. There is no general reason why this would be equal to

$\langle \sigma | L_rL_s |\rho\rangle = |S_r(\sigma) \cap S_s(\rho)|.$

Indeed, the subalgebra $\mathcal{L}(G)$ of $\mathcal{C}(G)$ generated by the selfadjoint operators $L_r,$ $r \geq 0$ is in general not well-understood.

Problem 9.1. If $G=(S,T)$ is a finite connected simple graph of diameter $n$ , show that $\{L_0,L_1,\dots,L_n\}$ is an orthogonal set in $\mathrm{End}\mathcal{C}(G)$ with respect to the Hilbert-Schmidt (aka Frobenius) scalar product. In particular, conclude that $\mathcal{L}(G)$ is a subalgebra of dimension at least $n+1.$

Although the algebra $\mathcal{L}(G)$ generated by the selfadjoint operators $L_0,L_1,L_2,\dots$ is not well-understood, the complete sequence of level operators can be conveniently wrapped into a single operator

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

called the exponential distance operator of $G=(S,T).$ The sum is finite because $L_r$ is the zero operator for all $r$ which exceed the diameter of $G.$ Note that $\Omega_q$ is really a one-parameter family of operators in $\mathrm{End}\mathcal{C}(G)$ depending on $q \in \mathbb{C}$ ; note also that $\Omega_q$ is selfadjoint for $q \in \mathbb{R}.$ The reason for the name “exponential distance operator” is that

$\Omega_q|\rho\rangle = \sum\limits_{\sigma \in S} q^{\mathrm{d}(\rho,\sigma)}|\sigma\rangle,$

which says that the matrix of $\Omega_q$ is the entrywise exponential of the distance matrix of $G=(S,T),$

$\langle \sigma | \Omega_q | \rho \rangle = q^{\mathrm{d}(\rho,\sigma)}.$

In recent years, graph theorists have grappled with the spectral theory of $\Omega_q$ without recognizing its true significance: the exponential distance operator encodes the same information as the distance operator in a way which interfaces more meaningfully with statistical mechanics on graphs. We spent some time exploring this in Week One.

Now we move on to a concrete case of the above in which $G=(S,T)$ is a specific family of graphs. Namely, we consider the graphs $G_n=(S_n,T_n)$ in which $S_n=\mathrm{Aut}\{1,\dots,n\}$ is the symmetric group and $T_n \subseteq S_n$ is the conjugacy class of transpositions. This looks strange because the edge set of a graph is not a subset of its vertex set; however for Cayley graphs of groups it can be regarded as such. More precisely, two vertices $\rho,\sigma \in S_n$ are adjacent in $G_n$ if and only if there exists $\tau \in T_n$ such that $\sigma = \rho\tau.$ The fact that we have group law means that we can consider adjacency as induced by multiplication. This same feature propagates up to the level of linear operators, where we can also identify $T_n \subseteq S_n$ with the adjacency operator $T_n \in \mathrm{End}\mathcal{C}(S_n)$ using convolution in $\mathcal{C}(S_n),$ which is itself induced by multiplication in $S_n$ . Namely, for any arbitrary subset $A \subseteq S_n$ we have a corresponding vector in $|A\rangle \in \mathcal{C}(S_n),$

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

which in turn gives becomes an operator $A \in \mathrm{End}\mathcal{C}(S_n)$ ,

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

Applying this recipe to the conjugacy class $T_n \subseteq S_n$ implements the adjacency operator on $G_n=(S_n,T_n)$ as right multiplication by $|T_n\rangle.$ More generally, $T_n=L_1$ is the sphere of radius one centered at the identity permutation $\iota \in S_n.$ If we apply this recipe to the sphere $L_r \subseteq S_n$ of radius $r$ centered at $\iota,$ we first get the vector

$|L_r\rangle = \sum\limits_{|\pi|=r} |\pi\rangle,$

which in turn becomes the operator

$L_r|\rho\rangle = \sum\limits_{|\pi|=r} |\rho\pi\rangle.$

These facts hold for all Cayley graphs. What is special about the case $G_n=(S_n,T_n)$ is that all of the spheres $L_0,L_1,L_2,\dots \subseteq S_n$ are invariant under conjugation, and in fact are disjoint unions of conjugacy classes in an especially transparent way,

$L_r = \bigsqcup\limits_{\substack{\alpha \vdash n \\ \ell(\alpha)=n-r}}C_\alpha,$

where $C_\alpha \subseteq S_n$ is the conjugacy class of permutations of cycle type $\alpha.$ This immediately implies that

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

is a central element in $\mathcal{C}(S_n),$ and hence that $L_1,L_2,L_3,\dots \in \mathrm{End}\mathcal{C}(S_n)$ are commuting selfadjoint operators. In particular, there exists an orthonormal basis $B \subset \mathcal{C}(S_n)$ such that $L_1,L_2,L_3,\dots$ belong to the corresponding diagonal subalgebra $\mathcal{D}(B) \leq \mathrm{End}\mathcal{C}(S_n).$ Actually, we can say something stronger. Starting with a subset $A \subseteq S_n$ , when we make the chain of identifications

$A \longrightarrow |A\rangle \longrightarrow A,$

the first arrow is quantization and the second is the regular representation. Saying that $A \subseteq S_n$ is conjugation invariant is exactly the same thing as saying that $|A\rangle \in \mathcal{C}(S_n),$ which in turn means (by Schur’s Lemma) that $A \in \mathrm{End}\mathcal{C}(S_n)$ acts as multiplication by a scalar operator with eigenvalue $\widehat{A}(\lambda)$ in every irreducible subrepresentation $V^\lambda$ of $\mathcal{C}(S_n).$ So, not only are the operators $L_0,L_1,L_2,\dots,L_{n-1}$ simultaneously diagonalizable, they are actually simultaneously diagonal in any orthonormal basis $B^\lambda$ of any irreducible representation $V^\lambda$ . But this is all abstractly true — what we do not have is a concrete formula for the Fourier transform $\widehat{L}^r(\lambda)$ of $L_r$ acting in a given irreducible representation $V^\lambda.$ In particular, we do not have any explicit numerical understanding of the spectrum of the adjacency operator $L_1=T_n$ of the graph $G_n=(S_n,T_n),$ and this is the information that we wish to obtain.

The first step down the path to explicitly diagonalizing the level operators of $G_n = (S_n,T_n)$ is recognize path is to recognize that the central elements $|L_0\rangle,|L_1\rangle,\dots,|L_{n-1}\rangle\rangle$ are nonlinear functions of a fundamental family of non central elements which are even more granular than conjugacy classes. Namely, we decompose

$T_n = J_1 \sqcup J_2 \sqcup \dots \sqcup J_n$ ,

where $J_t$ is the set of transpositions of the form $(st)$ with $s<t.$ These are the Jucys-Murphy subsets of $S_n$ , and the corresponding algebra elements

$|J_t\rangle = \sum\limits_{1 \leq s<t} |st\rangle, \quad 1 \leq t \leq n$

give a decomposition

$|T_n\rangle = |J_1\rangle + |J_2\rangle + \dots + |J_n\rangle$

into pairwise orthogonal elements whose norms are

$\|J_1\|=0, \|J_2\|=1, \|J_3\|=\sqrt{2},\dots,\|J_n\|=\sqrt{n-1}.$

Even though the Jucys-Murphy elements do not lie in the center $\mathcal{Z}_n=\mathcal{C}(S_n)$ of the convolution algebra they commute with one another. Hence, the Jucys-Murphy operators $J_1,J_2,\dots,J_n \in \mathrm{End}\mathcal{C}(S_n)$ are commuting selfadjoint operators, and hence are simultaneously diagonalizable. The simple but important way to see this commutativity is to recognize that we have a chain of groups

$S_0 \subset S_1 \subset S_2 \subset \dots \subset S_n$

in which $S_k=\mathrm{Aut}\{1,\dots,k\}$ is identified with the subgroup of $S_n$ consisting of permutations which fix $k+1,\dots,n.$ This gives a chain of subalgebras

$\mathcal{C}(S_0) \subset \mathcal{C}(S_1) \subset \mathcal{C}(S_2) \subset \dots \subset\mathcal{C}(S_n),$

in which $\mathcal{C}(S_k)$ is the span of all permutations which fix $k+1,\dots,n.$ Each of these subalgebras comes with its own center $\mathcal{Z}_k=Z\mathcal{C}(S_k),$ and while the commutative subalgebras

$\mathcal{Z}_1,\dots,\mathcal{Z}_n$

are not nested (in fact $\mathcal{Z}_k \cap \mathcal{Z}_l =\mathbb{C}|\iota\rangle$ for $k \neq l$ ) they commute with one another, and the the JM-elements $|J_1\rangle,\dots,|J_n\rangle$ belong to the commutative subalgebra $\mathcal{J}_n \subseteq \mathcal{C}(S_n)$ generated by their union,

$\mathcal{Z}_1 \cup \dots \cup \mathcal{Z}_n.$

We proved that $|J_1\rangle,|J_2\rangle,\dots,|J_n\rangle$ pairwise commute by showing that they are contained in the algebra $\mathcal{J}_n.$ Indeed, we have that

$|J_k \rangle = |T_k\rangle - |T_{k-1}\rangle$

is contained in the commutative algebra generated by $\mathcal{Z}_{k-1} \cup \mathcal{Z}_k$ in $\mathcal{C}(S_n).$ The key result which marks the transition from linear algebra to polynomial algebra in Math 202C is the following.

Theorem 9.1. We have

$|L_r\rangle = e_r(|J_1\rangle,\dots,|J_n\rangle),$

where $e_r(x_1,\dots,x_n)$ is the elementary symmetric polynomial of degree $r.$

A good way to test your understanding of this key result is to solve the following problem.

Problem 9.2. Prove that the exponential distance operator $\Omega_q$ of the Cayley graph $G_n=(S_n,T_n)$ factors as

$\Omega_q = (I+qJ_1)(I+qJ_2) \dots (I+qJ_n).$

Deduce from this that $\Omega_q$ is invertible for all complex $q$ satisfying $|q| < \frac{1}{n-1}.$

Theorem 9.1 is what led us into a discussion of polynomials in general, and symmetric polynomials in particular. The algebra $\mathcal{P}_n=\mathbb{C}[x_1,\dots,x_n]$ of polynomials in $n$ commuting selfadjoint variables has basis

$x^\alpha = x_1^{\alpha_1} \dots x_n^{\alpha_n}, \quad \alpha \in \mathrm{Com}_n$

indexed by the set $\mathrm{Com}_n$ of nonnegative integer vectors $\alpha=(\alpha_1,\dots,\alpha_n).$ We equip $\mathcal{P}_n$ with the scalar product in which $\{x^\alpha \colon \alpha \in \mathrm{Com}_n\}$ is orthonormal. We then have the orthogonal decomposition

$\mathcal{P}_n =\bigoplus\limits_{d=0}^\infty \mathcal{P}_n^d,$

where

$\mathcal{P}_n^d = \mathrm{Span}\{x^\alpha \colon \alpha \in \mathrm{Com}_n^d\}$

with $\mathrm{Com}_n^d = \{\alpha \in \mathrm{Com}_n \colon \alpha_1+\dots+\alpha_n=d\}.$

We consider the (infinite-dimensional) unitary representation $(\mathcal{P}_n,\varphi_n)$ of the symmetric group $S_n=\mathrm{Aut}\{1,\dots,n\}$ in which $\mathcal{P}_n$ is the polynomial algebra as above and

$\varphi_n(\pi) f(x_1,\dots,x_n)=f(x_{\pi^{-1}(1)},\dots,x_{\pi^{-1}(n)}).$

The space of invariants $\mathcal{S}_n=\mathcal{P}_n^{S_n}=\mathbb{C}[x_1,\dots,x_n]^{S_n}$ is (by definition) the algebra of symmetric polynomials in $n$ commuting selfadjoint variables. It has the orthogonal decomposition

$\mathcal{S}_n = \bigoplus\limits_{d=0}^\infty \mathcal{S}_n^d$

with $\mathcal{S}_n^d = \mathcal{S}_n \cap \mathcal{P}_n^d.$ An orthogonal basis for $\mathcal{S}_n$ is given by the monomial symmetric polynomials

$m_\lambda(x_1,\dots,x_n) = \sum\limits_{\alpha \in \mathcal{O}_\lambda} x^\alpha$

where $\lambda$ ranges over the set $\mathrm{Par}_n \subset \mathrm{Com}_n$ of nonnegative integer vectors with weakly decreasing coordinates, and $\mathcal{O}_\lambda \subset \mathrm{Com}_n$ is the set of all $\alpha$ ’s whose weakly decreasing rearrangement is $\lambda$ .

Problem 9.3. Give a bijection $\Phi$ between $\mathrm{Par}_n$ and the set of all $n$ -element subsets of $\mathbb{N}_0=\{0,1,2,3,\dots\}.$ Express the sum of the elements of $\Phi(\lambda)$ in terms of the sum $|\lambda|$ of the coordinates of $\lambda.$

The elementary symmetric polynomials $e_0,e_1,\dots,e_n \in \mathcal{S}_n$ are defined by

$e_r(x_1,\dots,x_n)=m_{(1^r,0^{n-r})}(x_1,\dots,x_n), \quad 0 \leq r \leq n$ ,

where $(1^r,0^{n-r})=(1,\dots,1,0,\dots,0)$ is the vector whose first $r$ coordinates equal $1$ and remaining coordinates equal $0.$ For $r>n$ , we declare $e_r$ to be the zero polynomial. Let $\mathrm{Par}$ be the set of nonnegative integer vectors of infinite length whose coordinates are weakly decreasing and eventually equal zero, and define

$e_\lambda(x_1,\dots,x_n) = \prod\limits_{i=1}^\infty e_{\lambda_i}(x_1,\dots,x_n)$ .

The condition $\lambda^\prime \in \mathrm{Par}_n$ is necessary and sufficient in order that $e_\lambda$ is not the zero polynomial, and we proved that

$\{e_\lambda(x_1,\dots,x_n) \colon \lambda^\prime \in \mathrm{Par}_n\}$

is a basis of $\mathcal{S}_n.$ This result is called the fundamental theorem of symmetric polynomials.

We are now going to consider a further algebraic consequence of this result. Let $\mathcal{C}(S_n)$ be the convolution algebra of the symmetric group $S_n=\mathrm{Aut}\{1,\dots,n\}$ . For each $1 \leq k \leq n,$ the symmetric group $S_k=\mathrm{Aut}\{1,\dots,k\}$ is isomorphic to the subgroup of $S_n$ consisting of permutations which fix the numbers $k+1,\dots,n.$ Thus we can view $\mathcal{C}(S_k)$ as the subalgebra of $\mathcal{C}(S_n)$ with basis $|\pi\rangle,$ $\pi \in S_k.$ Let $\mathcal{Z}_k$ denote the center of $\mathcal{C}(S_k)$ sitting inside $\mathcal{C}(S_n).$ The Jucys-Murphy algebra $\mathcal{J}_n$ is by definition the commutative subalgebra of $\mathcal{C}(S_n)$ generated by the set

$\mathcal{Z}_1 \cup \mathcal{Z}_2 \cup \dots \cup \mathcal{Z}_n.$

Within this subalgebra we have the Jucys-Murphy elements

$|J_k\rangle = |T_k\rangle - |T_{k-1}\rangle,\quad 1 \leq k \leq n,$

where $T_k$ is the conjugacy class of transpositions in $S_k.$ One of our first results is that level sets

$|L_r\rangle = \sum\limits_{\substack{\pi \in S_n \\ |\pi|=r}}|\pi\rangle$

are elementary symmetric polynomials evaluated on JM-elements,

$|L_r\rangle = e_r(|J_1\rangle,\dots,|J_n\rangle), \quad 0 \leq r \leq n-1.$

Since $|L_r\rangle \in \mathcal{Z}_n$ , combining this with the fundamental theorem of symmetric polynomials gives the following.

Theorem 9.2. For any $f \in \mathcal{S}_n=\mathbb{C}[x_1,\dots,x_n]^{S_n},$ we have $f(|J_1\rangle,\dots,|J_n\rangle) \in \mathcal{Z}_n.$

In words, this says that when you evaluate any arbitrary symmetric polynomial on the Jucys-Murphy elements and expand this out as a linear combination of permutations, every pair of conjugate permutations appears with the same coefficient.

As an example, let us consider the complete homogeneous symmetric polynomials, which are defined as

$h_r(x_1,\dots,x_n) = \sum\limits_{\lambda \vdash r} m_\lambda(x_1,\dots,_n)$ ,

where the sum is over all partitions of $r$ .

Problem 9.4 Prove that

$h_r(x_1,\dots,x_n)=\sum\limits_{1 \leq t_1 \leq \dots \leq t_r \leq n} x_{t_1}\dots x_{t_r},$

and deduce from this that

$h_r(|J_1\rangle,\dots,|J_n\rangle)=\sum\limits_{\pi \in S_n} \vec{W}^r(\pi)|\pi\rangle,$

where $\vec{W}^r(\pi)$ is the number of $r$ -step monotone walks $\iota \to \pi$ on the Cayley graph of $S_n.$

Thus, the function $\vec{W}^r(\pi)$ counts factorizations

$\pi=(s_1\ t_1) \dots (s_r\ t_r), \quad s_i<t_i,$

of a given permutation into transpositions subject to the condition

$t_1 \leq \dots \leq t_r.$

Problem 9.2 shows that $\vec{W}^r(\pi)$ depends only on the cycle type of $\pi.$ Although this fact has been known for over fifteen years, no combinatorial explanation has been found.

I will say a bit more about this enumerative problem since I know that some of you are Stirling number aficionados. For any permutation $\pi,$ the minimum length of a factorization of $\pi$ into transpositions is $|\pi|,$ and this upper bound of course applies to weakly monotone factorizations as well. Moreover, since we know that there exists a unique strictly monotone geodesic $\iota \to \pi,$ there is at least one weakly monotone geodesic.

Theorem 9.2. The number of weakly monotone factorizations of a full cycle $\gamma \in S_n$ into $r=n-1+2g$ transpositions is

$\vec{W}^{n-1+2g}(\pi) = \mathrm{Cat}_{n-1} \times T(n-1,n-1+2g),$

where $T(m,n)$ are the central factorial numbers of the second kind.

The central factorial numbers are certain generalizations of Stirling numbers which appear in quite a variety of situations.

The upshot of the above is that we actually know a few things about the algebra $\mathcal{L}_n=\mathcal{L}(G_n)$ for the all-transpositions Cayley graph $G_n=(S_n,T_n)$ of the symmetric group. Not only do we know that the distance operators $L_1,L_1,\dots,L_n$ , we have a polynomial representation of them in terms of the JM-operators $J_1,\dots,J_n.$ In particular, we know that the commutative algebra $\mathcal{L}_n$ is a subalgebra of $\mathcal{J}_n$ . Over the course of the next two lectures, we will prove that in fact $\mathcal{L}_n=\mathcal{J}_n.$ We will then pivot and give a completely different spectral description of this algebra in terms of a distinguished orthonormal basis of $\mathcal{C}(S_n)$ , known as its Gelfand-Tsetlin basis.

Math 202C: Lecture 9

Like this:

Published by Jonathan Novak

Leave a ReplyCancel reply

Share this:

Like this:

Published by Jonathan Novak

Leave a ReplyCancel reply

Discover more from Jonathan Novak