Lectures 5 and 6 of Math 202C give an application of the representation theory of the symmetric group 
In order to analyze this question rigorously, we need to model it mathematically. The first step is to say exactly what we mean by “shuffle.” We consider a deck of 
The top-to-random shuffle is a stochastic process evolving in discrete time. It may equivalently be formulated as a random walk on the the Cayley graph 
The elements of 
which you will recognize from our previous lectures as the top YJM element in 
This random walk is not equivalent to the top-to-random shuffle, but rather to a shuffling process in which one of the 
A shuffling process should have the property that as 
More formally, let us introduce the 
In probability theory, the corresponding distance 
This random walk is ergodic, and it follows from the Perron-Frobenius theorem in linear algebra that
for each
Shuffling infinitely many times is not something that can be done in the real world. Therefore what we want is an effective version of the above, which tells us how close our deck is to randomized after 
This weeks lectures, which take the form of a typeset document posted to Piazza in the resources section, explain how to do this using the representation theory of the symmetric group, in particular the spectral theory of the YJM elements which we have been discussing. A remarkable insight coming out of the analysis is that the top-to-random shuffle exhibits what is known as the cutoff phenomenon: for small values of
in the group algebra 
of the symmetric group 
despite the non-centrality of the 
‘s themselves. This is quite remarkable, as there is no obvious reason why an arbitrary symmetric polynomial 
should evaluate to a linear combination of conjugacy classes. 
is the irreducible representation of 
(more precisely, a representative of the isomorphism class of all such representations), then the operator 
is of the form 
is the identity operator and 
is a scalar. Note that this scalar must in fact be real, because each 
, being a sum of transpositions, is a selfadjoint element of 
This question has an amazing answer, which we now describe.
is a scalar operator in 
for all 
; this follows immediately from the fact that the map 
of the symmetric group 
as the subalgebra of 
satisfying 
The isotopic decomposition of an irreducible 
as an 
such that the Young diagram 
can be obtained from the Young diagram 
by adding a single cell. 
the isotypic decomposition of the irreducible 
-module as an 
-module is 
dimensional spaces 
indexed by “growth sequences” 
is a diagram with 
-cells, which encode the possible life histories of the multicellular organism 
Obviously, each such growth history corresponds uniquely to a standard Young tableau of shape 
— the entry of a given cell encodes the time instant at which that cell was added. Thus, multiplicity-free branching gives us a basis 
of each irreducible representation 
. Observe that the YJM elements 
(explaining why is a conceptually optimal way to answer one of the homework problems). The following Theorem is an enormously useful tool, both theoretically and computationally.
Moreover, for each irreducible representation 
on the corresponding Young basis 
is given by
is the content (i.e. column index minus row index) of the cell in 
containing the number 
.
acting in the irreducible representation 
and let 
be the Young basis vector corresponding to the standard tableau 
is an eigenvector of each of the operators 
and that the corresponding eigenvalues are, respectively,
![f \in \mathbb{C}[X_1,\dots,X_d]^{\mathrm{S}(d)}](https://s0.wp.com/latex.php?latex=f+%5Cin+%5Cmathbb%7BC%7D%5BX_1%2C%5Cdots%2CX_d%5D%5E%7B%5Cmathrm%7BS%7D%28d%29%7D&bg=FFFFFF&fg=000&s=0&c=20201002)
and any 
on the numbers 
, with 
being an arbitrary enumeration of the cells of 
is
![\mathbb{C}[X_1,\dots,X_d]^{\mathrm{S}(d)} \longrightarrow \mathcal{Z}(d).](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BC%7D%5BX_1%2C%5Cdots%2CX_d%5D%5E%7B%5Cmathrm%7BS%7D%28d%29%7D+%5Clongrightarrow+%5Cmathcal%7BZ%7D%28d%29.&bg=FFFFFF&fg=000&s=0&c=20201002)
![f_\alpha(X_1,\dots,X_d) \in \mathbb{C}[X_1,\dots,X_d]^{\mathrm{S}(d)}](https://s0.wp.com/latex.php?latex=f_%5Calpha%28X_1%2C%5Cdots%2CX_d%29+%5Cin+%5Cmathbb%7BC%7D%5BX_1%2C%5Cdots%2CX_d%5D%5E%7B%5Cmathrm%7BS%7D%28d%29%7D&bg=FFFFFF&fg=000&s=0&c=20201002)
such that 
of the conjugacy class 
acting in the irreducible representation 
is by definition the trace of the operator 
, with 
an arbitrary permutation in the conjugacy class 
Indeed, on one hand we have 
can be expressed as a polynomial in the levels 
of the Cayley graph of 
are not given by any simple formula. This is in a sense inevitable, as the computation of the irreducible characters of the symmetric groups is a 
-complete problem
which we can write down explicitly, and Theorem 1 gives us a way to explicitly calculate the action of 
, such that 
-dimensional Hilbert space in which 
is a 
-algebra
All of this is true for arbitrary groups, and indeed you can view 
as a 
to its corresponding group algebra 
simply by identifying it with the sum of its elements, and any family of disjoint subsets of 
In particular, for each 
we may view the corresponding conjugacy class 
and consider the linearly independent set in the group algebra, 
of 
, we have
in fact depends only on the conjugacy class of 
then 
for any 
Thus 
are called the connection coefficients (aka 
multiplication table for conjugacy classes. More generally, we can take arbitrary polynomials in conjugacy classes, and write them as linear combinations of conjugacy classes, and this often has enumerative meaning. For example, consider the class 
of transpositions. For any 
, we have 
Thus, 
is the same thing as the algebraic problem of resolving 
into a linear combination of conjugacy classes.
, and the two sums are in fact the same since 
Thus, the class algebra is a subalgebra of the 
is a central element, then 
whence 
is a linear combination of conjugacy classes, and we conclude that the class algebra 
as a functor from groups to commutative, unital 
of the Cayley graph of 
-linear combinations of conjugacy classes,
is the set of functions from ![[r]](https://s0.wp.com/latex.php?latex=%5Br%5D&bg=FFFFFF&fg=000&s=0&c=20201002)
to ![[d].](https://s0.wp.com/latex.php?latex=%5Bd%5D.&bg=FFFFFF&fg=000&s=0&c=20201002)
Equivalently, we have 
are the sums![Y_j = \sum\limits_{\{i \in [d] \colon i<j\}} (i\ j), \quad 1 \leq j \leq d.](https://s0.wp.com/latex.php?latex=Y_j+%3D+%5Csum%5Climits_%7B%5C%7Bi+%5Cin+%5Bd%5D+%5Ccolon+i%3Cj%5C%7D%7D+%28i%5C+j%29%2C+%5Cquad+1+%5Cleq+j+%5Cleq+d.&bg=FFFFFF&fg=000&s=0&c=20201002)
is an empty sum, hence equal to the zero element in 
of transpositions and view it as the 
strictly upper triangular matrix over 
is the transposition 
whenever 
and 
when not. Then 
we have
are known as the Young-![L_r = \sum\limits_{\substack{R \subseteq [d] \\ |R|=r}} \prod\limits_{j \in R} Y_j,](https://s0.wp.com/latex.php?latex=L_r+%3D+%5Csum%5Climits_%7B%5Csubstack%7BR+%5Csubseteq+%5Bd%5D+%5C%5C+%7CR%7C%3Dr%7D%7D+%5Cprod%5Climits_%7Bj+%5Cin+R%7D+Y_j%2C&bg=FFFFFF&fg=000&s=0&c=20201002)
of degree 
, we have 
be commuting ![\mathbb{C}[X_1,\dots,X_d].](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BC%7D%5BX_1%2C%5Cdots%2CX_d%5D.&bg=FFFFFF&fg=000&s=0&c=20201002)
As you know from Math 202B, polynomials ![f \in \mathbb{C}[X_1,\dots,X_d]](https://s0.wp.com/latex.php?latex=f+%5Cin+%5Cmathbb%7BC%7D%5BX_1%2C%5Cdots%2CX_d%5D&bg=FFFFFF&fg=000&s=0&c=20201002)
satisfying 
![\mathbb{C}[X_1,\dots,X_d]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BC%7D%5BX_1%2C%5Cdots%2CX_d%5D&bg=FFFFFF&fg=000&s=0&c=20201002)
denoted ![\mathbb{C}[X_1,\dots,X_d]^{\mathrm{S}(d)}.](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BC%7D%5BX_1%2C%5Cdots%2CX_d%5D%5E%7B%5Cmathrm%7BS%7D%28d%29%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
This subalgebra is itself a polynomial algebra.![\mathbb{C}[X_1,\dots,X_d]^{\mathrm{S}(d)} = \mathbb{C}[e_1,\dots,e_d].](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BC%7D%5BX_1%2C%5Cdots%2CX_d%5D%5E%7B%5Cmathrm%7BS%7D%28d%29%7D+%3D+%5Cmathbb%7BC%7D%5Be_1%2C%5Cdots%2Ce_d%5D.&bg=FFFFFF&fg=000&s=0&c=20201002)
![f \in \mathbb{C}[X_1,\dots,X_d]^{\mathrm{S}(d)},](https://s0.wp.com/latex.php?latex=f+%5Cin+%5Cmathbb%7BC%7D%5BX_1%2C%5Cdots%2CX_d%5D%5E%7B%5Cmathrm%7BS%7D%28d%29%7D%2C&bg=FFFFFF&fg=000&s=0&c=20201002)
the group algebra element 
is central.
depends only on the conjugacy class of 
on the YJM elements, we obtain 
, so that we must have 
for all 
as claimed. 
, write down all factorizations of the full cycle 
into three transpositions; identify the factorizations which are weakly monotone, and those which are strictly monotone. Repeat this procedure with the full cycle 
(as in Lecture 1, 
is complex vector space of dimension 
equipped with a scalar product).
is selfadjoint, then there is a positive integer 
real numbers 
and selfadjoint operators 
in 
satisfying
, and this term is applied more generally in ring theory to refer to anything equal to its own square. The “orthogonal” part is 
, the zero operator in 
This is a useful representation of 
, because orthogonal idempotence immediately implies that 
of selfadjoint idempotents acting in 
of subspaces of 
, the corresponding 
maps 
to the nearest point of the subspace 
. The correspondence between selfadjoint idempotents — which are often simply called orthogonal projections — and subspaces even holds in the infinite-dimensional setting provided 
, i.e. 
is for all practical purposes equivalent to the set 
of selfadjoint idempotents/orthogonal projections of rank 
being the distinct eigenvalues of 
. Obviously, selfadjoint operators 
are normal, 
, and so are unitary operators 
since 
. 
, there exists an orthonormal basis 
of 
for each 
, where 
are scalars, if and only if 
-linear combination of pairwise orthogonal selfadjoint idempotents if and only if 
, the symmetric group ![\sigma \colon [d] \to [d],](https://s0.wp.com/latex.php?latex=%5Csigma+%5Ccolon+%5Bd%5D+%5Cto+%5Bd%5D%2C&bg=FFFFFF&fg=000&s=0&c=20201002)
![[d]:=\{1,\dots,d\}](https://s0.wp.com/latex.php?latex=%5Bd%5D%3A%3D%5C%7B1%2C%5Cdots%2Cd%5C%7D&bg=FFFFFF&fg=000&s=0&c=20201002)
, with the group law being composition of functions. Elements of 
can be factored into a product of disjoint cyclic permutations, and this factorization is unique up to the order of the factors. Our starting point will be a rather different unique factorization theorem for permutations. To explain, let us consider 
-cycles,
can be written as a product of transpositions,
, where the subscript reminds that this quantity depends on the choice of generating set 
We will omit this subscript in order to lighten the notation, and if we switch to a different generating set 
inducing a different word norm on 
of a permutation 
for some 
. That is, all factorizations of 
in its unique decomposition into disjoint cycles.
| is a metric.
,
is nothing but the graph theory distance (or geodesic distance) on 
the Cayley graph of the symmetric group as generated by the conjugacy class 
are joined by an edge if and only if there is 
such that 
Note that this is an undirected graph because 
is the identity permutation for every 
so that 
is equivalent to 
Note also that 
Another feature of 
. By the join-cut relation, 
factors.
of 
This description also points to a refinement of the Hurwitz problem. Let us introduce the edge-labeling on 
on 
of edge labels. We say that a walk is strictly monotone if its signature is a strictly increasing sequence. Thus, an 
That is, 
with 
and 
The complete answer to the Hurwitz enumeration problem for 
is thus given by
and 
and let 
, then 
has a unique strictly monotone factorization by the induction hypothesis. If on the other hand 
), then 
and 
By the induction hypothesis, 
admits a unique strictly monotone factorization of length equal to 
, and the result follows.
, which is by convention a linear function of its second argument. The scalar product on 
the algebra of linear operators 
and the study of these symmetry classes is one of the main components of Math 202A. In particular, recall that an operator 
of 
, where 
are real numbers.
on a nested sequence of compact sets in 
is a selfadjoint operator such that the affiliated quadratic form 
is nonnegative, then any zero of 
is in the kernel of 
. 
be such that 
Consider a real perturbation of this zero in an arbitrary direction, i.e. consider 
, where 
is arbitrary and 
is a fixed unit vector. We then have
times
, so it must be the case that 
, otherwise 
would change sign at 
, which it does not, being a nonnegative function. Repeating the above with a pure imaginary perturbation 
, we get that 
as well. Thus 
is orthogonal to every unit vector 
, whence it must be the zero vector, 
is continuous. Thus, by the Extreme Value Theorem, there exists a unit vector 
at which 
attains its maximum value on 
, i.e. we have 
. But this is equivalent to 
where 
is selfadjoint (indeed, selfadjoint operators in 
is nonnegative. Since 
by construction, we may invoke Lemma 1 to conclude that 
is in the kernel of 
, i.e. 
.
-dimensional hyperplane in 
be the unit sphere in 
, let 
be the maximum of the quadratic form 
, and let 
be a point at which the maximum is achieved. By exactly the same argument as above, we get that 
is an eigenvector of 
. Indeed, we can iterate the argument 
times to obtain an orthonormal set 
of eigenvectors with eigenvalues 
and 
we declare 
if and only if 
is a subspace of 
. In fact, 
is its dimension 
. The graded poset 
sending a subspace to its orthogonal complement is an order-reversing involution.
as a covariant functor from the 
are vector spaces and 
is a linear transformation, we get an order-preserving function 
defined by 
might represent the possible states of some physical system, while the free vector space ![\mathbf{V}=\mathbb{C}[E]](https://s0.wp.com/latex.php?latex=%5Cmathbf%7BV%7D%3D%5Cmathbb%7BC%7D%5BE%5D&bg=FFFFFF&fg=000&s=0&c=20201002)
over this set allows for 
is its lattice of subsets 
, where meet and join are intersection and union. This is called a 
which is a cube when 
.
of subsets of 
, and there are factorially many of these. It is equally easy to spot 
saturated antichains, namely the collections 
consisting of all subsets of 
itself is then 
, and it is a 
. This is problematic, but one can analyze the subspace lattice of a vector space defined over 
without difficulty, and count chains, antichains, etc. For example, the antichain consisting of 
, which degenerates to the ordinary binomial coefficient in the 
limit, almost as if 
really did exist…
The analogue of the antichain 
assigns to each subspace 
the maximum of the quadratic form associated to 
of 
then for each 
we have
over the Grassmannian of 
-dimensional subspaces of 
For each 
and also set 
. In the proof of Theorem 1, we showed that
, namely 
It remains to show that the evaluation of 
is at least 
we have 
be any vector in 
. Using orthonormality of the eigenvectors we calculate 
be arbitrary. Since 
,
be a unit vector in 
. Since 
, we have 
by the above inequality. But also 
, which shows that 
, as required.
which preserves the scalar product, 
of unitary operators on 
. Note that the former depends on the scalar product but the latter does not; one may equivalently say that invertible operators map bases to bases, while unitary operators map orthonormal bases to orthonormal bases.
be the set of selfadjoint operators on 
, and let 
be the selfadjoint operator defined by 
consists entirely of selfadjoint operators having spectrum 
follows immediately from the selfadjointness of 
together with the fact that 
. To see that 
be the orthonormal basis of 
is an eigenvector of 
.
. By the Spectral Theorem, there exists an orthonormal basis 
If 
is the unitary operator sending 
to 
.
and adjoint orbits 
-Fock space interpolating between the symmetric and exterior algebras. The two parts of the course are then unified using the infinite wedge space formalism, whose connection with the theory of integrable systems via the Sato Grassmannian will be discussed if time permits.
with 
, the set of edges between 
and 
.
is an expander if subsets 
expand outwards into 
. In other words, all small subsets will have large boundary, respectively. Follow this intuition, we introduce the definition of boundary, based on edges and vertices respectively, to quantify the corresponding expansion.
, is the set of edges 
, which is the set of edges between disjoint set 
.
via maximizing over subsets ![\varepsilon \in [0, 1]](https://s0.wp.com/latex.php?latex=%5Cvarepsilon+%5Cin+%5B0%2C+1%5D&bg=FFFFFF&fg=000&s=0&c=20201002)
, a graph 
-edge-expander if 
.
.
is that we are examining the relative size of every cut in the graph, i.e., the number of edges crossing between 
is
-edge-expander. 
-vertex-expander. (We only consider 
, is defined as
. We didn’t follow this definition since we want to keep ![\varepsilon\in [0, 1]](https://s0.wp.com/latex.php?latex=%5Cvarepsilon%5Cin+%5B0%2C+1%5D&bg=FFFFFF&fg=000&s=0&c=20201002)
.
denote the adjacency Matrix of a 
real eigenvalues, denoted by 
, and corresponding orthonormal eigenvectors 
with 
. The spectrum of 
and the corresponding eigenvector is 
.
.
.
.
, in absolute value, is at most 
.
.
, which is often referred as one-sided.
. Actually, we can also show that the one-sided spectral gap is 
has spectral gap 
. (Hint: use the spectral property above.)
. Then for all 
:
: the number of edges between the two subsets 
: the expected number of edges between two subsets 
.
(a.k.a. large spectral gap) implies that this discrepancy is small, leading to the fact that the graph is nearly random in this sense, as discussed in [1]. We should mention that the converse of expander-mixing is true as well, stated as follows.
and some positive 
.
and 
be the characteristic vectors of subsets 
-th coordinate of 
and 
.
, we expand out the right hand side and apply orthogonality, which yields
.
, 
and 
. Shifting the first term on right hand side to the left, the desired result follows from Cauchy-Schwarz inequality:
and obtain 
, where each entry of 
, namely 
, lie in the interval ![[-1, 1]](https://s0.wp.com/latex.php?latex=%5B-1%2C+1%5D&bg=FFFFFF&fg=000&s=0&c=20201002)
. The Expander-Mixing Lemma is in the form of
. However, we can focus on the spectrum of $\latex A = A(G)$ without normalization when the expected degree $\latex d = O(1)$.
. An independent set 
, i.e., 
, which follows immediately from Lemma 10(Expander-Mixing Lemma[2]).
, where 
is the length of shortest path between 
and 
, then we have
.[6]
, then
.
with eigenvalues ![\bar{\lambda}_{1}, \cdots, \bar{\lambda}_n \in [-1, 1]](https://s0.wp.com/latex.php?latex=%5Cbar%7B%5Clambda%7D_%7B1%7D%2C+%5Ccdots%2C+%5Cbar%7B%5Clambda%7D_n+%5Cin+%5B-1%2C+1%5D&bg=FFFFFF&fg=000&s=0&c=20201002)
, we have
.
, the estimate of spectral gap was given by Nilli Alon.
term is a quantity that tends to zero for every fixed 
.
are arranged in a single row (or a single stack), and a randomly chosen card is repeatedly swapped with the rightmost (or top) card. The algebraic model for this procedure is the Cayley graph 
of the symmetric group as generated by the so-called “star transpositions”
such that 
is an edge if and only if one of the above transpositions swaps 
and gives a precise meaning to the statement that 
such shuffles are required in order to randomize the deck. The argument is pretty much all representation theory — only some very basic probabilistic reasoning is used towards the end.
are defined as the characters of 
normalized by the order of 
![\tilde{\chi}_\rho \tilde{\chi}_\sigma = \tilde{\chi}_\rho [\rho = \sigma], \quad \rho,\sigma \in \mathrm{B}(k).](https://s0.wp.com/latex.php?latex=%5Ctilde%7B%5Cchi%7D_%5Crho+%5Ctilde%7B%5Cchi%7D_%5Csigma+%3D+%5Ctilde%7B%5Cchi%7D_%5Crho+%5B%5Crho+%3D+%5Csigma%5D%2C+%5Cquad+%5Crho%2C%5Csigma+%5Cin+%5Cmathrm%7BB%7D%28k%29.&bg=FFFFFF&fg=000&s=0&c=20201002)
in the group algebra relative to the basis of orthogonal idempotents essentially makes multiplication in the group algebra trivial, which translates into the “Fourier coefficients of a product are products of Fourier coefficients” fact that we saw last Lecture. Note also that the behavior of orthogonal idempotents in the group algebra is formally identical to the behavior of orthogonal projections in Hilbert space — you perhaps know from Math 202B that this is not a coincidence, and if you don’t know this don’t worry, because we will discuss it.
coincides with the class of operators that are diagonal in the character basis of 
be an element of the group algebra, and let 
be the corresponding multiplication operator. Consider the character expansion of 
be another character. We have 
is an eigenvector of 
with eigenvalue the Fourier coefficient 
acts diagonally in the character basis:
with 
Indeed, the adjacency operator of the Cayley graph of 
if 
is a factor of 
and is equal to 
if 
Since we compute this scalar product for each and every generator 
the sum has 
terms equal to 
and 
terms equal to 
where 
such that 
for a given 
is simply 
since this just amounts to choosing 
of 
is 
of 
of functions
of  = \sum\limits_{\sigma \in \mathrm{B}(k)} a(\pi\sigma^{-1}) b(\sigma),](https://s0.wp.com/latex.php?latex=%5Ba%2Ab%5D%28%5Cpi%29+%3D+%5Csum%5Climits_%7B%5Csigma+%5Cin+%5Cmathrm%7BB%7D%28k%29%7D+a%28%5Cpi%5Csigma%5E%7B-1%7D%29+b%28%5Csigma%29%2C&bg=FFFFFF&fg=000&s=0&c=20201002)
as a generating function which are equivalent to complex valued functions on 
themselves (rather than their indicator functions), which induces the equivalent scalar product,
. The algebraic way to understand this combinatorial object is to replace the vertex set 
of 
of polynomials in noncommuting variables 
indexed by the vertices of 
In other words, this is the 
This algebra is graded by degree, and we have a decomposition 
i.e. the space of functions on 
is isomorphic to either/both 
and 
and the adjacency operator acts on this linear component to capture the edge structure of 
Indeed, the free algebra is isomorphic to the 
In the case where the vertex set of 
we can mod out by the group law and consider the quotient 
so functions on the group, or equivalently linear combinations of group elements, but now with the structure of an algebra.
the corresponding multilplication operator 
is defined by 
and 
To put this the Math 202B way, the operator 
is the image of 
in the right regular representation of 
is both unitary and selfadjoint, hence has eigenvalues 
is the multiplication operator 
where 
we have 
of group elements which have the property that 
showing that they have values in the subgroup generated by ![\langle \chi_\pi,\chi_\sigma \rangle = 2^k[\pi=\sigma], \quad \pi,\sigma \in \mathrm{B}(k).](https://s0.wp.com/latex.php?latex=%5Clangle+%5Cchi_%5Cpi%2C%5Cchi_%5Csigma+%5Crangle+%3D+2%5Ek%5B%5Cpi%3D%5Csigma%5D%2C+%5Cquad+%5Cpi%2C%5Csigma+%5Cin+%5Cmathrm%7BB%7D%28k%29.&bg=FFFFFF&fg=000&s=0&c=20201002)
we have the character expansion
being the Fourier coefficients of 
The main reason that character expansions are “better” than expansions in the group basis is that the Fourier coefficients of a product 
are just the products of the corresponding Fourier coefficients of 
— are better than the original group elements is that their multiplication is extremely simple. 
we have
and 
is a homomorphism and 
The result now follows from character orthogonality, which is Theorem 2 in Lecture 7.
we have 
is a multiplication operator if and only if it acts diagonally in the character basis. We will also find the corresponding eigenvalues, and hence count walks on