フック長の公式 Connection to representation theory

ウィキペディア

フック長の公式

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/04/18 14:05 UTC 版)

Connection to representation theory

The hook-length formula is of great importance in the representation theory of the symmetric group $S_{n}$, where the number $d_{\lambda }$ is known to be equal to the dimension of the complex irreducible representation $V_{\lambda }$ associated to $\lambda$, and is frequently denoted by $\dim V_{\lambda }$, $\dim \lambda$ or $f^{\lambda }$.

Detailed discussion

The complex irreducible representations $V_{\lambda }$ of the symmetric group are indexed by partitions $\lambda$ of $n$ (for an explicit construction see Specht module) . Their characters are related to the theory of symmetric functions via the Hall inner product in the following formula

$\chi ^{\lambda }(w)=\langle s_{\lambda },p_{\tau (w)}\rangle$

where $s_{\lambda }$ is the Schur function associated to $\lambda$ and $p_{\tau (w)}$ is the power-sum symmetric function of the partition $\tau (w)$ associated to the cycle decomposition of $w$. For example, if $w=(154)(238)(6)(79)$ then $\tau (w)=(3,3,2,1)$.

Since the identity permutation $e$ has the form $e=(1)(2)\cdots (n)$ in cycle notation, $\tau (e)=1+1+\cdots +1=1^{(n)}$. Then the formula says

$\dim V_{\lambda }=\chi ^{\lambda }(e)=\langle s_{\lambda },p_{1^{(n)}}\rangle$

Considering the expansion of Schur functions in terms of monomial symmetric functions using the Kostka numbers

$s_{\lambda }=\sum _{\mu }K_{\lambda \mu }m_{\mu },$

the inner product with $p_{1^{(n)}}=h_{1^{(n)}}$ is $K_{\lambda 1^{(n)}}$, because $\langle m_{\mu },h_{\nu }\rangle =\delta _{\mu \nu }$. Note that $K_{\lambda 1^{(n)}}$ is equal to $d_{\lambda }$. Hence

$\dim V_{\lambda }=d_{\lambda }.$

An immediate consequence of this is

$\sum _{\lambda \vdash n}\left(f^{\lambda }\right)^{2}=n!$

The above equality is also a simple consequence of the Robinson–Schensted–Knuth correspondence.

The computation also shows that:

$(x_{1}+x_{2}+\cdots +x_{k})^{n}=\sum _{\lambda \vdash n}s_{\lambda }f^{\lambda }.$

Which is the expansion of $p_{1^{(n)}}$ in terms of Schur functions using the coefficients given by the inner product, because $\langle s_{\mu },s_{\nu }\rangle =\delta _{\mu \nu }$. The above equality can be proven also checking the coefficients of each monomial at both sides and using the Robinson–Schensted–Knuth correspondence or, more conceptually, looking at the decomposition of $V^{\otimes n}$ by irreducible $GL(V)$ modules, and taking characters. See Schur–Weyl duality.

Outline of the proof of the hook formula using Frobenius formula

By the above considerations

$p_{1^{(n)}}=\sum _{\lambda \vdash n}s_{\lambda }f^{\lambda }$

So that

$\Delta (x)p_{1^{(n)}}=\sum _{\lambda \vdash n}\Delta (x)s_{\lambda }f^{\lambda }$

where $\Delta (x)=\prod _{i<j}(x_{i}-x_{j})$ is the Vandermonde determinant.

For a given partition $\lambda =(\lambda _{1},\lambda _{2},\cdots ,\lambda _{k})$ define $l_{i}=\lambda _{i}+k-i$ for $i=1,2,\cdots ,k$. For the following we need at least as many variables as rows in the partition, so from now on we work with $n$ variables $x_{1},\cdots ,x_{n}$.

Each term $\Delta (x)s_{\lambda }$ is equal to

$a_{(\lambda _{1}+k-1,\lambda _{2}+k-2,\dots ,\lambda _{k})}(x_{1},x_{2},\dots ,x_{k})=\det \left[{\begin{matrix}x_{1}^{l_{1}}&x_{2}^{l_{1}}&\dots &x_{k}^{l_{1}}\\x_{1}^{l_{2}}&x_{2}^{l_{2}}&\dots &x_{k}^{l_{2}}\\\vdots &\vdots &\ddots &\vdots \\x_{1}^{l_{k}}&x_{2}^{l_{k}}&\dots &x_{k}^{l_{k}}\end{matrix}}\right]$

See Schur function. Since the vector $(l_{1},l_{2},\cdots ,l_{k})$ is different for each partition, this means that the coefficient of $x_{1}^{l_{1}}\cdots x_{k}^{l_{k}}$ in $\Delta (x)p_{1^{(n)}}$, denoted $\left[\Delta (x)p_{1^{(n)}}\right]_{l_{1},\cdots ,l_{k}}$, is equal to $f^{\lambda }$. This is known as the Frobenius Character Formula, which gives one of the earliest proofs. All that remains is tracking that coefficient with a mixture of cleverness and brute force: Multiplying

$\Delta (x)=\sum _{w\in S_{n}}\operatorname {sgn} (w)x_{1}^{w(1)-1}x_{2}^{w(2)-1}\cdots x_{k}^{w(k)-1}$

and

$p_{1^{(n)}}=(x_{1}+x_{2}+\cdots +x_{k})^{n}=\sum {\frac {n!}{d_{1}!d_{2}!\cdots d_{k}!}}x_{1}^{d_{1}}x_{2}^{d_{2}}\cdots x_{k}^{d_{k}}$

we conclude that the coefficient that we are looking for is

$\sum _{w\in S_{n}}\operatorname {sgn} (w){\frac {n!}{(l_{1}-w(1)+1)!(l_{2}-w(2)+1)!\cdots (l_{k}-w(k)+1)!}}$

which can be written as

${\frac {n!}{l_{1}!l_{2}!\cdots l_{k}!}}\sum _{w\in S_{n}}\operatorname {sgn} (w)\left[(l_{1})(l_{1}-1)\cdots (l_{1}-w(1)+2)\right]\left[(l_{2})(l_{2}-1)\cdots (l_{2}-w(2)+2)\right]\left[(l_{k})(l_{k}-1)\cdots (l_{k}-w(k)+2)\right]$

The latter sum is equal to the following determinant

$\det \left[{\begin{matrix}1&l_{1}&l_{1}(l_{1}-1)&\dots &\prod _{i=0}^{k-2}(l_{1}-i)\\1&l_{2}&l_{2}(l_{2}-1)&\dots &\prod _{i=0}^{k-2}(l_{2}-i)\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&l_{k}&l_{k}(l_{k}-1)&\dots &\prod _{i=0}^{k-2}(l_{k}-i)\end{matrix}}\right]$

which column reduces to the Vandermonde determinant, and we obtain the formula

$d_{\lambda }={\frac {n!}{l_{1}!l_{2}!\cdots l_{k}!}}\prod _{i<j}(l_{i}-l_{j})$

Note that $l_{i}$ is the hook length of the first box in each row of the Young Diagram. Transforming this expression into the form ${\frac {n!}{\prod h_{\lambda }(i,j)}}$ claimed by the hook-length formula is a fairly simple exercise in combinatorics: For any given $i=1,2,\ldots ,k$, one has to argue that $l_{i}!=\left(\prod _{j>i}(l_{i}-l_{j})\right)\cdot \prod _{c}h_{\lambda }(c)$, where the latter product ranges over all cells $c$ in the $i$-row of the Young diagram of $\lambda$.