202C – Jonathan Novak

Math 202B: Lecture 15

Enumeration of topics:

Part $\mathcal{A}$ : Abstract algebras.
Part $\mathcal{F}$ : Function algebras.
Part $\mathcal{E}$ : Endomorphism algebras.
Part $\mathcal{C}$ : Convolution algebras.
Part $\mathcal{Z}$ : Class algebras.
Part $\mathcal{P}$ : Polynomial algebras.
Part $\mathcal{G}$ : Gelfand-Tsetlin algebras.

The function algebra of a finite set $X$ is the set $\mathcal{F}(X)$ of functions $A \colon X \to \mathbb{C}$ with operations defined pointwise. A basic family of functions are the elementary functions,

$E_x(y)=\delta_{xy}, \quad x,y \in X.$

Theorem F1. The elementary functions are nonzero pairwise orthogonal projections.

Combining Theorem F1 with Theorem A3, we get that the set $\{E_x \colon x \in X\}$ is a basis of $\mathcal{F}(X)$ .

The algebra $\mathcal{F}(X)$ can be understood completely. In particular, subalgebras can be explicitly classified. A partition of $X$ is a set $\mathfrak{p}=\{P_1,\dots,P_m\}$ of nonempty disjoint subsets of $X$ whose union is $X$ . The elements $P_i$ of $\mathfrak{p}$ are called its blocks. The set $\mathfrak{P}(X)$ of partitions of $X$ is partially ordered set under the refinement order, where $\mathfrak{p} \leq \mathfrak{q}$ if and only if $\mathfrak{q}$ can be obtained from $\mathfrak{p}$ by breaking blocks. Associated to every $\mathfrak{p} \in \mathfrak{P}(X)$ is the subalgebra $\mathcal{A}(\mathfrak{p})$ consisting of functions constant on the blocks of $\mathfrak{p}.$ Note that $\mathcal{A}(\mathfrak{p})$ is isomorphic to $\mathcal{F}(\mathfrak{p}).$

Theorem F2. The set $\{\mathcal{A}(\mathfrak{p}) \colon \mathfrak{p} \in \mathfrak{P}(X)\}$ is the complete collection of subalgebras of $\mathcal{F}(X)$ . Moreover, $\mathcal{A}(\mathfrak{p}) \leq \mathcal{A}(\mathfrak{q})$ if and only if $\mathfrak{p}\leq \mathfrak{q}.$

This classification theorem can be proved in several ways. A nice argument uses the finite-dimensional Stone-Weierstrass theorem. A subalgebra $\mathcal{A} \leq \mathcal{F}(X)$ is said to separate points if, for every $\{x,y\} \subseteq X,$ there exists a function $A \in \mathcal{A}$ such that $A(x) \neq A(y).$

Theorem F3. If $\mathcal{A} \leq \mathcal{F}(X)$ separates points, then $\mathcal{A}=\mathcal{F}(X).$

There is a parallel classification of ideals in $\mathcal{F}(X)$ . Let us order the set $\{S \subseteq X\}$ of all subsets of $X$ by inclusion. Associated to each $S \subseteq X$ is the ideal

$\mathcal{I}(S) = \{A \in \mathcal{F}(X) \colon A(x)=0 \text{ for all }x \in S\}.$

Theorem F4. The set $\{\mathcal{I}(S) \colon S \subseteq X\}$ is the complete collection of ideals in $\mathcal{F}(X)$ . Moreover, $\mathcal{I}(S) \subseteq \mathcal{I}(T)$ if and only if $T \subseteq S.$

Just like Theorem F2 shows that we cannot discover any new algebras by looking at subalgebras of functional algebras, Theorem F4 reveals that we cannot discover any new algebras by taking quotients of function algebras.

Theorem F5. For any $S \subseteq S,$ the quotient algebra $\mathfrak{F}(X)/\mathcal{I}(S)$ is isomorphic to the function algebra $\mathcal{F}(S).$

Now let us classify von Neumann algebra structures on $\mathcal{F}(X)$ . This means that we will find all Frobenius scalar products on $\mathcal{F}(X)$ ; since $\mathcal{F}(X)$ is commutative there is no distinction between left-Frobenius and right-Frobenius. Equivalently, we classified faithful states on $\mathcal{F}(X)$ , all of which are tracial. A function $P \in \mathcal{F}(X)$ is called a probability distribution if $P(x) \geq 0$ for all $x \in X$ , and $\sum_{x \in X} P(x)=1.$

Theorem F6. States $\sigma$ on $\mathcal{F}(X)$ are in bijection with probability distributions on $X$ : every state is of the form $\sigma(A) = \sum_{x \in X} A(x)P(x)$ for a unique probability distribution $P$ . Moreover, $\sigma$ is faithful if and only if $P$ is nonvanishing.

Theorem F6 is equivalent to the statement that all Frobenius scalar products are of the form

$\langle A,B \rangle = \sum\limits_{x \in X} \overline{A(x)}B(x)P(x)$

for a unique probability distribution $P$ having full support in $X.$

Going beyond understanding the inner workings of a given function algebra $\mathcal{F}(X),$ we can classify all algebras $\mathcal{A}$ which are isomorphic to a function algebra.$ Clearly, any such $\mathcal{A}$ must be commutative. A basis of $\mathcal{A}$ consisting of pairwise orthogonal projections is called a Fourier basis.

Theorem F7. An algebra $\mathcal{A}$ is isomorphic to a function algebra if and only if it admits a Fourier basis.

Theorem F7 is very important, and so is its proof. The fact that $\mathcal{F}(X)$ admits a Fourier basis is clear (the elementary functions). Conversely, suppose that $\mathcal{A}$ is an abstract algebra in which we are able to find a Fourier basis $\{F^\lambda\colon \lambda \in \Lambda\}$ indexed by some finite set $\Lambda$ . Then, every element $A \in \mathcal{A}$ can be expanded in this basis,

$A = \sum\limits_{\lambda \in \Lambda}\widehat{A}(\lambda)F^\lambda$

and the coefficients in this expansion define a function $\widehat{A} \in \mathcal{F}(\Lambda)$ . The mapping

$\Phi \colon \mathcal{A} \longrightarrow \mathcal{F}(\Lambda)$

defined by $\Phi(A) = \widehat{A}$ is an algebra isomorphism called the Fourier transform. The “the” here is justified by the following.

Theorem F8. The only Fourier basis is $\mathcal{F}(X)$ is the basis $\{E_x \colon x \in X\}$ of elementary functions.

Theorem F8 means that if a Fourier transform $\Phi \colon \mathcal{A} \to \mathcal{F}(\Lambda)$ exists, then it is unique up to relabeling the label set $\Lambda$ .

Math 202: Abstract Algebras

This is the review post for Part $\mathcal{A}$ : abstract algebras.

Throughout the Math 202 sequence and on the qualifying exam, the term “algebra” by default refers to a complex vector space $\mathcal{A}$ of positive, finite dimension equipped with a unital, associative, bilinear multiplication $\mathcal{A} \times \mathcal{A} \to \mathcal{A}$ denoted $(A,B) \mapsto AB$ and an antilinear, antimultiplicative, involution conjugation $\mathcal{A} \to \mathcal{A}$ denoted $A \mapsto A^*.$

The fundamental example is $\mathcal{A}=\mathbb{C}.$ Two further examples are $\mathbb{C}^n$ with coordinatewise multiplication and conjugation, and $\mathbb{C}^{n \times n}$ with matrix multiplication and Hermitian conjugation. Both coincide with $\mathbb{C}$ for $n=1.$ Thus, we have an example of a commutative algebra of every dimension, and for algebras of square dimension bigger than one we also have a noncommutative example.

