Template:Short description In mathematics, a Young tableau (Template:IPAc-en; 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 to study their properties.
Young tableaux were introduced by Alfred Young, a mathematician at Cambridge University, in 1900.<ref>Template:Citation.</ref><ref>Template:Citation. See in particular p. 133.</ref> They were then applied to the study of the symmetric group by Georg Frobenius in 1903. Their theory was further developed by many mathematicians, including Percy MacMahon, W. V. D. Hodge, G. de B. Robinson, Gian-Carlo Rota, Alain Lascoux, Marcel-Paul Schützenberger and Richard P. Stanley.
DefinitionsEdit
Note: this article uses the English convention for displaying Young diagrams and tableaux.
DiagramsEdit
A Young diagram (also called a Ferrers diagram, particularly when represented using dots) is a finite collection of boxes, or cells, arranged in left-justified rows, with the row lengths in non-increasing order. Listing the number of boxes in each row gives a partition Template:Mvar of a non-negative integer Template:Mvar, the total number of boxes of the diagram. The Young diagram is said to be of shape Template:Mvar, and it carries the same information as that partition. Containment of one Young diagram in another defines a partial ordering on the set of all partitions, which is in fact a lattice structure, known as Young's lattice. Listing the number of boxes of a Young diagram in each column gives another partition, the conjugate or transpose partition of Template:Mvar; one obtains a Young diagram of that shape by reflecting the original diagram along its main diagonal.
There is almost universal agreement that in labeling boxes of Young diagrams by pairs of integers, the first index selects the row of the diagram, and the second index selects the box within the row. Nevertheless, two distinct conventions exist to display these diagrams, and consequently tableaux: the first places each row below the previous one, the second stacks each row on top of the previous one. Since the former convention is mainly used by Anglophones while the latter is often preferred by Francophones, it is customary to refer to these conventions respectively as the English notation and the French notation; for instance, in his book on symmetric functions, Macdonald advises readers preferring the French convention to "read this book upside down in a mirror" (Macdonald 1979, p. 2). This nomenclature probably started out as jocular. The English notation corresponds to the one universally used for matrices, while the French notation is closer to the convention of Cartesian coordinates; however, French notation differs from that convention by placing the vertical coordinate first. The figure on the right shows, using the English notation, the Young diagram corresponding to the partition (5, 4, 1) of the number 10. The conjugate partition, measuring the column lengths, is (3, 2, 2, 2, 1).
Arm and leg lengthEdit
In many applications, for example when defining Jack functions, it is convenient to define the arm length aλ(s) of a box s as the number of boxes to the right of s in the diagram λ in English notation. Similarly, the leg length lλ(s) is the number of boxes below s. The hook length of a box s is the number of boxes to the right of s or below s in English notation, including the box s itself; in other words, the hook length is aλ(s) + lλ(s) + 1.
TableauxEdit
A Young tableau is obtained by filling in the boxes of the Young diagram with symbols taken from some alphabet, which is usually required to be a totally ordered set. Originally that alphabet was a set of indexed variables Template:Mvar, Template:Mvar, Template:Mvar..., but now one usually uses a set of numbers for brevity. In their original application to representations of the symmetric group, Young tableaux have Template:Mvar distinct entries, arbitrarily assigned to boxes of the diagram. A tableau is called standard if the entries in each row and each column are increasing. The number of distinct standard Young tableaux on Template:Mvar entries is given by the involution numbers
- 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (sequence A000085 in the OEIS).File:Standard Young Tableaux.pngAll standard Young tableaux with at most 5 boxes
In other applications, it is natural to allow the same number to appear more than once (or not at all) in a tableau. A tableau is called semistandard, or column strict, if the entries weakly increase along each row and strictly increase down each column. Recording the number of times each number appears in a tableau gives a sequence known as the weight of the tableau. Thus the standard Young tableaux are precisely the semistandard tableaux of weight (1,1,...,1), which requires every integer up to Template:Mvar to occur exactly once.
In a standard Young tableau, the integer <math>k</math> is a descent if <math>k+1</math> appears in a row strictly below <math>k</math>. The sum of the descents is called the major index of the tableau.<ref name="ste89"/>
VariationsEdit
There are several variations of this definition: for example, in a row-strict tableau the entries strictly increase along the rows and weakly increase down the columns. Also, tableaux with decreasing entries have been considered, notably, in the theory of plane partitions. There are also generalizations such as domino tableaux or ribbon tableaux, in which several boxes may be grouped together before assigning entries to them.
Skew tableauxEdit
A skew shape is a pair of partitions (Template:Math, Template:Math) such that the Young diagram of Template:Math contains the Young diagram of Template:Math; it is denoted by Template:Math. If Template:Math and Template:Math, then the containment of diagrams means that Template:Math for all Template:Mvar. The skew diagram of a skew shape Template:Math is the set-theoretic difference of the Young diagrams of Template:Mvar and Template:Mvar: the set of squares that belong to the diagram of Template:Mvar but not to that of Template:Mvar. A skew tableau of shape Template:Math is obtained by filling the squares of the corresponding skew diagram; such a tableau is semistandard if entries increase weakly along each row, and increase strictly down each column, and it is standard if moreover all numbers from 1 to the number of squares of the skew diagram occur exactly once. While the map from partitions to their Young diagrams is injective, this is not the case for the map from skew shapes to skew diagrams;<ref>For instance the skew diagram consisting of a single square at position (2,4) can be obtained by removing the diagram of Template:Math from the one of Template:Math, but also in (infinitely) many other ways. In general any skew diagram whose set of non-empty rows (or of non-empty columns) is not contiguous or does not contain the first row (respectively column) will be associated to more than one skew shape.</ref> therefore the shape of a skew diagram cannot always be determined from the set of filled squares only. Although many properties of skew tableaux only depend on the filled squares, some operations defined on them do require explicit knowledge of Template:Mvar and Template:Mvar, so it is important that skew tableaux do record this information: two distinct skew tableaux may differ only in their shape, while they occupy the same set of squares, each filled with the same entries.<ref>A somewhat similar situation arises for matrices: the 3-by-0 matrix Template:Mvar must be distinguished from the 0-by-3 matrix Template:Mvar, since Template:Math is a 3-by-3 (zero) matrix while Template:Math is the 0-by-0 matrix, but both Template:Mvar and Template:Mvar have the same (empty) set of entries; for skew tableaux however such distinction is necessary even in cases where the set of entries is not empty.</ref> Young tableaux can be identified with skew tableaux in which Template:Mvar is the empty partition (0) (the unique partition of 0).
Any skew semistandard tableau Template:Mvar of shape Template:Math with positive integer entries gives rise to a sequence of partitions (or Young diagrams), by starting with Template:Mvar, and taking for the partition Template:Mvar places further in the sequence the one whose diagram is obtained from that of Template:Mvar by adding all the boxes that contain a value ≤ Template:Mvar in Template:Mvar; this partition eventually becomes equal to Template:Mvar. Any pair of successive shapes in such a sequence is a skew shape whose diagram contains at most one box in each column; such shapes are called horizontal strips. This sequence of partitions completely determines Template:Mvar, and it is in fact possible to define (skew) semistandard tableaux as such sequences, as is done by Macdonald (Macdonald 1979, p. 4). This definition incorporates the partitions Template:Mvar and Template:Mvar in the data comprising the skew tableau.
Overview of applicationsEdit
Young tableaux have numerous applications in combinatorics, representation theory, and algebraic geometry. Various ways of counting Young tableaux have been explored and lead to the definition of and identities for Schur functions.
Many combinatorial algorithms on tableaux are known, including Schützenberger's jeu de taquin and the Robinson–Schensted–Knuth correspondence. Lascoux and Schützenberger studied an associative product on the set of all semistandard Young tableaux, giving it the structure called the plactic monoid (French: le monoïde plaxique).
In representation theory, standard Young tableaux of size Template:Mvar describe bases in irreducible representations of the symmetric group on Template:Mvar letters. The standard monomial basis in a finite-dimensional irreducible representation of the general linear group Template:Math are parametrized by the set of semistandard Young tableaux of a fixed shape over the alphabet {1, 2, ..., Template:Mvar}. This has important consequences for invariant theory, starting from the work of Hodge on the homogeneous coordinate ring of the Grassmannian and further explored by Gian-Carlo Rota with collaborators, de Concini and Procesi, and Eisenbud. The Littlewood–Richardson rule describing (among other things) the decomposition of tensor products of irreducible representations of Template:Math into irreducible components is formulated in terms of certain skew semistandard tableaux.
Applications to algebraic geometry center around Schubert calculus on Grassmannians and flag varieties. Certain important cohomology classes can be represented by Schubert polynomials and described in terms of Young tableaux.
Applications in representation theoryEdit
Template:See also Young diagrams are in one-to-one correspondence with irreducible representations of the symmetric group over the complex numbers. They provide a convenient way of specifying the Young symmetrizers from which the irreducible representations are built. Many facts about a representation can be deduced from the corresponding diagram. Below, we describe two examples: determining the dimension of a representation and restricted representations. In both cases, we will see that some properties of a representation can be determined by using just its diagram. Young tableaux are involved in the use of the symmetric group in quantum chemistry studies of atoms, molecules and solids.<ref>Philip R. Bunker and Per Jensen (1998) Molecular Symmetry and Spectroscopy, 2nd ed. NRC Research Press, Ottawa [1] pp.198-202.Template:ISBN</ref><ref>R.Pauncz (1995) The Symmetric Group in Quantum Chemistry, CRC Press, Boca Raton, Florida</ref>
Young diagrams also parametrize the irreducible polynomial representations of the general linear group Template:Math (when they have at most Template:Mvar nonempty rows), or the irreducible representations of the special linear group Template:Math (when they have at most Template:Math nonempty rows), or the irreducible complex representations of the special unitary group Template:Math (again when they have at most Template:Math nonempty rows). In these cases semistandard tableaux with entries up to Template:Mvar play a central role, rather than standard tableaux; in particular it is the number of those tableaux that determines the dimension of the representation.
Dimension of a representationEdit
{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Template:Plain image with caption
The dimension of the irreducible representation Template:Math of the symmetric group Template:Math corresponding to a partition Template:Mvar of Template:Mvar is equal to the number of different standard Young tableaux that can be obtained from the diagram of the representation. This number can be calculated by the hook length formula.
A hook length Template:Math of a box Template:Mvar in Young diagram Template:Math of shape Template:Mvar is the number of boxes that are in the same row to the right of it plus those boxes in the same column below it, plus one (for the box itself). By the hook-length formula, the dimension of an irreducible representation is Template:Math divided by the product of the hook lengths of all boxes in the diagram of the representation:
- <math>\dim\pi_\lambda = \frac{n!}{\prod_{x \in Y(\lambda)} \operatorname{hook}(x)}.</math>
The figure on the right shows hook-lengths for all boxes in the diagram of the partition 10 = 5 + 4 + 1. Thus
- <math>\dim\pi_\lambda = \frac{10!}{7\cdot5\cdot 4 \cdot 3\cdot 1\cdot 5\cdot 3\cdot 2\cdot 1\cdot1} = 288.</math>
Similarly, the dimension of the irreducible representation Template:Math of Template:Math corresponding to the partition λ of n (with at most r parts) is the number of semistandard Young tableaux of shape λ (containing only the entries from 1 to r), which is given by the hook-length formula:
- <math>\dim W(\lambda) = \prod_{(i,j) \in Y(\lambda)} \frac{r+j-i}{\operatorname{hook}(i,j)},</math>
where the index i gives the row and j the column of a box.<ref>Template:Cite book, eq. 9.28 and appendix B.4</ref> For instance, for the partition (5,4,1) we get as dimension of the corresponding irreducible representation of Template:Math (traversing the boxes by rows):
- <math>\dim W(\lambda) = \frac{7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 6\cdot 7\cdot 8\cdot 9\cdot 5}{7\cdot5\cdot 4 \cdot 3\cdot 1\cdot 5\cdot 3\cdot 2\cdot 1\cdot1} = 66 528.</math>
Restricted representationsEdit
A representation of the symmetric group on Template:Mvar elements, Template:Math is also a representation of the symmetric group on Template:Math elements, Template:Math. However, an irreducible representation of Template:Math may not be irreducible for Template:Math. Instead, it may be a direct sum of several representations that are irreducible for Template:Math. These representations are then called the factors of the restricted representation (see also induced representation).
The question of determining this decomposition of the restricted representation of a given irreducible representation of Sn, corresponding to a partition Template:Mvar of Template:Mvar, is answered as follows. One forms the set of all Young diagrams that can be obtained from the diagram of shape Template:Mvar by removing just one box (which must be at the end both of its row and of its column); the restricted representation then decomposes as a direct sum of the irreducible representations of Template:Math corresponding to those diagrams, each occurring exactly once in the sum.
See alsoEdit
NotesEdit
ReferencesEdit
- William Fulton. Young Tableaux, with Applications to Representation Theory and Geometry. Cambridge University Press, 1997, Template:Isbn.
- Template:Fulton-Harris Lecture 4
- Howard Georgi, Lie Algebras in Particle Physics, 2nd Edition - Westview
- Macdonald, I. G. Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, Oxford, 1979. viii+180 pp. Template:Isbn Template:MathSciNet
- Laurent Manivel. Symmetric Functions, Schubert Polynomials, and Degeneracy Loci. American Mathematical Society.
- Template:Cite journal
- Jean-Christophe Novelli, Igor Pak, Alexander V. Stoyanovskii, "A direct bijective proof of the Hook-length formula", Discrete Mathematics and Theoretical Computer Science 1 (1997), pp. 53–67.
- Bruce E. Sagan. The Symmetric Group. Springer, 2001, Template:Isbn
- Template:Eom
- Template:Cite journal
- Predrag Cvitanović, Group Theory: Birdtracks, Lie's, and Exceptional Groups. Princeton University Press, 2008.
External linksEdit
- Eric W. Weisstein. "Ferrers Diagram". From MathWorld—A Wolfram Web Resource.
- Eric W. Weisstein. "Young Tableau." From MathWorld—A Wolfram Web Resource.
- Semistandard tableaux entry in the FindStat database
- Standard tableaux entry in the FindStat database