Schur Polynomials as a Basis for Symmetric Functions

Hello! Welcome to the fifth lesson in our course.

Introduction

In our last lesson, we began exploring the algebraic tools used in the paper by defining symmetric polynomials. We focused on the elementary symmetric polynomials ($e_k$) and established their crucial role in connecting the roots of a polynomial to its coefficients via Vieta's formulas. We saw that the coefficients of the characteristic difference equation are symmetric functions of its roots.

The fundamental theorem of symmetric polynomials states that any symmetric polynomial can be expressed uniquely as a polynomial in the elementary symmetric polynomials. In the language of linear algebra, this means that products of elementary symmetric polynomials form a basis for the space of symmetric polynomials.

Today, we will introduce a different, and in many ways more profound, basis for this space: the Schur polynomials. These objects, denoted $s_{\lambda }$, are central to modern algebraic combinatorics and are the key to the paper's main proof.

This lesson corresponds to the second learning outcome of Module 4: Describe Schur polynomials as a basis for the space of symmetric functions. We will define Schur polynomials, see why they form a basis, and explore a beautiful combinatorial way to understand their structure.

1. The Landscape: Symmetric Functions and a Natural Basis

Before defining Schur polynomials, let's refine our understanding of the space they live in. In the last lesson, we considered polynomials in a fixed number of variables, $x_1,\dots ,x_n$. It is often more convenient to work in a setting that is independent of the number of variables, leading to the ring of symmetric functions. You can think of this as working with symmetric polynomials in an infinite number of variables, with the constraint that each polynomial has a bounded degree.