Inside a given algebra $\mathcal{A}$ there are various classes of special elements. The broadest of these is the class of normal elements, which consists of those $A \in \mathcal{A}$ which commute with their conjugate, $A^*A=AA^*.$ Two subclasses thereof are selfadjoint elements which are equal to their conjugate, $X^*=X$ , and unitary elements which satisfy $U^*U=I.$ Normal elements which are both selfadjoint and unitary are called reflections and they satisfy $R^2=I.$ Selfadjoint elements which can be factored as $N=A^*A$ are called nonnegative, and selfadjoint elements such that $P^2=P$ are called projections. Two projections which satisfy $PQ=0$ are said to be orthogonal.

Theorem A1. Every $A \in \mathcal{A}$ can be written $A=X+iY$ with $X,Y$ selfadjoint. Furthermore, this decomposition is unique and $A$ is normal if and only if $X$ and $Y$ commute.

Theorem A2. An algebra $\mathcal{A}$ is commutative if and only if all its elements are normal.

Theorem A3. Any set of nonzero pairwise orthogonal projections in $\mathcal{A}$ is linearly independent.

The category $\mathbf{Alg}$ has algebras as objects. Morphisms are linear transformations $\Phi \colon \mathcal{A} \to \mathcal{B}$ such that

$\Phi(I_\mathcal{A}) = I_\mathcal{B},\ \Phi(AB)=\Phi(A)\Phi(B),\ \Phi(A^*)=\Phi(A)^*,$

and these are called algebra homomorphisms. Two algebras $\mathcal{A}$ and $\mathcal{B}$ are said to be isomorphic if and only if there exists a bijective homomorphism between them.

Theorem A4. If $\mathcal{A}$ is a one-dimensional algebra then there exists a unique isomorphism $\mathcal{A} \to \mathbb{C}.$

Theorem A5. If $\mathcal{A}$ is a two-dimensional algebra then it is commutative.

Given any algebra homomorphism $\Phi \colon \mathcal{A} \to \mathcal{B},$ the set

$\mathrm{Im}(\Phi) = \{\Phi(A) \colon A \in \mathcal{A}\}$

is a subspace of $\mathcal{B}$ which contains $I_\mathcal{B}$ and is closed under multiplication and conjugation, i.e. it is a subalgebra of $\mathcal{B}.$ The set

$\mathrm{Ker}(\Phi) =\{K \in \mathcal{A} \colon \Phi(K)=0_\mathcal{B}\}$

is a subspace of $\mathcal{A}$ which does not necessarily contain $I_\mathcal{A}.$ However, $\mathrm{Ker}(\Phi)$ is closed under multiplication and conjugation, and in fact for every $K \in \mathrm{Ker}(\Phi)$ we have $\{AK,KA\} \subset \mathrm{Ker}(\Phi)$ for all $A \in \mathcal{A}$ , i.e. $\mathrm{Ker}(\Phi)$ is an ideal in $\mathcal{A}.$

Like the collection of subspaces of a given vector space, we can partially order the set of subalgebras of a given algebra $\mathcal{A}$ by set-theoretic inclusion. This poset has a unique minimal element given by $\mathbb{C}I=\{\alpha I \colon \alpha \in \mathbb{C}\}$ and a unique maximal element of the poset of subalgebras of $\mathcal{A}$ is $\mathcal{A}$ itself. Given two subalgebras $\mathcal{B}$ and $\mathcal{C}$ of $\mathcal{A}$ , there is a unique maximal subalgebra contained in both of them, namely $\mathcal{B} \cap \mathcal{C}$ . There is also a unique minimal subalgebra containing both $\mathcal{B}$ and $\mathcal{C}$ , namely the intersection of all subalgebras containing $\mathcal{B} \cap \mathcal{C}$ . This is called the algebra generated by $\mathcal{B} \cup \mathcal{C}$ and it is denoted $\mathrm{Alg}(\mathcal{B} \cup \mathcal{C}).$

Theorem A6. We have $\mathrm{Alg}(\mathcal{B} \cup \mathcal{C})=\mathrm{Span}\{A_1 \dots A_m \colon m \geq 0,\ A_i \in \mathcal{B} \cup \mathcal{C}\}.$

In fact, for an arbitrary subset $S \subseteq \mathcal{A}$ there is a unique minimal algebra $\mathrm{Alg}(S)$ containing $S$ , namely the intersection of all subalgebras containing it, and this is called the subalgebra generated by $S$ .

Theorem A7. We have $\mathrm{Alg}(S) = \mathrm{Span}\{A_1 \dots A_m \colon m \geq 0,\ A_i \in S \cup S^*\},$ where $S^*=\{A^* \colon A \in S\}.$

An important subalgebra of a given algebra $\mathcal{A}$ is its center,

$Z(\mathcal{A)}=\{Z \in \mathcal{A} \colon ZA=AZ \text{ for all }A \in \mathcal{A}\}.$

We have $Z(\mathcal{A})=\mathcal{A}$ if and only if $\mathcal{A}$ is commutative, and $\dim Z(\mathcal{A})$ can be viewed as a measure of how (non)commutative $\mathcal{A}$ is.

In fact, subalgebras always come in pairs: given $\mathcal{B} \leq \mathcal{A}$ the corresponding centralizer is

$Z(\mathcal{B},\mathcal{A})=\{A \in \mathcal{A} \colon AB=BA \text{ for all }B \in \mathcal{B}\}.$

Theorem A8. If $\mathcal{B}$ and $\mathcal{C}$ are subalgebras of $\mathcal{A}$ such that $\mathcal{C} \subseteq \mathcal{B},$ then their centralizers are subalgebras such that $Z(\mathcal{B},\mathcal{A}) \subseteq Z(\mathcal{C},\mathcal{A}).$

One may also consider the set of commutative subalgebras of a given algebra $\mathcal{A}$ ordered by inclusion. The intersection of any family of commutative subalgebras is again a commutative subalgebra. However, for an arbitrary set $X \subset \mathcal{A}$ there may not exist a commutative subalgebra containing it; this occurs for example if $X=\{A\}$ consists of a single non-normal element.

Theorem A9. A set $X \subseteq \mathcal{A}$ is contained in a commutative subalgebra of $\mathcal{A}$ if and only if $\mathrm{Alg}(X)$ is commutative.

The unique minimal element of the poset of commutative subalgebras of $\mathcal{A}$ is still $\mathbb{C}I$ , but there may be many maximal commutative subalgebras $\mathcal{B} \subseteq \mathcal{A}$ having the property that they are not contained in any strictly larger commutative subalgebra.

Theorem A10. A commutative subalgebra $\mathcal{B} \subseteq \mathcal{A}$ is a maximal commutative subalgebra if and only if $Z(\mathcal{B},\mathcal{A})=\mathcal{B}.$

A natural question is whether we can define a scalar product on a given algebra $\mathcal{A}$ which is compatible with its multiplication and conjugation. Given any scalar product on $\mathcal{A}$ , we can normalize it so that $\langle I,I \rangle =1.$ A scalar product so normalized is said to have the left-Frobenius property if

$\langle AB,C\rangle = \langle B,A^*C\rangle \quad\text{for all }A,B,C \in \mathcal{A}.$

We say that it has the right-Frobenius property if

$\langle AB,C\rangle = \langle A,CB^*\rangle \quad\text{for all }A,B,C \in \mathcal{A}.$

A scalar product satisfying $\langle I,I\rangle=1$ which has both the left-Frobenius property and the right-Frobenius property is called a Frobenius scalar product.

The existence of Frobenius scalar products on $\mathcal{A}$ is intimately related to the existence of special linear functionals on $\mathcal{A}$ . The reason for this is that given any linear functional $\varphi \colon \mathcal{A} \to \mathcal{C}$ we can define a corresponding Hermitian form on $\mathcal{A}$ by

$\langle A,B \rangle_\varphi := \varphi(A^*B),$

and this form has the left-Frobenius property.

A faithful state is a linear functional $\sigma \colon \mathcal{A} to \mathbb{C}$ satisfying $\sigma(I)=1$ and $\sigma(A^*A) \geq 0$ with equality if and only if $A=0_\mathcal{A}.$

