Schur functions in algebraic combinatorics

The Schur functions 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.

Let be a set of variables and let be the algebra of symmetric functions in . Bases for this algebra are indexed by partitions , i.e., is a weakly decreasing sequence of non-negative integers called parts. Associated with any partition is an alternant, which is the determinant

In particular, for the partition one has the Vandermonde determinant . In his thesis [a11], I. Schur defined the functions which bear his name as

where addition of partitions is component-wise. It is clear from this equation that is a symmetric homogeneous polynomial of degree .

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 left-justified rows with boxes in row . One obtains a semi-standard Young tableaux, , 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 , then its shape and a possible tableau are

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

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

Change of basis.

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

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

Note that this identity immediately implies

where is the partition with parts all equal to . These specializations also follow directly from the combinatorial definition of .

Representations.

The description of in terms of the power sum symmetric functions brings in the representation theory of the symmetric group . The irreducible representations of are indexed by partitions such that . Given a conjugacy class of corresponding to a partition , let denote its size and let be the value of the th irreducible character on the class. Now consider the power sum symmetric function , where .

The following now holds: If , then

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

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

Properties.

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

where is the value of on the class corresponding to . The mapping is an isomorphism of algebras. In fact, there are natural inner products on and that make 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 is another set of variables.

The Cauchy identity and its dual are

and

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 .

One can also describe the structure constants for the algebra in the basis 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 , , 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, . Also, a sequence of positive integers is a lattice permutation or ballot sequence if, in every prefix , the number of 's is at least as big as the number of 's for all . The Littlewood–Richardson rule [a7] states that if

then is equal to the number of semi-standard Young tableaux of shape and content such that is a ballot sequence. Via the characteristic mapping, the Littlewood–Richardson coefficients 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 .

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

References

[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)