Math 202C: Lecture 5

*** Problems in this Lecture due March 12 at 23:59 ***

Let

$\mathrm{Com}_n = \{(\alpha_1,\dots,\alpha_n) \in \mathbb{Z}^n \colon \alpha_i \geq 0\}$

be the set of nonnegative integer vectors with $n$ components. Elements $\alpha$ of $\mathrm{Com}_n$ are referred to as weak $n$ -part compositions, where “weak” means that some coordinates may be zero. Let

$\mathrm{Com}_n^d=\{\alpha \in \mathrm{Com}_n \colon \alpha_1+\dots +\alpha_n=d\}.$

Elements of $\mathrm{Com}_n^d$ are called weak $n$ -part compositions of $d.$ Let $\mathcal{P}_n$ be the Hilbert space with orthonormal basis

$|\alpha\rangle = |\alpha_1\dots\alpha_n\rangle,\quad \alpha \in \mathrm{Com}_n.$

That is, $\mathcal{P}_n$ is the space of complex-valued functions on weak $n$ -part compositions which vanish at all but finitely many points. A general vector in $\mathcal{P}_n$ thus has the form

$|v\rangle = \sum\limits_{\alpha \in \mathrm{Com}_n} c_\alpha |\alpha\rangle,$

where all but finitely many of the coefficients $c_\alpha \in \mathbb{C}$ are zero. Note that $\mathcal{P}_n$ is an infinite-dimensional Hilbert space, and recall that our definition of Hilbert space does not require completeness. We have an orthogonal direct sum decomposition

$\mathcal{P}_n = \bigoplus\limits_{d=0}^\infty \mathcal{P}_n^d,$

where

$\mathcal{P}_n^d = \mathrm{span}\{|\alpha\rangle \colon \alpha \in \mathrm{Com}_n^d\}.$

Problem 5.1. Prove that $\mathcal{P}_n^d$ is finite-dimensional, and determine its dimension.

Now define a multiplication in $\mathcal{P}_n$ by bilinearly extending the rule

$|\alpha\rangle|\beta\rangle = |\alpha+\beta\rangle.$

Furthermore, define a conjugation in $\mathcal{P}_n$ by antilinearly extending the rule

$|\alpha\rangle^*=|\alpha\rangle.$

Then, $\mathcal{P}_n$ is an infinite-dimensional commutative algebra which you likely know by another name: the algebra of polynomials in $n$ (commuting, selfadjoint) variables. Indeed, if we write

$x_1=|100\dots 0\rangle\ x_2=|010\dots 0\rangle, \dots x_n=|000\dots 1\rangle,$

then a basis vector in $\mathcal{P}_n$ becomes

$|\alpha\rangle = x_1^{\alpha_1} \dots x_n^{\alpha_n},$

and a general vector in $\mathcal{P}_n$ becomes

$|v\rangle = \sum\limits_{\alpha} c_\alpha|\alpha\rangle = \sum\limits_{\alpha} c_\alpha x_1^{\alpha_1} \dots x_n^{\alpha_n}.$

So, if you have ever wondered what exactly a polynomial is, the above constitutes one possible answer: a polynomial is a finitely-supported complex-valued function on the set of compositions. This explains the sense in which there are “no polynomial relations” among the “variables” $x_1,\dots,x_n$ . Indeed, writing

$\sum\limits_{\alpha \in \mathrm{Com}_n} c_\alpha x_1^{\alpha_1} \dots x_n^{\alpha_n} = \sum\limits_\alpha c_\alpha |\alpha\rangle =0$

shows that this means nothing more than linear independence of the computational basis in $\mathcal{P}_n$ . Also note that $\mathcal{P}_n^d$ is the span of all monomials whose exponents add to $d$ ,

$x_1^{\alpha_1}x_2^{\alpha_2} \dots x_n^{\alpha_n}, \quad \alpha_1+\dots+\alpha_n=d.$

Polynomials $f(x_1,\dots,x_n) \in \mathcal{P}_n^d$ are said to be homogeneous of degree $d$ , and the space of these is finite-dimensional.

Since you come with a lot of software already installed, we will continue to use the familiar notation

