Algebraic Combinatorics lecture 1

The class was surprisingly packed, with many familiar faces. Persi went right into the course outline. He said he will cover Stanley Enumerative Combinatorics volume II Ch 7 (maybe up to ch 7).

The central object is of course the space of symmetric functions ${\Lambda_k^n = \mathbb{Q}[x_1, \ldots, x_k]^{S_k}}$ where the superscript denotes ${S_k}$ invariant subspace. He introduced briefly several bases of this vector space: power sum ${p_\lambda}$, elementary ${p_\lambda}$, monomial ${m_\lambda}$, homogeneous ${h_\lambda}$, and Schur functions ${s_\lambda}$, all of which are indexed by partitions of some positive integer. The change of basis coefficients between one family and another will encode much combinatorial information. For instance if ${s_\lambda = \sum_\mu \chi_\mu^\lambda p_\mu}$, then the ${\chi_\mu^\lambda}$ is the character of ${S_n}$ indexed by ${\mu}$ evaluated at the conjugacy class ${\lambda}$.

Something I wasn’t aware of is that the Schur polynomials ${s_\lambda}$ themselves are characters are the unitary group ${U(n)}$, given as following:

$\displaystyle s_\lambda(m) = s_\lambda( e^{i\theta_1}, \ldots, e^{i \theta_k}) \ \ \ \ \ (1)$

where ${\theta_i}$‘s are the eigen-angles of ${m \in U(n)}$. This allows one to compute the following type of integral

$\displaystyle \int_{U(k)} \rm{Tr} (m^a) \bar{\rm{Tr}(m^b)} dm \ \ \ \ \ (2)$

because the trace can be seen as a symmetric polynomial of the eigenvalues, namely the simple power sum polynomials ${p_k = \sum_i x_i^k}$, which can be expressed in terms of the Schur polynomials by a change of basis. And since Schur polynomials are orthonormal with respect to Haar measure, one gets the integral above equals ${\delta_{ab} \Gamma(a)}$. This is written in Persi’s paper ” Patterns on Eigenvalues” on Bulletin of AMS. Other topics he will cover are

1. Hall inner product, which I am not if is the same as the defining inner product for Jack polynomials (maybe only for Hall-Littlewood polynomials).
2. Schur functions and RSK algorithm, which he says associates a permutation with two partitions (or Young Tableaux), which do have the same cardinality.
3. Classical definition of Schur functions by Jacobi
4. Character theory of ${S_n}$ and Murnagon Nakayama rule
5. Random Matrix theory (yay) and quasi-symmetric functions, which he says is popular nowadays
6. Polya theory- which seems highly combinatorial in nature, and deals with counting orbits of finite groups.
7. Combinatorial Hopf algebras
8. Macdonald polynomials, something I really need to learn
9. Shuffling cards : here he gave a probabilistic interpretation in terms of card shuffling model of the RSK algorithm.

The next highlight of the lecture is three partial orderings on the space of partitions of integers. First of all partitions are written with weakly decreasing component sizes. Then we have the following three orderings:

1. component-wise AND ordering (component-wise OR doesn’t make sense)
2. dominance ordering, which is that ${\mu \ge \nu}$ if ${\sum_{i=1}^k \mu_i \ge \sum_{i=1}^k \nu_i}$.
3. A common refinement of both of the above, which is a linear (i.e., total) ordering: in simple terms, it’s just lexicographical ordering.

Of course one can describe dominance ordering alternatively in terms of dot up-moving of Ferrer’s diagram. It’s a serious problem to show ${\lambda \ge \mu}$ iff ${\lambda^T \le \mu^T}$. From the fact that monomial symmetric polynomials span ${\Lambda^n}$ one instantly gets that it’s dimension is ${p(n)}$ which is the number of partitions of ${n}$. Next recall elementary symmetric functions are defined by ${\displaystyle e_i = \sum_{j_1 < \ldots < j_i} x_{j_1} \ldots x_{j_i}.}$ And for general ${\lambda}$, ${e_\lambda = \prod_i e_{\lambda_i}}$. The final punchline is the following proposition:

Theorem 1 The transition coefficients ${M_{\lambda \mu}}$ of ${e_\lambda}$ to ${m_\mu}$ gives the number of 0-1 matrices with row sum equal to ${\lambda_1, \lambda_2, \ldots}$ and column sum equal to ${\mu_1, \mu_2, \ldots}$.

To prove this, first observe that ${e_n}$ gives the generating function of all configurations of ${n}$ balls in infinitely many boxes satisfying the Fermi-Dirac allocation constraint: i.e., no two balls in the same box. This is true because each such allocation gets counted exactly once with the label ${x_{j_1} \ldots x_{j_n}}$ indicating the positions of the ${n}$ balls. On the other hand ${m_n}$ counts the power of ${x_1}$, ${x_2}$, etc, so a monomial term in ${e_\lambda}$ corresponds to choosing ${\lambda_1}$ distinct ${x_i}$‘s in the first row, ${\lambda_2}$ distinct ${x_i}$‘s in the second row, etc, and it will be a term in ${m_\mu}$ if there are ${\mu_1}$ ${x_1}$‘s chosen in total, ${\mu_2}$ ${x_2}$‘s chosen in total, etc. Now since ${e_\lambda}$ and ${m_\mu}$ are invariant under ${S_\infty}$, this gives the desired counting result.