Jonathan Novak

Math 289A: Lecture 7

In this lecture we will review what we have done so far from a slightly different perspective. Starting with the Fourier kernel

$F \colon \mathbb{R} \times \mathbb{R} \longrightarrow \mathbb{C},$

which is defined by $F(a,b) = e^{iab},$ we can define the characteristic function of a random variable $X$ with distribution $\mu$ by

$\varphi_X(a) = \mathbf{E}F(a,X) = \int\limits_{\mathbb{R}} F(a,x)\mu(\mathrm{d}x).$

This is an absolutely continuous function from $\mathbb{R}$ into the closed unit disc in $\mathbb{C}$ which uniquely determines the measure $\mu.$ To get some feel for which this might be, expand the Fourier kernel in a power series,

$F(a,b) = 1 + \sum_{d=1}^\infty \frac{i^d}{d!} (ab)^d.$

Then, assuming we can interchange expectation with the summation we get

$\mathbf{E}F(a,X) = 1 + \sum_{d=1}^\infty \frac{i^d}{d!} a^d\mathbf{E}[X^d],$

where

$\mathbf{E}[X^d] = \int\limits_{\mathbb{R}} x^d \mu(\mathrm{d}x)$ ,

is the degree $d$ moment of $X,$ or equivalently of $\mu.$ So at least heuristically, the characteristic function of $X$ is a generating function for the moments of its distribution. One situation in which this formal computation is quantitatively correct is when $\mu$ has compact support, so if the characteristic function does indeed characterize the distribution of $X$ then it must be the case that $\mu$ is characterized by its moments. It is not difficult to see why the why the moments of a probability measure with compact support determine it completely: if we know how to compute the expectation of polynomial functions of $X$ , then thanks to the Weierstrass approximation theorem we also know how to compute the expectation of continuous functions of $X,$ and this in turn tells us how $\mu$ measures intervals, by taking expectations of smooth bump functions. Of course, to obtain the fully general result that the characteristic function of $X$ completely determines its distribution a different argument is needed. For example, the Cauchy distribution has no moments whatsoever, but its characteristic function still exists and determines it uniquely.

The $N$ -dimensional Fourier kernel

$F_N \colon \mathbb{R^N} \times \mathbb{R^N} \longrightarrow \mathbb{C}$

is defined by

$F_N(A,B) = e^{i \langle A,B\rangle} = e^{i(a_1b_1+\dots+a_Nb_N)}, \quad A,B \in \mathbb{R}^N$

and the characteristic function of an $N$ -dimensional random vector $X_N$ is the continuous function $\mathbb{R}^N \to \mathbb{C}$ defined by

$\varphi_{X_N}(A) = \mathbf{E}F_N(A,X_N) = \int\limits_{\mathbb{R}^N} F_N(A,X) \mu_N(\mathrm{d}X),$

where $\mu_N$ is the distribution of $X_N$ in $\mathbb{R}^N.$ It is still true that $\varphi_{X_N}$ exists and uniquely determines $\mu_N$ , and we can tell a similar story about moments which supports this statement. To do so we first have to expand the $N$ -dimensional Fourier kernel in a power series. This is easy but let us first make some general observations about what this expansion must look like before doing the computation. Since $F_N(A,B) = F_N(B,A)$ and

$F_N(PA,PB) = e^{i\langle PA,PB\rangle} = e^{i \langle A,B \rangle} = F_N(A,B),$

for any $N \times N$ permutation matrix $P,$ we have

$F_N(A,B) =1 + \sum_{d=1}^\infty \frac{d^d}{d!} F_N^d(A,B)$

where $F_N^d(A,B)$ is a homogeneous polynomial of degree $d$ in $a_1b_1,\dots,a_Nb_N$ which is invariant under independent permutations of these variables. Therefore, we have

$F_N^d(A,B) = \sum\limits_{\alpha \in \mathsf{C}_N^d} (a_1b_1)^{\alpha_1}\dots (a_Nb_N)^{\alpha_N}F_N(\alpha)$

where $\mathsf{C}_N^d$ is the set of weak $N$ -part compositions $\alpha$ of $d \in \mathbb{N}$ and $F_N(\alpha)$ is a numerical coefficient. It is easy to determine this coefficient explicitly: since

$F_N(A,B) = e^{ia_1b_1} \dots e^{ia_Nb_N} = \left(\sum\limits_{d=0}^\infty \frac{i^d}{d!}(a_1b_1)^d \right)\dots \left(\sum\limits_{d=0}^\infty \frac{d^d}{d!}(a_Nb_N)^d \right),$

we have

$F_N(\alpha) = \frac{d!}{\alpha_1! \dots \alpha_N!}={d \choose \alpha_1,\dots,\alpha_N},$

the multinomial coefficient. Thus, the expected value of $F_N^d(A,X_N)$ is a generating polynomial for degree $d$ mixed moments of the entries of the random vector $X_N=(X_N(1),\dots,X_N(N))$ ,

$\mathbf{E}F_N^d(A,X_N) = \sum\limits_{\alpha \in \mathsf{C}_N^d} a_1^{\alpha_1} \dots a_N^{\alpha_N} \mathbf{E}[X^{\alpha_1}_N(1)\dots X^{\alpha_N}_N(N)]F_N(\alpha).$

In the previous lectures we defined a strange new kernel

$K_N \colon \mathbb{R}^N \times \mathbb{R}^N \longrightarrow \mathbb{C}$

$K_N(A,B) = \int\limits_{\mathbb{U}_N} F_N(A,|U|^2B)\mathrm{d}U,$

where the integration is against Haar probability measure on the unitary group $\mathbb{U}_N,$ and for any $U \in \mathbb{U}_N$ the matrix

$|U|^2=\begin{bmatrix} {} & \vdots & {} \\ \dots & |U_{xy}|^2 & \dots \\ {} & \vdots & {} \end{bmatrix}$

is obtained from $U=[U_{xy}]$ by taking the squared modulus of each entry. Thus for any $B \in \mathbb{R}^N$ the vector

$|U|^2B=\begin{bmatrix} |U_{11}|^2b_1 + \dots + |U_{1N}|^2b_N \\ |U_{21}|^2b_1 + \dots + |U_{2N}|^2b_N \\ \vdots \\ |U_{N1}|^2b_1 + \dots + |U_{NN}|^2b_N\end{bmatrix} \in \mathbb{R}^N$

has coordinates which are superpositions of the coordinates of $B,$ and because of this we named $K_N$ the $N$ -dimensional “quantum Fourier kernel.”

Problem 7.1. Prove that $K_N$ is a bounded symmetric kernel on $late \mathbb{R}^N$, i.e. $|K_N(A,B)|\leq 1$ and $K_N(A,B)=K_N(B,A)$ for all $A,B \in \mathbb{R}^N.$

Then, given a random vector $B_N$ with distribution $\sigma_N$ in $\mathbb{R}^N,$ we defined its quantum characteristic function by

$\psi_{B_N}(A)=\mathbf{E}K_N(A,B_N) = \int\limits_{\mathbb{R}^N} K_N(A,B)\sigma(\mathrm{d}B).$

