Math 202C: Lecture 13

In Lecture 12, we analyzed the top-to-random shuffle of a deck of n cards, which is the same thing as lazy simple random walk on the Cayley graph of the symmetric group \mathrm{S}(n) generated by the star transpositions

(1\ n), \dots, (n-1\ n).

An important role in this analysis was played the sum of these transpositions,

J_n = (1\ n) + \dots +(n-1\ n),

which is an element of the group algebra \mathbb{C}\mathrm{S}(n). In fact, J_n is one of a special family of elements in \mathbb{C}\mathrm{S}(n) called the Jucys-Murphy elements of \mathbb{C}\mathrm{S}(n). These element have many remarkable properties, a few of which we will discuss in this lecture — in fact, these simple transposition sums are so rich in structure that they encapsulate the entire representation theory of the symmetric group, and can be taken as the starting point for a very intuitive and streamlined re-imagining of this subject.

The JM elements can be understood in terms of the Cayley \Gamma = \mathrm{Cay}(\mathrm{S}(n),\mathrm{T}) as arising from a special edge-labeling of \Gamma called the Biane-Stanley edge labeling. To construct this labeling, mark each edge of the group corresponding to the transposition (i\ j) with j, the larger of the two numbers interchanged. Thus, each edge of \Gamma is assigned a label from the set \{2,\dots,n\}. Emanating from each vertex \pi \in \mathrm{S}(n) we see one 2-edge, two 3-edges, three 4-edges, etc., as in the picture below.

For a full example, the figure below shows the Cayley graph of the symmetric group \mathrm{S}(4) with the Biane-Stanley edge labeling, with 2-edges drawn in cyan, 3-edges in magenta, and 4-edges in black.

This edge labeling of the Cayley graph of the symmetric group was introduced by Richard Stanley in the context of noncrossing partitions, and you can read about this here. We will use the introduction of more structure on \Gamma to break away from the Markovian paradigm of the evolution of a memoryless particle on \Gamma.

Definition 1: A walk on \Gamma is said to be monotone if the labels of the edges it traverses form a non-decreasing sequence, and strictly monotone if the labels of the edges it traverses form an increasing sequence.

You can think of monotone walks as virtual histories of a particle moving around on \Gamma which learns from experience: once the particle traverses a road of value t, it refuses to traverse roads of lesser value. Strictly monotone walks are histories of an even more fastidious particle that seeks out roads of strictly increasing value as it evolves. If the motion of the particle is random, then monotone walks on \Gamma are histories of a self-interacting random walk, meaning a random walk whose next step at each time instant depends on its history up to that time.

Given permutations \rho,\sigma \in \mathrm{S}(n) and a nonnegative integer r, let H^r(\rho,\sigma) denote the number of r-step walks on \gamma from \rho to \sigma, and let E^r(\rho,\sigma) denote the number of strictly monotone r-step walks from \rho to \sigma. Obviously, we always have

0 \leq E^r(\rho,\sigma) \leq H^r(\rho,\sigma) \leq W^r(\rho,\sigma),

where we recall that W^r(\rho,\sigma) is the number of unrestricted r-step walks from \rho to \sigma.

Theorem 1: For any permutations \rho,\sigma \in \mathrm{S}(n), we have

E^r(\rho,\sigma) = \begin{cases} 1, \text{ if } r=|\rho^{-1}\sigma| \\ 0, \text{ otherwise}. \end{cases}

That is, there exists a unique strictly monotone walk between any two permutations, and this walk is a geodesic.

Proof: First, observe that the problem is vertex transitive: we have E^r(\rho,\sigma) = E^r(\tau\rho,\tau\sigma) for any \tau \in \mathrm{S}(n). Indeed, if

\sigma = \rho(s_1\ t_1) \dots (s_r\ t_r), \quad t_1< \dots < t_r

is a strictly monotone walk from \rho to \sigma, then

