# User:Kdpandit

Jump to: navigation, search

In mathematics, the Robinson-Schensted-Knuth correspondence, also referred to as the RSK correspondence or RSK algorithm, is a combinatorial bijection between generalized permutations (as 2 lined arrays) and pairs of semi-standard Young Tableaux (SSYT). It is a generalization of the Robinson-Schensted algorithm.

## Introduction

The Robinson-Schensted algorithm, which establishes a bijective mapping between permutations and pairs of Young Tableaux, both having shape ${\displaystyle \lambda }$:

${\displaystyle \pi \longleftrightarrow (\lambda ,P,Q)}$

where ${\displaystyle \pi \in S_{n}}$ is a permutation of order ${\displaystyle n}$ and ${\displaystyle P,Q}$ are Young Tableau of shape ${\displaystyle \lambda }$.

### Generalized permutations

A generalized permutation or two-line array ${\displaystyle w}$ is defined by[1]:

${\displaystyle p={\begin{pmatrix}i_{1}&i_{2}&\ldots &i_{m}\\j_{1}&j_{2}&\ldots &j_{m}\end{pmatrix}}}$

where,

1. ${\displaystyle i_{1}\leq i_{2}\leq i_{3}\ldots \leq i_{m}}$
2. if ${\displaystyle i_{r}=i_{s}}$ and ${\displaystyle r\leq s}$ then ${\displaystyle j_{r}\leq j_{s}}$

Example:

${\displaystyle p={\begin{pmatrix}1&1&1&2&2&3&3\\1&3&3&2&2&1&2\end{pmatrix}}}$

By extending the Robinson-Schensted algorithm to generalized permutations we can obtain one-to-one mappings from these types of permutations to ordered pairs, ${\displaystyle (P,Q)}$, where ${\displaystyle P}$ and ${\displaystyle Q}$ are SSYT of the same shape.

## The Robinson-Schensted-Knuth correspondence

The Robinson-Schensted-Knuth (RSK) algorithm works almost exactly like the Robinson-Schensted algorithm, the only difference being that RSK takes a generalized permutation as input. Stanley [1] uses this moniker. The basic operation consists of an insertion operation defined as ${\displaystyle P\longleftarrow k}$ of a positive integer ${\displaystyle k}$ into a SSYT ${\displaystyle P}$.

Let ${\displaystyle A=(a_{ij})_{i,j\geq 1}}$ be a matrix with non-negative elements of dimension ${\displaystyle m\times n}$. Let ${\displaystyle p_{A}}$ be a generalized permutation associated with ${\displaystyle A}$, defined as:

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

where in addition to the 2 rules specified in the definition of a generalized permutaion ${\displaystyle p_{A}}$ needs to satisfy:

1. For each ${\displaystyle (i,j)}$, there must be ${\displaystyle a_{ij}}$ values of ${\displaystyle r}$ for which ${\displaystyle (i_{r},j_{r})=(i,j)}$.

It is easy to see that there is a bijective mapping from ${\displaystyle A}$ to ${\displaystyle p_{A}}$.

Example: If

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

then

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

If we apply the RSK algorithm on the permutation ${\displaystyle p_{A}}$ we get the following theorem called the Robinson-Schensted-Knuth correspondence theorem[2].

Theorem 1: There is a one-one correspondence between matrices ${\displaystyle A=(a_{ij})_{i,j\geq 1}}$ (and by implication permutations ${\displaystyle p_{A}}$) and the ordered pairs ${\displaystyle (P,Q)}$, where ${\displaystyle P}$ and ${\displaystyle Q}$ have the same shape. In addition, each integer ${\displaystyle i}$ occurs exactly ${\displaystyle a_{i1}+a_{i2}+\ldots +a_{in}}$ times in ${\displaystyle Q}$ and each integer ${\displaystyle j}$ occurs exactly ${\displaystyle a_{1j}+a_{2j}+\ldots +a_{mj}}$ times in ${\displaystyle P}$.

