Young tableau
Inmathematics,aYoung tableau(/tæˈbloʊ,ˈtæbloʊ/;plural:tableaux) is acombinatorialobject useful inrepresentation theoryandSchubert calculus.It provides a convenient way to describe thegroup representationsof thesymmetricandgeneral lineargroups and to study their properties. Young tableaux were introduced byAlfred Young,amathematicianatCambridge University,in 1900.[1][2]They were then applied to the study of the symmetric group byGeorg Frobeniusin 1903. Their theory was further developed by many mathematicians, includingPercy MacMahon,W. V. D. Hodge,G. de B. Robinson,Gian-Carlo Rota,Alain Lascoux,Marcel-Paul SchützenbergerandRichard P. Stanley.
Definitions
[edit]Note: this article uses the English convention for displaying Young diagrams and tableaux.
Diagrams
[edit]![](https://upload.wikimedia.org/wikipedia/commons/thumb/f/f2/Young_diagram_for_541_partition.svg/150px-Young_diagram_for_541_partition.svg.png)
![](https://upload.wikimedia.org/wikipedia/commons/thumb/a/a6/Young_diagram_for_541_partition-French.svg/150px-Young_diagram_for_541_partition-French.svg.png)
AYoung diagram(also called aFerrers 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 apartitionλof a non-negative integern,the total number of boxes of the diagram. The Young diagram is said to be of shapeλ,and it carries the same information as that partition. Containment of one Young diagram in another defines apartial orderingon the set of all partitions, which is in fact alatticestructure, known asYoung's lattice.Listing the number of boxes of a Young diagram in each column gives another partition, theconjugateortransposepartition ofλ;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 byAnglophoneswhile the latter is often preferred byFrancophones,it is customary to refer to these conventions respectively as theEnglish notationand theFrench notation;for instance, in his book onsymmetric functions,Macdonaldadvises 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 ofCartesian 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 length
[edit]In many applications, for example when definingJack functions,it is convenient to define thearm lengthaλ(s) of a boxsas the number of boxes to the right ofsin the diagram λ in English notation. Similarly, theleg lengthlλ(s) is the number of boxes belows.Thehook lengthof a boxsis the number of boxes to the right ofsor belowsin English notation, including the boxsitself; in other words, the hook length isaλ(s) +lλ(s) + 1.
Tableaux
[edit]![](https://upload.wikimedia.org/wikipedia/commons/thumb/4/40/Young_tableaux_for_541_partition.svg/150px-Young_tableaux_for_541_partition.svg.png)
AYoung tableauis obtained by filling in the boxes of the Young diagram with symbols taken from somealphabet,which is usually required to be atotally ordered set.Originally that alphabet was a set of indexed variablesx1,x2,x3..., but now one usually uses a set of numbers for brevity. In their original application torepresentations of the symmetric group,Young tableaux havendistinct entries, arbitrarily assigned to boxes of the diagram. A tableau is calledstandardif the entries in each row and each column are increasing. The number of distinct standard Young tableaux onnentries is given by theinvolution numbers
- 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496,... (sequenceA000085in theOEIS).
All 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 calledsemistandard,orcolumn 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 theweightof the tableau. Thus the standard Young tableaux are precisely the semistandard tableaux of weight (1,1,...,1), which requires every integer up tonto occur exactly once.
In a standard Young tableau, the integeris adescentifappears in a row strictly below.The sum of the descents is called themajor indexof the tableau.[3]
Variations
[edit]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 withdecreasingentries have been considered, notably, in the theory ofplane 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 tableaux
[edit]![](https://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Skew_tableau_5422-21.svg/150px-Skew_tableau_5422-21.svg.png)
Askew shapeis a pair of partitions (λ,μ) such that the Young diagram ofλcontains the Young diagram ofμ;it is denoted byλ/μ.Ifλ= (λ1,λ2,...)andμ= (μ1,μ2,...),then the containment of diagrams means thatμi≤λifor alli.Theskew diagramof a skew shapeλ/μis the set-theoretic difference of the Young diagrams ofλandμ:the set of squares that belong to the diagram ofλbut not to that ofμ.Askew tableauof shapeλ/μ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;[4]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λandμ,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.[5]Young tableaux can be identified with skew tableaux in whichμis the empty partition (0) (the unique partition of 0).
Any skew semistandard tableauTof shapeλ/μwith positive integer entries gives rise to a sequence of partitions (or Young diagrams), by starting withμ,and taking for the partitioniplaces further in the sequence the one whose diagram is obtained from that ofμby adding all the boxes that contain a value ≤iinT;this partition eventually becomes equal toλ.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 calledhorizontal strips.This sequence of partitions completely determinesT,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λandμin the data comprising the skew tableau.
Overview of applications
[edit]Young tableaux have numerous applications incombinatorics,representation theory,andalgebraic geometry.Various ways of counting Young tableaux have been explored and lead to the definition of and identities forSchur functions.
Many combinatorial algorithms on tableaux are known, including Schützenberger'sjeu de taquinand theRobinson–Schensted–Knuth correspondence.Lascoux and Schützenberger studied anassociativeproduct on the set of all semistandard Young tableaux, giving it the structure called theplactic monoid(French:le monoïde plaxique).
In representation theory, standard Young tableaux of sizekdescribe bases in irreducible representations of thesymmetric grouponkletters. Thestandard monomial basisin a finite-dimensionalirreducible representationof thegeneral linear groupGLnare parametrized by the set of semistandard Young tableaux of a fixed shape over the alphabet {1, 2,...,n}. This has important consequences forinvariant theory,starting from the work ofHodgeon thehomogeneous coordinate ringof theGrassmannianand further explored byGian-Carlo Rotawith collaborators,de ConciniandProcesi,andEisenbud.TheLittlewood–Richardson ruledescribing (among other things) the decomposition oftensor productsof irreducible representations ofGLninto irreducible components is formulated in terms of certain skew semistandard tableaux.
Applications to algebraic geometry center aroundSchubert calculuson Grassmannians andflag varieties.Certain importantcohomology classescan be represented bySchubert polynomialsand described in terms of Young tableaux.
Applications in representation theory
[edit]Young diagrams are in one-to-one correspondence withirreducible representationsof thesymmetric groupover thecomplex numbers.They provide a convenient way of specifying theYoung symmetrizersfrom which theirreducible representationsare 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.[6][7]
Young diagrams also parametrize the irreducible polynomial representations of thegeneral linear groupGLn(when they have at mostnnonempty rows), or the irreducible representations of thespecial linear groupSLn(when they have at mostn− 1nonempty rows), or the irreducible complex representations of thespecial unitary groupSUn(again when they have at mostn− 1nonempty rows). In these cases semistandard tableaux with entries up tonplay 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 representation
[edit]The dimension of the irreducible representationπλof the symmetric groupSncorresponding to a partitionλofnis 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 thehook length formula.
Ahook lengthhook(x)of a boxxin Young diagramY(λ)of shapeλ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 isn!divided by the product of the hook lengths of all boxes in the diagram of the representation:
The figure on the right shows hook-lengths for all boxes in the diagram of the partition 10 = 5 + 4 + 1. Thus
Similarly, the dimension of the irreducible representationW(λ)ofGLrcorresponding to the partitionλofn(with at mostrparts) is the number of semistandard Young tableaux of shapeλ(containing only the entries from 1 tor), which is given by the hook-length formula:
where the indexigives the row andjthe column of a box.[8]For instance, for the partition (5,4,1) we get as dimension of the corresponding irreducible representation ofGL7(traversing the boxes by rows):
Restricted representations
[edit]A representation of the symmetric group onnelements,Snis also a representation of the symmetric group onn− 1elements,Sn−1.However, an irreducible representation ofSnmay not be irreducible forSn−1.Instead, it may be adirect sumof several representations that are irreducible forSn−1.These representations are then called the factors of therestricted representation(see alsoinduced representation).
The question of determining this decomposition of the restricted representation of a given irreducible representation ofSn,corresponding to a partitionλofn,is answered as follows. One forms the set of all Young diagrams that can be obtained from the diagram of shapeλ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 ofSn−1corresponding to those diagrams, each occurring exactly once in the sum.
See also
[edit]Notes
[edit]- ^Knuth, Donald E.(1973),The Art of Computer Programming, Vol. III: Sorting and Searching(2nd ed.), Addison-Wesley, p. 48,
Such arrangements were introduced by Alfred Young in 1900
. - ^Young, A. (1900),"On quantitative substitutional analysis",Proceedings of the London Mathematical Society,Series 1,33(1): 97–145,doi:10.1112/plms/s1-33.1.97.See in particular p. 133.
- ^Stembridge, John (1989-12-01)."On the eigenvalues of representations of reflection groups and wreath products".Pacific Journal of Mathematics.140(2). Mathematical Sciences Publishers: 353–396.doi:10.2140/pjm.1989.140.353.ISSN0030-8730.
- ^For instance the skew diagram consisting of a single square at position (2,4) can be obtained by removing the diagram ofμ= (5,3,2,1)from the one ofλ= (5,4,2,1),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.
- ^A somewhat similar situation arises for matrices: the 3-by-0 matrixAmust be distinguished from the 0-by-3 matrixB,sinceABis a 3-by-3 (zero) matrix whileBAis the 0-by-0 matrix, but bothAandBhave 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.
- ^Philip R. Bunker and Per Jensen (1998)Molecular Symmetry and Spectroscopy, 2nd ed. NRC Research Press, Ottawa[1] pp.198-202.ISBN9780660196282
- ^R.Pauncz (1995)The Symmetric Group in Quantum Chemistry, CRC Press, Boca Raton, Florida
- ^Predrag Cvitanović(2008).Group Theory: Birdtracks, Lie's, and Exceptional Groups.Princeton University Press.,eq. 9.28 and appendix B.4
References
[edit]- William Fulton.Young Tableaux, with Applications to Representation Theory and Geometry.Cambridge University Press, 1997,ISBN0-521-56724-6.
- Fulton, William;Harris, Joe(1991).Representation theory. A first course.Graduate Texts in Mathematics,Readings in Mathematics. Vol. 129. New York: Springer-Verlag.doi:10.1007/978-1-4612-0979-9.ISBN978-0-387-97495-8.MR1153249.OCLC246650103.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.ISBN0-19-853530-9MR553598
- Laurent Manivel.Symmetric Functions, Schubert Polynomials, and Degeneracy Loci.American Mathematical Society.
- Greene, Curtis;Nijenhuis, Albert;Wilf, Herbert S.(1979)."A probabilistic proof of a formula for the number of Young tableaux of a given shape".Advances in Mathematics.31(1). Amsterdam:Elsevier:104–109.doi:10.1016/0001-8708(79)90023-9.MR0521470.Zbl0398.05008.
- Jean-Christophe Novelli,Igor Pak,Alexander V. Stoyanovskii, "A direct bijective proof of the Hook-length formula",Discrete Mathematics and Theoretical Computer Science1(1997), pp. 53–67.
- Bruce E. Sagan.The Symmetric Group.Springer, 2001,ISBN0-387-95067-2
- Vinberg, E.B.(2001) [1994],"Young tableau",Encyclopedia of Mathematics,EMS Press
- Yong, Alexander (February 2007)."What is...a Young Tableau?"(PDF).Notices of the American Mathematical Society.54(2): 240–241.Retrieved2008-01-16.
- Predrag Cvitanović,Group Theory: Birdtracks, Lie's, and Exceptional Groups.Princeton University Press, 2008.
External links
[edit]- Eric W. Weisstein. "Ferrers Diagram".From MathWorld—A Wolfram Web Resource.
- Eric W. Weisstein. "Young Tableau."From MathWorld—A Wolfram Web Resource.
- Semistandard tableauxentry in theFindStatdatabase
- Standard tableauxentry in theFindStatdatabase