Littlewood–Richardson rule

In mathematics, especially in the area of algebra known as the representation theory and in the area of algebraic combinatorics dealing with Young tableaux and symmetric polynomials, the Littlewood–Richardson rule is a combinatorial description of the coefficients that arise when decomposing a product of two Schur functions as a linear combination of other Schur functions. These coefficients are natural numbers, which the Littlewood–Richardson rule describes as counting certain skew tableaux. They occur in many other mathematical contexts, for instance as multiplicity in the decomposition of tensor products of irreducible representations of general linear groups (or related groups like the special linear and special unitary groups), or in the decomposition of certain induced representations in the representation theory of the symmetric group.

Littlewood–Richardson coefficients depend on three partitions, say $lambda,mu,\; u$, of which $lambda$ and $mu$ describe the Schur functions being multiplied, and $u$ gives the Schur function of which this is the coefficient in the linear combination; in other words they are the coefficients $c\_\{lambda,mu\}^\; u$ such that:$s\_lambda\; s\_mu=sum\_\; u\; c\_\{lambda,mu\}^\; u\; s\_\; u.$The Littlewood–Richardson rule states that $c\_\{lambda,mu\}^\; u$ is equal to the number of Littlewood–Richardson tableaux of shape $u/lambda$ and of weight $mu$.

History

The Littlewood–Richardson rule was first stated in by Littlewood and Richardson in 1934 [Littlewood D. E., Richardson A. R., "Group characters and algebra" Philos. Trans. R. Soc. London Ser. A , 233 (1934) pp. 99–142] , but they only proved it in some fairly simple special cases.
Robinson [G. de B. Robinson, "On the representations of the symmetric group", American J. of Math. 60, (1938), 745–760.] claimed to complete their proof, but his argument had serious flaws; nevertheless it is reproduced in a book by Littlewood [Littlewood D. E., The theory of group characters and Matrix Representations of Groups, 2nd ed., Clarendon press, Oxford, 1950.] . The first rigorous proofs appeared only in the 1970s, after the necessary combinatorial theory was developed by Schensted [Schensted C., "Longest increasing and decreasing subsequences", Canadian J. of Math. 13, (1961), 179–191.] , Schützenberger [Schützenberger M. P., "Quelques remarques sur une construction de Schensted", Math. Scandinavica 12, (1963), 117–128.] [Schützenberger M. P., "La correspondance de Robinson", pp. 59–113 in Combinatoire et représentation du groupe symétrique (D. Foata, ed.), Lecture Notes in Math. 579, 1977.] , and Knuth [Knuth D. E., “Permutations, matrices and generalized Young tableaux”, Pacific J. of Math. 34, (1970), 709–727.] . Many interesting combinatorial constructions are related to the Littlewood–Richardson rule, notably the Robinson–Schensted correspondence.

Littlewood–Richardson tableaux

A Littlewood–Richardson tableau is a skew semistandard tableau with the additional property that the sequence obtained by concatenating its reversed rows is a lattice word (or lattice permutation), which means that in every initial part of the sequence any number $i$ occurs at least as often as the number $i+1$. Another equivalent (though not quite obviously so) characterization is that the tableau itself, and any tableau obtained from it be removing some number of its leftmost columns, has a weakly decreasing weight. Many other combinatorial notions have been found that turn out to be in bijection with Littlewood–Richardson tableaux, and can therefore also be used to define the Littlewood–Richardson coefficients.

Example

Consider the case that $lambda=(2,1)$, $mu=(3,2,1)$ and $u=(4,3,2)$. Then the fact that $c\_\{lambda,mu\}^\; u=2$ can be deduced from the fact that the two tableaux shown at the right are the only two Littlewood–Richardson tableaux of shape $u/lambda$ and weight $mu$. Indeed, since the last box on the first nonempty line of the skew diagram can only contain an entry 1, the entire first line must be filled with entries 1 (this is true for any Littlewood–Richardson tableau); in the last box of the second row we can only place a 2 by column strictness and the fact that our lattice word cannot contain any larger entry before it contains a 2. For the first box of the second row we can now either use a 1 or a 2. Once that entry is chosen, the third row must contain the remaining entries to make the weight (3,2,1), in a weakly increasing order, so we have no choice left any more; in both case it turns out that we do find a Littlewood–Richardson tableau.