\tau\sigma = \tau\rho (s_1\ t_1) \dots (s_r\ t_r), \quad t_1< \dots < t_r

is a strictly monotone walk from \tau\rho to \tau\sigma, and vice versa. It is thus sufficient to prove that

E^r(\iota,\pi) = \begin{cases} 1, \text{ if } r=|\pi| \\ 0, \text{ otherwise}, \end{cases}

where \iota \in \mathrm{S}(n) is the identity permutation. Here is a proof by picture: draw all strictly monotone walks on \Gamma departing from \iota. What results is a graphical presentation of \mathrm{S}(n) as a starlike tree:

The basic idea of an actual proof is as follows. First, verify that every cyclic permutation admits a unique strictly monotone factorization, the number of factors of which is one less than the length of the cycle, which is the smallest number of factors possible. Now for an arbitrary permutation, factor each of its cycles into a minimal strictly monotone product of transpositions, and observe that there is a unique way to rearrange the transposition factors of all these factorizations so that they are strictly monotone.

— Q.E.D.

A group-theoretic way to conceptualize Theorem 1 is as a unique factorization theorem for the symmetric group: every permutation \pi \in \mathrm{S}(n) has a unique factorization of the form

\pi = (s_1\ t_1)(s_2\ t_2) \dots (s_k\ t_k), \quad s_i<t_i,

such that t_1< t_2 < \dots < t_k, and moreover k=|\pi|. In terms of the group algebra \mathbb{C}\mathrm{S}(n), we may rephrase Theorem 1 as follows: we have

L_r = \sum\limits_{\substack{2 \leq t_1 < \dots < t_r \leq n\\ s_1<t_1, \dots, s_k<t_k}} (s_1\ t_1) \dots (s_r\ t_r), \quad 0 \leq r \leq n-1

where

L_r = \sum\limits_{\substack{ \pi \in \mathrm{S}(n) \\ |\pi|=r}} \pi

is the rth level of the Cayley graph, or in other words the identity-centered sphere of radius r in the symmetric group, viewed as an element of the group algebra \mathbb{C}\mathrm{S}(n). Equivalently, this can be written

L_r = \sum\limits_{2 \leq t_1 < \dots < t_r \leq n} \left( \sum\limits_{s_1=1}^{t_1} (s_1\ t_1) \right) \dots \left( \sum\limits_{s_r=1}^{t_r} (s_r\ t_r) \right).

Defintion 1: The Jucys-Murphy elements in \mathbb{C}\mathrm{S}(n) are the transposition sums

J_2= (1\ 2) \\ J_3 =(1\ 3) + (2\ 3)\\ \vdots \\ J_n=(1\ n) + (2\ n) + \dots + (n-1\ n).

For notational convenience, we set J_1:=\mathbf{0}, the zero element of the group algebra \mathbb{C}\mathrm{S}(n).

Problem 1: Prove that the JM elements commute with one another.

We can now connect the group algebra formulation of Theorem 1 to the theory of symmetric polynomials.

Let the symmetric group \mathrm{S}(n) act on the algebra of \mathbb{C}[x_1,\dots,x_n] of polynomials in n variables by permuting variables:

\sigma . f(x_1,\dots,x_n) = f(x_{\sigma(1)},\dots,x_{\sigma(n)}).

The algebra of symmetric polynomials is the corresponding space of invariants,

\mathbb{C}[x_1,\dots,x_n]^{\mathrm{S}(n)} = \{ f \in \mathbb{C}[x_1,\dots,x_n] \colon \sigma . f =f\}.$

A non-obvious fact is that this algebra of invariants is in fact a polynomial algebra.

Theorem (Newton): We have

\mathbb{C}[x_1,\dots,x_n]^{\mathrm{S}(n)} = \mathbb{C}[e_1(x_1,\dots,x_n),\dots,e_n(x_1,\dots,x_n)],

where

