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 A with non-negative integer entries and pairs (P,Q) of semistandard Young tableaux of equal shape, whose size equals the sum of the entries of A. More precisely the weight of P is given by the column sums of A, and the weight of Q by its row sums.

It is a generalization of the Robinson–Schensted correspondence, in the sense that taking A to be a permutation matrix, the pair (P,Q) 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 A results in interchange of the tableaux P,Q.

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 σ1, ..., σn of the permutation σ at the numbers 1, 2, ..., n; these form the second line when σ is given in two-line notation:

σ

=

(

1

2

…

n

σ

1

σ

2

…

σ

n

)

{\displaystyle \sigma ={\begin{pmatrix}1&2&\ldots &n\\\sigma _{1}&\sigma _{2}&\ldots &\sigma _{n}\end{pmatrix}}}

.

The first standard tableau P is the result of successive insertions; the other standard tableau Q records the successive shapes of the intermediate tableaux during the construction of P.

The Schensted insertion easily generalizes to the case where σ has repeated entries; in that case the correspondence will produce a semistandard tableau P rather than a standard tableau, but Q 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 Q as well.

Two-line arrays

The two-line array (or generalized permutation) wA corresponding to a matrix A is defined as

w

A

=

(

i

1

i

2

…

i

m

j

1

j

2

…

j

m

)

{\displaystyle w_{A}={\begin{pmatrix}i_{1}&i_{2}&\ldots &i_{m}\\j_{1}&j_{2}&\ldots &j_{m}\end{pmatrix}}}

in which for any pair (i,j) that indexes an entry Ai,j of A, there are Ai,j columns equal to

(

i

j

)

{\displaystyle {\tbinom {i}{j}}}

, and all columns are in lexicographic order, which means that

i

1

≤

i

2

≤

i

3

⋯

≤

i

m

{\displaystyle i_{1}\leq i_{2}\leq i_{3}\cdots \leq i_{m}}

, and

if

i

r

=

i

s

{\displaystyle i_{r}=i_{s}\,}

and

r

≤

s

{\displaystyle r\leq s}

then

j

r

≤

j

s

{\displaystyle j_{r}\leq j_{s}}

.

Example

The two-line array corresponding to

A

=

(

1

0

2

0

2

0

1

1

0

)

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

is

w

A

=

(

1

1

1

2

2

3

3

1

3

3

2

2

1

2

)

{\displaystyle w_{A}={\begin{pmatrix}1&1&1&2&2&3&3\\1&3&3&2&2&1&2\end{pmatrix}}}

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 P and a standard tableau Q0, where the latter can be turned into a semistandard tableau Q by replacing each entry b of Q0 by the b-th entry of the top line of wA. One thus obtains a bijection from matrices A to ordered pairs, (P,Q) of semistandard Young tableaux of the same shape, in which the set of entries of P is that of the second line of wA, and the set of entries of Q is that of the first line of wA. The number of entries j in P is therefore equal to the sum of the entries in column j of A, and the number of entries i in Q is equal to the sum of the entries in row i of A.

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 P, and an additional standard tableau Q0 recoding the successive shapes, given by

P

=

1

1

2

2

2

3

3

,

Q

0

=

1

2

3

7

4

5

6

,

{\displaystyle P\quad =\quad {\begin{matrix}1&1&2&2\\2&3\\3\end{matrix}},\qquad Q_{0}\quad =\quad {\begin{matrix}1&2&3&7\\4&5\\6\end{matrix}},}

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

P

=

1

1

2

2

2

3

3

,

Q

=

1

1

1

3

2

2

3

.

{\displaystyle P\quad =\quad {\begin{matrix}1&1&2&2\\2&3\\3\end{matrix}},\qquad Q\quad =\quad {\begin{matrix}1&1&1&3\\2&2\\3\end{matrix}}.}

Direct definition of the RSK correspondence

The above definition uses the Schensted algorithm, which produces a standard recording tableau Q0, 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.