This is a continuous function from $\mathbb{R}^N$ into the closed unit disc in $\mathbb{C}$ , and we claimed that $\psi_{B_N}$ uniquely determines the distribution $\sigma_N$ of $B_N.$ Since the quantum characteristic function of $B_N$ is clearly distinct from its classical characteristic function

$\varphi_{B_N}(A) = \mathbf{E}F_N(A,B_N)=\int\limits_{\mathbb{R}^N} F_N(A,B)\sigma(\mathrm{d}B),$

this must be true for some different reason. To understand what this reason might be, at least heuristically, we could proceed along the same lines we did with $F_N$ and try to determine if $\varphi_{B_N}(A)$ is some sort of generating function encoding natural statistics of $B_N$ .

Let’s give this a try. The first step is to expand the quantum Fourier kernel $K_N$ as a power series. Before doing the computation, we can look for some easy symmetries of $K_N$ which will tell us in advance what a series expansion of $K_N$ ought to look like. In fact, the quantum Fourier kernel is much more symmetric than the classical Fourier kernel – it is invariant under independent (as opposed to simultaneous) permutations of the coordinates of its arguments.

Problem 7.2. Prove that $K_N(PA,QB)=K_N(A,B)$ for any $A,B \in \mathbb{R}^N$ and any $N\times N$ permutation matrices $P,Q.$

From Problems 7.1 and 7.2, we can indeed infer the general form of a series expansion of the kernel $K_N.$ Namely, we have

$K_N(A,B) = 1 + \sum\limits_{d=1}^\infty \frac{i^d}{d!} K_N^d(A,B),$

where $K_N^d(A,B)$ is a homogeneously degree $d$ polynomial function of the coordinates $a_1,\dots,a_N,b_1,\dots,b_N$ which is invariant under independent permutations of $a_1,\dots,a_N$ and $b_1,\dots,b_N$ and stable under swapping these two sets of variables. What does such a polynomial look like?

A classical theorem of Newton asserts that a symmetric homogeneous degree $d$ polynomial in $N$ variables is a polynomial function of the power-sum polynomials

$p_1(x_1,\dots,x_N) = x_1+\dots+x_N \\ p_2(x_1,\dots,x_N)=x_1^2+\dots+x_N^2\\ \vdots \\ p_N(x_1,\dots,x_N)=x_1^N+\dots+x_N^N.$

Equivalently, the vector space $\Lambda_N^d$ of symmetric homogeneous degree $d$ polynomials in $N$ variables has as a linear basis the polynomials

$p_\alpha(x_1,\dots,x_N)=\prod\limits_{k=1}^{\ell(\alpha)} p_{\alpha_1k}(x_1,\dots,x_N),$

where $\alpha=(\alpha_1,\dots,\alpha_r)$ ranges over the set $\mathsf{P}_N^d$ of partitions of $d$ with largest part at most $N,$ and $\ell(\alpha)$ denoting the number of parts.

Problem 7.3. Prove that for any $\alpha \in \mathsf{P}_N^d$ and any $A \in \mathbb{R}^N,$ the evolution $p_\alpha(A)=p_\alpha(a_1,\dots,a_N)$ satisfies $|p_\alpha(A)| \leq \|A\|_\infty N^{\ell(\alpha)},$ and that this bound is sharp.

Thus, a power series expansion of the quantum Fourier kernel can be written in the form

$K_N(A,B) = 1 + \sum\limits_{d=1}^\infty \frac{i^d}{d!}\sum\limits_{\alpha,\beta \in \mathsf{P}_N^d} \frac{p_\alpha(a_1,\dots,a_N)}{N^{\ell(\alpha)}}\frac{p_\beta(b_1,\dots,b_N)}{N^{\ell(\beta)}}K_N(\alpha,\beta),$

where the coefficients satisfy $K_N(\alpha,\beta)=K_N(\beta,\alpha).$ This complicated-looking expression is actually quite meaningful. For any vector $A \in \mathbb{R}^N$ , the normalized power sum polynomial of degree $d$ in the coordinates of $A$ is

$\frac{p_k(a_1,\dots,a_N)}{N} = \int\limits_{\mathbb{R}} x^k \eta_A(\mathrm{d}x),$

where

$\eta_A = \frac{1}{N} \sum\limits_{i=1}^N \delta_{a_i}$

is the discrete probability measure on $\mathbb{R}$ which places equal mass at each coordinate of $A.$ This is called the empirical distribution of $A \in \mathbb{R}^N.$ Thus, the expansion of the quantum Fourier kernel $K_N(A,B)$ is a generating function for the moments of the empirical distributions of its arguments. Consequently, for $B_N$ a random vector, the quantum characteristic function $\psi_{B_N}(A)$ is a generating function for expectations of polynomials in the random variables

$p_1(B_N),p_2(B_N),p_3(B_N),\dots,$

which are the moments of the (random) empirical distribution of the random vector $B_N.$

Math 289A: Lecture 6

Here is a link to the slides from today’s Zoom lecture: https://web.goodnotes.com/s/GPePlT3BSSbzDsGPUrqG2G#page-5

Note that some of this material was typed up towards the end of the Lecture 5 notes.

Math 289A: Lecture 5

Let $\mathbb{H}_N$ be the real vector space of Hermitian matrices with the Hilbert-Schmidt scalar product

$\langle X,Y \rangle =\mathrm{Tr}\, XY.$

Let

$f \colon \mathbb{H}_N \longrightarrow \mathbb{R}^N$

be the function from Hermitian matrices to standard Euclidean space defined by

$f(X) = (\text{eigenvalues of }X\text{ listed largest to smallest}).$

Theorem 5.1 (Hoffman-Wielandt Inequality). For any $X,Y \in \mathbb{H}_N$ we have

$\|f(X)-f(Y)\| \leq \|X-Y\|.$

Proof: By the spectral theorem, there are unitary matrices $V,W \in \mathbb{U}_N$ and non-increasing vectors $A,B \in \mathbb{R}^N$ such that

$X=VAV^* \quad\text{and}\quad Y=WBW^*.$

The square of the Hilbert-Schmidt norm of the difference $X-Y$ is

$\|X-Y\|^2 = \langle VAV^*-WBW^*,VAV^*-WBW^*\rangle = \mathrm{Tr}\, (VAV^*-WBW^*)^2,$

and

$\mathrm{Tr}\, (VAV^*-WBW^*)^2=\mathrm{Tr}\, A^2 -2\mathrm{Tr}\, VAV^*WBW^*+\mathrm{Tr}\, B^2.$

Therefore, if we can show

$\mathrm{Tr}\, AUBU^* \leq \mathrm{Tr}\, AB$

holds for all $U \in \mathbb{U}_N,$ we will have proved the claimed inequality (make sure you understand why).

Now,

$\mathrm{Tr}\, AUBU^* = \sum_{i,j=1}^N a_ib_j |U_{ij}|^2,$

and $[|U_{ij}|^2]$ is a doubly stochastic matrix. Therefore, the maximum value of $\mathrm{Tr}\, AUBU^*$ over all $U \in \mathbb{U}_N$ is bounded by the maximum value of the function

$g(M) = \sum_{i,j=1}^N a_ib_j |M_{ij}|,$

