Young tableau

In mathematics, a Young tableau (pl.: tableaux) is a combinatorial object useful in representation theory. 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. They were then applied to the study of 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.

Definitions

Note: this article uses the English convention for displaying Young diagrams and tableaux.

A Young diagram (also called Ferrers diagram) is a finite collection of boxes, or cells, arranged in left-justified rows, with the row sizes weakly decreasing (each row has the same or shorter length than its predecessor). Listing the number of boxes in each row gives a partition ${\displaystyle \lambda }$  of a positive integer n, the total number of boxes of the diagram. The Young diagram is said to be of shape ${\displaystyle \lambda }$ , and it carries the same information as that partition. Listing the number of boxes in each column gives another partition, the conjugate or transpose parition of ${\displaystyle \lambda }$ ; one obtains a Young diagram of that shape by reflecting the orginal diagram along its main diagonal.

 

Young diagram of the partition (5, 4, 1)

There is almost universal agreement that in labelling 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 convenstions 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. This nomenclature probably started out as a joke: in his book on symmetric functions, Macdonald advises readers preferring the French convention to "read this book upside down in a mirror". The English notation corresponds to the one universally used for matrices, while the French notation is closer to the convention of Cartesian coordinates; note however that 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).

 

A standard Young tableau of shape (5, 4, 1)

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 used to be a set of indexed variables ${\displaystyle x_{1},x_{2},x_{3},\dots }$ , but nowadays one nearly always just uses some set of numbers (while this seems less profound, it obviously saves space). In their original application to representations of the symmetric group, Young tableaux have n distinct entries, arbirtarily assigned to boxes of the diagram, and within that set of taleaux those whose rows and columns are increasing are called standard. In other applications, it is more natural to view the standard Young tableaux as a subset of another set of tableaux, in which larger set the same number is allowed to appear more than once (or not at all). A tableau is then called semistandard, or column strict, if the entries weakly increase along the rows and strictly increase down the columns. Recording the number of times each integer appears in a semistandard tableau gives a sequence known as the weight of the tableau. Now the standard Young tableaux are precisely the semistandard tableaux of weight (1,1,…,1) (which requires every integer up to n to occur exactly once).

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 a domino tableaux or ribbon tableaux, in which several boxes may be grouped together before assigning entries to them.

A skew diagram is obtained by removing a smaller Young diagram from a larger one that contains it. If the smaller diagram is ${\displaystyle \mu =(\mu _{1},\mu _{2},\ldots )}$  and the larger diagram is ${\displaystyle \lambda =(\lambda _{1},\lambda _{2},\ldots )}$  then we must have ${\displaystyle \mu _{i}\leq \lambda _{i}}$  for all ${\displaystyle i}$ . There is however in general more than one way to obtain a given skew diagram in this way, for instance the skew diagram consisting of a single square at position (2,4) can be obtained by removing the diagram of ${\displaystyle \mu =(5,3,2,1)}$  from the one of ${\displaystyle \lambda =(5,4,2,1)}$ , but also in (infinitely) many other ways. Skew diagrams can be filled to form skew tableaux, and one can distinguish semistandard and standard skew tableaux in the same way as for Young tableaux. However, when using a skew diagram in such a way to build a tableau, one usually has in mind a specific way to to view the diagram as the difference between two Young diagrams, and many operations defined on skew tableaux in fact depend on a choice to so realize the skew diagram. It is then best to define the shape of a skew tableau not as the skew diagram being filled, but as a skew shape consisting explicitly of a pair of partitions ${\displaystyle (\mu ,\lambda )}$  satisfying ${\displaystyle \mu _{i}\leq \lambda _{i}}$  for all ${\displaystyle i}$ , and denoted ${\displaystyle \lambda /\mu }$ . Young tabelaux can be identified with skew tableaux in which ${\displaystyle \mu }$  is the empty partition (0) (the unique partition of 0).