e_r(x_1,\dots,x_n) = \sum\limits_{1 \leq i_1 < \dots < i_r \leq n} x_{i_1} \dots x_{i_r}, \quad 1 \leq r \leq n.

Newton’s theorem, which is often called the fundamental theorem of symmetric function theory, says that every f \in  \mathbb{C}[x_1,\dots,x_n]^{\mathrm{S}(n)} is a polynomial in the elementary symmetric polynomials e_1,\dots,e_n.

Theorem 2: The substitution rule

f(x_1,\dots,x_n) \mapsto f(J_1,\dots,J_n)

defines a homomorphism

\mathbb{C}[x_1,\dots,x_n]^{\mathrm{S}(n)} \longrightarrow \mathcal{Z}(n),

from the algebra of symmetric polynomials in n variables to the center of \mathbb{C}\mathrm{S}(n).

Proof: Theorem 1 says that

L_r = e_r(J_1,\dots,J_n).

Thus, by Newton’s theorem, any symmetric polynomial f(J_1,\dots,J_n) evaluated on the JM elements will be a polynomial in L_0,\dots,L_{n-1}. It thus suffices to show that each level of the Cayley graph (identified with the formal sum of its constituents) is an element of \mathcal{Z}(n). But this is clear: the center \mathcal{Z}(n) is spanned by the conjugacy classes C_\mu of \mathrm{S}(n) (each of which is identified with the formal sum of its constituents), and

L_r = \sum\limits_{\substack{\mu \vdash n \\ \ell(\mu)=n-r}} C_\mu.

— Q.E.D.

Theorem 2 has rather interesting consequences for monotone walks on the Cayley graph. Note that, if we consider all walks on the Cayley graph, then the number W^r(\iota,\pi) of r-step walks from the identity to a given permutation \pi depends only on the conjugacy class of \pi. Indeed, if \pi' is a conjugate of \pi, \pi' = \sigma\pi\sigma^{-1}, then every factorization

\pi = (s_1\ t_1) \dots (s_r\ t_r)

of \pi corresponds to the factorization

\pi' = (s_1'\ t_1') \dots (s_r'\ t_r')

in which

(s_i'\ t_i') = \sigma (s_i\ t_i) \sigma^{-1},

and this correspondence is clearly bijective. This simple argument does not show that the number of monotone factorizations

\pi = (s_1\ t_1) \dots (s_r\ t_r), \quad t_1 \leq \dots \leq t_r

is equal to the number of monotone factorizations of \pi, because conjugating each of the factors will not necessarily preserve the monotonicity condition. However, the following more sophisticated argument shows that indeed H^r(\iota,\pi)=H^r(\iota,\pi').

For each r \in \mathbb{N}, the degree r complete symmetric polynomial is defined by

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

We have

h_r(J_1,\dots,J_n) = \sum\limits_{1 \leq t_1 \leq \dots \leq t_r } J_{t_1} \dots J_{t_r} \\= \sum\limits_{1 \leq t_1 \leq \dots \leq t_r } \left( \sum\limits_{s_1=1}^{t_1} (s_1\ t_1) \right) \dots \left( \sum\limits_{s_r=1}^{t_r} (s_r\ t_r) \right) \\=\sum\limits_{\substack{ 1 \leq t_1 \leq \dots \leq t_r \leq n \\ s_i < t_i }} (s_1\ t_1) \dots (s_r\ t_r),

which is the sum of all monotone products of r transpositions. Evaluating each term in the sum and collecting like coefficients, the coefficient of \pi is the number of monotone factorizations of \pi, and the coefficient of \pi' is the number of monotone factorizations of \pi'. But, since this sum is a linear combination of conjugacy classes by Theorem 2, and since \pi and \pi' belong to the same conjugacy class, these coefficients are equal.

In the next lecture, we will combine the spectral theory of the JM elements with their combinatorial properties to give eigenvalue formulas for the enumeration of monotone walks on the Cayley graph.

Leave a Reply