$f(x_1,\dots,x_n) = \sum\limits_{\alpha \in \mathrm{Com}_n} c_\alpha x_1^{\alpha_1} \dots x_n^{\alpha_n}$

for vectors $|v\rangle$ in $\mathcal{P}_n = \mathbb{C}[x_1,\dots,x_n].$ This will allow us to more readily access your existing libraries, fragmented as they may be. The monomial basis of $\mathcal{P}_n$ is

$|\alpha\rangle= x_1^{\alpha_1} \dots x_n^{\alpha_n}.$

If we want to write things in a compressed way, we may use

$f(x)=\sum\limits_\alpha c_\alpha x^\alpha.$

One advantage of the classical polynomial notation is that it allows you to visualize homomorphisms from $\mathcal{P}_n$ into other algebras as “substitutions.”

Definition 5.1. An algebra homomomorphism $\Xi \colon \mathcal{P}_n \to \mathcal{A}$ is called a specialization when $\mathcal{A}$ is commutative.

Any specialization $\Xi$ is uniquely determine by the images $A_1=\Xi(x_1),\dots,A_n=\Xi(x_n)$ , since with the image of a general polynomial

$f(x_1,\dots,x_n) = \sum\limits_\alpha c_\alpha x_1^{\alpha_1} \dots x_n^{\alpha_n}$

