Robinson-Schensted-Knuth algorithms

---

robinson_schensted robinson_schensted_knuth

Recall the RS algorithms.

The Robinson-Schensted-Knuth (RSK) algorithm is the Robinson-Schensted algorithm taking matrices as input. By default we consider the row insertion algorithm: \(\text{RSK} = \text{RSK}_{\text{Row}}\). Given a nonnegative integer matrix \(A\), one can convert it to a word \(w(A)\), and the RSK algorithm is defined as RS (with row insertion) taking \(w(A)\) as the input

\[ \text{RSK} (A) := \text{RS}_{\text{Row}} (w(A)) \]

The conversion is by multiplicity: suppose \(A = (a_{ij})_{n \times \ell}\), then

\[ w(A) := (1^{a_{11}} 2^{a_{12}} ... \ell^{a_{1 \ell}} 1^{a_{21}} 2^{a_{22}} ... \ell^{a_{2 \ell}} ... 1^{a_{n1}} 2^{a_{n2}} ... \ell^{a_{n \ell}}) \]

where \(k^m\) means \(k\) repeated \(m\) times.

For example

\[ w(\begin{pmatrix} 1 & 0 & 4 \\ 4 & 2 & 3 \end{pmatrix}) = (13333111122333) \]

One can also define the RSK column insertion algorithm, which is called the Burge correspondence. It is defined in the same way as the RSK row insertion, except we use a different conversion from matrices to words, which reads from right to left rather than from left to right as in \(w\):

\begin{align} \text{RSK}_{\text{Col}} (A) &:= \text{RS}_{\text{Col}} (w'(A)) \\ w'(A) &:= (\ell^{a_{1 \ell}} ... 2^{a_{12}} 1^{a_{11}} \ell^{a_{2 \ell}} ... 2^{a_{22}} 1^{a_{21}} ... \ell^{a_{n \ell}} ... 2^{a_{n2}} 1^{a_{n1}}) \end{align}

so the previous example becomes

\[ w'(\begin{pmatrix} 1 & 0 & 4 \\ 4 & 2 & 3 \end{pmatrix}) = (33331333221111) \]

The reason for having a different conversion is to get the RSK correspondences and the integrability results that can be derived from the correspondences.