Robinson–Schensted–Knuth correspondence

In mathematics, the Robinson–Schensted–Knuth correspondence, also referred to as the RSK correspondence or RSK algorithm, is a combinatorial bijection between matrices Template:Math with non-negative integer entries and pairs Template:Math of semistandard Young tableaux of equal shape, whose size equals the sum of the entries of Template:Math. More precisely the weight of Template:Math is given by the column sums of Template:Math, and the weight of Template:Math by its row sums. It is a generalization of the Robinson–Schensted correspondence, in the sense that taking Template:Math to be a permutation matrix, the pair Template:Math will be the pair of standard tableaux associated to the permutation under the Robinson–Schensted correspondence.

The Robinson–Schensted–Knuth correspondence extends many of the remarkable properties of the Robinson–Schensted correspondence, notably its symmetry: transposition of the matrix Template:Math results in interchange of the tableaux Template:Math.

The Robinson–Schensted–Knuth correspondence

Introduction

The Robinson–Schensted correspondence is a bijective mapping between permutations and pairs of standard Young tableaux, both having the same shape. This bijection can be constructed using an algorithm called Schensted insertion, starting with an empty tableau and successively inserting the values σ₁, ..., σ_n of the permutation σ at the numbers 1, 2, ..., n; these form the second line when σ is given in two-line notation:

$\sigma =\left(\begin{array}{cccc}1& 2& \dots & n\\ {\sigma }_1& {\sigma }_2& \dots & {\sigma }_n\end{array}\right)$.

The first standard tableau Template:Math is the result of successive insertions; the other standard tableau Template:Math records the successive shapes of the intermediate tableaux during the construction of Template:Math.

The Schensted insertion easily generalizes to the case where σ has repeated entries; in that case the correspondence will produce a semistandard tableau Template:Math rather than a standard tableau, but Template:Math will still be a standard tableau. The definition of the RSK correspondence reestablishes symmetry between the P and Q tableaux by producing a semistandard tableau for Template:Math as well.

Two-line arrays

The two-line array (or generalized permutation) Template:Math corresponding to a matrix Template:Math is defined as

$w_A=\left(\begin{array}{cccc}{i}_1& i_2& \dots & i_m\\ j_1& j_2& \dots & j_m\end{array}\right)$

in which for any pair Template:Math that indexes an entry Template:Math of Template:Math, there are Template:Math columns equal to $(\genfrac{}{}{0ex}{}{i}{j})$, and all columns are in lexicographic order, which means that

1. $i_1\le i_2\le i_3\cdots \le i_m$, and
2. if $i_r=i_s$ and $r\le s$ then $j_r\le j_s$.

Example

The two-line array corresponding to

$A=\left(\begin{array}{ccc}1& 0& 2\\ 0& 2& 0\\ 1& 1& 0\end{array}\right)$

is

$w_A=\left(\begin{array}{ccccccc}1& 1& 1& 2& 2& 3& 3\\ 1& 3& 3& 2& 2& 1& 2\end{array}\right)$

Definition of the correspondence

By applying the Schensted insertion algorithm to the bottom line of this two-line array, one obtains a pair consisting of a semistandard tableau Template:Math and a standard tableau Template:Math, where the latter can be turned into a semistandard tableau Template:Math by replacing each entry Template:Math of Template:Math by the Template:Math-th entry of the top line of Template:Math. One thus obtains a bijection from matrices Template:Math to ordered pairs, Template:Math of semistandard Young tableaux of the same shape, in which the set of entries of Template:Math is that of the second line of Template:Math, and the set of entries of Template:Math is that of the first line of Template:Math. The number of entries Template:Math in Template:Math is therefore equal to the sum of the entries in column Template:Math of Template:Math, and the number of entries Template:Math in Template:Math is equal to the sum of the entries in row Template:Math of Template:Math.

Example

In the above example, the result of applying the Schensted insertion to successively insert 1,3,3,2,2,1,2 into an initially empty tableau results in a tableau Template:Math, and an additional standard tableau Template:Math recoding the successive shapes, given by