$\Xi(f(x_1,\dots,x_n)=\sum\limits_\alpha A_1^{\alpha_1} \dots A_n^{\alpha_n} =:f(A_1,\dots,A_n).$

Conversely, given any elements $A_1,\dots,A_n$ in a commutative algebra $\mathcal{A}$ there is a unique specialization $\Xi \colon \mathbb{C}[x_1,\dots,x_n] \to \mathcal{A}$ such that $\Xi(x_1)=A_1,\dots,\Xi(x_n)=A_n.$

For example, consider the specialization $\Xi \colon \mathcal{P}_n \to \mathbb{C}$ determined by

$\Xi(x_1)=1,\ \Xi(x_2)=2,\ \dots,\ \Xi(x_n)=n.$

Then, for a general polynomial

$f(x_1,\dots,x_n) = \sum\limits_{\alpha \in \mathrm{Com}_n} c_\alpha x_1^{\alpha_1}x_2^{\alpha_2} \dots x_n^{\alpha_n}$

we have

$\Xi(f) = f(1,2,\dots,n) = \sum\limits_{\alpha \in \mathrm{Com}_n} c_\alpha 1^{\alpha_1}2^{\alpha_2} \dots n^{\alpha_n}.$

In simpler times, people were interested in finding the image of the power sum polynomial

$p_r(x_1,\dots,x_n)=x_1^r + x_2^r + \dots + x_n^r$

under the specialization $\Xi,$ which is the number

$\Xi(p_r)=p_r(1,2,\dots,n) = 1^r+2^r+ \dots+ n^r.$

A formula for this number was eventually found in terms of another family of numbers called Bernoulli numbers, which are themselves not so easy to describe. The main conceptual insight this formula provides is that $\Xi(p_r)$ admits a second description as the the image of a univariate polynomial $q_r(x)$ under the specialization $x \mapsto n$ .

In probability theory, one is concerned with specializations of $\mathcal{P}_n$ whose target $\mathcal{A}$ is the algebra of complex-valued random variables on a given probability space. In fact, the problem we want to solve in this context is the stochastic version of the above numerical problem: given $X_1,\dots,X_n \in \mathcal{A}$ , determine the distribution of

$p_r(X_1,\dots,X_n)=X_1^r+ \dots + X_n^r$

in terms of the joint distribution of $X_1,\dots,X_n$ . Probability theory provides efficient tools for doing this when the random variables $X_1,\dots,X_n$ are independent. If they are highly correlated, however, we know much less.

Problem 5.2. Determine the distribution of $p_r(X_1,\dots,X_n)$ when $X_1,\dots,X_n$ are iid Bernoulli random variables.

We can recast the content of Lecture 4 in terms of a specialization of $\mathcal{P}_n$ whose target is the Jucys-Murphy algebra, $\mathcal{J}_n$ . Recall that $\mathcal{J}_n$ is the commutative subalgebra of the convolution algebra $\mathcal{C}(S_n)$ of the symmetric group $S_n=\mathrm{Aut}\{1,\dots,n\}$ generated by

$\mathcal{Z}_1 \cup \mathcal{Z}_2 \cup \dots \cup \mathcal{Z}_n$ ,

where $\mathcal{Z}_k=Z\mathcal{C}(S_k)$ is the center of the subalgebra $\mathcal{C}(S_k)$ of $\mathcal{C}(S_n)$ consisting of functions supported on permutations which fix the points $k+1,k+2,\dots,n.$ The Jucys-Murphy specialization of $\mathcal{P}_n$ is the algebra homomorphism

$\Xi \colon \mathcal{P}_n \longrightarrow \mathcal{J}_n$

defined by

$\Xi(x_1)=|J_1\rangle,\ \Xi(x_2)=|J_2\rangle,\ \dots,\ \Xi(x_n)=|J_n\rangle,$

where

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

are the Jucys-Murphy elements in $\mathcal{C}(S_n).$ Our key result is that the metric level sets

$|L_r\rangle = \sum\limits_{\substack{\pi \in S_n \\ |\pi|=r}} |\pi\rangle, \quad 1 \leq r \leq n,$

in the symmetric group (identity-centered spheres in the all-transpositions metric) are the image of a particular family of the polynomials $e_1,\dots,e_n \in \mathcal{P}_n$ under the JM-specialization. The polynomials in question are the elementary symmetric polynomials

$e_r(x_1,\dots,x_n) = \sum\limits_{1 \leq t_1 < \dots < t_r \leq n} x_{t_1}x_{t_2} \dots x_{t_r}, \quad 1 \leq r \leq n,$

which may also be written

$e_r(x_1,\dots,x_n) = \sum\limits_{\substack{I \subseteq \{1,\dots,n\} \\ |I|=r}} \prod\limits_{i \in I}x_i.$

Our theorem from Lecture 4 (which actually goes back to Lecture 1, and seems to have been completely uninteresting to many people) is that

$|L_r \rangle = e_r(|J_1\rangle,|J_2\rangle,\dots,|J_n\rangle).$

We can also look at the image of this identity in the regular representation of $\mathcal{C}(S_n)$ , where it becomes

$L_r= e_r(J_1,J_2,\dots,J_n),$

giving us a polynomial decomposition of the metric level-set operators $L_r \in \mathrm{End}\mathcal{C}(S_n)$ on the all-transpositions Cayley graph of $S_n$ in terms of a simpler family of operators $J_t \in \mathrm{End}\mathcal{C}(S_n).$ As described in Lecture 1, the metric level set operators on any graph interpolate between the adjacency operator and the distance operator. However, the polynomial decomposition of these operators given above is a special feature of the all-transpositions Cayley graph of the symmetric group, and we will soon diagonalize the Jucys-Murphy operators $J_1,\dots,J_n \in \mathrm{End}\mathcal{C}(S_n).$

Before doing this, let us come to an understanding of the elementary symmetric polynomials, and symmetric polynomials more generally. The basic fact is that we have a natural unitary representation of $S_n$ on $\mathcal{P}_n$ , namely the group homomorphism

$\varphi \colon S_n \longrightarrow U(\mathcal{P}_n)$

from the symmetric group of $\{1,\dots,n\}$ to the unitary group of $\mathcal{P}_n$ defined by

$\varphi(\pi)|\alpha\rangle = |\alpha_{\pi(1)}\alpha_{\pi(2)} \dots \alpha_{\pi(n)}\rangle, \quad \pi \in S_n,\ \alpha \in \mathrm{Com}_n.$

Note that this is an infinite-dimensional unitary representation of the symmetric group, but that each of the finite-dimensional subspaces $\mathcal{P}_n^d$ is a finite-dimensional unitary representation of $S_n.$ In polynomial notation, we have

$\varphi(\pi)x^\alpha = x_1^{\alpha_{\pi(1)}}x_2^{\alpha_{\pi(2)}} \dots x_n^{\alpha_{\pi(n)}} = x_{\pi^{-1}(1)}^{\alpha_1}x_{\pi^{-1}(2)}^{\alpha_2} \dots x_{\pi^{-1}(n)}^{\alpha_n},$

and thus for a general polynomial

$f(x_1,\dots,x_n) = \sum\limits_{\alpha \in \mathrm{Com}_n} c_\alpha x_1^{\alpha_1}x_2^{\alpha_2} \dots x_n^{\alpha_n}$

we have

$\varphi(\pi) f(x_1,\dots,x_n) = \sum\limits_{\alpha \in \mathrm{Com}_n} c_\alpha x_{\pi^{-1}(1)}^{\alpha_1}x_{\pi^{-1}(2)}^{\alpha_2} \dots x_{\pi^{-1}(n)}^{\alpha_n}=f(x_{\pi^{-1}(1)}, \dots x_{\pi^{-1}(n)}).$

Like every unitary representation, $(\mathcal{P}_n,\varphi)$ contains a space of invariants,

$\mathcal{S}_n = \mathcal{P}_n^{S_n} = \mathbb{C}[x_1,\dots,x_n]^{S_n},$

and since $\mathcal{P}_n$ is a commutative algebra so is $\mathcal{S}_n$ . The commutative algebra $\mathcal{S}_n$ is called the algebra of symmetric polynomials in $n$ variables, and it consists precisely of those polynomials such that

$f(x_1,\dots,x_n)=f(x_{\pi(1)},\dots,x_{\pi(n)}), \quad \text{for all } \pi \in S_n.$

Let us find a basis for $\mathcal{S}_n$ . First, $S_n$ acts on $\mathrm{Com}_n$ , which is just a set and not a Hilbert space, according to

$\pi \cdot \alpha = (\alpha_{\pi(1)},\dots,\alpha_{\pi(n)}).$

This action preserves the coordinate sum of $\alpha,$ so in fact $S_n$ is acting on each of the finite sets $\mathrm{Com}_n^d,$ whose cardinality is easy to compute (Problem 4.1). However, the number of orbits into which $\mathrm{Com}_n^d$ decomposes under $S_n$ is not at all easy to compute. Let $\mathrm{Par}_n^d \subset \mathrm{Com}_n^d$ be the set of weak $n$ -part compositions of $d$ , and observe that each of these may be identified with a partition of $d$ having at most $n$ parts. The coordinates of a given composition $\alpha \in \mathrm{Com}_n^d$ can be permuted so that they become a weakly decreasing list of numbers, hence the orbits of $\mathrm{Com}_n^d$ may be indexed by the elements of $\mathrm{Par}_n^d$ and we obtain the decomposition

$\mathrm{Com}_n^d = \bigsqcup\limits_{\lambda \in \mathrm{Par}_n^d} \mathcal{O}_\lambda,$

where $\mathcal{O}_\lambda$ is the set of compositions which sort to the partition $\lambda.$ The monomial symmetric polynomials are defined by

$m_\lambda(x_1,\dots,x_n) = \sum\limits_{\alpha \in \mathcal{O}_\lambda} x^\alpha.$

Problem 5.3. Prove that the monomial symmetric polynomials form an orthogonal basis of $\mathcal{S}_n$ . Decompose the power sum symmetric polynomials $p_r(x_1,\dots,x_n)$ and elementary symmetric polynomials $e_r(x_1,\dots,x_n)$ in this basis.

The above was a first-principles construction of a basis for the space of $S_n$ -invariants in $\mathcal{P}_n$ . On the other hand, we know from Math 202B that for any unitary representation $(V,\varphi)$ of a finite group $G$ , averaging the operators $\varphi(g)$ gives the orthogonal projection $V \to V^G.$

Problem 5.4. Show that the operator $P = \frac{1}{n!}\sum_{\pi \in S_n} \varphi(\pi)$ projects each monomial in $\mathcal{P}_n$ onto an element of $\mathcal{S}_n$ that is in fact a monomial symmetric polynomial, up to an explicitly describable scalar factor.

Math 202C: Lecture 5

Like this:

Published by Jonathan Novak

2 Comments

Leave a ReplyCancel reply

Share this:

Like this:

Published by Jonathan Novak

2 Comments

Leave a ReplyCancel reply

Discover more from Jonathan Novak