Algebraic combinatorics Lecture 3

First it is useful to have the Hall inner product {\langle,\rangle} on {\Lambda}, the space of all symmetric functions in infinitely many variables. It is defined by

\displaystyle   \langle m_\mu, h_\lambda \rangle = \delta_{\mu,\lambda} \ \ \ \ \ (13)

To show it’s symmetric, we check it on the basis {\{h_\lambda\}}. Then it follows from the fact that each transition coefficient {N_{\lambda,\mu}} from {h_\lambda} to {m_\mu} is symmetric, because it counts the number of natural number valued matrices with prescribed row and column sum given by {\lambda,\mu}. Whenever two sets of basis functions {u_\lambda, v_\mu} satisfy (13), we say they are dual bases. In that case, we have

Proposition 4

\displaystyle  \prod_{i,j} (1-x_i y_j)^{-1} = \sum_\lambda u_\lambda(x) v_\lambda(y). \ \ \ \ \ (14)

The proof is somewhat opaque, but straightforward. Proof: By change of bases, we have {m_\lambda = \sum \xi_{\lambda,\rho} u_\rho}, and {h_\mu = \sum \eta_{\mu,\nu} v_\nu}, for some coefficients {\xi_{\lambda,\rho}} and {\eta_{\mu,\nu}}. We use Greek letter indices because the partitions are not totally ordered a priori. The fact that {m_\lambda} and {h_\mu} are dual translate to {\xi A \eta^T = I}, where {A_{\lambda,\mu} = \langle u_\lambda, v_\mu \rangle}. The fact {u_\lambda,v_\mu} are dual to each other is equivalent to {\xi \eta^T = I}. Now the proposition is true for {m_\lambda} and {h_\mu}, thus we have

\displaystyle  \prod \frac{1}{1-x_i y_j} = \sum_\lambda m_\lambda(x) h_\lambda(y) \\ = \sum_\lambda (\sum_\rho \xi_{\lambda,\rho} u_\rho)(\sum_\nu \eta_{\lambda,\nu} v_\nu)\\ = \sum_{\rho, \nu} (\sum_\lambda \xi_{\lambda,\rho} \eta_{\lambda,\nu}) u_\rho(x) v_\nu(y) = \sum_\rho u_\rho(x) v_\rho(y). \ \ \ \ \ (15)


Persi mentioned that it would be nice to have a more conceptual proof of the above. Luckily I found it, and will present it below: Proof: (second time) We define two integral kernels {U, V: {\mathbb R}^{\mathcal{P}_n} \times \Lambda_n \rightarrow {\mathbb R}} by, for {f \in {\mathbb R}^{\mathcal{P}_n}}, {g \in \Lambda_n}:

\displaystyle  U(f,g) = \int_{U(n)} \sum_{\lambda \vdash n} f(\lambda) u_\lambda(x) g(x) m(dx) \ \ \ \ \ (16)

If we fix an orthonormal basis {P = \{p_\lambda\}_{\lambda \vdash n}} of {\Lambda_n} under the Hall inner product, it determines an isomorphism {\phi: {\mathbb R}^{\mathcal{P}_n} \cong \Lambda_n} given by {\phi(f) = \sum_\lambda f(\lambda) p_\lambda} and {U,V} can be written in terms of {P} as a square matrix. The condition {\langle u_\lambda, v_\mu \rangle = \delta_{\lambda,\mu}} translates to {U^T V = Id_{{\mathbb R}^{\mathcal{P}_n}}}. Hence we must have {U V^T = Id_{\Lambda_n}} by uniqueness of group inverse. But {U V^T} can be represented as an integral kernel

\displaystyle  (U V^T f) (x) = \int_{y \in U(n)} k(x,y) f(y) m(dy) \ \ \ \ \ (17)

and for {U,V} coming from {h_\lambda}, {m_\mu}, {k(x,y)} is computed to be {\prod_{i,j} (1-x_i y_j)^{-1}}. So it must be the same for general dual pair {u_\lambda}, {v_\mu} as well, i.e., {k(x,y)} is the identity kernel on {(U(n), \langle,\rangle_{\rm{Hall}})}. As a consequence, we see that

\displaystyle  \int_{U(n)} \prod_{1 \le i,j \le n} \frac{1}{1-x_i y_j} f(y) = f(x) \ \ \ \ \ (18)

for all symmetric functions {f} on {n} variables. I checked this for {n=1} using Cauchy integral formula and it worked:

