FACTOID # 13: New York has America's lowest percentage of residents who are veterans.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Young tableau

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. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ... In mathematics Representation theory is the name given to the study of standard representations of abstract mathematical structures. ... Group representation theory is the branch of mathematics that studies properties of abstract groups via their representations as linear transformations of vector spaces. ... In mathematics, the symmetric group on a set X, denoted by SX or Sym(X), is the group whose underlying set is the set of all bijective functions from X to X, in which the group operation is that of composition of functions, i. ...


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. Alfred Young (16 April 1873 - 15 December 1940) was a mathematician born in Widnes, Lancashire, England. ... Leonhard Euler, one of the greatest mathematicians of all time A mathematician is a person whose primary area of study and research is the field of mathematics. ... The University of Cambridge (often Cambridge University), located in Cambridge, England, is the second-oldest university in the English-speaking world and has a reputation as one of the worlds most prestigious universities. ... Picture of Frobenius Ferdinand Georg Frobenius (October 26, 1849 - August 3, 1917) was a German mathematician, best-known for his contributions to the theory of differential equations and to group theory. ... Percy Alexander MacMahon Percy Alexander MacMahon (b. ... An editor has expressed a concern that the subject of the article does not satisfy the notability guideline for Biographies. ... Gian-Carlo Rota (April 27, 1932 – April 18, 1999, known as Juan Carlos Rota to Spanish speakers) was an Italian-born American mathematician and philosopher. ... Marcel-Paul Marco Schützenberger (24 October 1920 - 29 July 1996) was a French mathematician and Doctor of Medicine with impact across the fields of formal language, combinatorics, and information theory. ... Richard P. Stanley (born 1944) is Norman Levinson Professor of Applied Mathematics at the Massachusetts Institute of Technology, in Cambridge, Massachusetts. ...

Contents

Definitions

Young diagram

The Young diagram for the partition 10 = 5 + 4 + 1
A 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 = k1 + k2 + ... + km, where k1k2 ≥ .... A partition can be described by a Young diagram which consists of m rows, with the first row containing k1 boxes, the second row containing k2 boxes, etc. Each row is left-justified. Image File history File links No higher resolution available. ... In mathematics, a partition of a positive integer n is a way of writing n as a sum of positive integers. ... In mathematics, a partition of a positive integer n is a way of writing n as a sum of positive integers. ...


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.


Young tableau

One of Young tableaux for the partition 10=5+4+1
A 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: Image File history File links No higher resolution available. ...

  • 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 mathematics, the multiplicity of a member of a multiset is how many memberships in the multiset it has. ...

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

A semi-standard tableau may have any entries 1, 2, ..., t, where t is usually explicitly specified. Not all numbers from the set 1, 2, ..., t need to appear in a semi-standard Young tableaux, and some may appear more than once. Because the numbers need to increase in rows, we must have tge m in order for the semi-standard Young tableaux to exist.


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. In mathematics, the term irreducible is used in several ways. ... In mathematics, the symmetric group on a set X, denoted by SX or Sym(X), is the group whose underlying set is the set of all bijective functions from X to X, in which the group operation is that of composition of functions, i. ... In mathematics, a complex number is a number of the form where a and b are real numbers, and i is the imaginary unit, with the property i 2 = −1. ... In mathematics, a Young symmetrizer is an element of the group algebra of the symmetric group, constructed in such a way that the image of the element corresponds to an irreducible representation of the symmetric group. ... In mathematics, the permutation group SN has order N!. Its conjugacy classes are labeled by partitions of N. Therefore according to the representation theory of a finite group the number of inequivalent irreducible representations is equal to the number of partitions of N. They are labeled by Young diagrams. ...


Dimension of a representation

Hook-lengths of the boxes for the partition 10=5+4+1
Hook lengths

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. Image File history File links No higher resolution available. ...


A hook length operatorname{hook}(x) 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:

{rm dim} , pi_lambda = frac{n!}{prod_{x in 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 {rm dim} , pi_lambda = frac{10!}{1cdot1cdot 1 cdot 2cdot 3cdot 3cdot 4cdot 5cdot 5cdot7} = 288 .


Restricted representations

A representation of the symmetric group on n elements, Sn is also a representation of the symmetric group on n − 1 elements, Sn−1. However, an irreducible representation of Sn may not be irreducible for Sn−1. Instead, it may be a direct sum of several representations that are irreducible for Sn−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 Sn. In abstract algebra, the direct sum is a construction which combines several vector spaces (or groups, or abelian groups, or modules) into a new, bigger one. ... In mathematics, if G is a group and H a subgroup, then for any linear representation ρ of G, we can define the restricted representation ρ|H by simply setting ρ|H(h) = ρ(h). ... In mathematics, and in particular group representation theory, the induced representation is one of the major general operations for passing from a representation of a subgroup H to a representation of the (whole) group G itself. ...


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 Sn so that the result is still a valid diagram.


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. In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ...


See also

In mathematics, the Robinson–Schensted algorithm is a combinatorial algorithm, first discovered by Robinson in 1938, which establishes a bijective correspondence between elements of the symmetric group and pairs of standard Young tableaux of the same shape. ... In number theory, a partition of a positive integer n is a way of writing n as a sum of positive integers. ...

References

  • 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.

  Results from FactBites:
 
Science Fair Projects - Young tableau (846 words)
In mathematics, a Young tableau is a combinatorial object useful in representation theory.
The conjugate partition is 10 = 3 + 2 + 2 + 2 + 1.
Young diagrams are in one-to-one correspondence with irreducible representations of the symmetric group.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m