计数组合学7.12（ RSK算法的一些推论)

7.12 RSK算法的一些推论

通过RSK算法直接得出的关于对称函数的最重要结果如下，称为柯西恒等式。

7.12.1 定理

我们有
$$\prod _{i,j}(1-x_i{y}_j{)}^{-1}=\sum _{\lambda }{s}_{\lambda }(\mathbf{x})s_{\lambda }(\mathbf{y}).(7.44)$$

证明.
写出
$$\prod _{i,j}(1-x_i{y}_j{)}^{-1}=\prod _{i,j}\left[\sum _{a_{ij}\ge 0}(x_i{y}_j{)}^{a_{ij}}\right].(7.45)$$

在这个展开式中，一项 $x^{\alpha }{y}^{\beta }$ 是通过选择一个具有有限支撑的 $\mathbb{N}$ 矩阵 $A^{\prime }=(a_{ij}{)}^{\prime }$（$A$ 的转置），使得 $\text{row}(A)=\alpha$ 且 $\text{col}(A)=\beta$ 而得到的。因此，(7.45) 中 $x^{\alpha }{y}^{\beta }$ 的系数是满足 $\text{row}(A)=\alpha$ 和 $\text{col}(A)=\beta$ 的 $\mathbb{N}$ 矩阵 $A$ 的个数 $N_{\alpha \beta }$。（这个陈述也等价于 (7.9)。）另一方面，在 ${\sum }_{\lambda }{s}_{\lambda }(\mathbf{x})s_{\lambda }(\mathbf{y})$ 中 $x^{\alpha }{y}^{\beta }$ 的系数是具有相同形状 $\lambda$ 的半标准杨表(SSYT)对 $(P,Q)$ 的个数，且满足 $\text{type}(P)=\alpha$ 和 $\text{type}(Q)=\beta$。RSK算法在矩阵 $A$ 和杨表对 $(P,Q)$ 之间建立了一个双射，因此证明完成。□

柯西恒等式 (7.44) 有一些直接的推论。

7.12.2 推论.

Schur函数构成 $\Lambda$ 的一个标准正交基，即 $⟨s_{\lambda },s_{\mu }⟩={\delta }_{\lambda \mu }$.

证明. 结合推论 7.10.6 和引理 7.9.2。□

线性代数注记. 我们说Schur函数构成 $\Lambda$ 的一个整标准正交基，因为根据命题 7.10.5，它们实际上生成了阿贝尔群 ${\Lambda }_{\mathbb{Z}}$。一般来说，一个具有特定基（在我们的情形是单项对称函数）和正定对称标量积的向量空间是否具有整标准正交基是一个微妙的问题。对于我们的情形，这样的基等价于存在一个整矩阵 $A$ 使得 $A^{\prime }A=N$，其中 $N$ 是从 $m_{\lambda }$ 到 $h_{\lambda }$ 的转换矩阵。那么我们说 $N$ 是整等价于恒等矩阵。下一个结果（无非是标准的线性代数）将 $A$ 识别为Kostka矩阵 $K$。注意，一般来说，如果存在整标准正交基，那么它在符号和顺序意义下是唯一的。这是因为两个这样的基之间的转换矩阵必须既是整的又是正交的。容易看出，唯一的整正交矩阵是带符号的置换矩阵。

7.12.3 推论.

固定分拆 $\mu ,v⊢n$. 那么
$$\sum _{\lambda ⊢n}{K}_{\lambda \mu }{K}_{\lambda v}=N_{\mu v}=⟨h_{\mu },h_v⟩,$$
其中 $K_{\lambda \mu }$ 和 $K_{\lambda v}$ 表示Kostka数，而 $N_{\mu v}$ 是满足 $\text{row}(A)=\mu$ 和 $\text{col}(A)=v$ 的 $\mathbb{N}$ 矩阵 $A$ 的个数。

