Schur polynomial

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, Schur polynomials, named after Issai Schur, are certain symmetric polynomials in n variables, indexed by partitions, that generalize the elementary symmetric polynomials and the complete homogeneous symmetric polynomials. In representation theory they are the characters of irreducible representations of the general linear groups. The Schur polynomials form a linear basis for the space of all symmetric polynomials. Any product of Schur functions can be written as a linear combination of Schur polynomials with non-negative integral coefficients; the values of these coefficients is given combinatorially by the Littlewood–Richardson rule. More generally, skew Schur polynomials are associated with pairs of partitions and have similar properties to Schur polynomials.

Definition[edit]

Schur polynomials are indexed by integer partitions. Given a partition λ = (λ1, λ2, …,λn), where λ1λ2≥ … ≥ λn, and each λj is a non-negative integer, the functions

 a_{(\lambda_1+n-1, \lambda_2+n-2, \dots , \lambda_n)} (x_1, x_2, \dots , x_n) =
\det \left[ \begin{matrix} x_1^{\lambda_1+n-1} & x_2^{\lambda_1+n-1} & \dots & x_n^{\lambda_1+n-1} \\
x_1^{\lambda_2+n-2} & x_2^{\lambda_2+n-2} & \dots & x_n^{\lambda_2+n-2} \\
\vdots & \vdots & \ddots & \vdots \\
x_1^{\lambda_n} & x_2^{\lambda_n} & \dots & x_n^{\lambda_n} \end{matrix} \right]

are alternating polynomials by properties of the determinant. A polynomial is alternating if it changes sign under any transposition of the variables.

Since they are alternating, they are all divisible by the Vandermonde determinant,

 a_{(n-1, n-2, \dots , 0)} (x_1, x_2, \dots , x_n) = \det \left[ \begin{matrix} x_1^{n-1} & x_2^{n-1} & \dots & x_n^{n-1} \\
x_1^{n-2} & x_2^{n-2} & \dots & x_n^{n-2} \\
\vdots & \vdots & \ddots & \vdots \\
1 & 1 & \dots & 1 \end{matrix} \right] = \prod_{1 \leq j < k \leq n} (x_j-x_k).

The Schur polynomials are defined as the ratio


 s_{\lambda} (x_1, x_2, \dots , x_n) =
\frac{ a_{(\lambda_1+n-1, \lambda_2+n-2, \dots , \lambda_n+0)} (x_1, x_2, \dots , x_n)}
{a_{(n-1, n-2, \dots , 0)} (x_1, x_2, \dots , x_n) }.

This is a symmetric function because the numerator and denominator are both alternating, and a polynomial since all alternating polynomials are divisible by the Vandermonde determinant.

Properties[edit]

The degree d Schur polynomials in n variables are a linear basis for the space of homogeneous degree d symmetric polynomials in n variables.

For a partition λ = (λ1, λ2, ..., λn), the Schur polynomial is a sum of monomials,


s_\lambda(x_1,x_2,\ldots,x_n)=\sum_T x^T = \sum_T x_1^{t_1}\cdots x_n^{t_n}

where the summation is over all semistandard Young tableaux T of shape λ. The exponents t1, ..., tn give the weight of T, in other words each ti counts the occurrences of the number i in T. This can be shown to be equivalent to the definition from the first Giambelli formula using the Lindström–Gessel–Viennot lemma (as outlined on that page).

The first Jacobi-Trudi formula expresses the Schur polynomial as a determinant in terms of the complete homogeneous symmetric polynomials,

 s_{\lambda} = \det_{ij} h_{\lambda_{i} + j - i}, 1 \le i,j \le n = 
\left| \begin{matrix} h_{\lambda_1} & h_{\lambda_1 + 1} & \dots & h_{\lambda_1 + n - 1} \\
h_{\lambda_2-1} & h_{\lambda_2} & \dots & h_{\lambda_2+n-2} \\
\vdots & \vdots & \ddots & \vdots \\
h_{\lambda_n-n+1} & h_{\lambda_n-n+2} & \dots & h_{\lambda_n} \end{matrix} \right|,[1]

where hi := s(i).

