Young tableau

From Wikipedia, the free encyclopedia

In mathematics, a Young tableau is a combinatorial object useful in representation theory. It provides a convenient way to describe the group representations of the symmetric group 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. The theory was further developed by Alfred Young, and by other mathematicians including Alain Lascoux, Percy MacMahon, G. de B. Robinson, Gian-Carlo Rota, Marcel-Paul Schützenberger and Richard P. Stanley.

Contents 1 Definitions 1.1 Young diagram 1.2 Young tableau 2 Applications in representation theory 2.1 Dimension of a representation 2.2 Restricted representations 2.3 Constructing representations 3 See also 4 References

[edit] Definitions

[edit] Young diagram

A Young diagram (also called Ferrers diagram) is a way to represent partitions of a number n. Let n be a natural number. A partition is a way of expressing n as a sum of natural numbers: n = k₁ + k₂ + ... + k_m, where k₁ ≥ k₂ ≥ .... A partition can be described by a Young diagram which consists of m rows, with the first row containing k₁ boxes, the second row containing k₂ boxes, etc. Each row is left-justified.

Let's call this partition k (dropping the subscript, but remembering that it is there). Then the partition conjugate to k is the partition of n consisting of the count of boxes in each column. That is, for each Young diagram, there is a conjugate diagram which has the horizontal and vertical reflected across the diagonal.

The figure on the right shows the Young diagram corresponding to the partition 10 = 5 + 4 + 1. The conjugate partition is 10 = 3 + 2 + 2 + 2 + 1.

[edit] Young tableau

A Young tableau is obtained by taking a Young diagram and writing numbers 1, 2, ..., n into n boxes of this diagram, subject to the following constraints:

• in each row, the numbers must be increasing from left to right;
• in each column, the numbers must be increasing from top to bottom.

If each number appears in exactly one square, the tableau is called a standard tableau. The figure on the right shows one of the standard Young tableaux for the partition 10 = 5 + 4 + 1.

Semi-standard tableaux are a variant of this object in which a number can appear in more than one square (with multiplicity greater than one). For semi-standard tableaux, the first constraint above is weakened:

• in each row, the numbers must be nondecreasing from left to right.

Thus, a semi-standard tableau may only have entries 1, 2, ..., m (the number of rows in the Young diagram) instead of 1, 2, ..., n (the number of squares in the Young diagram).

[edit] 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.

[edit] Dimension of a representation

The dimension of the irreducible representation π_λ corresponding to a partition λ is equal to the number of different Young tableaux that can be obtained from the diagram of the representation. This number can be calculated by hook-length formula.

A hook length of a box x in Young diagram λ 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:

The figure on the right shows hook-lengths for all boxes in the diagram of the partition 10 = 5 + 4 + 1. Thus .

[edit] 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 induced representations. The problem is to determine the induced representations, given a Young diagram for the representation of S_n.

The answer is that the induced 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.

[edit] Constructing representations

Young tableaux can be also used to construct representations of the symmetric group over arbitrary fields and to study their structure. In general these representations will no longer be irreducible.

[edit] See also

• Robinson-Schensted algorithm
• Partition (number theory)

[edit] References

• William Fulton. Young Tableaux, with Applications to Representation Theory and Geometry. Cambridge University Press, 1997.
• William Fulton and Joe Harris, Representation Theory, A First Course (1991) Springer Verlag New York, ISBN 0-387-974495-4 See Chapter 4
• Bruce E. Sagan. The Symmetric Group. Springer, 2001
• 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.