RSK algorithms as path transformations
robinson_schensted_knuth robinson_schensted pitman_transform
We write the RSK algorithms as path transformations analogous to the RS as Pitman's transform of type A. The derivation is similar to that note. Define operators \(\odot\) and \(\otimes\) on pairs of functions on \(\pint\) as
\[ (f \odot g) (n) = \max_{k = 1 : n} \{f(k) + g(n) - g(k - 1)\} \\ (f \otimes g) (n) = \min_{k = 1 : n} \{f(k - 1) + g(n) - g(k)\} \]Note that the definitions of these operators are slightly different from those in Pitman's transform of type A.
Given an input matrix \(A = (a_{ij})\), let the paths \(S_k\) be defined as
\[ S_k(n) := \sum_{i = 1 : n} a_{i k} \qquad (1) \]As usual, let \((\lambda^k_j)_{1 \le j \le k}\) be the GT pattern corresponds to the output tableaux. Then we the same (in terms of \(\odot\) and \(\otimes\)) path transformations as in Pitman's transform of type A:
\begin{align} \mu^k_1 &= S_k\\ \lambda^k_k &= \mu^k_k \\ (\lambda^k_j, \mu^k_{j + 1}) &= (\lambda^{k - 1}_j \odot \mu^k_j, \mu^k_j \otimes \lambda^{k - 1}_j), \qquad j < k. \end{align}Similarly, the RSK column insertion algorithm has the corresponding path transformation definition:
\begin{align} \mu^k_k &= S_k\\ \lambda^k_1 &= \mu^k_1 \\ (\lambda^k_j, \mu^k_{j - 1}) &= (\lambda^{k - 1}_{j - 1} \otimes \mu^k_j, \mu^k_j \odot \lambda^{k - 1}_{j - 1}), \qquad 1 < j \le k. \end{align}