as $M$ ranges over all doubly stochastic matrices. Since $g$ is a linear function on the Birkhoff polytope, it achieves its maximum value at an extreme point of this convex set, so at a permutation matrix. The vertex corresponding to the identity matrix gives

$g(I) = \sum\limits_{i=1}^N a_i b_i = \mathrm{Tr}\, AB,$

and since the coordinates of $A$ and $B$ are nonincreasing the identity permutation is the optimal matching.

– QED

Now let $X_N$ be a random Hermitian matrix.

Theorem 5.2. The following are equivalent:

The characteristic function of $X_N$ is invariant under unitary conjugation;
The distribution of $X_N$ is invariant under unitary conjugation;
$X_N$ is equal in distribution to a random Hermitian matrix of the form $U_NB_NU_N^*,$ where $U_N$ is a uniformly random unitary matrix and $B_N$ is a random real diagonal matrix independent of $U_N$ .

We have already proved the equivalence of (1) and (2).

Problem 5.2. Complete the proof of Theorem 5.1.

At this point we have enough information to explain how the characteristic function of a unitarily invariant random Hermitian determines the joint distribution of its eigenvalues.

Theorem 5.2. The characteristic function of a unitarily invariant random Hermitian matrix is equal to the quantum characteristic function of its eigenvalues.

Obviously, this statement needs to be explained.

Let $B_N$ be a real random vector whose distribution $\sigma_N$ in $\mathbb{R}^N$ is arbitrary, and let $U_N$ be an independent random unitary matrix whose distribution $\eta_N$ in $\mathbb{U}_N$ is uniform (Haar) measure. Then $X_N=U_NB_NU_NB^*$ is a unitarily invariant random Hermitian matrix, and by Theorem 5.2 every unitarily invariant random Hermitian matrix is equal in law to a matrix constructed in this way.

Because $\mathbb{H}_N$ is non-compact, there is no such thing as a uniformly random Hermitian matrix. The matrix $X_N = U_NB_NU_N^*$ is as close as we can get: it is uniform conditional on the distribution of its eigenvalues $B_N.$ If $\mu_N$ is the distribution of $X_N$ in $\mathbb{H}_N$ , a random sample from $\mu_N$ is obtained by sampling a vector from the distribution $\sigma_N$ on $\mathbb{R}^N,$ and then choosing a uniformly random point on the $\mathbb{U}_N$ -orbit in $\mathbb{H}_N$ which contains this vector.

In terms of characteristic functions, this says that

$\varphi_{X_N}(A) = \mathbf{E}_{\mu_N}\left[e^{i \mathrm{Tr} AU_NB_NU_N^*}\right] = \mathbf{E}_{\sigma_N} \left[K_N(A,B_N)\right],$

where

$K_N(A,B) = \mathbf{E}_{\eta_N}\left[e^{i\mathrm{Tr}\, AUBU^*}\right] = \int_{\mathbb{U}_N} e^{i \mathrm{Tr}\, AUBU^*} \eta_N(\mathrm{d}U)$

is the characteristic function of a uniformly random Hermitian matrix from the $\mathbb{U}_N$ orbit containing $B \in \mathbb{R}^N$ viewed as a diagonal matrix. Thus, $K_N(A,B)$ is the characteristic function of a uniformly random Hermitian matrix with prescribed eigenvalues. This defines a bounded symmetric kernel

$K_N \colon \mathbb{R}^N \times \mathbb{R}^N \longrightarrow \mathbb{C}$

which we call the quantum Fourier kernel, because it is a superposition of standard $N$ -dimensional Fourier kernels

$K_N(A,B) = \int_{\mathbb{U}_N}e^{i \sum_{x,y=1}^N a_xb_y |U_{xy}|^2} \eta_N(\mathrm{d}U).$

Problem 5.3. Prove that indeed $K_N(A,B)=K_N(B,A)$ and $|K_N(A,B)|\leq 1.$ Moreover, show that $K_N(A,B)$ is invariant under independent permutations of the coordinates of $A,B \in \mathbb{R}^N.$

If $K_N(A,B)$ is the quantum Fourier kernel, then

$\psi_{B_N}(A) = \mathbf{E}[K_N(A,B_N)] = \int_{\mathbb{R}^N} K_N(A,B) \sigma_N(\mathrm{d}B)$

deserves to be called the quantum characteristic function of random vector $B_N$ , or the quantum Fourier transform of the probability measure $\sigma_N.$ What we have shown in this lecture is that for any unitarily invariant random Hermitian matrix $X_N,$ we have

$\varphi_{X_N}(A) = \psi_{B_N}(A), \quad A \in \mathbb{R}^N,$

where $B_N$ is any $N$ -dimensional random vector whose components are eigenvalues of $X_N$ (this is what Theorem 5.2 means). We can also state the above as

$\varphi_{D_N}(A) = \psi_{B_N}(A), \quad A \in \mathbb{R}^N,$

where $D_N$ is the diagonal of the random matrix $X_N$ .

The conclusion to be drawn from all of this is that figuring out how to analyze the eigenvalues of a unitarily invariant random Hermitian matrix $X_N$ given its characteristic function $\varphi_{X_N}$ is exactly the same thing as figuring out how to analyze an arbitrary random real vector $B_N$ given its quantum characteristic function $\psi_{B_N}.$

Before telling you how we will do this, let me tell you how we won’t. The main reason the Hoffman-Weilandt theorem was presented in this lecture is that the proof makes you think about maximizing the function

$g(U) = \sum_{x,y=1}^N a_xb_y|U_{xy}|^2$

over unitary matrices $U.$ The action $g(U)$ is exactly what appears in the exponent of the quantum Fourier kernel:

$K_N(A,B) = \int_{\mathbb{U}_N} e^{i g(U)} \mathrm{d}U.$

(I am going to stop writing the Haar measure $\eta_N$ explicitly in Haar integrals, so just $\mathrm{d}U$ rather than $\eta_N(\mathrm{d}U)$ ). Now, the method of stationary phase predicts that $K_N(A,B)$ should be approximated by contributions from the local maxima of the action, which means that this integral should localize to a sum over permutations. This turns out to be exactly correct, not just a good approximation, and the reasons for this are rooted in symplectic geometry. The end result is the following determinantal formula for the quantum Fourier kernel.

Theorem 5.4 (HCIZ Formula). For any $A,B \in \mathbb{R}^N$ with no repeated coordinates we have

$K_N(A,B) = \frac{1!2! \dots (N-1)!}{i^{N \choose 2}}\frac{\det [ e^{ia_xb_y}]}{\det[a_x^{N-y}]\det[b_x^{N-y}]}.$

This is a very interesting formula which makes manifest all the symmetries of the quantum Fourier kernel claimed in Problem 5.3 (but, you should solve that problem without using the determinantal formula). It is also psychologically satisfying in that it shows exactly how the quantum Fourier kernel is built out of classical one-dimensional Fourier kernels. However, it is not really good for much else. We will explain this further in the coming lectures. But first we will adapt all of the above to random rectangular matrices.

Math 289A: Lecture 4

We have defined the characteristic function of a random Hermitian matrix $X$ according to the usual recipe for random variables taking values in a Euclidean space: it is the expectation

