Namespaces
Variants
Actions

Difference between revisions of "Young tableau"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex done)
 
Line 1: Line 1:
 +
 
''of order $m$''
 
''of order $m$''
  
Line 25: Line 26:
 
In Western literature the phrase Ferrers diagram is also used for a Young diagram. In the Russian literature the phrase  "Young tableau"  ( "Yunga tablitsa" ) and  "Young diagram"  ( "Yunga diagramma" ) are used precisely in the opposite way, with  "tablitsa"  referring to the pictorial representation of a partition and  "diagramma"  being a filled-in  "tablitsa" .
 
In Western literature the phrase Ferrers diagram is also used for a Young diagram. In the Russian literature the phrase  "Young tableau"  ( "Yunga tablitsa" ) and  "Young diagram"  ( "Yunga diagramma" ) are used precisely in the opposite way, with  "tablitsa"  referring to the pictorial representation of a partition and  "diagramma"  being a filled-in  "tablitsa" .
  
Let $\kappa$ denote a [[partition]] of $m$ ($\kappa=(\kappa_1,\ldots,\kappa_t)$, $\kappa_i \in \{0,1,\ldots\}$, $\kappa_1+\cdots+\kappa_t=m$) as well as its corresponding [[Young diagram]], its pictorial representation. Let $\lambda$ be a second partition of $m$. A $\kappa$-tableau of type $\lambda$ is a Young diagram $\kappa$ with its boxes filled with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910025.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910026.png" />'s, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910027.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910028.png" />'s, etc. For a semi-standard $\kappa$-tableau of type $\lambda$, the labelling of the boxes is such that the rows are non-decreasing (from left to right) and the columns are strictly increasing (from top to bottom). E.g.
+
Let $\kappa$ denote a [[partition]] of $m$ ($\kappa=(\kappa_1,\ldots,\kappa_t)$, $\kappa_i \in \{0,1,\ldots\}$, $\kappa_1+\cdots+\kappa_t=m$) as well as its corresponding [[Young diagram]], its pictorial representation. Let $\lambda$ be a second partition of $m$. A $\kappa$-tableau of type $\lambda$ is a Young diagram $\kappa$ with its boxes filled with $\lambda_1$ $1$'s, $\lambda_2$ $2$'s, etc. For a semi-standard $\kappa$-tableau of type $\lambda$, the labelling of the boxes is such that the rows are non-decreasing (from left to right) and the columns are strictly increasing (from top to bottom). E.g.
  
 
<pre style="font-family: monospace;color:black">
 
<pre style="font-family: monospace;color:black">
Line 39: Line 40:
 
is a semi-standard $(5,3,2)$-tableau of type $(4,2,2,2)$. The numbers $K(\kappa,\lambda)$ of semi-standard $\kappa$-tableaux of type $\lambda$ are called Kostka numbers.
 
is a semi-standard $(5,3,2)$-tableau of type $(4,2,2,2)$. The numbers $K(\kappa,\lambda)$ of semi-standard $\kappa$-tableaux of type $\lambda$ are called Kostka numbers.
  
To each partition $\mu$ of $n$, there are associated two  "natural"  representations of $S_n$, the symmetric group on $n$ letters: the induced representation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910043.png" /> and the Specht module <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910044.png" />. The representation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910045.png" /> is:
+
To each partition $\mu$ of $n$, there are associated two  "natural"  representations of $S_n$, the symmetric group on $n$ letters: the induced representation $\rho(\mu)$ and the Specht module $[\mu]$. The representation $\rho(u)$ is:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910046.png" /></td> </tr></table>
+
$$
 +
\rho(\mu) = \operatorname{Ind}_{G_\mu}^{S_n} 1,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910047.png" /> is the [[trivial representation]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910048.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910049.png" /> is the Young subgroup of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910050.png" /> determined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910051.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910052.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910053.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910054.png" /> and otherwise <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910055.png" /> is the subgroup of permutations on the letters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910056.png" />.
+
where $1$ is the [[trivial representation]] of $G_\mu$ and $G_\mu$ is the Young subgroup of $S_n$ determined by $\mu$, $G_\mu = S_{\mu_1} \times \cdots \times S_{\mu_m}$, where $S_{\mu_i} = \{1\}$ if $\mu_i = 0$ and otherwise $S_{\mu_i}$ is the subgroup of permutations on the letters $\mu_1 + \dots + \mu_{i-1} + 1, \ldots, \mu_1 + \dots + \mu_i$.
  