Theorem A.10. Faithful states on $\mathcal{A}$ are in bijection with left-Frobenius scalar products on $\mathcal{A}.$

A trace is a linear functional $\tau \colon \mathcal{A} \to \mathcal{C}$ which satisfies $\tau(AB)=\tau(BA).$

Theorem A.11. Faithful tracial states on $\mathcal{A}$ are in bijection with Frobenius scalar products on $\mathcal{A}.$

An algebra $\mathcal{A}$ equipped with a Frobenius scalar product is called a von Neumann algebra. Equivalently, a von Neumann algebra is an algebra $\mathcal{A}$ together with a faithful tracial state.

Math 202C: Lecture 14

Let us begin by reviewing some basic material from Math 202AB. Let $X$ be an orthonormal basis of a Hilbert space $V$ . The corresponding diagonal subalgebra $\mathcal{D}(X) \subset \mathrm{End}(V)$ is the set of all operators which act diagonally on $X.$ That is, $A \in \mathcal{D}(X)$ if and only if $Ax = \widehat{A}(x)x$ for each $x \in X,$ where $\widehat{A}(x) \in \mathbb{C}$ is a scalar. Equivalently,

$A = \sum\limits_{x\in X}\widehat{A}(x)P_x,$

where $P_x \in \mathcal{E}(V)$ is the orthogonal projection of $V$ onto the line spanned by $x.$ A physicist would write this projection operator as $P_x=|x\rangle \langle x|,$ and so that in Dirac notation the above decomposition becomes

$A = \sum\limits_{x \in X} \widehat{A}(x)|x\rangle\langle x|.$

We have that $\mathcal{D}(X)$ is isomorphic to $\mathcal{F}(X)$ via $A \mapsto \widehat{A}$ . This is a particularly transparent instance of the Fourier transform.

We know from Math 202B that $\mathcal{D}(X)$ is a maximal abelian subalgebra of $\mathrm{End}(V)$ , and moreover that every MASA in $\mathrm{End}(V)$ is $\mathcal{D}(X)$ for some orthonormal basis $X$ . You should know why this is true, and moreover you should be able to prove that it is true to someone who does not believe you. Subsequently, you can and should taunt them with your understanding of the algebra $\mathcal{D}(X) \cap \mathcal{D}(Y).$

A basic problem in linear algebra is: given $A \in \mathrm{End}(V),$ does there exist an orthonormal basis $X \subset V$ such that $A \in \mathcal{D}(X)$ ? According to the Spectral Theorem, the answer is “yes” if and only if $A$ is normal. People who live on the wrong side of the tracks refer to this as “unitary diagonalizability,” but you should not mock their intellectual poverty: even if you enjoy thinking in austere algebraic terms an occasional trip to the wrong side of the tracks can be rewarding.

With that polemic out of our system, let us return to our current object of study: the tower of symmetric groups

$S_1 \subset S_2 \subset S_3 \subset \dots.$

For each $n \in \mathbb{N},$ choose an arbitrary parameterization of the isomorphism classes of irreducible unitary representations of $S_n$ by the set $\mathrm{Par}_n$ of partitions of $n,$ and for each $\lambda \in \mathrm{Par}_n$ choose an arbitrary representative $V^\lambda$ of the corresponding isomorphism class. These choices being made, we define a graph $\mathfrak{B}$ called the branching graph of the tower of symmetric groups. The vertex set of $\mathfrak{B}$ is the set

$\mathrm{Par} = \bigsqcup\limits_{n=1}^\infty \mathrm{Par}_n$

of all partitions, so $\mathfrak{B}$ is an infinite graph. Moreover, this graph is graded: each $\mathrm{Par}_n$ is an independent set, and every edge of the graph joins a vertex of $\mathrm{Par}_n$ to a vertex of $\mathrm{Par}_{n+1}$ for some $n \in \mathbb{N}.$ The precise adjacency relation is the following: if $\mu \in \mathrm{Par}_n$ and $\lambda \in \mathrm{Par}_{n+1},$ then $\{\lambda,\mu\}$ is an edge of $\mathfrak{B}$ if and only if when $V^\lambda$ is restricted to a representation of $S_{n-1}$ it contains an irreducible subspace $V^\lambda[\mu]$ isomorphic as a representation of $S_{n-1}$ to $V^\mu.$

The work that we have done over the last two lectures tells us that the graph $\mathfrak{B}$ we have now constructed is simple: it has no multiple edges. Thus, by construction, for any positive integers $1 \leq k <n$ and any $\lambda \in \mathrm{Par}_n$ we have an orthogonal decomposition

$V^\lambda = \bigoplus\limits_{\gamma \in \mathrm{Geo}(\mathrm{Par}_k,\lambda)} V^\lambda[\gamma],$

where $\mathrm{Geo}(\mathrm{Par}_k,\lambda)$ is the set of geodesics in $\mathfrak{B}$ joining a point of $\mathrm{Par}_k$ to the specified point $\lambda \in \mathrm{Par}_n$ , and for each such geodesic $V^\lambda[\gamma]$ is a nonzero subspace of $V^\lambda$ in which $S_k$ acts irreducibly. Note that while all of these subspaces $V^\lambda[\gamma]$ are distinct (indeed, pairwise orthogonal), sum of them may be isomorphic to one another as representations of $S_k$ ; indeed, for any particular $\mu \in \mathrm{Par}_k$ the number of spaces in the above decomposition isomorphic to $V^\mu$ is $|\mathrm{Geo}(\mu,\lambda)|.$

The most extreme case of this is the case $k=1,$ where

$V^\lambda=\bigoplus\limits_{\gamma \in \mathrm{Geo}(1,\lambda)} V^\lambda[\gamma]$

is an orthogonal decomposition of $V^\lambda$ into one-dimensional subspaces known as the Gelfand-Tsetlin lines of $V^\lambda.$ If we choose a unit vector $x^\lambda_\gamma$ from each Gelfand-Tsetlin line $V^\lambda[\gamma],$ we obtain an orthonormal basis of $V^\lambda$ called a Gelfand-Tsetlin basis. Typically one ignores the phase ambiguity implicit in such a choice and simply calls any such choice $X_n^\lambda=\{x^\lambda_\gamma \colon \gamma \in \mathrm{Geo}(1,\lambda)\}$ “the” Gelfand-Tsetlin basis of $V^\lambda,$ which really means that the basis is uniquely defined up to the phase ambiguity. In any case, this gives our first handle on the dimensions of the irreducible representations of the symmetric groups: we now know that

$\dim V^\lambda = |\mathrm{Geo}(1,\lambda)|.$

Now, for each $n \in \mathbb{N}$ and every $\lambda \in \mathrm{Par}_n,$ let $\mathcal{G}_n^\lambda$ be the subalgebra of $\mathcal{C}(S_n)$ consisting of all elements $|A\rangle$ whose image $A^\lambda \in \mathrm{End}(V^\lambda)$ belongs to the diagonal subalgebra $\mathcal{D}(X_n^\lambda)$ of the GT-basis $X_n^\lambda \subset V^\lambda.$ In other words, the image

$A = \bigoplus\limits_{\lambda \in \mathrm{Par}_n} A^\lambda$

of $|A\rangle \in \mathcal{G}_n^\lambda$ under the Wedderburn isomorphism

$\mathcal{C}(S_n) \simeq \bigoplus\limits_{\lambda \in \mathrm{Par}_n} \mathrm{End}(V^\lambda),$

has the feature that, if we look at it as a block matrix relative to the $GT$ -basis in every irreducible representations, the $\lambda$ -block of $A$ is a diagonal matrix. Thus, if we define the Gelfand-Tsetlin subalgebra of $\mathcal{C}(S_n)$ to be

$\mathcal{G}_n = \bigsqcup\limits_{\lambda \in \mathrm{Par}_n} \mathcal{G}_n^\lambda,$