A more geometrical description

The condition that the sequence of entries read from the tableau in a somewhat peculiar order form a lattice word, can be replaced by a more local and geometrical condition. Since in a semistandard tableau equal entries never occur in the same column, one can number the copies of any value from right to left, which is their order in of occurrence in the sequence that should be a lattice word. Call the number so associated to each entry its index, and write an entry "i" with index "j" as "i" ["j"] . Now if some Littlewood–Richardson tableau contains an entry $i>1$ occurs with index "j", then that entry "i" ["j"] should occur in a row strictly below that of $i-1\; [j]$ (which certainly also occurs, since the entry "i" − 1 occurs as least as often as the entry "i" does). In fact the entry "i" ["j"] should also occur in a column no further to the right than that same entry $i-1\; [j]$ (which at first sight appears to be a stricter condition). If the weight of the Littlewood–Richardson tableau is fixed beforehand, then one can form a fixed collection of indexed entries, and the if these are placed in a way respecting those geometric restrictions, in addition to those of semistandard tableaux and the condition that indexed copies of the same entries should respect right-to-left ordering of the indexes, then the resulting tableaux are guaranteed to be Littlewood–Richardson tableaux.

An algorithmic form of the rule

The Littlewood–Richardson as stated above gives a combinatorial expression for individual Littlewood–Richardson coefficients, but gives no indication of a practical method to enumerate the Littlewood–Richardson tableaux in order to find the values of these coefficients. Indeed for given $lambda,mu,\; u$ there is no simple criterion to determine whether any Littlewood–Richardson tableaux of shape $u/lambda$ and of weight $mu$ exist at all (although there are a number of necessary conditions, the simplest of which is $|lambda|+|mu|=|\; u|$); therefore it seems inevitable that in some cases one has to go through an elaborate search, only to find that no solutions exist.

Nevertheless, the rule leads to a quite efficient procedure to determine the full decomposition of a product of Schur functions, in other words to determine all coefficients $c\_\{lambda,mu\}^\; u$ for fixed λ and μ, but varying ν. This fixes the weight of the Littlewood–Richardson tableaux to be constructed and the "inner part" λ of their shape, but leaves the "outer part" ν free. Since the weight is known, the set of indexed entries in the geometric description is fixed. Now for successive indexed entries, all possible positions allowed by the geometric restrictions can be tried in a backtracking search. The entries can be tried in increasing order, while among equal entries they can be tried by "decreasing" index. The latter point is the key to efficiency of the search procedure: the entry "i" ["j"] is then restricted to be in a column to the right of $i\; [j+1]$, but no further to the right than $i-1\; [j]$ (if such entries are present). This strongly restricts the set of possible positions, but "always leaves at least one valid position for $i\; [j]$"; thus every placement of an entry will give rise to at least one complete Littlewood–Richardson tableau, and the search tree contains no dead ends.

External links

* [http://young.sp2mi.univ-poitiers.fr/cgi-bin/form-prep/marc/LiE_form.act?action=LRR An online program] , decomposing products of Schur functions using the Littlewood–Richardson rule

See also

* Ring of symmetric functions
* Schur function

References

*Macdonald, I. G. "Symmetric functions and Hall polynomials." Second edition. Oxford Mathematical Monographs. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1995. x+475 pp. ISBN 0-19-853489-2 MathSciNet|id=96h:05207
*van Leeuwen, M. A. A., " [http://www-math.univ-poitiers.fr/~maavl/pdf/lrr.pdf The Littlewood-Richardson rule, and related combinatorics] ", in Math. Soc. of Japan Memoirs 11, Interaction of Combinatorics and Representation Theory