## Combinatorial properties of RSK correspondence

### RSK and permutation matrices

If ${\displaystyle A}$ is a permutation matrix then RSK outputs standard Young Tableaux (SYT), ${\displaystyle P,Q}$ of the same shape ${\displaystyle \lambda }$. Conversely, if ${\displaystyle P,Q}$ are SYT having the same shape ${\displaystyle \lambda }$, then the corresponding matrix ${\displaystyle 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 ${\displaystyle n\geq 1}$ we have ${\displaystyle \sum _{\lambda \vdash n}(f^{\lambda })^{2}=n!}$ where ${\displaystyle \lambda \vdash n}$ means ${\displaystyle \lambda }$ varies over all partitions of ${\displaystyle n}$ and ${\displaystyle f^{\lambda }}$ is the number of standard Young tableaux of shape ${\displaystyle \lambda }$.

By examining the structure of the Robinson-Schensted-K algorithm we can prove the following theorem:[3]

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

This leads to the following surprising corollary that links the number of involutions on ${\displaystyle S_{n}}$ with the number of tableaux that can be formed from ${\displaystyle S_{n}}$ (An involution is a permutation that is its own inverse)[3]:

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

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

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

${\displaystyle a(n)=a(n-1)+(n-1)a(n-2)}$

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

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

### Symmetry of RSK[1]

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

### Symmetric Matrices[1]

1. Let ${\displaystyle A}$ be an matrix with non-negative entries, then ${\displaystyle A=A^{T}}$ if and only if ${\displaystyle P=Q}$ where ${\displaystyle A}$ is mapped to ${\displaystyle (P,Q)}$ by the RSK algorithm.
2. Let ${\displaystyle A=A^{T}}$ and let the RSK algorithm map the matrix ${\displaystyle A}$ to the pair ${\displaystyle (P,P)}$, where ${\displaystyle P}$ is an SSYT of shape ${\displaystyle \alpha }$. Let ${\displaystyle \alpha =(\alpha _{1},\alpha _{2},\ldots )}$ where the ${\displaystyle \alpha _{i}\in N}$ and ${\displaystyle \sum \alpha _{i}<\infty }$. Then the map ${\displaystyle A\longmapsto P}$ establishes a bijection between symmetric matrices with row(${\displaystyle A}$) ${\displaystyle =\alpha }$ and SSYT's of type ${\displaystyle \alpha }$.

## Applications of the RSK correspondence

Knuth proved a number of important results that involve symmetric functions that can be derived from the RSK correspondence[2].

### Cauchy's Identity

We have,

${\displaystyle \prod _{i,j}(1-x_{i}y_{j})^{-1}=\sum _{\lambda }s_{\lambda }(x)s_{\lambda }(y)}$

where ${\displaystyle s_{\lambda }}$ are schur functions.

### Kostka numbers

Fix partitions ${\displaystyle \mu ,\nu \vdash n}$, then

${\displaystyle \sum _{\lambda \vdash n}K_{\lambda \mu }K_{\lambda \nu }=N_{\mu \nu }}$

where ${\displaystyle K_{\lambda \mu }}$ and ${\displaystyle K_{\lambda \nu }}$ denote the Kostka numbers and ${\displaystyle N_{\mu \nu }}$ is the number of matrices ${\displaystyle A}$, with non-negative elements, with row row(${\displaystyle A}$) ${\displaystyle =\mu }$ and column(${\displaystyle A}$) ${\displaystyle =\nu }$.

## References

1. ^ a b c d Stanley, Richard P., Enumerative Combinatorics, Volume2. Cambridge University Press. ISBN 0-521-55309-1, 0-521-56069-1. Page 316-380
2. ^ a b Knuth, Donald E., Permutations, matrices, and generalized Young tableaux. Pacific J. Math. Volume 34, Number 3 (1970), 709-727. Available at http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.pjm/1102971948&page=record
3. ^ a b Knuth, Donald E., The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, 1973. Page 54-58