In this space, there is a very natural and intuitive basis: the monomial symmetric functions, $m_{\lambda }$. These are constructed from partitions. A partition $\lambda =({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_k)$ is a sequence of non-increasing positive integers. The monomial symmetric function $m_{\lambda }$ is the sum of all distinct monomials that can be formed by permuting the exponents from the parts of $\lambda$.

For example, in variables $x_1,x_2,x_3,\dots$, for the partition $\lambda =(2,1)$:
$m_{(2,1)}={\sum }_{i\ne j}{x}_i^2{x}_j=x_1^2{x}_2+x_2^2{x}_1+x_1^2{x}_3+x_3^2{x}_1+x_2^2{x}_3+x_3^2{x}_2+\dots$
The set of all $m_{\lambda }$ where $\lambda$ is a partition of an integer $d$ forms a basis for the space of homogeneous symmetric functions of degree $d$.

The following resource provides a formal definition.

{
    "intro": "This section from 'An introduction to Schur polynomials' by A. Prasad defines monomial symmetric polynomials and states that they form a basis.",
    "resource_title": "An introduction to Schur polynomials",
    "resource_id": "b54d3",
    "relevant_parts": [
        0
    ],
    "instructions": "Please read Section 1, 'Symmetric Polynomials'. Focus on the definition of the monomial symmetric polynomial, \(m_\\lambda\), and Theorem 1.2, which establishes it as a basis.",
    "estimated_time": "5 minutes"
}

2. An Algebraic Definition of Schur Polynomials

With the monomial basis $m_{\lambda }$ in hand, we are ready to define the Schur polynomials, $s_{\lambda }$. The original definition, due to Cauchy, is algebraic and expresses $s_{\lambda }$ as a ratio of two determinants.

First, for a sequence of integers $\alpha =({\alpha }_1,\dots ,{\alpha }_n)$, we define the alternant $a_{\alpha }$ as the determinant of a specific matrix:
$a_{\alpha }(x_1,\dots ,x_n)=\det (x_i^{{\alpha }_j}{)}_{i,j=1}^n$
An alternant polynomial has the property that swapping any two variables $x_i$ and $x_j$ multiplies the polynomial by $-1$.

The simplest non-trivial alternant is the Vandermonde determinant, which you may have encountered before. It corresponds to $\delta =(n-1,n-2,\dots ,1,0)$:
$a_{\delta }=\det (x_i^{n-j})={\prod }_{1\le i<j\le n}(x_i-x_j)$

The Schur polynomial $s_{\lambda }(x_1,\dots ,x_n)$ for a partition $\lambda =({\lambda }_1,\dots ,{\lambda }_n)$ is then defined as the ratio of two alternants:
$s_{\lambda }=\frac{a_{\lambda +\delta }}{a_{\delta }}$
where $\lambda +\delta =({\lambda }_1+n-1,{\lambda }_2+n-2,\dots ,{\lambda }_n+0)$. It is a non-trivial fact that this ratio is not only a polynomial but also a symmetric polynomial.

This definition is powerful, connecting Schur polynomials to the theory of determinants and alternating functions.

{
    "intro": "This section from Prasad's notes gives the classic bialternant definition of Schur polynomials.",
    "resource_title": "An introduction to Schur polynomials",
    "resource_id": "b54d3",
    "relevant_parts": [
        1
    ],
    "instructions": "Please read Section 5, 'Cauchy’s Bialternant Form of a Schur Polynomial'. Focus on the definition of \(s_\\lambda\) in equation (5.1) and the statement of Theorem 5.3.",
    "estimated_time": "10 minutes"
}

3. Schur Polynomials as a Basis

As stated in Theorem 5.3 of the previous reading, the Schur polynomials form a basis for the space of homogeneous symmetric polynomials. This is a cornerstone of the theory. Just like the monomial symmetric functions $\{m_{\lambda }\}$, the set of Schur functions $\{s_{\lambda }\}$ provides a complete set of building blocks for all symmetric functions.

The following resource provides a more formal and general statement of this fundamental result, framing it in the ring of symmetric functions (Sym) that we alluded to earlier.

The fact that the Schur functions form a $\mathbb{Z}$-basis is significant. It means that any symmetric function can be written as a unique linear combination of Schur functions with integer coefficients. This is a stronger condition than being a basis over, say, the rational numbers, and it points to the deep combinatorial nature of these objects.

4. A Combinatorial View: Semistandard Young Tableaux

We now have two bases for symmetric functions: the monomial basis $\{m_{\lambda }\}$ and the Schur basis $\{s_{\lambda }\}$. To understand the relationship between them—and to gain a more intuitive grasp of Schur polynomials—we turn to a beautiful combinatorial definition.

This definition involves filling the boxes of a Young diagram (the diagram representing the partition $\lambda$) with integers according to certain rules. This filled diagram is called a semistandard Young tableau (SSYT).

A SSYT of shape $\lambda$ is a filling of the Young diagram of $\lambda$ with positive integers such that:

1. Entries are weakly increasing across each row.
2. Entries are strictly increasing down each column.

The Schur function $s_{\lambda }$ can then be expressed as a sum over all possible SSYT of shape $\lambda$:
$s_{\lambda }={\sum }_{T\in \text{SST}(\lambda )}{x}^T$
where $x^T$ is the monomial formed by the entries of the tableau $T$. For example, if a tableau $T$ contains two 1s, one 2, and three 4s, its corresponding monomial is $x_1^2{x}_2{x}_4^3$.

Let's take $\lambda =(2,1)$. The SSYTs with entries from $\{1,2,3\}$ are:

The sum of their monomials gives $s_{(2,1)}(x_1,x_2,x_3)$.

This combinatorial definition has a profound consequence. If we group the terms in the sum by their monomial, we get the expansion of $s_{\lambda }$ in the monomial basis $\{m_{\mu }\}$:
$s_{\lambda }={\sum }_{\mu }{K}_{\lambda \mu }{m}_{\mu }$
The coefficient $K_{\lambda \mu }$, called the Kostka number, is simply the number of SSYT of shape $\lambda$ and "weight" $\mu$ (meaning the monomial is of type $\mu$).

This explicitly shows how to translate from the Schur basis to the monomial basis, making the change-of-basis concept concrete.

{
    "intro": "This section from Savage's notes provides the combinatorial definition of Schur functions via tableaux and explicitly defines the Kostka numbers as the change-of-basis coefficients.",
    "resource_title": "Symmetric Functions",
    "resource_id": "08fe6",
    "relevant_parts": [
        2
    ],
    "instructions": "Please read from the start of the subsection containing Theorem 3.4.11 up to Proposition 3.4.15. Focus on Corollary 3.4.12, which gives the formula for \(s_\\lambda\), and Proposition 3.4.15, which defines the Kostka numbers \(K_{\\lambda/\\mu,\\nu}\) (our \(K_{\\lambda\\nu}\) is the case where \(\\mu = \\emptyset\)).",
    "estimated_time": "10 minutes"
}

Conclusion

In this lesson, we introduced the Schur polynomials, a sophisticated and essential tool in the study of symmetric functions.

Key Takeaways:

• Symmetric functions can be built from several different bases. We looked at the intuitive monomial basis $\{m_{\lambda }\}$.
• Schur polynomials $\{s_{\lambda }\}$ form another, more fundamental, integer basis for the space of symmetric functions.
• Schur polynomials have a concise algebraic definition as a ratio of determinants (Cauchy's bialternant formula).
• They also have a rich combinatorial structure, defined as a sum over semistandard Young tableaux (SSYT).
• This combinatorial view gives us the Kostka numbers, which are the integer coefficients for converting from the Schur basis to the monomial basis.

The fact that the Schur basis is so central to the theory, with deep connections to both algebra (determinants) and combinatorics (tableaux), is why it is so powerful. The paper you are studying leverages this power to solve its optimization problem.

Preview of the Next Lesson:
We will build directly on today's concepts to explore Schur positivity. A symmetric function is called Schur-positive if the coefficients in its Schur basis expansion are all non-negative. This property is the linchpin of the paper's main argument, and understanding it will be a major step toward deciphering the proof.