In Lecture 12, we analyzed the top-to-random shuffle of a deck of cards, which is the same thing as lazy simple random walk on the Cayley graph of the symmetric group generated by the star transpositions
An important role in this analysis was played the sum of these transpositions,
which is an element of the group algebra In fact, is one of a special family of elements in called the Jucys-Murphy elements of 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 as arising from a special edge-labeling of called the Biane-Stanley edge labeling. To construct this labeling, mark each edge of the group corresponding to the transposition with the larger of the two numbers interchanged. Thus, each edge of is assigned a label from the set Emanating from each vertex we see one -edge, two -edges, three -edges, etc., as in the picture below.
For a full example, the figure below shows the Cayley graph of the symmetric group with the Biane-Stanley edge labeling, with -edges drawn in cyan, -edges in magenta, and -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 to break away from the Markovian paradigm of the evolution of a memoryless particle on
Definition 1: A walk on 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 which learns from experience: once the particle traverses a road of value , 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 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 and a nonnegative integer let denote the number of -step walks on from to and let denote the number of strictly monotone -step walks from to Obviously, we always have
where we recall that is the number of unrestricted -step walks from to
Theorem 1: For any permutations we have
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 for any Indeed, if
is a strictly monotone walk from to then
is a strictly monotone walk from to and vice versa. It is thus sufficient to prove that
where is the identity permutation. Here is a proof by picture: draw all strictly monotone walks on departing from . What results is a graphical presentation of 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.
A group-theoretic way to conceptualize Theorem 1 is as a unique factorization theorem for the symmetric group: every permutation has a unique factorization of the form
such that and moreover In terms of the group algebra we may rephrase Theorem 1 as follows: we have
is the th level of the Cayley graph, or in other words the identity-centered sphere of radius in the symmetric group, viewed as an element of the group algebra Equivalently, this can be written
Defintion 1: The Jucys-Murphy elements in are the transposition sums
For notational convenience, we set the zero element of the group algebra
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 act on the algebra of of polynomials in variables by permuting variables:
The algebra of symmetric polynomials is the corresponding space of invariants,
A non-obvious fact is that this algebra of invariants is in fact a polynomial algebra.
Theorem (Newton): We have
Newton’s theorem, which is often called the fundamental theorem of symmetric function theory, says that every is a polynomial in the elementary symmetric polynomials
Theorem 2: The substitution rule
defines a homomorphism
from the algebra of symmetric polynomials in variables to the center of
Proof: Theorem 1 says that
Thus, by Newton’s theorem, any symmetric polynomial evaluated on the JM elements will be a polynomial in It thus suffices to show that each level of the Cayley graph (identified with the formal sum of its constituents) is an element of But this is clear: the center is spanned by the conjugacy classes of (each of which is identified with the formal sum of its constituents), and
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 of -step walks from the identity to a given permutation depends only on the conjugacy class of Indeed, if is a conjugate of then every factorization
of corresponds to the factorization
and this correspondence is clearly bijective. This simple argument does not show that the number of monotone factorizations
is equal to the number of monotone factorizations of because conjugating each of the factors will not necessarily preserve the monotonicity condition. However, the following more sophisticated argument shows that indeed
For each the degree complete symmetric polynomial is defined by
which is the sum of all monotone products of transpositions. Evaluating each term in the sum and collecting like coefficients, the coefficient of is the number of monotone factorizations of and the coefficient of is the number of monotone factorizations of But, since this sum is a linear combination of conjugacy classes by Theorem 2, and since and 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.