Math 202C: Lecture 4

*** Problems in this lecture due April 12 at 23:59 ***

Let $S_n=\mathrm{Aut}\{1,\dots,n\}$ be the symmetric group on $\{1,\dots,n\}.$ Our convention is that permutations are multiplied left-to-right, $\rho\sigma := \sigma \circ \rho.$ We identify $lates S_n$ with its Cayley graph $\mathrm{Cay}(S_n,T_n)$ as generated by the conjugacy class of transpositions,

$T_n=\{\tau=(s t) \colon 1 \leq s <t \leq n\}.$

Thus, two permutations $\rho,\sigma \in S_n$ are adjacent if and only if $\sigma=\rho\tau$ for $\tau \in T_n.$ Under this identification, $S_n$ decomposes into a disjoint union of $n$ independent sets, the levels

$L_r=\{\pi \in S_n \colon |\pi|=r\} = \{\pi \in S_n \colon n-\mathsf{cyc}(\pi)=r\}, \quad 0 \leq r \leq n-1.$

The cardinalities of these levels make up the $n$ th row in the number triangle whose entries are the Stirling numbers of the first kind. Each level further decomposes as a disjoint union of conjugacy classes: we have

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

where $\Lambda$ is the set of partitions of $n$ , and $\ell(\alpha)$ is the number of terms in the partition $\alpha$ . We can encode this decomposition algebraically in $\mathcal{C}(S_n)$ as

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

Note that, because $S_n$ is an ambivalent group, each class indicator $|C_\alpha\rangle$ is a selfadjoint element in the convolution algebra $\mathcal{C}(S_n)$ . In the regular representation, the above becomes an identity in $\mathrm{End}\mathcal{C}(S_n)$ , namely

$L_r = \sum\limits_{\substack{\alpha \in \Lambda \\ \ell(\alpha)=n-r}} C_\alpha,$

and we have used this already to give a simple proof of the fact that the metric level set operators $L_1,\dots,L_{n-1}$ on $S_n=\mathrm{Cay}(S_n,T_n)$ commute. In particular, these selfadjoint operators are simultaneously diagonalizable. In this Lecture, we will obtain a different combinatorial decomposition of $L_r$ which opens the door to actually diagonalizing $L_1,\dots,L_{n-1}.$

In Lecture 1, we defined an edge-labeling of $S_n$ by marking each edge corresponding to the transposition $(s\ t)$ with $t$ , the larger of the two elements it transposes. We defined a walk on $S_n$ to be strictly monotone if the labels of the edges it traverses form a strictly increasing sequence. It is clear that the length of any such walk is at most $n-1,$ which is the diameter of $S_n$ . The following remarkable result holds.

Theorem 4.1. There exists a unique strictly monotone walk between every pair of permutations, and this walk is a geodesic.

Theorem 4.1 gives a second description of $L_r$ as the set of all strictly monotone $r$ -step walks on $S_n$ emanating from the identity permutation, $\iota.$ The figure below illustrates this for $n=4,$ with $\text{blue}=2,$ $\text{purple}=3,$ $\text{black}=4.$

The Jucys-Murphy spanning tree of $S_4$ .

The Jucys-Murphy spanning tree of $S_4$ .

Definition 4.2. The Jucys-Murphy subsets of $S_n$ are defined by

$J_1=\emptyset$

$J_2 = \{(1 2)\}$

$J_3=\{(1 3),(2 3)\}$

$\vdots$

$J_n=\{(1 n),(2 n),\dots,(n-1 n).\}$

Thus,

$J_t = \{(s t) \colon 1 \leq s <t\}$

is the set of all transpositions which swap a given number $t$ with smaller numbers $s$ . The set $J_1 = \emptyset$ is included only for notational convenience, as a sequence with initial index $2$ may be unsettling. It is clear that the JM-subsets of $S_n$ are pairwise disjoint, and that their union is $T_n=L_1$ . More generally, the set of all $r$ -step strictly monotone walks on $S_n$ emanating from the identity permutation $\iota$ is in bijection with