The group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910057.png" /> acts on the set of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910059.png" />-tableaux by permuting the labels. Two <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910060.png" />-tableaux are equivalent if they differ by a permutation of their labels keeping the sets of indices in each row set-wise invariant. An equivalence class of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910061.png" />-tableaux is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910062.png" />-tabloid. The action of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910063.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910064.png" />-tableaux induces an action on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910065.png" />-tabloids, and extending this linearly over a base field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910066.png" /> gives a representation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910067.png" /> which is evidently isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910068.png" />. The dimension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910069.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910070.png" />. Given a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910071.png" />-tableau <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910072.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910073.png" /> be the following element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910074.png" />:
+
The group $S_n$ acts on the set of all $\mu$-tableaux by permuting the labels. Two $\mu$-tableaux are equivalent if they differ by a permutation of their labels keeping the sets of indices in each row set-wise invariant. An equivalence class of $\mu$-tableaux is a $\mu$-tabloid. The action of $S_n$ on $\mu$-tableaux induces an action on $\mu$-tabloids, and extending this linearly over a base field $F$ gives a representation of $S_n$ which is evidently isomorphic to $\rho(\mu)$. The dimension of $\rho(\mu)$ is $(\square_\mu^n)$. Given a $\mu$-tableau $t$, let $\kappa_\tau$ be the following element of $F[S_n]$:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910075.png" /></td> </tr></table>
+
$$
 +
\kappa_t = \sum_{\pi \in C_t} \operatorname{sign}(\pi) \pi,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910076.png" /> is the column-stabilizer of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910077.png" />, i.e. the subgroup of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910078.png" /> of all permutations that leave the labels of the columns of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910079.png" /> set-wise invariant.
+
where $C_t$ is the column-stabilizer of $t$, i.e. the subgroup of $S_n$ of all permutations that leave the labels of the columns of $t$ set-wise invariant.
  
The Specht module, $[\mu]$, of $\mu$ is the submodule of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910082.png" /> spanned by all the elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910083.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910084.png" /> is the tabloid of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910085.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910086.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910087.png" />-tableau. Over a field of characteristic zero the Specht modules give precisely all the different absolutely-irreducible representations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910088.png" />. By Young's rule, the number of times that the Specht module <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/y/y099/y099100/y09910089.png" /> over $\mathbf{Q}$ occurs (as a composition factor) in $\rho(\kappa)$ is equal to the Kostka number $K(\kappa,\lambda)$. If $e_t$ is the [[Young symmetrizer]] of a $\mu$-tableau $t$, then the Specht module defined by the underlying diagram is isomorphic to the ideal $F[S_n]e_t$ of $F[S_n]$. This is also (up to isomorphism) the representation denoted by $T_{\mu}$ in [[Representation of the symmetric groups]]. Cf. [[Majorization ordering]] for a number of other results involving partitions, Young diagrams and tableaux, and representations of the symmetric groups.
+
The Specht module, $[\mu]$, of $\mu$ is the submodule of $\rho(\mu)$ spanned by all the elements $\kappa_t\{t\}$, where $\{t\}$ is the tabloid of $t$ and $t$ is a $\mu$-tableau. Over a field of characteristic zero the Specht modules give precisely all the different absolutely-irreducible representations of $S_n$. By Young's rule, the number of times that the Specht module $[\lambda]$ over $\mathbf{Q}$ occurs (as a composition factor) in $\rho(\kappa)$ is equal to the Kostka number $K(\kappa,\lambda)$. If $e_t$ is the [[Young symmetrizer]] of a $\mu$-tableau $t$, then the Specht module defined by the underlying diagram is isomorphic to the ideal $F[S_n]e_t$ of $F[S_n]$. This is also (up to isomorphism) the representation denoted by $T_{\mu}$ in [[Representation of the symmetric groups]]. Cf. [[Majorization ordering]] for a number of other results involving partitions, Young diagrams and tableaux, and representations of the symmetric groups.
  
 
====References====
 
====References====
Line 58: Line 63:
 
</table>
 
</table>
  
{{TEX|want}}
+
{{TEX|done}}

Latest revision as of 03:36, 15 February 2024

of order $m$

A Young diagram of order $m$ in whose cells the different numbers $1,\ldots,m$ have been inserted in some order, e.g.

┌───┬───┬───┬───┐
│ 5 │ 7 │ 9 │ 4 │
├───┼───┼───┼───┘
│ 8 │ 2 │ 1 │    
├───┼───┴───┘    
│ 3 │            
├───┤            
│ 6 │            
└───┘ 

A Young tableau is called standard if in each row and in each column the numbers occur in increasing order. The number of all Young tableaux for a given Young diagram $t$ of order $m$ is equal to $m!$ and the number of standard Young tableaux is $$ \frac{m!}{\prod\lambda_{ij}} $$

where the product extends over all the cells $c_{ij}$ of $t$ and $\lambda_{ij}$ denotes the length of the corresponding hook.