$P=\begin{array}{cccc}1& 1& 2& 2\\ 2& 3\\ 3\end{array},Q_0=\begin{array}{cccc}1& 2& 3& 7\\ 4& 5\\ 6\end{array},$

and after replacing the entries 1,2,3,4,5,6,7 in Template:Math successively by 1,1,1,2,2,3,3 one obtains the pair of semistandard tableaux

$P=\begin{array}{cccc}1& 1& 2& 2\\ 2& 3\\ 3\end{array},Q=\begin{array}{cccc}1& 1& 1& 3\\ 2& 2\\ 3\end{array}.$

Direct definition of the RSK correspondence

The above definition uses the Schensted algorithm, which produces a standard recording tableau Template:Math, and modifies it to take into account the first line of the two-line array and produce a semistandard recording tableau; this makes the relation to the Robinson–Schensted correspondence evident. It is natural however to simplify the construction by modifying the shape recording part of the algorithm to directly take into account the first line of the two-line array; it is in this form that the algorithm for the RSK correspondence is usually described. This simply means that after every Schensted insertion step, the tableau Template:Math is extended by adding, as entry of the new square, the Template:Math-th entry Template:Math of the first line of Template:Math, where b is the current size of the tableaux. That this always produces a semistandard tableau follows from the property (first observed by Knuth) that for successive insertions with an identical value in the first line of Template:Math, each successive square added to the shape is in a column strictly to the right of the previous one.

Here is a detailed example of this construction of both semistandard tableaux. Corresponding to a matrix

$A=\left(\begin{array}{ccccccc}0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0\end{array}\right)$

one has the two-line array

$w_A=\left(\begin{array}{cccccccc}2& 2& 3& 4& 5& 6& 6& 8\\ 4& 6& 4& 7& 5& 3& 4& 1\end{array}\right).$

The following table shows the construction of both tableaux for this example

Inserted pair	$(\genfrac{}{}{0ex}{}{2}{4})$	$(\genfrac{}{}{0ex}{}{2}{6})$	$(\genfrac{}{}{0ex}{}{3}{4})$	$(\genfrac{}{}{0ex}{}{4}{7})$	$(\genfrac{}{}{0ex}{}{5}{5})$	$(\genfrac{}{}{0ex}{}{6}{3})$	$(\genfrac{}{}{0ex}{}{6}{4})$	$(\genfrac{}{}{0ex}{}{8}{1})$
Template:Math	$\begin{array}{c}4\end{array}$	$\begin{array}{cc}4& 6\end{array}$	$\begin{array}{cc}4& 4\\ 6\end{array}$	$\begin{array}{ccc}4& 4& 7\\ 6\end{array}$	$\begin{array}{ccc}4& 4& 5\\ 6& 7\end{array}$	$\begin{array}{ccc}3& 4& 5\\ 4& 7\\ 6\end{array}$	$\begin{array}{ccc}3& 4& 4\\ 4& 5\\ 6& 7\end{array}$	$\begin{array}{ccc}1& 4& 4\\ 3& 5\\ 4& 7\\ 6\end{array}$
Template:Math	$\begin{array}{c}2\end{array}$	$\begin{array}{cc}2& 2\end{array}$	$\begin{array}{cc}2& 2\\ 3\end{array}$	$\begin{array}{ccc}2& 2& 4\\ 3\end{array}$	$\begin{array}{ccc}2& 2& 4\\ 3& 5\end{array}$	$\begin{array}{ccc}2& 2& 4\\ 3& 5\\ 6\end{array}$	$\begin{array}{ccc}2& 2& 4\\ 3& 5\\ 6& 6\end{array}$	$\begin{array}{ccc}2& 2& 4\\ 3& 5\\ 6& 6\\ 8\end{array}$

Combinatorial properties of the RSK correspondence

The case of permutation matrices