$\bigsqcup\limits_{1 \leq t_1 < \dots < t_r \leq n} J_{t_1} \times J_{t_2} \times \dots \times J_{t_r},$

and hence we have a bijection.

$L_r \simeq \bigsqcup\limits_{1 \leq t_1 < \dots < t_r \leq n} J_{t_1} \times J_{t_2} \times \dots \times J_{t_r},$

We will now encode this correspondence algebraically in $\mathcal{C}(S_n).$

Definition 4.3. The Jucys-Murphy elements in $\mathcal{C}(S_n)$ are

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

The JM-elements are selfadjoint elements satisfying $\langle J_t | J_t \rangle = t-1$ and

$|T_n\rangle = \sum\limits_{t=1}^n |J_t\rangle.$

Thus, $J_1,\dots,J_n \in \mathrm{End}\mathcal{C}(S_n)$ are selfadjoint operators satisfying

$T_n = \sum\limits_{t=1}^n J_t,$

where $T_n$ is the adjacency operator on $\mathrm{Cay}(S_n,T_n).$

Problem 4.2. Prove that the operator norm of $J_t$ is $\|J_t\|=t-1.$

At this point, we can write down the algebraic identity

$|L_r\rangle = \sum\limits_{1 \leq t_1 < \dots < t_r \leq n}|J_{t_1}\rangle \dots |J_{t_n}\rangle.$

This is equivalent to the combinatorial decomposition of $L_r$ in terms of $JM$ -subsets, but at the same time it has many advantages. To see these we first the need the following fact.

Theorem 4.3. The JM-elements $|J_1\rangle,\dots,|J_n\rangle$ pairwise commute in $\mathcal{C}(S_n).$

One way to verify this would be to check directly that the products

$|J_k\rangle|J_l\rangle = \sum\limits_{i<k}\sum\limits_{j<l}|ik\rangle|jl\rangle \quad\text{and}\quad |J_k\rangle|J_l\rangle = \sum\limits_{i<k}\sum\limits_{j<l}|jl\rangle|ik\rangle$

are indeed the same. We will instead construct a manifestly commutative subalgebra $\mathcal{J}_n$ of $\mathcal{C}(S_n)$ which contains $\{|J_1\rangle,\dots,|J_n\rangle\}.$

The key to this construction is the fact that the symmetric groups $S_1,S_2,\dots,S_n$ form an inductive chain

$S_1 \subset S_2 \subset \dots \subset S_n,$

where we identity $S_k=\mathrm{Aut}\{1,\dots,k\}$ with the subgroup of $S_n$ consisting of permutations which fix the numbers $k+1,k+2,\dots,n.$ This gives an inductive chain of algebras,

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

each of which has its own center, giving us a collection

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

of commutative subalgebras of $\mathcal{C}(S_n).$ However, it is not true that these commutative subalgebras form an inductive chain. In fact, they are as disjoint as subalgebras can be.

Problem 4.3. Prove that $Z\mathcal{C}(S_k) \cap Z\mathcal{C}(S_l)=\mathbb{C}|\iota\rangle$ for $k<l.$

What is true is that each element of $Z\mathcal{C}(S_k)$ commutes with every element of $Z\mathcal{C}(S_l).$ Indeed, assuming $k<l$ , the center $Z\mathcal{C}(S_l)$ consists of all elements commuting with every element of $\mathcal{C}(S_l),$ and

$Z\mathcal{C}(S_k) \subset \mathcal{C}(S_k) \subset \mathcal{C}(S_l).$

Definition 4.4. The Jucys-Murphy subalgebra $\mathcal{J}_n$ of $\mathcal{C}(S_n)$ is the commutative subalgebra generated by $Z\mathcal{C}(S_1) \cup Z\mathcal{C}(S_2) \cup \dots \cup Z\mathcal{C}(S_n).$