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}