证明. 在 (7.44) 两边取 $x^{\alpha }{y}^{\beta }$ 的系数。□

7.12.4 推论

我们有

$$h_{\mu }=\sum _{\lambda }{K}_{\lambda \mu }{s}_{\lambda }.(7.46)$$

换句话说，如果 $M(u,v)$ 表示 $\Lambda$ 的基 {vλ}\{v_{\lambda}\}{vλ​} 到基 {uλ}\{u_{\lambda}\}{uλ​} 的转换矩阵（即 $u_{\lambda }={\sum }_{\mu }M(u,v{)}_{\lambda \mu }{v}_{\mu }$），那么

$$M(h,s)=M(s,m{)}^{\prime }.$$

我们给出这个推论的三个证明，本质上都是等价的。

第一证明： 令 $h_{\mu }={\sum }_{\lambda }{a}_{\lambda \mu }{s}_{\lambda }$。由推论 7.12.2，我们有 $a_{\lambda \mu }=⟨h_{\mu },s_{\lambda }⟩$。由于根据标量积 $⟨,⟩$ 的定义 (7.30) 有 $⟨h_{\mu },m_{\nu }⟩={\delta }_{\mu \nu }$，那么由 (7.35) 有 $⟨h_{\mu },s_{\lambda }⟩=K_{\lambda \mu }$。□

第二证明： 固定 $\mu$。那么
$$h_{\mu }=\sum _A{\mathbf{x}}^{\text{col}(A)}$$
$$=\sum _{(P,\mathcal{Q})}{\mathbf{x}}^{\mathcal{Q}}\text{由 RSK 算法}$$
$$=\sum _{\lambda }{K}_{\lambda \mu }\sum _{\mathcal{Q}}{\mathbf{x}}^{\mathcal{Q}}$$
$$=\sum _{\lambda }{K}_{\lambda \mu }{s}_{\lambda },$$
其中 (i) $A$ 取遍所有满足 $\text{row}(A)=\mu$ 的 $\mathbb{N}$ 矩阵，(ii) $(P,\mathcal{Q})$ 取遍所有具有相同形状且满足 $\text{type}(P)=\mu$ 的半标准杨表(SSYT)对，且 (iii) $\mathcal{Q}$ 取遍所有形状为 $\lambda$ 的半标准杨表(SSYT)。□

第三证明： 在恒等式
$$\sum _{\lambda }{m}_{\lambda }(\mathbf{x})h_{\lambda }(\mathbf{y})=\sum _{\lambda }{s}_{\lambda }(\mathbf{x})s_{\lambda }(\mathbf{y})$$
两边取 $m_{\mu }(\mathbf{x})$ 的系数。
（由 (7.10) 和 (7.44) 可知两边相等。）□

下一个推论可以看作给出了关于Schur函数 $s_{\lambda }$ 的、形状为 $\lambda$ 的标准杨表(SYT)的个数 $f^{\lambda }$ 的生成函数。

7.12.5 推论

我们有

$$h_1^n=\sum _{\lambda ⊢n}{f}^{\lambda }{s}_{\lambda }.(7.47)$$

证明. 在 (7.44) 两边取 $x_1{x}_2\cdots x_n$ 的系数。为了得到一个双射证明，考虑当 $\text{col}(A)=(1^n)$ 时应用RSK算法 $A\stackrel{\text{RSK}}{\to }(P,\mathcal{Q})$。□

最后我们给出一个已经在 (7.43) 中给出的恒等式，但值得在这里重复。

7.12.6 推论

我们有

$$\sum _{\lambda ⊢n}(f^{\lambda }{)}^2=n!.$$

证明. 将 (7.47) 视为变量 $\mathbf{x}=(x_1,x_2,\dots )$ 中的表达式，并在两边取 $x_1{x}_2\cdots x_n$ 的系数。为了得到一个双射证明（如方程 (7.43) 前所述），考虑应用于 $n\times n$ 置换矩阵的RSK算法。□