= Robinson-Schensted-Knuth correspondence
{c}
{title2=$A\longleftrightarrow(P,Q)$}
= RSK correspondence
{c}
{synonym}
= RSK algorithm
{c}
{synonym}
= RSK
{c}
{synonym}
List each pair $(i,j)$ with multiplicity $a_{ij}$, sorted first by $i$ and then by $j$. Apply <row insertion> to the lower letters $j$, and record the upper letters $i$ in the new cells. The <row insertion> comparison is strictly greater than the carried entry. The result is a pair of <Semistandard Young tableaux> of the same shape. Reverse insertion removes the rightmost cell containing the largest recording entry, then replaces the rightmost strictly smaller entry in each preceding row. It reconstructs the ordered list, proving the <bijection>. The insertion and recording contents are respectively the column sums and row sums of $A$.
Back to article page
