7.14 对偶 RSK 算法

存在 RSK 算法的一种变体，其与乘积 ${\prod }_{i,j}(1+x_i{y}_j)$ 的关系类似于 RSK 算法本身与 ${\prod }_{i,j}(1-x_i{y}_j{)}^{-1}$ 的关系。我们称此变体为对偶 RSK 算法并记为 $A\stackrel{{\text{RSK}}^{\ast }}{⟶}(P,Q)$。 矩阵 $A$ 现在是一个有限支撑的 $(0,1)$-矩阵。像之前一样构造双行数组 $w_A$。 对偶 RSK 算法的执行过程与 RSK 算法完全相同，区别在于元素 $i$ 撞出的是最左边 $\ge i$ 的元素，而不是最左边 $>i$ 的元素。（特别地，对于置换矩阵，RSK 和 RSK* 是一致的。）由此可得 $P$ 的每一行都是严格递增的。

7.14.1 例子
设
$$A=\left[\begin{array}{ccc}1& 0& 1\\ 0& 1& 0\\ 1& 0& 1\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]$$

则
$$w_A=\left(\begin{array}{ccccccc}1& 1& 2& 3& 3& 4& 5\\ 1& 3& 2& 1& 3& 3& 2\end{array}\right)$$

由对偶 RSK 算法得到的数组 $(P(1),Q(1)),\dots ,(P(7),Q(7))$，其中 $(P,Q)=(P(7),Q(7))$，如下所示：

7.14.2 定理

对偶 RSK 算法建立了有限支撑的 $(0,1)$-矩阵 $A$ 与满足以下条件的对 $(P,Q)$ 之间的双射：$P^{\prime }$（$P$ 的转置）和 $Q$ 是半标准 Young 表 (SSYT)，且 $\mathrm{sh}(P)=\mathrm{sh}(Q)$。此外，$\mathrm{col}(A)=\mathrm{type}(P)$ 且 $\mathrm{row}(A)=\mathrm{type}(Q)$。

定理 7.14.2 的证明类似于定理 7.11.5 的证明，故省略。

正如我们从普通 RSK 算法得到 Cauchy 恒等式 (7.44) 一样，我们有以下结果，称为对偶 Cauchy 恒等式。

7.14.3 定理

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

定理 7.14.3 的一个重要推论是 $\omega s_{\lambda }$ 的求值。首先我们需要观察 $\omega$（作用于 $y$ 变量）对乘积 ${\prod }_{i,j}(1+x_i{y}_j)$ 的影响。

7.14.4 引理

令 ${\omega }_y$ 表示仅作用于 $y$ 变量的 $\omega$（因此我们将 $x_i$ 视为与 $\omega$ 交换的常数）。则
$${\omega }_y\prod _{i,j}(1-x_i{y}_j{)}^{-1}=\prod _{i,j}(1+x_i{y}_j).$$

证明。我们有
$${\omega }_y\prod _{i,j}(1-x_i{y}_j{)}^{-1}={\omega }_y\sum _{\lambda }{m}_{\lambda }(x)h_{\lambda }(y)\text{(由命题 7.7.4)}$$
$$=\sum _{\lambda }{m}_{\lambda }(x)e_{\lambda }(y)\text{(由定理 7.6.1)}$$
$$=\prod _{i,j}(1+x_i{y}_j)\text{(由命题 7.4.1)}.\square$$

另一种证明可以通过将乘积 ${\prod }_{i,j}(1-x_i{y}_j{)}^{-1}$ 和 ${\prod }_{i,j}(1+x_i{y}_j)$ 按幂和对称函数展开（等式 (7.20) 和 (7.21)）并应用命题 7.7.5 给出。

7.14.5 定理

对每个 $\lambda \in \mathrm{Par}$，我们有
$$\omega s_{\lambda }=s_{{\lambda }^{\prime }}.$$

证明。我们有
$$\sum _{\lambda }{s}_{\lambda }(x)s_{{\lambda }^{\prime }}(y)=\prod _{i,j}(1+x_i{y}_j)\text{(由定理 7.14.3)}$$
$$={\omega }_y\prod _{i,j}(1-x_i{y}_j{)}^{-1}\text{(由引理 7.14.4)}$$
$$={\omega }_y\sum _{\lambda }{s}_{\lambda }(x)s_{\lambda }(y)\text{(由定理 7.12.1)}$$
$$=\sum _{\lambda }{s}_{\lambda }(x){\omega }_y\left(s_{\lambda }(y)\right).$$
在两边取 $s_{\lambda }(x)$ 的系数。由于 $s_{\lambda }(x)$ 是线性无关的，我们得到 $s_{{\lambda }^{\prime }}(y)={\omega }_y\left(s_{\lambda }(y)\right)$，或者简写为 $s_{{\lambda }^{\prime }}=\omega s_{\lambda }$。 $\square$

稍后（定理 7.15.6）我们会将定理 7.14.5 推广到斜 Schur 函数。

在命题 7.7.5 之后我们提到过，$\omega :{\Lambda }^n\to {\Lambda }^n$ 的特征多项式等于 $(x^2-1{)}^{o(n)}(x-1{)}^{k(n)}$，其中 $o(n)$ 是 ${\mathfrak{S}}_n$ 中奇共轭类的数量，而 $k(n)$ 是 $n$ 的自共轭分拆的数量。特别地，特征值 $1$ 的重数超过特征值 $-1$ 的重数 $k(n)$。这个事实也是定理 7.14.5 的直接推论。因为如果 $\lambda \ne {\lambda }^{\prime }$，那么 $\omega$ 将 $s_{\lambda }$ 和 $s_{{\lambda }^{\prime }}$ 互换，对应一个特征值 $1$ 和一个特征值 $-1$。剩下的是 $k(n)$ 个满足 $\lambda ={\lambda }^{\prime }$ 的特征向量 $s_{\lambda }$，其对应的特征值为 $1$。