$\varphi_{X}(T) = \mathbf{E}\left[e^{i\langle T,X \rangle}\right],$

where the argument $T$ ranges over the real vector space

$\mathbb{H}_N = \{X \in \mathbb{C}^{N \times N} \colon X^*=X\},$

which carries the Hilbert-Schmidt scalar product

$\langle T,X \rangle = \mathrm{Tr}\, TX.$

Equivalently,

$\varphi_{X}(T) = \int\limits_{\mathbb{H}_N} e^{i \mathrm{Tr}\, TX}\mu_X(\mathrm{d}X),$

where $\mu_X$ is the distribution of $X$ in $\mathbb{H}$ . With this definition in hand, we can consider special classes of random Hermitian matrices carved out by clauses of the form

“A random Hermitian matrix $X$ is said to be (descriptor) if its characteristic function satisfies (property).”

A natural construction of this form arises from the Spectral Theorem. The set

$\mathbb{U}_N=\{U \in \mathbb{C}^{N \times N} \colon UU^*=UU^*=I\}$

of unitary matrices is a group under matrix multiplication, called the unitary group of rank $N.$ The group $\mathbb{U}_N$ acts on the Euclidean space $\mathbb{H}_N$ by conjugation, which is a group homomorphism

$\Phi \colon \mathbb{U}_N \longrightarrow \mathrm{Aut}(\mathbb{H}_N,\langle \cdot,\cdot\rangle)$

from $\mathbb{U}$ into the orthogonal group of the Euclidean space $\mathbb{H}$ defined by

$\Phi(U)T = UTU^*, \quad U \in \mathbb{U}_N,\ T \in \mathbb{H}_N.$

Problem 4.1. Prove that $\Phi$ really is a group homomorphism from $\mathbb{U}_N$ into orthogonal transformations of Euclidean space $\mathbb{H}_N.$

One formulation of the Spectral Theorem says: the conjugation orbit

$\mathcal{O}_X = \{UXU^* \colon U \in \mathbb{U}_N\}$

of any Hermitian matrix $X \in \mathbb{H}_N$ contains a diagonal matrix $A,$ which is unique up to simultaneous permutations of its rows and columns.

Definition 4.1. A random Hermitian matrix $X$ is said to be unitarily invariant if its characteristic function $\varphi_{X}$ satisfies

$\varphi_{X}(UTU^*) = \varphi_{X}(T)$

for all $T \in \mathbb{H}_N$ and all $U \in\mathbb{U}_N.$ That is, $X$ is unitarily invariant if its characteristic function $\varphi_{X}$ is constant on each $\mathbb{U}_N$ -orbit of $\mathbb{H}_N.$

Unitary invariance is a basic symmetry with many ramifications. First of all, it leads to a massive reduction in complexity by allowing us to view the characteristic function of $X$ as a function of $A \in \mathbb{R}^N$ rather than a function of $T \in \mathbb{H}_N.$ Indeed, for any arbitrary Hermitian $T,$ the Spectral Theorem says that $UTU^*=A$ for some unitary matrix $U \in \mathbb{U}_N$ and some diagonal matrix $A \in \mathbb{H}_N.$ Unitary invariance of the characteristic function then gives

$\varphi_{X}(T) = \varphi_{X}(UTU^*) = \varphi_{X}(A).$

The diagonal Hermitian matrix

$A = \begin{bmatrix} a_1 & {} & {} \\ {} & \ddots & {} \\ {} & {} & a_N\end{bmatrix}$

can be viewed as a vector $A =(a_1,\dots,a_N) \in \mathbb{R}^N,$ so that the characteristic function of a unitarily invariant random Hermitian matrix $X$ can be viewed as a continuous function

$\varphi_{X} \colon \mathbb{R}^N \longrightarrow \mathbf{D}$

on $N$ -dimensional Euclidean space taking values in the closed unit disc $\mathbf{D} \subset \mathbb{C}.$

Problem 4.2. Prove that the characteristic function of a unitarily invariant random Hermitian matrix $X$ is a symmetric function on $\mathbb{R}^N.$

Now we discuss the probabilistic ramifications of unitary invariance, i.e. what Definition 4.2 implies about the distribution of $X.$

Theorem 4.1. The distribution of a unitarily invariant random Hermitian matrix $X$ is completely determined by the joint distribution of its diagonal matrix elements $X_{11},\dots,X_{NN}$ , which are exchangeable real random variables.

Proof: For $A=\mathrm{diag}(a_1,\dots,a_N)$ real diagonal, we have

$\mathrm{Tr}\, AX = a_1X_{11} + \dots + a_NX_{NN}.$

Consequently, we have

$\varphi_{X}(A) = \mathbb{E}[e^{i\mathrm{Tr}\, AX}] = \mathbb{E}[e^{i(a_1X_{11} + \dots + a_NX_{NN})}],$

which is exactly the characteristic function of the real random vector

$D = (X_{11},\dots,X_{NN}).$

Thus, the characteristic function $\varphi_X(A)=\varphi_D(A).$ The exchangeability of $X_{11},\dots,X_{11}$ follows from Problem 4.1.

-QED

It is important to note that exchangeable random variables are identically distributed, but not necessarily independent.

Problem 4.3. Prove that the diagonal matrix elements of a unitarily invariant random Hermitian matrix $X$ are independent if and only if the distribution $\mu_{X}$ is a Gaussian measure on $\mathbb{H}_N.$

Now we characterize unitary invariance as a feature of the distribution of a random Hermitian matrix.

Theorem 4.2. A random Hermitian matrix $X$ is unitarily invariant if and only if $X$ and $UX_NU^*$ have the same distribution for every $U \in \mathbb{U}_N.$

Proof: Note that for any random Hermitian matrix $X$ and any deterministic unitary matrix $U \in \mathbb{U}_N$ we have

$\varphi_{UXU^*}(T) =\varphi_{X}(U^*TU),\quad T \in \mathbb{H}_N,$

by cyclic invariance of the trace. If $X$ is unitarily invariant, this becomes

$\varphi_{UXU^*}(T) =\varphi_{X}(T), \quad T \in \mathbb{H}_N,$

which is equivalent to equidistribution of $X$ and $UX_NU^*.$ Conversely, if $UXU^*$ and $X$ have the same distribution then their characteristic functions are equal.

-QED

Theorem 4.2 is quite important for the following reason. Define a random linear operator acting on $\mathbb{C}^N$ by

$L_Xv = Xv, \quad v \in \mathbb{C}^N.$

The matrix of $L_{X}$ in the standard basis $e_1,\dots,e_N$ of $\mathbb{C}^N$ is $X.$ The matrix of $L_{X}$ in some other orthonormal basis $f_1,\dots,f_N$ is the $UXU^*$ , where $U$ is the matrix of the linear transformation defined by $e_i \mapsto f_i.$ Unitary invariance says that $UXU^*$ has the same distribution as $X$ – the random matrix of the random operator $L_{X}$ has the same law for any choice of orthonormal basis in the Hilbert space $\mathbb{C}^N.$ In this sense, unitarily invariant random Hermitian matrices are precisely those random matrices which correspond to canonically defined random Hermitian operators on finite-dimensional Hilbert space.

