In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, 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 tableau In mathematics, a Young tableau (; plural: tableaux) is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups and ...
x. They occur in many other mathematical contexts, for instance as
multiplicity
Multiplicity may refer to: In science and the humanities
* Multiplicity (mathematics), the number of times an element is repeated in a multiset
* Multiplicity (philosophy), a philosophical concept
* Multiplicity (psychology), having or using mult ...
in the decomposition of
tensor product
In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otimes W ...
s of
finite-dimensional representations of general linear groups, or in the decomposition of certain
induced representations
In group theory, the induced representation is a representation of a group, , which is constructed using a known representation of a subgroup . Given a representation of '','' the induced representation is, in a sense, the "most general" represent ...
in the
representation theory of the symmetric group
In mathematics, the representation theory of the symmetric group is a particular case of the representation theory of finite groups, for which a concrete and detailed theory can be obtained. This has a large area of potential applications, from sym ...
, or in the area of
algebraic combinatorics
Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algeb ...
dealing with
Young tableaux In mathematics, a Young tableau (; plural: tableaux) is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups and ...
and
symmetric polynomials.
Littlewood–Richardson coefficients depend on three
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
s, say
, of which
and
describe the Schur functions being multiplied, and
gives the Schur function of which this is the coefficient in the linear combination; in other words they are the coefficients
such that
:
The Littlewood–Richardson rule states that
is equal to the number of Littlewood–Richardson tableaux of
skew shape and of weight
.
History
The Littlewood–Richardson rule was first stated by but though they claimed it as a theorem they only proved it in some fairly simple special cases.
claimed to complete their proof, but his argument had gaps, though it was so obscurely written that these gaps were not noticed for some time, and his argument is reproduced in the book . Some of the gaps were later filled by . The first rigorous proofs of the rule were given four decades after it was found, by and , after the necessary combinatorial theory was developed by , , and in their work on the
Robinson–Schensted correspondence In mathematics, the Robinson–Schensted correspondence is a bijective correspondence between permutations and pairs of standard Young tableaux of the same shape. It has various descriptions, all of which are of algorithmic nature, it has many rem ...
.
There are now several short proofs of the rule, such as , and using
Bender-Knuth involutions.
used the
Littelmann path model
In mathematics, the Littelmann path model is a combinatorial device due to Peter Littelmann for computing multiplicities ''without overcounting'' in the representation theory of symmetrisable Kac–Moody algebras. Its most important application ...
to generalize the Littlewood–Richardson rule to other semisimple Lie groups.
The Littlewood–Richardson rule is notorious for the number of errors that appeared prior to its complete, published proof. Several published attempts to prove it are incomplete, and it is particularly difficult to avoid errors when doing hand calculations with it: even the original example in contains an error.
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
occurs at least as often as the number
. Another equivalent (though not quite obviously so) characterization is that the tableau itself, and any tableau obtained from it by 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
,
and
. Then the fact that
can be deduced from the fact that the two tableaux shown at the right are the only two Littlewood–Richardson tableaux of shape
and weight
. 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 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
with index ''j'', then that entry ''i''
'j''should occur in a row strictly below that of