Schur functions in algebraic combinatorics

From Encyclopedia of Mathematics - Reading time: 6 min

The Schur functions sλ are a special basis for the algebra of symmetric functions Λ. They are also intimately connected with representations of the symmetric and general linear groups (cf. also Representation of the symmetric groups). Standard references are [a3], [a6], [a8], [a9].

Definitions.[edit]

Let x={x1,,xl} be a set of variables and let Λ be the algebra of symmetric functions in x. Bases for this algebra are indexed by partitions λ=(λ1,,λl), i.e., λ is a weakly decreasing sequence of l non-negative integers λi called parts. Associated with any partition is an alternant, which is the l×l determinant

aλ=det(xiλj).

In particular, for the partition δ=(l1,l2,,0) one has the Vandermonde determinant aδ=i<j(xixj). In his thesis [a11], I. Schur defined the functions which bear his name as

sλ=aλ+δaδ,

where addition of partitions is component-wise. It is clear from this equation that sλ is a symmetric homogeneous polynomial of degree |λ|=Σiλi.

There is a more combinatorial definition of a Schur function. A partition λ can be viewed as a Ferrers shape, obtained by placing dots or cells in l left-justified rows with λi boxes in row i. One obtains a semi-standard Young tableaux, T, of shape λ by replacing each dot by a positive integer so that rows weakly increase and columns strictly increase (cf. also Young tableau). For example, if λ=(4,2,1), then its shape and a possible tableau are

 ┌───┬───┬───┬───┐  ┌───┬───┬───┬───┐ 
 │   │   │   │   │  │ 1 │ 1 │ 1 │ 3 │ 
 ├───┼───┼───┴───┘  ├───┼───┼───┴───┘ 
 │   │   │          │ 2 │ 3 │         
 ├───┼───┘          ├───┼───┘         
 │   │              │ 4 │             
 └───┘     and      └───┘ .            


Each tableau determines a monomial xT=iTxi, e.g., in the example above, xT=x13x2x32x4. The second definition of the Schur function is then

sλ=TxT,

where the sum is over all semi-standard Young tableaux of shape λ with entries between 1 and l.

Change of basis.[edit]

The Schur functions can also be written in terms of the other standard bases for Λ. A monomial symmetric function mλ is the sum of all monomials whose exponent sequence is some permutation of λ. Also, define the Kostka number [a5] Kλμ as the number of semi-standard Young tableaux T of shape λ and content μ=(μ1,,μl), i.e., T contains μi entries equal to i for 1il. The combinatorial definition of sλ immediately gives the following rule, known as Young's rule:

sλ=μKλμmμ.

Now consider the complete homogeneous symmetric functions hλ=hλ1hλl and the elementary symmetric functions λ=eλ1eλl, where hλi (respectively, eλi) is the sum of all (respectively, all square-free) monomials of degree λi. Also, let λ denote the partition conjugate to λ, whose parts are the column lengths of λ's shape. In the preceding example, λ=(3,2,1,1). For the two bases under consideration, the function sλ can be described as a determinant (the Jacobi–Trudi identity [a2], [a12] and its dual):

sλ=det(hλii+j),

sλ=det(eλii+j).

Note that this identity immediately implies

s(l)=hl and s(1l)=el,

where (1l) is the partition with l parts all equal to 1. These specializations also follow directly from the combinatorial definition of sλ.

Representations.[edit]

The description of sλ in terms of the power sum symmetric functions brings in the representation theory of the symmetric group Sn. The irreducible representations of Sn are indexed by partitions λ such that |λ|=n. Given a conjugacy class of Sn corresponding to a partition μ, let kμ denote its size and let χμλ be the value of the λth irreducible character on the class. Now consider the power sum symmetric function pλ=pλ1pλl, where pλi=x1λi++xlλi.

The following now holds: If |λ|=n, then

sλ=1n!|μ|=nkμχμλpμ.

In other words, sλ is the cycle-indicator generating function (in the sense of Polyá–Redfield enumeration) for the irreducible character of Sn corresponding to λ.

Now, consider the complex general linear group GLl. A representation ρ:GLlGLm is polynomial if, for every XGLl, the entries of ρ(X) are polynomials in the entries of X. The polynomial representations of GLl are indexed by the partitions λ with l non-negative parts. Let be the character of a polynomial representation ρ and let X have eigenvalues x1,,xl. Then is a polynomial function of the xi (because this is true for diagonalizable X and these are dense in GLl) and is symmetric (because is a class function). In fact, more is true: The irreducible polynomial characters of GLl are precisely the sλ for λ with l non-negative parts.

Properties.[edit]

The connection with representations of Sn can be used to construct an isomorphism of algebras. Let Rn denote the vector space of all class functions on Sn and let R=n>0Rn. The irreducible characters form a basis for R, and it can be endowed with a multiplication by induction of the tensor product. The characteristic or Frobenius mapping [a1] ch:RΛ is defined on χRx by