If $A$ is a permutation matrix then RSK outputs standard Young Tableaux (SYT), $P,Q$ of the same shape $\lambda$. Conversely, if $P,Q$ are SYT having the same shape $\lambda$, then the corresponding matrix $A$ is a permutation matrix. As a result of this property by simply comparing the cardinalities of the two sets on the two sides of the bijective mapping we get the following corollary:

Corollary 1: For each $n\ge 1$ we have $\sum _{\lambda ⊢n}(t_{\lambda }{)}^2=n!$ where $\lambda ⊢n$ means $\lambda$ varies over all partitions of $n$ and $t_{\lambda }$ is the number of standard Young tableaux of shape $\lambda$.

Symmetry

Let $A$ be a matrix with non-negative entries. Suppose the RSK algorithm maps $A$ to $(P,Q)$ then the RSK algorithm maps $A^T$ to $(Q,P)$, where $A^T$ is the transpose of $A$.

In particular for the case of permutation matrices, one recovers the symmetry of the Robinson–Schensted correspondence:

Theorem 2: If the permutation $\sigma$ corresponds to a triple $(\lambda ,P,Q)$, then the inverse permutation, ${\sigma }^{-1}$, corresponds to $(\lambda ,Q,P)$.

This leads to the following relation between the number of involutions on $S_n$ with the number of tableaux that can be formed from $S_n$ (An involution is a permutation that is its own inverse):

Corollary 2: The number of tableaux that can be formed from $\{1,2,3,\dots ,n\}$ is equal to the number of involutions on $\{1,2,3,\dots ,n\}$.

Proof: If $\pi$ is an involution corresponding to $(P,Q)$, then $\pi ={\pi }^{-}$ corresponds to $(Q,P)$; hence $P=Q$. Conversely, if $\pi$ is any permutation corresponding to $(P,P)$, then ${\pi }^{-}$ also corresponds to $(P,P)$; hence $\pi ={\pi }^{-}$. So there is a one-one correspondence between involutions $\pi$ and tableaux $P$

The number of involutions on $\{1,2,3,\dots ,n\}$ is given by the recurrence:

$a(n)=a(n-1)+(n-1)a(n-2)$

Where $a(1)=1,a(2)=2$. By solving this recurrence we can get the number of involutions on $\{1,2,3,\dots ,n\}$,

$I(n)=n!\sum _{k=0}^{\lfloor n/2\rfloor }\frac{1}{2^{k}k!(n-2k)!}$

Symmetric matrices

Let $A=A^T$ and let the RSK algorithm map the matrix $A$ to the pair $(P,P)$, where $P$ is an SSYT of shape $\alpha$. Let $\alpha =({\alpha }_1,{\alpha }_2,\dots )$ where the ${\alpha }_i$ are non-negative integers and $\sum _i{\alpha }_i<\mathrm{\infty }$. Then the map $A⟼P$ establishes a bijection between symmetric matrices with $\mathrm{r}\mathrm{o}\mathrm{w}(A)=\alpha$ and SSYT's of weight $\alpha$.

Applications of the RSK correspondence

Cauchy's identity

The Robinson–Schensted–Knuth correspondence provides a direct bijective proof of the following celebrated identity for symmetric functions:

$\prod _{i,j}(1-x_i{y}_j{)}^{-1}=\sum _{\lambda }{s}_{\lambda }(x)s_{\lambda }(y)$

where $s_{\lambda }$ are Schur functions.

Kostka numbers

Fix partitions $\mu ,\nu ⊢n$, then

$\sum _{\lambda ⊢n}{K}_{\lambda \mu }{K}_{\lambda \nu }=N_{\mu \nu }$

where $K_{\lambda \mu }$ and $K_{\lambda \nu }$ denote the Kostka numbers and $N_{\mu \nu }$ is the number of matrices $A$, with non-negative elements, with $\mathrm{r}\mathrm{o}\mathrm{w}(A)=\mu$ and $\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{m}\mathrm{n}(A)=\nu$.

References

• Template:Cite book