then we have obtained a maximal commutative subalgebra of $\mathcal{C}(S_n)$ consisting of those elements $|A\rangle$ which act diagonally on the GT-basis $X_n^\lambda$ of every irreducible representation $V^\lambda$ of $S_n.$

In fact, in “Phase I” of our current project (representation theory of the symmetric groups), we met the Gelfand-Tsetlin algebra in a different guise. Recall that the Jucys-Murphy subalgebra $\mathcal{J}_n$ of $\mathcal{C}(S_n)$ was defined to be the algebra generated by

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

where $\mathcal{Z}_k$ is the center of $\mathcal{C}(S_k).$ We had to put in some significant work to show that $\mathcal{J}_n = \mathbb{C}[|J_1\rangle,\dots,|J_n\rangle]$ , which is shorthand for saying that the Jucys-Murphy specialization of the polynomial algebra $\mathcal{P}_n=\mathbb{C}[x_1,\dots,x_n]$ is a surjection onto $\mathcal{J}_n.$ This effort front loading is now starting to pay off.

Theorem 14.1. We have $\mathcal{G}_n = \mathcal{J}_n.$

Proof: First we prove that $\mathcal{J}_n \subseteq \mathcal{G}_n.$ For this we use the fact, since we have already shown $\mathcal{J}_n=\mathbb{C}[|J_1\rangle,\dots,|J_n\rangle],$ it is sufficient to show that each JM-element $|J_k\rangle$ belongs to the $GT$ -algebra $\mathcal{J}_n.$ Since $|J_k\rangle=|T_k\rangle-|T_{k-1}\rangle,$ this reduces to showing that the sum $|T_k\rangle$ of all transpositions in $S_k$ belongs to $\mathcal{G}_n.$ To demonstrate this, fix $\lambda \vdash n$ and let

$V^\lambda = \bigoplus\limits_{\gamma \in \mathrm{Geo}(\mathrm{Par}_k,\lambda)} V^\lambda[\gamma]$

be its orthogonal decomposition into irreducible $S_k$ -invariant subspaces, as constructed above. On one hand, each vector in the GT-basis $X^\lambda \subset V^\lambda$ belongs to one of the spaces $V^\lambda[\gamma],$ and on the other $|T_k\rangle \in \mathcal{Z}_k$ acts as a scalar operator in each of these spaces by Schur’s Lemma.