Comments

In Western literature the phrase Ferrers diagram is also used for a Young diagram. In the Russian literature the phrase "Young tableau" ( "Yunga tablitsa" ) and "Young diagram" ( "Yunga diagramma" ) are used precisely in the opposite way, with "tablitsa" referring to the pictorial representation of a partition and "diagramma" being a filled-in "tablitsa" .

Let $\kappa$ denote a partition of $m$ ($\kappa=(\kappa_1,\ldots,\kappa_t)$, $\kappa_i \in \{0,1,\ldots\}$, $\kappa_1+\cdots+\kappa_t=m$) as well as its corresponding Young diagram, its pictorial representation. Let $\lambda$ be a second partition of $m$. A $\kappa$-tableau of type $\lambda$ is a Young diagram $\kappa$ with its boxes filled with $\lambda_1$ $1$'s, $\lambda_2$ $2$'s, etc. For a semi-standard $\kappa$-tableau of type $\lambda$, the labelling of the boxes is such that the rows are non-decreasing (from left to right) and the columns are strictly increasing (from top to bottom). E.g.

┌───┬───┬───┬───┬───┐
│ 1 │ 1 │ 1 │ 1 │ 4 │
├───┼───┼───┼───┴───┘
│ 2 │ 2 │ 3 │        
├───┼───┼───┘        
│ 3 │ 4 │            
└───┴───┘ 

is a semi-standard $(5,3,2)$-tableau of type $(4,2,2,2)$. The numbers $K(\kappa,\lambda)$ of semi-standard $\kappa$-tableaux of type $\lambda$ are called Kostka numbers.

To each partition $\mu$ of $n$, there are associated two "natural" representations of $S_n$, the symmetric group on $n$ letters: the induced representation $\rho(\mu)$ and the Specht module $[\mu]$. The representation $\rho(u)$ is:

$$ \rho(\mu) = \operatorname{Ind}_{G_\mu}^{S_n} 1, $$

where $1$ is the trivial representation of $G_\mu$ and $G_\mu$ is the Young subgroup of $S_n$ determined by $\mu$, $G_\mu = S_{\mu_1} \times \cdots \times S_{\mu_m}$, where $S_{\mu_i} = \{1\}$ if $\mu_i = 0$ and otherwise $S_{\mu_i}$ is the subgroup of permutations on the letters $\mu_1 + \dots + \mu_{i-1} + 1, \ldots, \mu_1 + \dots + \mu_i$.

The group $S_n$ acts on the set of all $\mu$-tableaux by permuting the labels. Two $\mu$-tableaux are equivalent if they differ by a permutation of their labels keeping the sets of indices in each row set-wise invariant. An equivalence class of $\mu$-tableaux is a $\mu$-tabloid. The action of $S_n$ on $\mu$-tableaux induces an action on $\mu$-tabloids, and extending this linearly over a base field $F$ gives a representation of $S_n$ which is evidently isomorphic to $\rho(\mu)$. The dimension of $\rho(\mu)$ is $(\square_\mu^n)$. Given a $\mu$-tableau $t$, let $\kappa_\tau$ be the following element of $F[S_n]$:

$$ \kappa_t = \sum_{\pi \in C_t} \operatorname{sign}(\pi) \pi, $$

where $C_t$ is the column-stabilizer of $t$, i.e. the subgroup of $S_n$ of all permutations that leave the labels of the columns of $t$ set-wise invariant.

The Specht module, $[\mu]$, of $\mu$ is the submodule of $\rho(\mu)$ spanned by all the elements $\kappa_t\{t\}$, where $\{t\}$ is the tabloid of $t$ and $t$ is a $\mu$-tableau. Over a field of characteristic zero the Specht modules give precisely all the different absolutely-irreducible representations of $S_n$. By Young's rule, the number of times that the Specht module $[\lambda]$ over $\mathbf{Q}$ occurs (as a composition factor) in $\rho(\kappa)$ is equal to the Kostka number $K(\kappa,\lambda)$. If $e_t$ is the Young symmetrizer of a $\mu$-tableau $t$, then the Specht module defined by the underlying diagram is isomorphic to the ideal $F[S_n]e_t$ of $F[S_n]$. This is also (up to isomorphism) the representation denoted by $T_{\mu}$ in Representation of the symmetric groups. Cf. Majorization ordering for a number of other results involving partitions, Young diagrams and tableaux, and representations of the symmetric groups.

References

[a1] D. Knuth, "The art of computer programming" , 3 , Addison-Wesley (1973)
How to Cite This Entry:
Young tableau. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Young_tableau&oldid=54786
This article was adapted from an original article by E.B. Vinberg (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article