Math 289A: Lecture 3

Lecture slides: https://share.goodnotes.com/s/Rhz5cq25WnLksLyCWa1ML5

Problem 3.1. True or false: the set of unistochastic matrices is a connected subset of the Birkhoff polytope.

Math 289A: Lecture 2

Lecture slides: https://drive.google.com/file/d/1zfLtzPlx32o07LNvx6pvZXKRxOXDvpVL/view

Math 289A: Lecture 1

Let $\mathbb{L}$ be a Euclidean space and $\mathfrak{B}$ its Borel sigma algebra.

Definition 1.1. A random variable taking values in $\mathbb{L}$ is a measurable function $X$ from a probability space $(\Omega,\mathfrak{F},\mathbf{P})$ into $\mathbb{L}.$

Every random variable leads a double life: it is both a function into $\mathbb{L}$ and a measure on $\mathbb{L}.$

Definition 1.2. The distribution of $X$ is the probability measure on Borel sets $\mathsf{S} \subseteq \mathbb{L}$ defined by

$\mu_X(\mathsf{S}) = \mathbf{P}\left(\{\omega \in \Omega \colon X(\omega) \in \mathsf{S}\}\right).$

Strictly speaking, it is not correct to conflate $X$ with its distribution $\mu_X$ , since one could have a second random variable $Y$ which is distinct from $X$ but has the same distribution – when this happens we say that $X$ and $Y$ are “equal in distribution”, or “equal in law.” I heard the “double life” descriptor in a probability course taught by David Steinsaltz, and I think it is helpful provided one keeps the above caveat in mind. In fact I will go one step further and say that $X$ leads a triple life – it is also a complex-valued function on $\mathbb{L}.$

Definition 1.2. The characteristic function of $X$ is defined by the expectation

$\varphi_{X}(T) = \mathbf{E}\left[ e^{i \langle T,X\rangle} \right] = \int\limits_{\mathbb{L}} e^{i \langle T,X \rangle} \mu_{X}(\mathrm{d}X), \quad T \in \mathbb{L}.$

That is, the characteristic function of a random variable is the Fourier transform of its distribution.

Problem 1.1. Prove that the characteristic function of a random variable is an absolutely continuous function from $\mathbb{L}$ into the closed unit disc in $\mathbb{C}.$

The characteristic function of $X$ faithfully encodes its distribution: if $Y$ is another random variable, then $X$ and $Y$ are equal in law if and only if they have the same characteristic function. This is a famous result in probability theory – a proof can be found in virtually any textbook on the subject. What makes characteristic functions so useful is that they transform probability into analysis, specifically harmonic analysis, which allows us to apply analytic methods to probabilistic questions. In particular, the famous Levy Continuity Theorem characterizes convergence in distribution for sequences of random variables in terms of the corresponding sequence of characteristic functions. This provides an efficient approach to the classical limit theorems of probability theory, the Law of Large Numbers and the Central Limit Theorem. Again, you will find an exposition of this approach in any standard probability text.

Random Matrix Theory is one of the most active areas of research in contemporary probability theory. It is a beautiful blend of algebra and probability which enjoys striking connections with many other fields, including combinatorics, number theory, physics, statistics, and something called “data science.” Strangely, RMT makes no use of characteristic functions – I am not aware of a single textbook on random matrices which even defines the characteristic function of a random matrix, despite the fact that this is simply a special case of the above construction.

To be concrete, let us take $\mathbb{H}$ to be the real vector space of $N \times N$ Hermitian matrices equipped with the scalar product

$\langle X,Y \rangle = \mathrm{Tr}\, XY,$

where $\mathrm{Tr}$ denotes the standard matrix trace.

Problem 1.2. Prove that the above really does define a scalar product on the space of Hermitian matrices, and write down an orthonormal basis.

Everything we have said so far about random variables taking values in a general Euclidean space $\mathbb{L}$ is perfectly valid in the special case where $\mathbb{L}=\mathbb{H}.$ Thus, there is no definitional obstruction to analyzing a random variable $X$ taking values in $\mathbb{H}$ via its characteristic function $\varphi_X.$ But there is a conceptual issue: random matrices are random variables which lead not just a triple life, but a quadruple life. More precisely, a random Hermitian matrix $X$ has associated to it not just a measure $\mu_X$ and a function $\varphi_X,$ but also an operator $L_X$ defined by matrix multiplication

$L_X(v) = Xv, \quad v \in \mathbb{C}^N.$

The random operator $L_X$ is a geometric object, a random linear transformation of $\mathbb{C}^N,$ and as such has geometric invariants such as eigenvalues and eigenvectors.

The statistical behavior of the geometric invariants of $L_X$ is encoded in the characteristic function $\varphi_X$ of its matrix $X$ . However, the characteristic function “sees” $X$ as a random vector in the $N^2$ -dimensional Euclidean space $\mathbb{H},$ not as a random operator on the $N$ -dimensional Hilbert space $\mathbb{C}^N,$ and the question of how to extract geometric information from $\varphi_X$ does not have an obvious or easy answer. Because of this, researchers in random matrix theory long ago abandoned characteristic functions. The subject has developed its own specific tools which have been very successful but have also distanced it from other parts of probability theory.

In recent years the question of whether a Fourier-analytic approach to random matrices might be possible after all has begun to be reconsidered. I do not claim to have a satisfactory answer to this question, but we will explore it in this topics course and perhaps see the beginnings of an answer. To get the most out of this endeavor, it would be best to absorb the standard approach to random matrix theory at the same time. The course notes by Todd Kemp and Terence Tao are both excellent resources which are freely available online.

Math 202B: Lecture 4

In this lecture we describe the lattice of subalgebras of $\mathcal{F}(X).$ Our main tool will be a discrete version of the Stone-Weierstrass theorem. Let $\mathcal{A}$ be a subalgebra of $\mathcal{F}(X)$ . We say that $\mathcal{A}$ separates $X$ if, for any distinct points $x\neq y$ in $X$ , there is a function $A \in \mathcal{A}$ such that $A(x) \neq A(y)$ . It turns out that there is only one separating subalgebra in $\mathcal{F}(X).$

Theorem 4.1. A subalgebra $\mathcal{A}$ of $\mathcal{F}(X)$ separates $X$ if and only if $\mathcal{A}=\mathcal{F}(X)$ .

Proof: One direction is clear: if $\mathcal{A}=\mathcal{F}(X)$ , then it contains all the elementary functions. If $x,y \in X$ are distinct, then $E_x(x)=1\neq 0=E_x(y).$

Now suppose we are given a separating subalgebra $\mathcal{A}$ of $\mathcal{F}(X)$ . Let $x \in X$ be an arbitrary point. By hypothesis, for each $y \in X\backslash\{x\}$ there is a function $A_{xy} \in \mathcal{A}$ such that $A_{xy}(x) \neq A_{xy}(y)$ , and by centering and scaling we can assume without loss in generality that

$A_{xy}(x)=1 \quad\text{and}\quad A_{xy}(y)=0.$

Now observe that

$E_x = \prod\limits_{y \in X\backslash\{x\}} A_{xy}.$