The second Jacobi-Trudi formula expresses the Schur polynomial as a determinant in terms of the elementary symmetric polynomials,

 s_{\lambda} = \det_{ij} e_{\lambda'_{i} + j - i}, 1 \le i,j \le l = 
\left| \begin{matrix} e_{\lambda'_1} & e_{\lambda'_1 + 1} & \dots & e_{\lambda'_1 + n - 1} \\
e_{\lambda'_2-1} & e_{\lambda'_2} & \dots & e_{\lambda'_2+n-2} \\
\vdots & \vdots & \ddots & \vdots \\
e_{\lambda'_l-l+1} & e_{\lambda'_l-l+2} & \dots & e_{\lambda'_l} \end{matrix} \right|,[2]

where ei := s(i)j. and λ' is the conjugate partition to λ.

These two formulae are known as determinantal identities. Another such identity is Giambelli's formula, which expresses the Schur function for an arbitrary partition in terms of those for the hook partitions contained within the Young diagram. In Frobenius' notation, the partition is denoted

 (a_{1}, ... a_{r}| b_{1}, ... b_{r})

where, for each diagonal element in position ii, ai denotes the number of boxes to the right in the same row and bi denotes the number of boxes beneath it in the same column (the arm and leg lengths, respectively).

The Giambelli identity expresses the partition as the determinant

 s_{ (a_{1}, ... a_{r}| b_{1}, ... b_{r})} = \det ( s_{(a_{i} | b_{j})}) .

Schur polynomials can be expressed as linear combinations of monomial symmetric functions mμ with non-negative integer coefficients Kλμ called Kostka numbers,

s_\lambda= \sum_\mu K_{\lambda\mu}m_\mu.\

Evaluating the Schur polynomial sλ in (1,1,...,1) gives the number of semi-standard Young tableaux of shape λ with entries in 1, 2, ..., n. One can show, by using the Weyl character formula for example, that

s_\lambda(1,1,\dots,1) = \prod_{1\leq i < j \leq n} \frac{\lambda_i - \lambda_j + j-i}{j-i}.

In this formula, λ, the tuple indicating the width of each row of the Young diagram, is implicitly extended with zeros until it has length n. The sum of the elements λi is d. See also the Hook length formula which computes the same quantity for fixed λ.

Example[edit]

The following extended example should help clarify these ideas. Consider the case n = 3, d = 4. Using Ferrers diagrams or some other method, we find that there are just four partitions of 4 into at most three parts. We have

 s_{(2,1,1)} (x_1, x_2, x_3) = \frac{1}{\Delta} \;
\det \left[ \begin{matrix} x_1^4 & x_2^4 & x_3^4 \\ x_1^2 & x_2^2 & x_3^2 \\ x_1 & x_2 & x_3 \end{matrix}
\right] = x_1 \, x_2 \, x_3 \, (x_1 + x_2 + x_3)
 s_{(2,2,0)} (x_1, x_2, x_3) = \frac{1}{\Delta} \;
\det \left[ \begin{matrix} x_1^4 & x_2^4 & x_3^4 \\ x_1^3 & x_2^3 & x_3^3 \\ 1 & 1 & 1 \end{matrix}
\right]= x_1^2 \, x_2^2 + x_1^2 \, x_3^2 + x_2^2 \, x_3^2 
+ x_1^2 \, x_2 \, x_3 + x_1 \, x_2^2 \, x_3 + x_1 \, x_2 \, x_3^2

and so on. Summarizing:

  1.  s_{(2,1,1)} = e_1 \, e_3
  2.  s_{(2,2,0)} = e_2^2 - e_1 \, e_3
  3.  s_{(3,1,0)} = e_1^2 \, e_2 - e_2^2 - e_1 \, e_3
  4.  s_{(4,0,0)} = e_1^4 - 3 \, e_1^2 \, e_2 + 2 \, e_1 \, e_3 + e_2^2.

Every homogeneous degree-four symmetric polynomial in three variables can be expressed as a unique linear combination of these four Schur polynomials, and this combination can again be found using a Gröbner basis for an appropriate elimination order. For example,

\phi(x_1, x_2, x_3) = x_1^4 + x_2^4 + x_3^4

is obviously a symmetric polynomial which is homogeneous of degree four, and we have

\phi = s_{(2,1,1)} - s_{(3,1,0)} + s_{(4,0,0)}.\,\!

Relation to representation theory[edit]

The Schur polynomials occur in the representation theory of the symmetric groups, general linear groups, and unitary groups. The Weyl character formula implies that the Schur polynomials are the characters of finite-dimensional irreducible representations of the general linear groups, and helps to generalize Schur's work to other compact and semisimple Lie groups.

Several expressions arise for this relation, one of the most important being the expansion of the Schur functions sλ in terms of the symmetric power functions p_k=\sum_i x_i^k. If we write χλ
ρ
for the character of the representation of the symmetric group indexed by the partition λ evaluated at elements of cycle type indexed by the partition ρ, then

s_\lambda = \sum_{\nu} \frac{\chi^\lambda_\nu}{z_\nu} p_\nu = \sum_{\rho=(1^{r_1},2^{r_2},3^{r_3},\dots)}\chi^\lambda_\rho \prod_k \frac{p^{r_k}_k}{r_k! k^{r_k} },

where ρ = (1r1, 2r2, 3r3, ...) means that the partition ρ has rk parts of length k.

A proof of this can be found in R. Stanley's Enumerative combinatoric II, Corollary 7.17.5.

The integers χλ
ρ
can be computed using the Murnaghan–Nakayama rule.

Skew Schur functions[edit]

Skew Schur functions sλ/μ depend on two partitions λ and μ, and can be defined by the property

\langle s_{\lambda/\mu},s_\nu\rangle = \langle s_{\lambda},s_\mu  s_\nu\rangle.

Similar to the ordinary Schur polynomials, there are numerous ways to compute these. The corresponding Jacobi-Trudi identities are

s_{\lambda/\mu} = (h_{\lambda_i - \mu_j -i + j}), 1\leq i,j \leq l(\lambda),
s_{\lambda'/\mu'} = (e_{\lambda_i - \mu_j -i + j}), 1\leq i,j \leq l(\lambda).

There is also a combinatorial interpretation of the skew Schur polynomials, namely it is a sum over all semi-standard Young tableaux (or column-strict tableaux) of the skew shape \lambda/\mu.

Generalizations[edit]

There are numerous generalizations of Schur polynomials:

Double Schur polynomials[edit]

The double Schur polynomials[3] can be seen as a generalization of the shifted Schur polynomials. These polynomials are also closely related to the factorial Schur polynomials. Given a parititon λ, and a sequence a1, a2,… one can define the double Schur polynomial sλ(x || a) as

s_\lambda(x||a) = \sum_T \prod_{\alpha \in \lambda}(x_{T(\alpha)} - a_{T(\alpha)-c(\alpha)})

where the sum is taken over all reverse semi-standard Young tableaux T of shape λ, and integer entries in 1,…,n. Here T(α) denotes the value in the box α in T and c(α) is the content of the box.

A combinatorial rule for the Littlewood-Richardson coefficients (depending on the sequence a), is given by A.I Molev in.[3] In particular, this implies that the shifted Schur polynomials have non-negative Littlewood-Richardson coefficients.

The shifted Schur polynomials, s*λ(y) , can be obtained from the double Schur polynomials by specializing ai=-i and yi=xi+i.

Factorial Schur polynomials[edit]

The factorial Schur polynomials may be defined as follows. Given a parititon λ, and a sequence a1, a2, … one can define the factorial Schur polynomial sλ(x|a) as

s_\lambda(x|a) = \sum_T \prod_{\alpha \in \lambda}(x_{T(\alpha)} - a_{T(\alpha)+c(\alpha)})

where the sum is taken over all semi-standard Young tableaux T of shape λ, and integer entries in 1,…,n. Here T(α) denotes the value in the box α in T and c(α) is the content of the box.

There is also a determinant formula,


s_\lambda(x|a) = \frac{\det[(x_j|a)^{\lambda_i+n-i}]_{1\leq i,j\leq n}}{\prod_{i<j}(x_i-x_j)}

where (y|a)k = (y-a1)... (y-ak). It is clear that if we let ai=0 for all i, we recover the usual Schur polynomial sλ.

The double Schur polynomials and the factorial Schur polynomials in n variables are related via the identity sλ(x||a) = sλ(x|u) where an-i+1 = ui.

See also[edit]

References[edit]

  1. ^ Formula A.5 in Fulton, William; Harris, Joe (1991), Representation theory. A first course, Graduate Texts in Mathematics, Readings in Mathematics 129, New York: Springer-Verlag, ISBN 978-0-387-97495-8, MR 1153249, ISBN 978-0-387-97527-6 
  2. ^ Formula A.6 in Fulton, William; Harris, Joe (1991), Representation theory. A first course, Graduate Texts in Mathematics, Readings in Mathematics 129, New York: Springer-Verlag, ISBN 978-0-387-97495-8, MR 1153249, ISBN 978-0-387-97527-6 
  3. ^ a b Molev, A.I. (June 2009). "Littlewood–Richardson polynomials". Journal of Algebra 321 (11): 3450–3468. doi:10.1016/j.jalgebra.2008.02.034.