User:Kdpandit

From Wikipedia, the free encyclopedia
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[edit]

The Robinson-Schensted algorithm, which establishes a bijective mapping between permutations and pairs of Young Tableaux, both having shape :

where is a permutation of order and are Young Tableau of shape .

Generalized permutations[edit]

A generalized permutation or two-line array is defined by[1]:

where,

  1. if and then

Example:


By extending the Robinson-Schensted algorithm to generalized permutations we can obtain one-to-one mappings from these types of permutations to ordered pairs, , where and are SSYT of the same shape.

The Robinson-Schensted-Knuth correspondence[edit]

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 of a positive integer into a SSYT .

Let be a matrix with non-negative elements of dimension . Let be a generalized permutation associated with , defined as:

where in addition to the 2 rules specified in the definition of a generalized permutaion needs to satisfy:

  1. For each , there must be values of for which .

It is easy to see that there is a bijective mapping from to .

Example: If

then

If we apply the RSK algorithm on the permutation we get the following theorem called the Robinson-Schensted-Knuth correspondence theorem[2].

Theorem 1: There is a one-one correspondence between matrices (and by implication permutations ) and the ordered pairs , where and have the same shape. In addition, each integer occurs exactly times in and each integer occurs exactly times in .

Combinatorial properties of RSK correspondence[edit]

RSK and permutation matrices[edit]

If is a permutation matrix then RSK outputs standard Young Tableaux (SYT), of the same shape . Conversely, if are SYT having the same shape , then the corresponding matrix 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 we have where means varies over all partitions of and is the number of standard Young tableaux of shape .

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

Theorem 2: If the permutation corresponds to a triple , then the inverse permutation, , corresponds to .

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

Corollary 2: The number of tableaux that can be formed from is equal to the number of involutions on .

Proof: If is an involution corresponding to , then corresponds to ; hence . Conversely, if is any permutation corresponding to , then also corresponds to ; hence . So there is a one-one correspondence between involutions and tableax

The number of involutions on is given by the recurrence:

Where . By solving this recurrence we can get the number of involutions on ,

Symmetry of RSK[1][edit]

Let be a matrix with non-negative entries. Suppose the RSK algorithm maps to then the RSK algorithm maps to , where is the transpose of .

Symmetric Matrices[1][edit]

  1. Let be an matrix with non-negative entries, then if and only if where is mapped to by the RSK algorithm.
  2. Let and let the RSK algorithm map the matrix to the pair , where is an SSYT of shape . Let where the and . Then the map establishes a bijection between symmetric matrices with row() and SSYT's of type .

Applications of the RSK correspondence[edit]

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

Cauchy's Identity[edit]

We have,

where are schur functions.

Kostka numbers[edit]

Fix partitions , then

where and denote the Kostka numbers and is the number of matrices , with non-negative elements, with row row() and column() .

References[edit]

  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