Now we prove $\mathcal{J}_n=\mathcal{G}_n$ using finite-dimensional Stone-Weierstrass and the fact that $\mathcal{G}_n$ is isomorphic to the function algebra $\mathcal{F}(\mathrm{Geo}_n)$ , where $\mathrm{Geo}_n$ is the set of all geodesics from $\mathrm{Par}_1$ to $\mathrm{Par}_n$ in the branching graph $\mathfrak{B}$ (make sure you understand why). Under this isomorphism, $\mathcal{J}_n$ becomes a subalgebra $\widehat{\mathcal{J}}_n$ of $\mathcal{F}(\mathrm{Geo}_n),$ and in order to invoke Stone-Weirstrass to prove that $\widehat{\mathcal{J}}_n=\mathcal{F}(\mathrm{Geo}_n)$ we just have to show that $\widehat{\mathcal{J}}_n$ separates points. If $\gamma,\gamma' \in \mathrm{Geo}_n$ are distinct geodesics $\mathrm{Par}_1 \to \mathrm{Par}_n$ in $\mathfrak{B},$ then there necessarily exists $2 \leq k \leq n$ such that $\gamma$ passes through $\mu \in \mathrm{Par}_k$ and $\gamma'$ passes through $\mu' \in \mathrm{Par}_k$ and $\mu \neq \mu'.$ In particular, $V^\mu$ and $V^{\mu'}$ are non-isomorphic irreducible representations of $S_k$ . Now, every element $|C_\nu\rangle \in \mathcal{Z}_k$ acts as a scalar operator in each of these irreducible representations: the eigenvalue of $|C_\nu\rangle$ acting in $V^\mu$ is the central character

$\omega^\mu_\nu=\frac{|C_\nu|}{\dim V^\mu}\chi^{\mu}_\nu$

and the eigenvalue of $|C_\nu\rangle$ acting in $V^{\mu'}$ is the central character

$\omega^{\mu'}_\nu=\frac{|C_\nu|}{\dim V^{\mu'}}\chi^{\mu'}_\nu.$

If it were the case that $\omega^\mu_\nu=\omega^{\mu'}_\nu$ for all $\nu \in \mathrm{Par}_k,$ this would force

$\chi^\mu_\nu = \frac{\dim V^\mu}{\dim V^{\mu'}}\chi^{\mu'}_\nu$

for all $\nu \in \mathrm{Par}_k,$ which would contradict the linear independence of characters of non-isomorphic irreducible representations. $\square$

Math 202C: Lecture 13

*** Problems due May 3 at 23:59 ***

Let $H \leq G$ be finite groups. In Lecture 12, we proved that restriction of irreducible representations of $G$ to $H$ is multiplicity-free if and only if the centralizer $Z(\mathcal{C}(H),\mathcal{C}(G))$ is a commutative subalgebra of $\mathcal{C}(G).$ Our objective now is to use this criterion to establish that restriction of irreducible representations of $S_n$ to $S_{n-1}$ is multiplicity free.

For the moment we stay in the general context where the group $G$ and its subgroup $H$ are arbitrary; eventually we will set $G=S_n$ and $H=S_{n-1}.$ By definition, the centralizer $Z(\mathcal{C}(H),\mathcal{C}(G))$ is the set of all $|A\rangle \in \mathcal{C}(G)$ which commute with every $|B\rangle \in \mathcal{C}(H),$ and it is clear that this condition is equivalent to

$|A\rangle|h\rangle = |h\rangle|A\rangle, \quad h \in H,$

which is in turn equivalent to

$|A\rangle = |h\rangle|A\rangle|h\rangle^*, \quad h \in H,$

with $|h\rangle^*=|h^{-1}\rangle.$ To understand those elements $|A\rangle \in \mathcal{C}(H)$ which have the above property, consider an equivalence relation on $G$ defined by

$g_1 \sim g_2 \iff g_2=hg_1h^{-1} \text{ for some} h \in H.$

That is, equivalence classes under this relation are orbits of $H$ acting on $G$ by conjugation. Let $\Lambda$ be a set parameterizing the distinct $H$ -conjugacy classes in $G$ ,

$\{H-\text{conjugacy classes in }G\} = \{C_\alpha \colon \alpha \in \Lambda\}.$

In the case where $H=G,$ this is just the set of conjugacy classes in $G$ as per usual, making the following a generalization of something we already know.

Problem 13.1. Prove that the set $\{|C_\alpha\rangle \colon \alpha \in \Gamma\}$ is an orthogonal basis of $Z(\mathcal{C}(H),\mathcal{C}(G)).$

In the case $H=G,$ the centralizer $Z(\mathcal{C}(H),\mathcal{C}(G))$ is the center $Z(\mathcal{C}(G)),$ which is commutative by definition, and the above problem recovers the 202B fact that the center of the convolution algebra of a group has a basis consisting of indicator functions of conjugacy classes. At the other extreme, if $H=\{\iota\}$ is the subgroup consisting solely of the identity element, then $Z(\mathcal{C}(H),\mathcal{C}(G))=\mathcal{C}(G),$ which is commutative precisely when $G$ is abelian. In between these two extremes, it may be more difficult to determine whether or not $Z(\mathcal{C}(H),\mathcal{C}(G))$ is commutative, but there is a particular circumstance which will force this to be the case.

Problem 13.2. Prove that if the class basis $\{|C_\alpha\rangle \colon \alpha \in \Lambda\}$ consists of selfadjoint elements, then $Z(\mathcal{C}(H),\mathcal{C}(G))$ is a commutative algebra.

We now specialize to the case $G=S_n$ and $H=S_{n-1}.$ We would like to find a concrete indexing of the $S_{n-1}$ -conjugacy classes in $S_n$ . For permutations, the operation of conjugation has a simple combinatorial meaning: conjugating $g$ by $h$ relabels the elements in the cycles of $g$ according to $h$ . If $h$ is confined to $S_{n-1},$ then it cannot relabel $n$ , hence in order for two permutations $g_1$ and $g_2$ in $S_n$ to be $S_{n-1}$ -conjugates it is necessary that the cycle containing $n$ in each have the same length.

Problem 13.3. Prove that the above condition is also sufficient for $g_1$ and $g_2$ to be $S_{n-1}$ -conjugates.

We can now conclude that $S_{n-1}$ -conjugacy classes in $S_n$ are indexed by pairs $(r,\alpha)$ consisting of an integer $1 \leq r \leq n$ corresponding to the length of the cycle containing $n$ and a partition $\alpha \vdash n-r$ consisting to the cycle-type of the remainder of the permutation. In particular, we get the dimension formula

$\dim Z(\mathcal{C}(S_{n-1},\mathcal{C}(S_n))=\sum\limits_{r=1}^n p(n-r),$

where $p(k)$ is the number of partitions of $k$ . Furthermore, it is easy to see that if an $S_{n-1}$ -conjugacy class $C_{(r,\alpha)}$ contains a permutation $\pi$ , then it also contains $\pi^{-1}$ , since the inverse of a permutation not only has the same cycle type, but actually the same elements within each cycle. Thus, the centralizer $Z(\mathcal{C}(S_{n-1}),\mathcal{C}(S_n))$ is commutative by Problem 13.2.

The significance of this commutativity is that, by Lecture 12, it is equivalent to multiplicity-free branching for irreducible representations of the symmetric groups: the isotypic decomposition of any irreducible representation $V^\lambda$ of $S_n$ when viewed as a representation of $S_{n-1}$ has the form

$V^\lambda = \bigoplus_{\mu \vdash n-1} \mathrm{Mult}(V^\mu,V^\lambda)V^\mu, \quad \mathrm{Mult}(V^\mu,V^\lambda) \in \{0,1\}.$

In Lecture 14, we will use this fact to construct a special orthonormal basis in $V^\lambda$ which we will then exploit mercilessly.

Math 202C: Lecture 12

*** Problems in this lecture due 05/03/2026 at 23:59 ***

Let $\mathcal{A}$ be an algebra. In Week I of Math 202B, we saw that subalgebras of $\mathcal{A}$ always come in pairs: associated to each subalgebra $\mathcal{B} \leq \mathcal{A}$ is its centralizer $Z(\mathcal{B},\mathcal{A}),$ the set of elements in $A$ which commute with every element in $\mathcal{B}.$ We used this fact to characterize maximal abelian subalgebras of $\mathcal{A}$ as precisely those commutative subalgebras $\mathcal{B} \leq \mathcal{A}$ which are equal to their own centralizer, $\mathcal{B}=Z(\mathcal{B},\mathcal{A}).$

A problem we might have already posed back then is to characterize those subalgebras $\mathcal{B} \leq \mathcal{A}$ for which $Z(\mathcal{B},\mathcal{A})$ is commutative. Today, we will address this question in the case where $\mathcal{A}=\mathcal{C}(G)$ is the convolution algebra of a finite group $G$ and $\mathcal{B}=\mathcal{C}(H)$ is the convolution algebra of a subgroup $H \leq G,$ viewed as the subalgebra of $\mathcal{C}(G)$ spanned by the orthogonal set $\{|h\rangle \colon h \in H\}.$

For any element $|A\rangle \in \mathcal{C}(G)$ , let $A \in \mathrm{End}\mathcal{C}(G)$ denote its image in the regular representation of $\mathcal{C}(G).$ Furthermore, let $\Lambda(G)$ be a set indexing isomorphism classes of irreducible unitary representations of $G$ , and for each $\lambda \in \Lambda(G)$ let $A^\lambda \in \mathrm{End}(V^\lambda)$ denote the image of $|A\rangle \in \mathcal{C}(G)$ in a representative $V^\lambda$ of the isomorphism class indexed by $\lambda \in \Lambda(G).$

Problem 12.1. Prove that $|A\rangle \in Z(\mathcal{C}(H),\mathcal{C}(G))$ if and only if $A^\lambda B^\lambda = B^\lambda A^\lambda$ for each $|B\rangle \in \mathcal{C}(H)$ and every $\lambda \in \Lambda(G).$

Let $\lambda \in \Lambda(G)$ be arbitrary but fixed. Thanks to Problem 12.1, understanding when $Z(\mathcal{C}(H),\mathcal{C}(G))$ is commutative reduces to understanding when the algebra $\mathrm{End}_H(V^\lambda)$ is commutative. If it were the case that $V^\lambda$ was an irreducible representation of $\mathcal{C}(H)$ this would be extremely easy, since then Schur’s Lemma would force $\mathrm{End}_H(V^\lambda)$ to be one-dimensional. However, $V^\lambda$ is an irreducible representation of $\mathcal{C}(G),$ and there is no reason why it should be irreducible as a representation of the subalgebra $\mathcal{C}(H).$ So, we will have to understand what conditions would cause $\mathrm{End}_H(V^\lambda)$ to be commutative by analyzing the behavior of $V^\lambda$ under restriction from $G$ to $H.$

Let $\Lambda(H)$ be a set parameterizing isomorphism classes of irreducible unitary representations of $H$ (or equivalently irreducible linear representations of $\mathcal{C}(H)$ ). Consider the isotypic decomposition of $V^\lambda$ as a representation of $H$ , which has the form

$V^\lambda =\bigoplus\limits_{\mu \in \Lambda(H)} V^\lambda[\mu],$

where two summands $V^\lambda[\mu]$ and $V^\lambda[\nu]$ are isomorphic unitary representations of $H$ if and only if $\mu = \nu.$ In finer detail, each $V^\lambda[\mu]$ further decomposes as

$V^\lambda[\mu]=W^\mu_1 \oplus \dots \oplus W^\mu_{m_{\lambda\mu}},$

where $W^\mu_i$ and $W^\mu_j$ are isomorphic irreducible unitary representations of $H$ and $m_{\lambda\mu}=\mathrm{Mult}(W^\mu,V^\lambda)$ is a positive integer.

Problem 12.2. Prove that if $T \in \mathrm{End}_H(V^\lambda)$ , then $T$ maps each $H$ -isotypic component $V^\lambda[\mu]$ of $V^\lambda$ into itself.

Problem 12.2 allows us to focus on intertwiners $T \in \mathrm{End}_H(V^\lambda[\mu])$ for a fixed $\mu \in \Lambda(H)$ . Each such operator may be visualized as a block matrix

$T = \begin{bmatrix} {} & \vdots & {} \\ \dots & T_{ji}^\lambda & \dots \\ {} & \vdots & {} \end{bmatrix}_{i,j=1}^{m_{\lambda\mu}},$

where $T_{ij}^\lambda \in \mathrm{End}_H(W^\mu_j,W^\mu_i).$ Now, since $W^\mu_j$ and $W^\mu_i$ are irreducible unitary representations of $H,$ Schur’s Lemma tells us that $\mathrm{End}_H(W^\mu_j,W^\mu_i)$ is one-dimensional, so in fact each block $T_{ij}^\lambda$ can be identified with a scalar $t_{ji}^\lambda$ and $T$ itself can be identified with an $m_{\lambda\mu} \times m_{\lambda\mu}$ matrix of complex numbers. We thus have an algebra isomorphism

$\mathrm{End}_H(V^\lambda) \simeq \bigoplus\limits_{\mu \in \Lambda(H)} \mathrm{End}(\mathbb{C}^{m_{\lambda\mu}}),$

which is important as a standalone fact, but also tells us that $\mathrm{End}_H(V^\lambda)$ is commutative if and only if $m_{\lambda\mu}=1$ for each $\mu \in \Lambda(H).$ We have thus established the following theorem.

Theorem 12.1. The centralizer $Z(\mathcal{C}(H),\mathcal{C}(G))$ is a commutative subalgebra of $\mathcal{C}(G)$ if and only if the restriction of each irreducible unitary representation of $G$ to a unitary representation of $H$ is multiplicity free: for every $\lambda \in \Lambda(G)$ we have

$V^\lambda = \bigoplus\limits_{\mu \in \Lambda(H)} m_{\lambda\mu}W^\mu, \quad m_{\lambda\mu} \in \{0,1\}.$

Math 202C: Lecture 11

*** Problems in this lecture due 05/03/2026 at 23:59 ***

In Lecture 10, we proved that the Jucys-Murphy specialization $\Xi_n \colon \mathcal{S}_n \to \mathcal{Z}_n$ is a surjection of the algebra $\mathcal{S}_n=\mathbb{C}[x_1,\dots,x_n]^{S_n}$ of symmetric polynomials onto the center $\mathcal{Z}_n=\mathcal{C}(S_n)$ of the convolution algebra of the symmetric group $S_n.$ That is, for every central element $|A\rangle \in \mathcal{C}(S_n)$ there exists a symmetric polynomial $f \in \mathcal{S}_n$ such that $|A\rangle = f(\Xi_n),$ where

$f(\Xi_n) = f(|J_1\rangle,\dots,|J_n\rangle)$

is the evaluation of $f$ on the Jucys-Murphy elements

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

Equivalently, combining the fundamental theorem of symmetric polynomials with the fact that

$e_r(\Xi_n) = |L_r\rangle, \quad 0 \leq r \leq n-1,$

where

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

is the sum of all elements on level $r$ of the Cayley graph $G_n=(S_n,T_n)$ of $S_n$ as generated by the class $T_n = C_1(n)$ of transpositions, we can say that there exists a (not necessarily symmetric) polynomial $g \in \mathcal{P}_n=\mathbb{C}[x_1,\dots,x_n]$ such that

$|A\rangle = g(|L_0\rangle,|L_1\rangle,\dots,|L_{n-1}\rangle).$

So the two takeaways are:

Every central element is a symmetric polynomial in the Jucys-Murphy elements $|J_t\rangle$ ;
Every central element is a polynomial in the level elements $|L_r\rangle.$

Symbolically, we have

$\mathcal{Z}_n=\mathbb{C}[|J_1\rangle,\dots,|J_n\rangle]^{S_n}=\mathbb{C}[|L_0\rangle,\dots,|L_{n-1}\rangle],$

which means that we have two surjective specializations

$\mathcal{S}_n \to \mathcal{Z}_n \quad\text{and}\quad \mathcal{P}_n \to \mathcal{Z}_n$ ,

the first obtained by substituting $|J_1\rangle,\dots,|J_n\rangle$ for the variables of symmetric polynomials in $n$ variables, and the second obtained by substituting $|L_0\rangle,\dots,|L_{n-1}\rangle$ for the variables of arbitrary polynomials in $n$ variables.

This begs the question: what happens when we substitute $|J_1\rangle,\dots,|J_n\rangle$ for the variables of arbitrary polynomials in $n$ variables? More precisely, recall that $\mathcal{J}_n$ is the commutative subalgebra of $\mathcal{C}(S_n)$ generated by

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

where $\mathcal{Z}_k$ is the center of the subalgebra $\mathcal{C}(S_k)$ of $\mathcal{C}(S_n)$ spanned by permutations which fix the points $k+1,\dots,n.$ Our original proof of the fact that the JM-elements commute was simply to point out that they lie in the commutative algebra $\mathcal{J}_n.$ We may thus regard the JM-specialization as an algebra homomorphism

$\Xi_n \colon \mathcal{P}_n \longrightarrow \mathcal{J}_n$

defined by

$f(x_1,\dots,x_n) \mapsto f(\Xi_n)=f(|J_1\rangle,\dots,|J_n\rangle).$

Since we know that $\Xi_n$ surjects $\mathcal{S}_n$ onto $\mathcal{Z}_n,$ the natural guess is that it surjects $\mathcal{P}_n$ onto $\mathcal{J}_n$ .

Theorem 11.1. The JM-specialization is a surjection of $\mathcal{P}_\mathbb{C}[x_1,\dots,x_n]$ onto $\mathcal{J}_n = \mathrm{Alg}(\mathcal{Z}_1 \cup \dots \cup \mathcal{Z}_n).$

In fact, this is a direct consequence of what we have already established, which gives that

$\Xi_k \colon \mathcal{S}_k \to \mathcal{Z}_k$

is surjective for each $k$ .

Problem 11.1. Write out a careful proof of Theorem 11.1.

Note to those who are perusing one of the recommended texts, namely this one: the material we have established so far takes us up to and through the proof of Theorem 4.4.5, as well as the result there called Olshanskis’s theorem, although our arguments have been quite different.

Math 202C: Lecture 10

Let $G=(S,T)$ be a finite connected simple graph with vertex set $S=\{\pi,\rho,\sigma,\dots\}$ and edge set $T$ . We pass to the Hilbert space $\mathcal{F}(S)$ with orthonormal basis $|\pi\rangle,|\rho\rangle,|\sigma\rangle,\dots$ and consider the selfadjoint operators

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

which encode the entire metric structure of $G$ . We have that $L_r$ is the zero operator for all $r$ which exceed the diameter of $G,$ while the nonzero operators $\{L_0,L_1,\dots,L_{\mathrm{diam}(G)}\}$ form an orthogonal set in $\mathrm{End}\mathcal{C}(S)$ with respect to the Hilbert-Schmidt scalar product. However, not much is known about the subalgebra $\mathcal{L}(G)$ of $\mathrm{End}\mathcal{F}(S)$ generated by the selfadjoint operators $L_r.$

If $G=(S,T)$ is the Cayley graph of a finite group $S$ corresponding to a symmetric set of generators $T \subseteq S,$ we are in a more favorable situation because the operator $L_r$ is the image of an element of the convolution algebra $\mathcal{C}(S),$ namely

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

in the regular representation. Because the regular representation is faithful, we can view $\mathcal{L}(G)$ as the subalgebra of $\mathcal{C}(S)$ generated by the selfadjoint elements $|L_r\rangle,$ and leverage the group structure of $S$ to help us understand the situation. For example, if $S$ is an abelian group we automatically get that $\mathcal{L}(G)$ is a commutative algebra.

Problem 10.1. Let $G_n=(S_n,T_n)$ be the Cayley graph corresponding to the cyclic group $S_n=\{g^0,g^1,\dots,g^{n-1}\}$ of order $n$ with generating set $T_n=\{g,g^{-1}\}.$ This graph is easy to picture: it is a cycle on $n$ vertices. Show that

$\mathcal{L}(G_n) = \left\{\sum\limits_{k=0}^{n-1} a_k|g^k\rangle \colon a_k=a_{-k}\right\},$

and compute the dimension of this commutative algebra.

Now let us consider the Cayley graph $G_n=(S_n,T_n)$ of the symmetric group $S_n=\mathrm{Aut}\{1,\dots,n\}$ as generated by the conjugacy class of transpositions, $T_n=\{(st) \colon 1 \leq s<t \leq n\}.$ This is a nonabelian group, and yet the operators $L_0,L_1,L_2,\dots$ commute. This is a consequence of the fact that the elements

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

where $C_\mu \subseteq S_n$ denotes the conjugacy class of permutations of cycle type $\mu$ , belong to the center $\mathcal{Z}_n$ of $\mathcal{C}(S_n)$ . Thus, the sphere sums $|L_r\rangle$ generate a subalgebra $\mathcal{L}_n$ of $\mathcal{Z}_n$ . In fact, we have the following classical result of Farahat-Higman.

Theorem 10.1. $\mathcal{L}_n=\mathcal{Z}_n.$

In this lecture we will prove Theorem 10.1, or at least explain why it is true. Our starting point is the first main result of Math 202C, namely that

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

where $|J_1\rangle,\dots,|J_n\rangle \in \mathcal{C}(S_n)$ are the Jucys-Murphy elements and $e_r(x_1,\dots,x_n)$ is the elementary symmetric polynomial of degree $r$ . This together with the second main result in Math 202C so far, the fundamental theorem of symmetric polynomials, gives us a specialization

$\Xi_n \colon \mathcal{S}_n \longrightarrow \mathcal{Z}_n$

of the algebra $\mathcal{S}_n=\mathbb{C}[x_1,\dots,x_n]^{S_n}$ of symmetric polynomials defined by

$\Xi_n(f(x_1,\dots,x_n))=f(|J_1\rangle,\dots,|J_n\rangle).$

The image of $\mathcal{S}_n$ under $\Xi_n$ is exactly $\mathcal{L}_n,$ so that Theorem 10.1 is equivalent to the following.

Theorem 10.2. $\Xi_n$ is surjective.

Problem 10.1. Carefully explain the equivalence between Theorems 10.1 and 10.2.

In order to prove Theorem 10.2, we would ideally like to explicitly construct a family $f_\mu(x_1,\dots,x_n)$ of symmetric polynomials indexed by partitions $\mu \vdash n$ such that

$f_\mu(|J_1\rangle,\dots,|J_n\rangle)=C_\mu.$

In fact, we know how to do this in three cases: the polynomials

$f_{(1,1,\dots, 1)}:=e_0,\ f_{(2,1,\dots,1)}:=e_1, \quad f_{(n)}:=e_{n-1}$

map to the conjugacy classes

$|C_{(1,1,\dots,1)}\rangle,\ |C_{(2,1,\dots,1)}\rangle,\ |C_{(n)}\rangle$

under $\Xi_n.$

Next, we would like to construct symmetric polynomials $f_{(3,1,\dots,1)}$ and $f_{(2,2,1,\dots,1)}$ such that

$f_{(3,1,\dots,1)}(|J_1\rangle,\dots,|J_n\rangle)=|C_{(3,1,\dots,1)}\rangle$

and

$f_{(2,2,1,\dots,1)}(|J_1\rangle,\dots,|J_n\rangle) = |C_{(2,2,1,\dots,1)}\rangle.$

However, at present we only know that

$e_2(|J_1\rangle,\dots,|J_n\rangle)=|L_2\rangle=|C_{(3,1,\dots,1)}\rangle+|C_{(2,2,1,\dots,1)}\rangle.$

Before going any further, let us note that the standard labeling $C_\mu$ of conjugacy classes in $S_n$ is not ideal for our purposes. Instead, it is much better to define the reduced cycle-type of a permutation $\pi \in C_\mu$ to be the partition $\nu$ obtained by subtracting $1$ from each part of $\mu.$ Then, the decomposition of the levels $L_r$ of the Cayley graph becomes

$|L_r\rangle = \sum\limits_{\nu \vdash r} C_\nu(n),$

where $C_\nu(n)$ is the conjugacy class of permutations in $S_n$ of reduced cycle type $\nu.$ In this language, the data we have so far is

$e_0(\Xi_n) = C_0(n),\ e_1(\Xi_n) = C_1(\Xi_n),\ e_{n-1}=C_{n-1}(n).$

It is definitely not the case that $e_r(\Xi_n)=C_r(n)$ — what is actually true is that

$e_r(\Xi_n) = |L_r(n)\rangle, \quad 0 \leq r \leq n,$

and the three data points above are precisely those in which a single level actually is a conjugacy class.

Now let us come back to the first unknown case of our problem: we know that

$e_2(\Xi_n)=|C_2(n)\rangle + |C_{11}(n)\rangle,$

but we do not yet know that each of the summands in this expression can be expressed as a symmetric polynomial in the JM-elements. The space $\mathcal{S}_n^2$ of homogeneous degree $2$ symmetric polynomial in $n$ variables is two-dimensional, with monomial basis

$m_2(x_1,\dots,x_n) = p_2(x_1,\dots,x_n) = \sum\limits_{1 \leq I \leq n} x_i^2,\\ m_{11}(x_1,\dots,x_n)=e_2(x_1,\dots,x_n)=\sum\limits_{1 \leq i <j \leq n}x_ix_j.$

We already know what $m_{11}(\Xi_n)=e_2(\Xi_n)$ is, so it remains to calculate

$m_2(\Xi_n)=p_2(\Xi_n)=\sum\limits_{1 \leq t \leq n} |J_t\rangle^2.$

Now,

$|J_t\rangle^2 = \sum\limits_{s_1,s_2<t} |s_1t\rangle |s_2t\rangle=\sum\limits_{s<t} |st\rangle|st\rangle+\sum\limits_{s_1\neq s_2<t}|s_1t\rangle|s_2t\rangle.$

The first sum is just $t-1$ copies of $|st\rangle|st\rangle=|\iota\rangle,$ giving a net contribution of

$\sum\limits_{1 \leq t \leq n}(t-1)|\iota\rangle={n \choose 2}C_0(n).$

$\sum\limits_{1 \leq t \leq n}\sum\limits_{s_1\neq s_2<t}|s_1t\rangle|s_2t\rangle=|C_2(n)\rangle.$

We thus have a system of two linear equations,

$m_{11}(\Xi_n) = |C_{11}(n)\rangle+|C_2(n)\rangle \\ m_2(\Xi_n) = |C_2(n)\rangle+{n \choose 2}|C_0(n)\rangle.$

The second equation gives us

$|C_2(n)\rangle=m_2(\Xi_n)-{n \choose 2}m_0(\Xi_n),$

which is a symmetric polynomial in the JM-elements, and substituting this into the first equation and solving we get

$|C_{11}(n)\rangle=m_{11}(\Xi_n)-m_2(\Xi_n)+{n \choose 2}m_0(\Xi_n)$ ,

so that we have successfully expressed each of the conjugacy classes $C_\nu(n)$ of $S_n$ of reduced cycle type $\nu\vdash 2$ as a symmetric polynomial in the JM-elements.

For level $L_3$ in $S_n,$ the class expansion of the monomial symmetric polynomials $m_\lambda(\Xi_n)$ of degree three is

$m_3(\Xi_n) = C_3(n) + (2n-3)C_1(n) \\ m_{21}(\Xi_n) = C_{21}(n)+3C_3(n)+\left({n \choose 2}-1\right)C_1(n) \\ m_{111}(\Xi_n) = C_{111}(n)+C_{21}(n)+C_3(n),$

which modulo levels $L_0,L_1,L_2$ becomes

$\tilde{m}_3(\Xi_n) =C_3(n) \\ \tilde{m}_{21}(\Xi_n) =C_{21}(n)+3C_3(n) \\ \tilde{m}_{111}(\Xi_n) =C_{111}(n)+C_{21}(n)+C_3(n).$

If we order the partitions of $3$ as $3 < 21 < 111,$ this is the triangular system

$\begin{bmatrix} \tilde{m}_3(\Xi_n) \\ \tilde{m}_{21}(\Xi_n) \\ \tilde{m}_{111}(\Xi_n) \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} C_3(n) \\ C_{21}(n) \\ C_{111}(n) \end{bmatrix}.$

These computations can, to some extent, be performed in full generality. The result which comes out of the attempt to do so is the following fairly explicit description of the images of all monomial symmetric polynomials under the JM-specialization $\Xi_n$ .

Theorem 10.2. For each level $0 \leq r \leq n-1$ of the Cayley graph $G_n=(S_n,T_n)$ , not only do we have $e_r(\Xi_n) = |L_r\rangle,$ but in fact for every partition $\lambda \vdash r$ there holds a class expansion

$m_\lambda(\Xi_n) = \sum\limits_{|nu|\leq |\lambda|}L^\lambda_\nu(n)C_\nu(n)$ ,

in which the coefficients $L^\lambda_\nu(n)$ are polynomials in $n$ . In fact, $L^\lambda_\nu(n)$ is independent of $n$ for $|\lambda|=|\nu|=r,$ and modulo lower levels $L_0,L_1,\dots,L_{r-1}$ , we have

$\tilde{m}_\lambda(\Xi_n) = C_\lambda(n) + \sum\limits_{\substack{\nu \vdash r \\ \nu < \lambda}}L^\lambda_\nu(n),$

where $\nu < \lambda$ means that $\nu,\lambda$ are partitions of $r$ with $\nu$ coarser than $\lambda.$

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 8

As in Lecture 7, let $\mathrm{Par}_n$ denote the set of nonnegative integer vectors $\mu=(\mu,\dots,\mu_n)$ with weakly decreasing coordinates. Then, each $\mu \in \mathrm{Par}_n$ can be viewed as a partition of the number

$|\mu|=\mu_1+\dots+\mu_n$

having at most $n$ parts. Set

$\mathrm{Par}_n^d = \{\mu \in \mathrm{Par}_n^d \colon |\mu|=d\}.$

We know that the monomial symmetric polynomials

$\{m_\mu(x_1,\dots,x_n) \colon \mu \in \mathrm{Par}_n^d\}$

form a basis of the degree $d$ component $\mathcal{S}_n^d$ of the algebra $\mathcal{S}_n=\mathbb{C}[x_1,\dots,x_n]^{S_n}$ of symmetric polynomial in $n$ commuting selfadjoint variables $x_1,\dots,x_n.$

The fundamental theorem of symmetric polynomials gives a second basis of $\mathcal{S}_n^d$ constructed from the elementary symmetric polynomials

$e_r(x_1,\dots,x_n) = \sum\limits_{\substack{I \subseteq [n] \\ |I|=r}} \prod\limits_{i \in I} x_i.$

Let $\mathrm{Par}^d$ denote the set of all partitions of $d$ , and observe that we may think of this as the set of all nonnegative integer vectors $\lambda=(\lambda_1,\dots,\lambda_d)$ with weakly decreasing coordinates whose total sum $|\lambda|$ equals $d.$ We extend the definition of the elementary symmetric polynomial multiplicatively by defining

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

where by convention $e_0(x_1,\dots,x_n)=1$ . Then, in order for $e_\lambda(x_1,\dots,x_n)$ not to be the zero polynomial it is necessary and sufficient that $\lambda_1 \leq n,$ which is equivalent to the condition $\lambda^\prime \in \mathrm{Par}_n.$ The fundamental theorem of symmetric polynomials says that

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

is a basis of $\mathcal{S}_n^d.$ Equivalently, the claim is that

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

is a basis of $\mathcal{S}_n^d.$

In Lecture 7, we assembled the main ingredients needed to establish this. First, we showed that for any $\lambda \in \mathrm{Par}^d$ we have

$e_\lambda(x_1,\dots,x_n) = \sum\limits_{\mu \in \mathrm{Par}_n^d} M_{\lambda\mu}m_\mu(x_1,\dots,x_n),$

where $M_{\lambda\mu}$ is the number of $d \times n$ matrices with entries in $\{0,1\}$ whose row sums are encoded by $\lambda=(\lambda_1,\dots,\lambda_d)$ and whose column sums are encoded by $\mu=(\lambda_1,\dots,\lambda_n).$ Note that this is consistent with what we have seen: if $\lambda_1>n,$ then there cannot be a $\{0,1\}$ -matrix with $n$ columns whose first row sums to $\lambda_1,$ and all the coefficients $M_{\mu\lambda}$ are zero. Second (this is a homework problem), we have $M_{\lambda\mu}=0$ unless $\mu \leq \lambda^\prime$ in dominance order on $\mathrm{Par}_n^d,$ and moreover $M_{\lambda\lambda'}=1.$

Now let us complete the proof of the fundamental theorem. From the above, for any $\lambda$ such that $\lambda^\prime \in \mathrm{Par}_n^d$ we have

$e_\lambda = \sum\limits_{\mu \leq \lambda'}M_{\lambda\mu}m_\mu,$

where we are suppressing the variables $x_1,\dots,x_n$ to lighten the notation. Now let $\nu \in \mathrm{Par}_n^d$ be such that $\lambda^\prime = \nu.$ Since transpose of Young diagrams is an involution, this is equivalent to $\lambda=\nu'$ , and the above becomes

$e_{\nu^\prime}=\sum\limits_{\mu \leq \nu}M_{\nu^\prime \mu}m_\mu.$

Now in the above I am simply going to replace the letter $\nu$ with $\lambda$ because this helps me keep things straight in my mind (this has no mathematical content, it’s purely psychological). Making this letter replacement the above is

$e_{\lambda^\prime}=\sum\limits_{\mu \leq \lambda}M_{\lambda^\prime \mu}m_\mu.$

Now, the splitting of the term of the sum corresponding to $\mu=\lambda$ we have

$e_{\lambda^\prime}=m_\lambda+\sum\limits_{\mu < \lambda}M_{\lambda^\prime \mu}m_\mu$

where the sum on the right hand side is now over partitions $\mu$ which are strictly less than $\lambda$ in dominance order on $\mathrm{Par}_n^d.$

First we show that $\{e_{\lambda^\prime} \colon \lambda \in \mathrm{Par}_n^d\}$ spans $\mathcal{S}_n^d.$ Suppose otherwise. Then, there must be some monomial symmetric polynomial $m_\mu$ which cannot be represented as a linear combination of the elementary polynomials $e_{\lambda^\prime}.$ Let us choose such an $m_\mu$ with $\mu$ minimal in the dominance order on $\mathrm{Par}_n^d.$ Then, by our formula above,

$m_\mu = e_{\mu^\prime} - \sum\limits_{\nu < \mu} M_{\mu^\prime \nu}m_\nu,$

and the summation on the right does lie in the span of $\{e_{\lambda^\prime} \colon \lambda \in \mathrm{Par}_n^d\}$ , which gives a contradiction.

Now we show that $\{e_{\lambda^\prime} \colon \lambda \in \mathrm{Par}_n^d\}$ is linearly independent. Indeed, suppose

$\sum\limits_{\lambda \in \mathrm{Par}_n^d} c_\lambda e_{\lambda^\prime}=0$

where not all coefficients $c_\lambda$ equal zero. Choose a nonzero coefficient $c_\lambda$ with $\lambda$ maximal in dominance order. Then, in the monomial expansion of the left hand side, the coefficient of $m_\lambda$ is exactly $c_\lambda$ , which forces $c_\lambda=0,$ contradiction.

This completes the proof that $\{e_\lambda^\prime \colon \lambda \in \mathrm{Par}_n^d\}$ is a basis of the finite-dimensional Hilbert space $\mathcal{S}_n^d.$ Since the argument was formulated for arbitrary degree $d,$ we conclude that

$\{e_{\lambda'} \colon \lambda \in \mathrm{Par}_n\}$

is a basis of the infinite-dimensional algebra $\mathcal{S}_n$ . Finally, because $e_\lambda$ is defined multiplicatively, this is equivalent to

$\mathcal{S}_n = \mathbb{C}[e_1,\dots,e_n],$

showing that the algebra $\mathcal{S}_n$ of symmetric polynomials in variables $x_1,\dots,x_n$ is isomorphic to the algebra $\mathbb{C}[e_1,\dots,e_n]$ of all polynomials in variables

$e_1=x_1+x_2+\dots+x_n,\ \dots,\ e_n=x_1x_2 \dots x_n.$

Category Archives: 202C