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}}^{?}}{?}(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$。