Any skew semistandard tableau ${\displaystyle T}$  with positive integer entries gives rise to a sequence of partitions (or Young diagrams), by starting with ${\displaystyle \mu }$ , and taking for the partition ${\displaystyle i}$  places further in the sequence the one whose diagram is obtained from that of ${\displaystyle \mu }$  by adding all the boxes that contain a value ${\displaystyle \leq i}$  in ${\displaystyle T}$ . 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 ${\displaystyle T}$ , and it is in fact possible to define (skew) semistandard tableaux as such sequences, as is done in the mentioned book by Macdonald.

Overview of applications

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–Shensted–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 k describe bases in irreducible representations of the symmetric group on k letters. The standard monomial basis in a finite-dimensional irreducible representation of the general linear group GL_n are parametrized by the set of semistandard Young tableaux of a fixed shape over the alphabet ${\displaystyle \{1,2,\ldots ,n\}}$ . This has important consequences for invariant theory, starting from the work of Hodge on the homogeneous coordinate ring of the Grassmanian 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 GL_n into irreducible components is formulated in terms of certain skew semistandard tableaux.

Applications to algebraic geometry center around Schubert calculus on Grassmanians and flag varieties. Certain important cohomology classes can be represented by Schubert polynomials and described in terms of Young tableaux.

Applications in representation theory

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.

Dimension of a representation

 
Hook lengths

The dimension of the irreducible representation ${\displaystyle \pi _{\lambda }\,\!}$  of the symmetric group ${\displaystyle S_{n}}$ , corresponding to a partition ${\displaystyle \lambda \,\!}$  of ${\displaystyle n}$ , 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 hook-length formula.

A hook length ${\displaystyle \operatorname {hook} (x)}$  of a box ${\displaystyle x}$  in Young diagram ${\displaystyle Y(\lambda )\,\!}$  of shape ${\displaystyle \lambda \,\!}$  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 n! divided by the product of the hook lengths of all boxes in the diagram of the representation:

${\displaystyle {\rm {dim}}\,\pi _{\lambda }={\frac {n!}{\prod _{x\in Y(\lambda )}{\rm {hook}}(x)}}.}$ 

The figure on the right shows hook-lengths for all boxes in the diagram of the partition 10 = 5 + 4 + 1. Thus ${\displaystyle {\rm {dim}}\,\pi _{\lambda }={\frac {10!}{1\cdot 1\cdot 1\cdot 2\cdot 3\cdot 3\cdot 4\cdot 5\cdot 5\cdot 7}}=288}$ .

Restricted representations

A representation of the symmetric group on n elements, S_n is also a representation of the symmetric group on n − 1 elements, S_n−1. However, an irreducible representation of S_n may not be irreducible for S_n−1. Instead, it may be a direct sum of several representations that are irreducible for S_n−1. These representations are then called restricted representations (see also induced representations). The problem is to determine the restricted representations, given a Young diagram for the representation of S_n.

The answer is that the restricted representations are exactly the ones with Young diagrams which can be obtained by deleting one square from the Young diagram of the representation of S_n so that the result is still a valid diagram.

Young tableaux for SU(N) with examples

Connection between Young tableaux and Dynkin numbers

 

Given a representation R of G=SU(N) with Dynkin indexes (q₁ ...,q_k,.. q_N-1) its Young tableau consists of N-1 blocks each of k rows and q_k columns. Therefore in SU(3) the adjoint has Dynkin numbers (1,1) and its tableau is made of one block of one column and one row (since q₁=1) and a block of two rows and one column (since q₂=1). On the same footing you can find the result for (2,0) and (0,1), that are usually called the 6 and the 3* representations of SU(3).

Symmetry structure of a n-index tensor (representation) of SU(N)

A Tableau is a way to encode the symmetry structure of a representation. Assigning an index to each box we can link a n-box tableau to a n-index tensor. This tensor will be antisymmetric under the exchange of indexes belonging to the same column of the tableau and symmetric under the exchange of two indexes belonging to the same row of the tableau.