ch(χ)=1n!|μ|=nkμχμpμ,

where χμ is the value of on the class corresponding to μ. The mapping ch:RΛ is an isomorphism of algebras. In fact, there are natural inner products on R and Λ that make ch an isometry.

A number of identities involving Schur functions have interesting bijective proofs using the combinatorial definition. Among the most famous are the following, in which it is assumed that y={y1,,yl} is another set of variables.

The Cauchy identity and its dual are

λsλ(x)sλ(y)=i,j=1l11xiyj

and

λsλ(x)sλ(y)=i,j=1l(1+xiyj).

D. Knuth [a4] has given algorithmic bijections between matrices and semi-standard Young tableaux that prove these identities. It is a generalization of a mapping of C. Schensted [a10] for standard Young tableaux, i.e., semi- standard Young tableaux where the entries are precisely 1,,|λ|.

One can also describe the structure constants for the algebra Λ in the basis sλ combinatorially. If μλ as Ferrers shapes, then one has a skew shape λ/μ consisting of all dots or cells that are in λ but not in μ. Skew semi-standard Young tableaux are defined in the obvious way. The reverse row word for a semi-standard Young tableaux T, πT, is obtained by reading the entries in each row from right to left, starting with the top row and working down. For the example tableau, πT=3111324. Also, a sequence of positive integers π=w1wn is a lattice permutation or ballot sequence if, in every prefix w1wk, the number of i's is at least as big as the number of (i+1)'s for all i1. The Littlewood–Richardson rule [a7] states that if

λsμ=νcλμνsν,

then cλμν is equal to the number of semi-standard Young tableaux T of shape ν/λ and content μ such that πT is a ballot sequence. Via the characteristic mapping, the Littlewood–Richardson coefficients cλμν can also be viewed as giving the multiplicities of the character product χλχμ when decomposed into irreducibles. Equivalently, one can consider the decomposition of the inner tensor product of two irreducible polynomial representations of GLl.

There are many generalizations of Schur functions, one of the most notable being the Hall–Littlewood functions. See [a8] for more information.

References[edit]

[a1] F.G. Frobenius, "Über die Charactere der symmetrischen Gruppe" Sitz. K. Preuss. Akad. Wiss (1900) pp. 516–534 (Also: Gesammelte Abh. 3 Springer, 1968, 148-166)
[a2] C. Jacobi, "De functionibus alternantibus earumque divisione per productum e differentiis elementorum conflatum" J. Reine Angew. Math. , 22 (1841) pp. 360–371 (Also: Math. Werke 3, Chelsea, 1969, 439-452)
[a3] G.D. James, A. Kerber, "The representation theory of the symmetric group" , Encycl. Math. Appl. , 16 , Addison-Wesley (1981)
[a4] D.E. Knuth, "Permutations, matrices and generalized Young tableaux" Pacific J. Math. , 34 (1970) pp. 709–727
[a5] C. Kostka, "Über den Zusammenhang zwischen einigen Formen von symmetrischen Funktionen" Crelle's J. , 93 (1882) pp. 89–123
[a6] D.E. Littlewood, "The theory of group characters" , Oxford Univ. Press (1950)
[a7] D.E. Littlewood, A.R. Richardson, "Group characters and algebra" Philos. Trans. R. Soc. London Ser. A , 233 (1934) pp. 99–142
[a8] I.G. Macdonald, "Symmetric functions and Hall polynomials" , Oxford Univ. Press (1995) (Edition: Second)
[a9] B.E. Sagan, "The symmetric group: representations, combinatorial algorithms, and symmetric functions" , Wadsworth&Brooks/Cole (1991) (Second ed.: Springer, to appear)
[a10] C. Schensted, "Longest increasing and decreasing subsequences" Canad. J. Math. , 13 (1961) pp. 179–191
[a11] I. Schur, "Über eine Klasse von Matrizen die sich einer gegeben Matrix zuordnen lassen" Inaugural Diss. Berlin (1901)
[a12] N. Trudi, "Intorno un determinante piu generale di quello che suol dirsi determinante delle radici di una equazione, ed alle funzioni simmetriche complete di queste radici" Rend. Accad. Sci. Fis. Mat. Napoli , 3 (1864) pp. 121–134 (Also: Giornale di Mat. 2 (1864), 152–158; 180–186)

How to Cite This Entry: Schur functions in algebraic combinatorics (Encyclopedia of Mathematics) | Licensed under CC BY-SA 3.0. Source: https://encyclopediaofmath.org/wiki/Schur_functions_in_algebraic_combinatorics
1 |
↧ Download this article as ZWI file
Encyclosphere.org EncycloReader is supported by the EncyclosphereKSF