The RS correspondence is a correspondence which associates to each permutation a pair of standard Young tableaux of the same shape.

The RSK correspondence associates to each integer matrix (with non-negative entries) a pair of semistandard Young tableaux of the same shape.

Given an integer matrix, replace it by a permutation matrix whose rows and columns, when partitioned according to the row and column sums of the original matrix, have block sums equal to the entries of the original matrix. There is a unique such permutation matrix with the property that there are no descents within any of the blocks (each block is a partial permutation).

For example, if

$A=\begin{pmatrix} 2 & 1\\ 1 & 0\end{pmatrix}$

then the corresponding permutation matrix is

$\tilde A =\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\end{pmatrix}$

Here the row and column partitions are both $(3,1)$.

It seems to be well-known (for example, it is implicit in Fulton's *matrix ball construction*) that to obtain the SSYT's for $A$, one may substitute for each entry in the SYT's for $\tilde A$ the integers corresponding to the blocks the rows and columns corresponding to these entries belong.

In the above example, the SYT's associated to $\tilde A$ are

$P = Q = \begin{array}{cc} 1 & 2 & 3 \\ 4 & &\end{array}$

into which we would saubstitute $1$ for $1,2,3$ and $2$ for $4$ to get the SSYT's for $A$:

$P = Q = \begin{array}{cc} 1 & 1 & 1 \\ 2 & & \end{array}$.

Is there a nice reference for this result?

2more comments