Multiplication rule of tableaux

 

The multiplication of Tableaux A and B, AxB, happen on the same footing of what shown before. You label each box in the first row one of the tableaux with the a letter, which the representative of an index of the tensor the tableau stands for. Say you label the first row of the tableau B with the letter a. Then you label the second row with the letter "b" and so on. Once you have labelled all the row the tableau B, you start building on the tableau A. You build first placing the a-s of the first row then the b's then the c's. The only rule you have to follow is that the resulting tableaux, at each stage, must have a number of boxes in each row which is greater or equal as you go from the last row to the first. The other rule is that in each row the number of a must be greater of the number of b.

Conservation of the n-ality

For SU(N) a column of N boxes represent an antisymmetrization of N indexes, therefore it corresponds to the ε tensor. This tensor is an invriant, therefore does not change the structure of the tensor the tableau represent. Thus you can delete all the columns with N boxes which appear in the tableau. For this reason in the product of tableaux A and B, with A made of i boxes and B made of k boxes,

i+k mod(N)

is the same in each term of the product. This is the consevation of the N-ality (i.e. triality for SU(3) and so and so forth).

Dimension of the representation

 

Computation of the dimension of the representation the tableau stands for is done by filling the boxes with numbers. For SU(N) you place N in the upper-left box. Then you fill the first row with N+1, N+2 ... and the first column with N-1, N-2, ... This will result in something like the picture. Then you compute the hook factor H and the tableau factor F. A hook is a path into the tableau which is straight and then turn right. A hook cross each box zero or one time. Each hook has a hook-factor which amounts to the number of boxes it cross. H is the product of all the possible hook factors. F is just the multiplication of the all the numbers you used to fill the tableaux. The dimension of the representation is

dim=F/H

Complex conjugation of a tableaux

 
Complex Conjugation

For SU(N) the representation R and R* have Young Tableaux which can be assembled in a rectangle of height N by mean of a rigid rotation of one of the two tableaux. Some example for SU(5) is provided in the picture. Notice for instance that the 24, which is the adjoint and therefore real, has the same tableau of the 24*.

Branching rules with Young tableaux

Young Tableaux can also be used to find how a representation R of the SU(N) transform as representation of the subgroup H. See Georgi for details.

Extensively expanded examples

Young tableaux can be used to compute the multiplications
3x3*=u^k v_i = 8+1 with
8=v_iu^k-1/3 δ_k^mv_mu^k
1=1/3 u_kv^k
6x3=10+8
Branching rules
3->2+1
8->3+2+2+1

See also

• Partition (number theory)
• Robinson-Schensted algorithm
• Schur–Weyl duality
• Young's lattice

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 MR 96h:05207 {{mr}}: Check mr value (help)
• William Fulton. Young Tableaux, with Applications to Representation Theory and Geometry. Cambridge University Press, 1997, ISBN 0521567246.
• William Fulton and Joe Harris, Representation Theory, A First Course (1991) Springer Verlag New York, ISBN 0-387-97495-4 See Chapter 4
• Bruce E. Sagan. The Symmetric Group. Springer, 2001, ISBN 0387950672
• Eric W. Weisstein. "Ferrers Diagram". From MathWorld--A Wolfram Web Resource.
• Eric W. Weisstein. "Young Tableau." From MathWorld--A Wolfram Web Resource.
• Jean-Christophe Novelli, Igor Pak, Alexander V. Stoyanovkii, "A direct bijective proof of the Hook-length formula", Discrete Mathematics and Theoretical Computer Science 1 (1997), pp.53–67.
• Howard Georgi, Lie Algebras in Particle Physics, 2nd Edition - Westview
• Yong, Alexander (2007). "What is...a Young Tableau?" (PDF). Notices of the American Mathematical Society. 54 (2): pp.240–241. Retrieved 2008-01-16. {{cite journal}}: |pages= has extra text (help); Unknown parameter |month= ignored (help)