Since each of the factors $A_{xy}$ in this product belongs to $\mathcal{A}$ and $\mathcal{A}$ is closed under products, we obtain $E_x \in \mathcal{A}$ . Since $x$ was arbitrary, $\mathcal{A}$ contains all the elementary functions, and since $\mathcal{A}$ is closed under linear combinations it is equal to $\mathcal{F}(X)$ .

-QED

We are now ready to classify the subalgebras of $\mathcal{F}(X)$ . This is done by explicitly describing a family of subalgebras, and then using Theorem 2.3 to prove that there are no others apart from these.

Definition 4.1. A partition of $X$ is a set $\mathbf{P}$ of disjoint nonempty subsets of $X$ whose union is $X.$ Each $P \in \mathbf{P}$ is called a block of $\mathbf{P}.$

The set $\Pi(X)$ of all partitions of $X$ has a natural partial order called refinement order: we declare $\mathbf{P} \leq \mathbf{Q}$ if every block of $\mathbf{P}$ is a union of blocks of $\mathbf{Q}$ . When $\mathbf{P} \leq \mathbf{Q}$ we say that $\mathbf{P}$ is coarser than $\mathbf{Q}$ , or equivalently that $\mathbf{Q}$ is finer than $\mathbf{P}.$ In fact, $\Pi(X)$ is a lattice, and you way wish to think about its greatest lower bound and least upper bound operations, though we do not need these for our purposes. Below is the Hasse diagram of $\Pi(X)$ for $X$ a set of four points.

Now observe that associated to every partition $\mathbf{P}$ of $X$ is a subalgebra $\mathcal{A}(\mathbf{P})$ of $\mathcal{F}(X)$ , namely the set of functions on $X$ which are constant on the blocks of $\mathbf{P}.$

Problem 4.1. Prove that $\mathcal{A}(\mathbf{P})$ is a subalgebra of $\mathcal{F}(X)$ . Furthermore, show that $\mathcal{A}(\mathbf{P})$ is isomorphic to $\mathcal{F}(\mathbf{P})$ .

We are now ready for the classification of subalgebras of the function algebra $\mathcal{F}(X)$ .

Theorem 4.2. If $\mathcal{A}$ is a subalgebra of $\mathcal{F}(X),$ then $\mathcal{A}=\mathcal{A}(\mathbf{P})$ for some partition $\mathbf{P}$ of $X$ . In particular, every subalgebra of a function algebra is isomorphic to a function algebra.

Proof: The proof is by induction on the cardinality of $X$ . In the base case, $X=\{x\}$ is a singleton set, and $\mathcal{F}(X)=\mathcal{F}(\{x\})$ is a one-dimensional algebra. The unique partition of $X$ is $\mathbf{P}=\{\{x\}\},$ and $\mathcal{A}(\{\{x\}\})$ is the set of functions in $\mathcal{F}(\{x\})$ which are constant on $\{x\}$ , which is all of $\mathcal{F}(\{x\}).$

For the induction step, let $\mathcal{A} \neq \mathcal{F}(X)$ be a proper subalgebra of $\mathcal{F}(X)$ . Then, by the Stone-Weierstrass theorem, there are distinct points $x,y \in X$ such that $A(x)=A(y)$ for all $A \in \mathcal{A}$ . This means that every function in $A$ is constant on the the two-element set $\{x,y\}$ . Thus, $\mathcal{A}$ is a subalgebra of $\mathcal{A}(\mathbf{P}_{xy}),$ where $\mathbf{P}_{xy}$ is the partition of $X$ with one block $\{x,y\}$ of size two and the remaining blocks of size one. By Problem 3.2, the algebra $\mathcal{A}(\mathbf{P}_{xy})$ is isomorphic $\mathcal{F}(\mathbf{P}_{xy})$ , and $|\mathbf{P}_{xy}|=|X|-1.$ Thus, by the induction hypothesis, $\mathcal{A}=\mathcal{A}(\mathbf{Q})$ for $\mathbf{Q}$ a partition of $\mathbf{P}_{xy}.$

-QED

Problem 4.2. Prove that the number of non-isomorphic subalgebras of $\mathcal{F}(X)$ is $|X|$ .

Math 202B: Lecture 7

We have previously met the function algebra $\mathcal{F}(X)$ of a finite set and the linear algebra $\mathcal{L}(V)$ of a finite-dimensional Hilbert space. In this lecture, we introduce a third family of algebras associated to finite groups. In Math 202B, all groups are finite, so going forward “group” always means “finite group.”

Let $G$ be a group with group law written multiplicatively: for any elements $g,h \in G$ , their product is $gh \in G$ . Since $G$ is a finite set, we can form the algebra $\mathcal{F}(G)$ of functions $A \colon G \to \mathbb{C}$ . As explained in Lecture 3, this function algebra has a natural basis consisting of the elementary functions

$E_g(h) = \delta_{gh},\quad g,h \in G$

which are orthogonal projections in $\mathcal{F}(G)$ . However, the function algebra $\mathcal{F}(G)$ has nothing to do with the group structure of $G,$ so from the point of view of this construction the fact that $G$ is a group and not just a set is irrelevant.

We can use the underlying group structure to define a different algebra $\mathcal{C}(G)$ whose elements are functions $A \colon G \to \mathbb{C}$ , but whose operations differ from those of $\mathcal{F}(G)$ and are defined using the group structure of $G$ . In $\mathcal{C}(G)$ , multiplication of functions not defined pointwise, but rather by convolution: we declare

$E_gE_h = E_{gh}, \quad g,h \in G.$

Thus, the multiplication tensor of $\mathcal{C}(G)$ is not the three-dimensional identity matrix, but rather a two-dimensional object: the multiplication table of $G.$ Thus for any two functions

$A = \sum\limits_{g \in G} \alpha_g E_g \quad\text{and}\quad B=\sum\limits_{g \in G}\beta_gE_g,$

their convolution product is given by

$A*B=\sum\limits_{g,h \in G} \alpha_g\beta_h E_{gh},$

which can equivalently be written

$AB = \sum\limits_{k \in G} \left(\sum\limits_{gh=k}\alpha_g\beta_h \right)E_k,$

$AB= \sum\limits_{g \in G} \left(\sum\limits_{h \in G}\alpha_{gh^{-1}}\beta_h \right)E_g$

$AB= \sum\limits_{g \in G} \left(\sum\limits_{h \in G}A(gh^{-1})B(h) \right)E_g.$

This is very different from the product of $A$ and $B$ viewed as elements of $\mathcal{F}(G)$ , which is

$AB=\sum\limits_{g \in G} A(g)B(g)E_g.$

Similarly, instead of defining conjugation in $\mathcal{C}(G)$ using pointwise using conjugation in $\mathbb{C}$ , we define it using the the natural involution in $G$ , which is taking inverses,

$E_g^* = E_{g^{-1}}, \quad g \in G,$

and extend this antilinearly,

$A^* = \left(\sum\limits_{g \in G} \alpha_g E_g\right)^*=\sum\limits_{g \in G}\bar{\alpha}_g E_{g^{-1}} = \sum\limits_{g \in G} \bar{\alpha}_{g^{-1}}E_g.$

This group-theoretic conjugation is indeed antimultiplicative with respect to convolution,