\displaystyle  \int_{U(1)} \frac{1}{1-xy} f(x) dx = \int_{[0,2\pi]} \frac{1}{1- e^{i\theta} y} f(e^{i\theta}) \frac{1}{2\pi} d\theta \\ = \frac{1}{2 \pi i}\oint_0 \frac{1}{1-z y} f(\bar{z}) dz = f(y) \ \ \ \ \ (19)

assuming {|y| = 1}. \Box

Using the fact that {\sum_\lambda p_\lambda(x) p_\lambda(y)/z_\lambda = \prod \frac{1}{1-x_i y_j}} , we have

Corollary 5

  1. The normalized power sum polynomials {\{\frac{p_\lambda(x)}{\sqrt{z_\lambda}}\}} forms an orthonormal basis, whose existence implies that the Hall inner product is positive definite. Thus {p_\lambda/\sqrt{z_\lambda}}‘s are self dual.
  2. The involution {\omega} is a self-adjoint isometry.

Again the second statement is checked on {p_\lambda}‘s. Secret: The Hall inner product {\langle, \rangle} actually comes from the {L^2} inner product on {U(n)}. This is perhaps as natural as it could get. Recall the set of conjugation invariant functions {H} on {U(n)}, consists of those {f \in L^2(U(n))} with {f(A B A^{-1}) = f(B)} for any {A, B \in U(n)}. They are necessarily symmetric functions of the eigenvalues of {B}, because being conjugation invariant implies they are functions of the eigenvalue vector {\vec{\lambda} = (e^{i \theta_1}, \ldots, e^{i \theta_n})} of {B} and since one can conjugate {B} by permutation matrices, {f} has to be symmetric in the components of {\vec{\lambda}} as well. A FACT to be proved later:

\displaystyle  \langle f, g\rangle_{Hall} = \langle f, g\rangle_{L^2(U(n))} = \int_{[0,2\pi]^n} f(e^{i \theta_1}, \ldots, e^{i \theta_n}) \bar{g} (e^{i \theta_1}, \ldots, e^{i \theta_n}) \frac{1}{2^n n!} \prod_{1 \le j < k \le n} | e^{i \theta_k} - e^{i \theta_j}|^2 d \theta_1 \ldots d\theta_n. \ \ \ \ \ (20)

Thus we see the joint distribution of the eigenvalues associated with the Haar distributed unitary matrix ensemble is given by the quadratic Vandermonde factor in the integrand. Quadratic because unitary ensemble corresponds to invariance parameter {\beta= 2}, so for {SO(n)} or {SP(n) \subset SU(2n)}, {\beta} will be {1} and {4} respectively, but there are other changes to the joint distribution functions as well. Next we hasten to define Schur functions combinatorially, which are quite a mouthful. For each partition {\lambda \vdash n} one associates a tableau {T_\lambda} (pl. tableaux) of shape {\lambda} (look up Wikipedia), then

Definition 6 A semi-standard Young Tableaux is an assignment of boxes of {\Gamma_\lambda} with natural numbers (repeating allowed) that are weakly increasing from left to right in each row, and strictly increasing down each column. Also define {\Gamma_{\lambda / \mu}} (pronounced Lambda minus Miu), by removing the boxes of {\Gamma_\mu} from {\Gamma_\lambda}, assuming the latter is dominated by the former. We can similar deifne semistandard Young tableaux associated with {\Gamma_{\lambda/ \mu}}. Then Schur functions indexed by {\lambda /\mu} is defined by

\displaystyle  s_{\lambda / \mu} = \sum_{T \text{ SSYT of } \lambda / \mu} x^T. \ \ \ \ \ (21)

where {x^T = \prod_i x_i^{\alpha_i}} where {\alpha_i} is the number of boxes in {\Gamma_{\lambda/ \mu}} with label {i} in {T}.


  1. {s_{\lambda / \mu} \in \Lambda} (should be totally not obvious).
  2. {\{s_\lambda\}} where {\lambda} is a partition of anything with at most n parts give all the irreducible characters of {U(n)}. The restriction on number of parts is cleraly necessary because {U(n)} only has {n} eigenvalues, hence for example if {\lambda = 1^{n+1}}, then there won’t be any feasible SSYT {T} that is admissible in the defining sum of {s_\lambda} as a function of n variables, thus it becomes the trivial character, repeating the one associated with {\emptyset}.


About aquazorcarson

math PhD at Stanford, studying probability
This entry was posted in algebraic combinatorics, Uncategorized and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s