$(E_g*E_h)^* = E_{gh}^*=E_{(gh)^{-1}}=E_{h^{-1}g^{-1}} = E_{h^{-1}}*E_{g^{-1}}=E_h^**E_g^*,$

as well as involutive,

$(E_g^*)^* = E_{g^{-1}}^*=E_{(g^{-1})^{-1}}= E_g.$

Finally, the multiplicative unit in $\mathcal{C}(G)$ is $I= E_e$ , where $e \in G$ is the group unit, as opposed to being the constant function equal to $1$ on every $g \in G$ , which is the multiplicative unit in $\mathcal{F}(G).$

Let us record the above as an official definition.

Definition 7.1. The convolution algebra (aka a group algebra) of a group $G$ is the vector space

$\mathcal{C}(G) = \{A \colon G \to \mathbb{C}\}$

of complex-valued functions on $G$ with multiplication defined by

$[AB](g) = \sum\limits_{h \in G}A(gh^{-1})B(h)$

and conjugation defined by

$[A^*](g) = \overline{A(g^{-1})}.$

In summary, $\mathcal{F}(G)$ and $\mathcal{C}(G)$ are exactly the same as vector spaces, but they are different as algebras. In particular, the elementary functions $\{E_g \colon g \in G\}$ are a basis of $\mathcal{F}(G)$ consisting of orthogonal projections, but in $\mathcal{C}(G)$ they form a basis consisting of unitary elements.

Problem 7.1. Prove that if $G,H$ are isomorphic groups then their convolution algebras $\mathcal{C}(G)$ and $\mathcal{C}(H)$ are isomorphic algebras (the converse is false, bonus points if you give a counterexample). Also show that $\mathcal{C}(G)$ is commutative if and only if $G$ is abelian.

To further highlight the difference between $\mathcal{C}(G)$ and $\mathcal{F}(G)$ , let us consider their selfadjoint elements. To say that a function $A \colon G \to \mathbb{C}$ is selfadjoint as an element of $\mathcal{F}(G)$ simply means that it is real-valued:

$A^*(g) = A(g) \iff \overline{A(g)} = A(g).$

However, $A$ being selfadjoint in $\mathcal{C}(G)$ means something else.

Problem 7.2. Prove that in $\mathcal{C}(G)$ we have

$A^*(g)=A(g) \iff \overline{A(g^{-1}})=A(g).$

To further compare and contrast the function algebra $\mathcal{F}(G)$ and the convolution algebra $\mathcal{C}(G)$ , let us consider their subalgebras. From Lecture 3 we know that the lattice of subalgebras of $\mathcal{F}(G)$ is isomorphic to the lattice of partitions of $G$ , which has nothing to do with the group structure on $G$ . On the other hand, we have a subalgebra of $\mathcal{C}(G)$ associated to every subgroup of $H$ of $G$ , defined by

$\mathcal{A}(H) = \{A \in \mathcal{C}(g) \colon A(g) = 0 \text{ unless }g \in H\}$ .

Problem 7.3. Prove that $\mathcal{A}(H)$ is a subalgebra of $\mathcal{C}(G)$ , and moreover that $\mathcal{A}(H)$ is isomorphic to $\mathcal{C}(H).$

This raises the question of whether subalgebras of $\mathcal{C}(G)$ are in bijection with subgroups of $G$ , i.e. whether the lattice of subalgebras of $\mathcal{C}(G)$ is isomorphic to the lattice of subgroups of $G$ , which would be analogous to the situation with function algebras. This is not true in general. Consider the following element of $\mathcal{C}(G)$ ,

$P = \frac{1}{|G|} \sum_{g \in G} E_g,$

which is the average of the elementary functions. Equivalently, $P\colon G \to \mathbb{C}$ is the constant function

$P(g) = \frac{1}{|G|}, \quad g \in G.$

Then $P$ is selfadjoint (make sure you understand why), and also

$P^2 = \frac{1}{|G|^2} \sum_{h \in G} \sum_{g \in G} E_gE_h=\frac{1}{|G|^2} \sum_{h \in G} \sum_{g \in G} E_{gh}.$

Now, the internal sum is just

$\sum_{g \in G} E_{gh} = \sum_{g \in G} E_g,$

since multiplying each element $g \in G$ by a fixed group element $h \in G$ just permutes the points of the group (make sure you understand why). Therefore, $P^2=P$ and we conclude that the average of all elementary functions $E_g$ is a projection in $\mathcal{C}(G)$ . Now consider the subalgebra of $\mathcal{C}(G)$ generated by the the multiplicative identity $I=E_e$ and $P$ ,

$\mathcal{A}=\mathrm{alg}\{I,P\} = \{\alpha I + \beta P \colon \alpha,\beta \in \mathbb{C}\}$ .

Since $I,P$ are linearly independent (make sure you understand why), we have located a two-dimensional subalgebra inside $\mathcal{C}(G)$ , for any group $G$ . If $G$ is a group of odd order, Lagrange’s theorem tells us that any subgroup $H \leq G$ must also have odd order, and consequently the subalgebra $\mathcal{A}=\mathrm{alt}\{I,P\}$ cannot be the algebra of functions vanishing outside some subgroup $H$ of $G$ , for then $\mathcal{A}$ would be isomorphic to $\mathcal{C}(H)$ and its dimensions would be the cardinality of $H$ , which is impossible since $|H|$ cannot be even.

Math 202B: Lecture 24

In Lecture 23 we worked out the irreducible representations of the symmetric group $S_3$ and computed their characters. Proceeding by bare hands becomes difficult quickly since the cardinality of $S_n$ grows very rapidly (indeed, superexponentially) with $n$ .

We can at least answer one natural question, which encouragingly was asked by Yunseong Jung in Lecture 23: is the standard representation of $S_n$ irreducible for all $n$ ? If so, we will have three irreducible unitary representations of $S_n$ , namely the trivial and alternating ones, which are one-dimensional, and the standard representation, which is $n-1$ dimensional. This isn’t much – the number of irreducible representations of $S_n$ is the number of partitions of $n,$ which according to the Hardy-Ramanujan formula is asymptotically

$\frac{1}{4\sqrt{3}n}\exp \pi\sqrt{\frac{2}{3}n}$

for large $n$ – but it’s better than nothing.

Start with the permutation representation $(V,\varphi)$ of $S_n$ , so $V$ is a Hilbert space with orthonormal basis $\{e_x \colon x \in X\}$ , $X=\{1,\dots,n\},$ and $\varphi \colon S_n \to U(\mathcal{L}(V))$ is the group homomorphism defined by

$\varphi(g)e_x = e_{g(x)}, \quad g \in S_n,\ x\in X.$

The character of the permutation representation of $S_n$ is

$\chi^V(g) = \mathrm{Tr} \varphi(g) = \sum\limits_{x\in X} \langle e_x, \varphi(g)e_x \rangle = \sum\limits_{x \in X} \langle e_x,e_{g(x)}\rangle,$

so $\chi^V(g)$ is the number of fixed points (i.e. one-cycles) of the permutation $g.$ Therefore,

$\langle \chi^V,\chi^V\rangle = \sum\limits_{g \in S_n} |\mathrm{Fix}(g)|^2,$

where $\mathrm{Fix}(g) \subseteq X$ is the set of fixed points of $g \in S_n$ . To understand this sum, let us begin with the simpler version without the squares. By Burnside’s Lemma, which is a consequence of the orbit-stabilizer theorem, we have

$\frac{1}{|S_n|} \sum\limits_{g \in S_n} |\mathrm{Fix}(g)| = \left|X/S_n\right|,$

where $X/S_n$ is the number of orbits of $S_n$ acting on $X.$ Obviously, the number of orbits of $S_n$ acting on $X=\{1,\dots,n\}$ is one, i.e. $S_n$ acts transitively on $X,$ so

$\frac{1}{|S_n|} \sum\limits_{g \in S_n} |\mathrm{Fix}(g)| = \left|X/S_n\right|,$

which can be interpreted probabilistically as saying that the expected number of fixed points in a uniformly random sample from $S_n$ is one.

We can use a version of the same argument to evaluate $\langle \chi^V,\chi^V\rangle.$ To get the exponent of $2$ into the equation, let $S_n$ act on $X\times X$ by $g\cdot (x,y)=(g(x),g(y)).$ Then, we have

$(g(x),g(y))=(x,y) \iff g(x) =x \text{ and }g(y)=y,$

so that points of $X\times X$ which are fixed by a given $g \in S_n$ are in bijection with pairs of points in $X$ which are fixed by $g$ . Applying Burnside’s Lemma we thus have

$\langle \chi^V,\chi^V\rangle = \sum\limits_{g \in S_n} |\mathrm{Fix}(g)|^2=\left|(X \times X)/S_n\right|.$

It is not too difficult to determine the number of orbits of $S_n$ acting on $X \times X.$ Indeed, consider any point $(x,y) \in X \times X.$ Either $x=y$ or $x \neq y$ . In the first case, the orbit of $(x,y)$ under $S_n$ consists of all pairs of points with equal coordinates, in the second case it is all pairs of points with distinct coordinates; these two mutually exclusive cases are the only possibilities. We thus have

$\frac{1}{|S_n|}\sum\limits_{g \in S_n} |\mathrm{Fix}(g)|^2=2,$

which says that the second moment of the random variable $Z$ which gives the number of fixed points in a uniformly random permutation is equal to two. Since $\mathbb{E}[Z]=1$ and $\mathbb{E}[Z^2]=2$ you might be tempted to assume that the $k$ th moment of $Z$ is $\mathbb{E}[Z^k]=k,$ but this is wrong and the correct answer is quite a bit more interesting.

For our purposes, all we need is

$\langle \chi^V,\chi^V\rangle =2|S_n|.$

Let $A \in \mathcal{C}(S_n)$ be the random variable defined by

$A(g) = |\mathrm{Fix}(g)|^2.$

We conclude from the above that the character $\chi^V$ of the permutation representation of $S_n$ satisfies

$\langle \chi,\chi \rangle = 2|S_n|.$

Now let $W$ be the one-dimensional subspace of $V$ spanned by $e_1+\dots+e_n,$ which is an irreducible representation of $S_n$ , and let $W^\perp$ be its orthogonal complement, which is the standard representation of $S_n$ . Since $V=W \oplus W^\perp,$ we have $\chi^V=\chi^W+\chi^{W^\perp},$ and therefore

$\langle \chi^V,\chi^V\rangle = \langle \chi^W+\chi^{W^\perp},\chi^W+\chi^{W^\perp}\rangle = \langle \chi^W,\chi^W\rangle + \langle \chi^{W^\perp},\chi^{W^\perp}\rangle,$

where we have used character orthogonality to claim

$\langle \chi^W\chi^{W^\perp}\rangle = 0$

on the grounds that $W$ and $W^\perp$ are non-isomorphic representations of $S_n$ for $n>1.$ Indeed, $W$ is the trivial representation of $S_n$ , in which every permutation acts as the identity on this one-dimensional space. The standard representation $W^\perp$ is the alternating representation of $S_n$ if $n=2,$ and for $n>2$ its dimension is strictly larger than one.

To finish the argument, write

$\langle \chi^W,\chi^W\rangle = \langle \chi^V,\chi^V\rangle - \langle \chi^{W^\perp},\chi^{W^\perp}\rangle=2|S_n|-|S_n| = |S_n|,$

where the fact that $\langle \chi^{W^\perp},\chi^{W^\perp}\rangle=|S_n|$ follows from its irreducibility. Likewise, since $\langle \chi^W,\chi^W\rangle =|S_n|,$ the standard representation of the symmetric group is irreducible.

Thankfully, the basic idea in the representation theory of the symmetric groups is very simple: $S_{n-1}$ is a subgroup of $S_n$ (more precisely, $S_{n-1}$ is isomorphic to the subgroup of $S_n$ consisting of all permutations of $1,2, \dots ,n$ that have $n$ as a fixed point). Thus we have an infinite sequence of nested groups

$S_1 \subset S_2 \subset S_3 \subset \dots,$

or equivalently an infinite sequence of nested algebras

$\mathcal{C}(S_1) \subset \mathcal{C}(S_2) \subset \mathcal{C}(S_3) \subset \dots.$

The strategy is therefore to analyze representations of $S_n$ inductively, by understanding how the unitary representations of $S_n$ is related to those of $S_{n-1}.$

Let $\Lambda_n$ be a set indexing isomorphism classes of irreducible unitary representations of $S_n,$ or equivalently irreducible linear representations of its convolution algebra $\mathcal{C}(S_n).$ For each $\lambda \in \Lambda_n,$ let $(V^\lambda,\Phi^\lambda)$ be a representative of the corresponding isomorphism class. We know $\Lambda_n$ concretely: it is the set of integer partitions of the number $n$ , which also index conjugacy classes in $S_n.$

Since $(V^\lambda,\Phi^\lambda)$ is irreducible, the image of $\mathcal{C}(S_n)$ in $\mathcal{L}(V^\lambda)$ under $\Phi^\lambda$ is all of $\mathcal{L}(V^\lambda),$ by Burnside’s theorem. On the other hand, viewing $S_{n-1}$ as a subgroup of $S_n$ and hence $\mathcal{C}(S_{n-1})$ as a subalgebra of $\mathcal{C}(S_n),$ the image of $\mathcal{C}(S_{n-1})$ in $\mathcal{L}(V^\lambda)$ is not necessarily all of $\mathcal{L}(V^\lambda),$ meaning that $V^\lambda$ is a unitary representation of $S_{n-1},$ but not necessarily an irreducible one. So viewed as a representation of $S_{n-1},$ there is an isotypic decomposition

$V^\lambda = \bigoplus\limits_{\mu \in \Lambda_{n-1}} \langle V^\mu,V^\lambda\rangle V^\mu,$

where the direct sum is over the set $\Lambda_{n-1}$ of partitions of $n-1,$ and $\langle V^\mu,V^\lambda$ is the multiplicity of $V^\mu$ in $V^\lambda$ viewed as a representation of $S_{n-1}.$ The main theorem in the representation theory of the symmetric groups is a strikingly simple description of this isotypic decomposition, which we discuss in Lecture 25.