Robinson-Schensted-Knuth correspondence

AUTHORS:

  • Travis Scrimshaw (2012-12-07): Initial version

EXAMPLES:

We can perform RSK and the inverse on a variety of objects:

sage: p = Tableau([[1,2,2],[2]]); q = Tableau([[1,3,3],[2]])
sage: gp = RSK_inverse(p, q); gp
[[1, 2, 3, 3], [2, 1, 2, 2]]
sage: RSK(*gp)
[[[1, 2, 2], [2]], [[1, 3, 3], [2]]]
sage: m = RSK_inverse(p, q, 'matrix'); m
[0 1]
[1 0]
[0 2]
sage: RSK(m)
[[[1, 2, 2], [2]], [[1, 3, 3], [2]]]

TESTS:

Check that it is a correspondence between all types of input and the input is preserved:

sage: t1 = Tableau([[1, 2, 5], [3], [4]])
sage: t2 = Tableau([[1, 2, 3], [4], [5]])
sage: gp = RSK_inverse(t1, t2); gp
[[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]]
sage: w = RSK_inverse(t1, t2, 'word'); w
word: 14532
sage: m = RSK_inverse(t1, t2, 'matrix'); m
[1 0 0 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 1 0 0]
[0 1 0 0 0]
sage: p = RSK_inverse(t1, t2, 'permutation'); p
[1, 4, 5, 3, 2]
sage: t1
[[1, 2, 5], [3], [4]]
sage: t2
[[1, 2, 3], [4], [5]]
sage: RSK(*gp) == [t1, t2]
True
sage: RSK(w) == [t1, t2]
True
sage: RSK(m) == [t1, t2]
True
sage: RSK(p) == [t1, t2]
True
sage: gp
[[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]]
sage: w
word: 14532
sage: m
[1 0 0 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 1 0 0]
[0 1 0 0 0]
sage: p
[1, 4, 5, 3, 2]

REFERENCES:

[Knu1970](1, 2) Donald E. Knuth. Permutations, matrices, and generalized Young tableaux. Pacific J. Math. Volume 34, Number 3 (1970), pp. 709-727. http://projecteuclid.org/euclid.pjm/1102971948
[EG1987](1, 2, 3, 4) Paul Edelman, Curtis Greene. Balanced Tableaux. Advances in Mathematics 63 (1987), pp. 42-99. http://www.sciencedirect.com/science/article/pii/0001870887900636
sage.combinat.rsk.RSK(obj1=None, obj2=None, insertion='RSK', check_standard=False, **options)

Perform the Robinson-Schensted-Knuth (RSK) correspondence.

The Robinson-Schensted-Knuth (RSK) correspondence is most naturally stated as a bijection between generalized permutations (also known as two-line arrays, biwords, ...) and pairs of semi-standard Young tableaux (P, Q) of identical shape. The tableau P is known as the insertion tableau and Q is known as the recording tableau.

The basic operation is known as row insertion P \leftarrow k (where P is a given semi-standard Young tableau, and k is an integer). Row insertion is a recursive algorithm which starts by setting k_0 = k, and in its i-th step inserts the number k_i into the i-th row of P by replacing the first integer greater than k_i in the row by k_i and defines k_{i+1} as the integer that has been replaced. If no integer greater than k_i exists in the i-th row, then k_i is simply appended to the row and the algorithm terminates at this point.

Now the RSK algorithm starts by initializing two semi-standard tableaux P_0 and Q_0 as empty tableaux. For each nonnegative integer t starting at 0, take the pair (j_t, k_t) from p and set P_{t+1} = P_t \leftarrow k_t, and define Q_{t+1} by adding a new box filled with j_t to the tableau Q_t at the same location the row insertion on P_t ended (that is to say, adding j_t such that P_{t+1} and Q_{t+1} have the same shape). The iterative process stops when t reaches the size of p, and the pair (P_t, Q_t) at this point is the image of p under the Robinson-Schensted-Knuth correspondence.

This correspondence has been introduced in [Knu1970], where it has been referred to as “Construction A”.

For more information, see Chapter 7 in [Sta-EC2].

We also note that integer matrices are in bijection with generalized permutations. In addition, we can also convert any word w (and any permutation) to a generalized permutation by considering the top line to be (1, 2, \ldots, n) where n is the length of w.

The optional argument insertion allows to specify an alternative insertion procedure to be used instead of the standard Robinson-Schensted-Knuth insertion. If the input is a reduced word of a permutation (i.e., a type A Coxeter element), one can set insertion to 'EG', which gives Edelman-Greene insertion, an algorithm defined in [EG1987] Definition 6.20 (where it is referred to as Coxeter-Knuth insertion). The Edelman-Greene insertion is similar to the standard row insertion except that if k_i and k_i + 1 both exist in row i, we only set k_{i+1} = k_i + 1 and continue.

INPUT:

  • obj1, obj2 – Can be one of the following:
    • A word in an ordered alphabet
    • An integer matrix
    • Two lists of equal length representing a generalized permutation
    • Any object which has a method _rsk_iter() which returns an iterator over the object represented as generalized permutation or a pair of lists.
  • insertion – (Default: 'RSK') The following types of insertion are currently supported:
    • 'RSK' – Robinson-Schensted-Knuth
    • 'EG' – Edelman-Greene (only for reduced words of permutations/type A Coxeter elements)
  • check_standard – (Default: False) Check if either of the resulting tableaux should be standard tableau.

EXAMPLES:

If we only give one line, we treat the top line as being (1, 2, \ldots, n):

sage: RSK([3,3,2,4,1])
[[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]]
sage: RSK(Word([3,3,2,4,1]))
[[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]]
sage: RSK(Word([2,3,3,2,1,3,2,3]))
[[[1, 2, 2, 3, 3], [2, 3], [3]], [[1, 2, 3, 6, 8], [4, 7], [5]]]

With a generalized permutation:

sage: RSK([1, 2, 2, 2], [2, 1, 1, 2])
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]
sage: RSK(Word([1,1,3,4,4]), [1,4,2,1,3])
[[[1, 1, 3], [2], [4]], [[1, 1, 4], [3], [4]]]
sage: RSK([1,3,3,4,4], Word([6,2,2,1,7]))
[[[1, 2, 7], [2], [6]], [[1, 3, 4], [3], [4]]]

If we give it a matrix:

sage: RSK(matrix([[0,1],[2,1]]))
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]

We can also give it something looking like a matrix:

sage: RSK([[0,1],[2,1]])
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]

There are also variations of the insertion algorithm in RSK, and currently only Edelman-Greene insertion is supported:

sage: RSK([2,1,2,3,2], insertion='EG')
[[[1, 2, 3], [2, 3]], [[1, 3, 4], [2, 5]]]

We reproduce figure 6.4 in [EG1987]:

sage: RSK([2,3,2,1,2,3], insertion='EG')
[[[1, 2, 3], [2, 3], [3]], [[1, 2, 6], [3, 5], [4]]]

There is also RSK_inverse() which performs the inverse of the bijection on a pair of semistandard tableaux. We note that the inverse function takes 2 separate tableaux inputs, so to compose with RSK(), we need to use the python * on the output:

sage: RSK_inverse(*RSK([1, 2, 2, 2], [2, 1, 1, 2]))
[[1, 2, 2, 2], [2, 1, 1, 2]]
sage: P,Q = RSK([1, 2, 2, 2], [2, 1, 1, 2])
sage: RSK_inverse(P, Q)
[[1, 2, 2, 2], [2, 1, 1, 2]]

TESTS:

Empty objects:

sage: RSK(Permutation([]))
[[], []]
sage: RSK(Word([]))
[[], []]
sage: RSK(matrix([[]]))
[[], []]
sage: RSK([], [])
[[], []]
sage: RSK([[]])
[[], []]
sage: RSK(Word([]), insertion='EG')
[[], []]
sage.combinat.rsk.RSK_inverse(p, q, output='array', insertion='RSK')

Return the generalized permutation corresponding to the pair of tableaux (p,q) under the inverse of the Robinson-Schensted-Knuth algorithm.

For more information on the bijeciton, see RSK().

INPUT:

  • p, q – Two semi-standard tableaux of the same shape

  • output – (Default: 'array') if q is semi-standard:

    • 'array' – as a two-line array (i.e. generalized permutation or biword)
    • 'matrix' – as an integer matrix

    and if q is standard, we can have the output:

    • 'word' – as a word

    and additionally if p is standard, we can also have the output:

    • 'permutation' – as a permutation
  • insertion – (Default: RSK) The insertion algorithm used in the bijection. Currently only 'RSK' and 'EG' (Edelman-Greene) are supported.

EXAMPLES:

If both p and q are standard:

sage: t1 = Tableau([[1, 2, 5], [3], [4]])
sage: t2 = Tableau([[1, 2, 3], [4], [5]])
sage: RSK_inverse(t1, t2)
[[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]]
sage: RSK_inverse(t1, t2, 'word')
word: 14532
sage: RSK_inverse(t1, t2, 'matrix')
[1 0 0 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 1 0 0]
[0 1 0 0 0]
sage: RSK_inverse(t1, t2, 'permutation')
[1, 4, 5, 3, 2]
sage: RSK_inverse(t1, t1, 'permutation')
[1, 4, 3, 2, 5]
sage: RSK_inverse(t2, t2, 'permutation')
[1, 2, 5, 4, 3]
sage: RSK_inverse(t2, t1, 'permutation')
[1, 5, 4, 2, 3]

If the first tableau is semistandard:

sage: p = Tableau([[1,2,2],[3]]); q = Tableau([[1,2,4],[3]])
sage: ret = RSK_inverse(p, q); ret
[[1, 2, 3, 4], [1, 3, 2, 2]]
sage: RSK_inverse(p, q, 'word')
word: 1322

In general:

sage: p = Tableau([[1,2,2],[2]]); q = Tableau([[1,3,3],[2]])
sage: RSK_inverse(p, q)
[[1, 2, 3, 3], [2, 1, 2, 2]]
sage: RSK_inverse(p, q, 'matrix')
[0 1]
[1 0]
[0 2]

Using the Edelman-Greene insertion:

sage: pq = RSK([2,1,2,3,2], insertion='RSK'); pq
[[[1, 2, 2], [2, 3]], [[1, 3, 4], [2, 5]]]
sage: RSK_inverse(*pq, insertion='EG')
[2, 1, 2, 3, 2]

Note

Currently the constructor of Tableau accept as input lists that are not even tableaux but only filling of a partition diagram. This feature should not be used with RSK_inverse.

TESTS:

From empty tableaux:

sage: RSK_inverse(Tableau([]), Tableau([]))
[[], []]

Check that RSK_inverse() is the inverse of RSK() on the different types of inputs/outputs:

sage: f = lambda p: RSK_inverse(*RSK(p), output='permutation')
sage: all(p == f(p) for n in range(7) for p in Permutations(n))
True
sage: all(RSK_inverse(*RSK(w), output='word') == w for n in range(4) for w in Words(5, n))
True
sage: from sage.combinat.integer_matrices import IntegerMatrices
sage: M = IntegerMatrices([1,2,2,1], [3,1,1,1])
sage: all(RSK_inverse(*RSK(m), output='matrix') == m for m in M)
True

sage: n = ZZ.random_element(200)
sage: p = Permutations(n).random_element()
sage: is_fine = True if p == f(p) else p ; is_fine
True

Same for Edelman-Greene (but we are checking only the reduced words that can be obtained using the reduced_word() method from permutations):

sage: g = lambda w: RSK_inverse(*RSK(w, insertion='EG'), insertion='EG', output='permutation')
sage: all(p.reduced_word() == g(p.reduced_word()) for n in range(7) for p in Permutations(n))
True

sage: n = ZZ.random_element(200)
sage: p = Permutations(n).random_element()
sage: is_fine = True if p == f(p) else p ; is_fine
True

Both tableaux must be of the same shape:

sage: RSK_inverse(Tableau([[1,2,3]]), Tableau([[1,2]]))
Traceback (most recent call last):
...
ValueError: p(=[[1, 2, 3]]) and q(=[[1, 2]]) must have the same shape
sage.combinat.rsk.robinson_schensted_knuth(obj1=None, obj2=None, insertion='RSK', check_standard=False, **options)

Perform the Robinson-Schensted-Knuth (RSK) correspondence.

The Robinson-Schensted-Knuth (RSK) correspondence is most naturally stated as a bijection between generalized permutations (also known as two-line arrays, biwords, ...) and pairs of semi-standard Young tableaux (P, Q) of identical shape. The tableau P is known as the insertion tableau and Q is known as the recording tableau.

The basic operation is known as row insertion P \leftarrow k (where P is a given semi-standard Young tableau, and k is an integer). Row insertion is a recursive algorithm which starts by setting k_0 = k, and in its i-th step inserts the number k_i into the i-th row of P by replacing the first integer greater than k_i in the row by k_i and defines k_{i+1} as the integer that has been replaced. If no integer greater than k_i exists in the i-th row, then k_i is simply appended to the row and the algorithm terminates at this point.

Now the RSK algorithm starts by initializing two semi-standard tableaux P_0 and Q_0 as empty tableaux. For each nonnegative integer t starting at 0, take the pair (j_t, k_t) from p and set P_{t+1} = P_t \leftarrow k_t, and define Q_{t+1} by adding a new box filled with j_t to the tableau Q_t at the same location the row insertion on P_t ended (that is to say, adding j_t such that P_{t+1} and Q_{t+1} have the same shape). The iterative process stops when t reaches the size of p, and the pair (P_t, Q_t) at this point is the image of p under the Robinson-Schensted-Knuth correspondence.

This correspondence has been introduced in [Knu1970], where it has been referred to as “Construction A”.

For more information, see Chapter 7 in [Sta-EC2].

We also note that integer matrices are in bijection with generalized permutations. In addition, we can also convert any word w (and any permutation) to a generalized permutation by considering the top line to be (1, 2, \ldots, n) where n is the length of w.

The optional argument insertion allows to specify an alternative insertion procedure to be used instead of the standard Robinson-Schensted-Knuth insertion. If the input is a reduced word of a permutation (i.e., a type A Coxeter element), one can set insertion to 'EG', which gives Edelman-Greene insertion, an algorithm defined in [EG1987] Definition 6.20 (where it is referred to as Coxeter-Knuth insertion). The Edelman-Greene insertion is similar to the standard row insertion except that if k_i and k_i + 1 both exist in row i, we only set k_{i+1} = k_i + 1 and continue.

INPUT:

  • obj1, obj2 – Can be one of the following:
    • A word in an ordered alphabet
    • An integer matrix
    • Two lists of equal length representing a generalized permutation
    • Any object which has a method _rsk_iter() which returns an iterator over the object represented as generalized permutation or a pair of lists.
  • insertion – (Default: 'RSK') The following types of insertion are currently supported:
    • 'RSK' – Robinson-Schensted-Knuth
    • 'EG' – Edelman-Greene (only for reduced words of permutations/type A Coxeter elements)
  • check_standard – (Default: False) Check if either of the resulting tableaux should be standard tableau.

EXAMPLES:

If we only give one line, we treat the top line as being (1, 2, \ldots, n):

sage: RSK([3,3,2,4,1])
[[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]]
sage: RSK(Word([3,3,2,4,1]))
[[[1, 3, 4], [2], [3]], [[1, 2, 4], [3], [5]]]
sage: RSK(Word([2,3,3,2,1,3,2,3]))
[[[1, 2, 2, 3, 3], [2, 3], [3]], [[1, 2, 3, 6, 8], [4, 7], [5]]]

With a generalized permutation:

sage: RSK([1, 2, 2, 2], [2, 1, 1, 2])
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]
sage: RSK(Word([1,1,3,4,4]), [1,4,2,1,3])
[[[1, 1, 3], [2], [4]], [[1, 1, 4], [3], [4]]]
sage: RSK([1,3,3,4,4], Word([6,2,2,1,7]))
[[[1, 2, 7], [2], [6]], [[1, 3, 4], [3], [4]]]

If we give it a matrix:

sage: RSK(matrix([[0,1],[2,1]]))
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]

We can also give it something looking like a matrix:

sage: RSK([[0,1],[2,1]])
[[[1, 1, 2], [2]], [[1, 2, 2], [2]]]

There are also variations of the insertion algorithm in RSK, and currently only Edelman-Greene insertion is supported:

sage: RSK([2,1,2,3,2], insertion='EG')
[[[1, 2, 3], [2, 3]], [[1, 3, 4], [2, 5]]]

We reproduce figure 6.4 in [EG1987]:

sage: RSK([2,3,2,1,2,3], insertion='EG')
[[[1, 2, 3], [2, 3], [3]], [[1, 2, 6], [3, 5], [4]]]

There is also RSK_inverse() which performs the inverse of the bijection on a pair of semistandard tableaux. We note that the inverse function takes 2 separate tableaux inputs, so to compose with RSK(), we need to use the python * on the output:

sage: RSK_inverse(*RSK([1, 2, 2, 2], [2, 1, 1, 2]))
[[1, 2, 2, 2], [2, 1, 1, 2]]
sage: P,Q = RSK([1, 2, 2, 2], [2, 1, 1, 2])
sage: RSK_inverse(P, Q)
[[1, 2, 2, 2], [2, 1, 1, 2]]

TESTS:

Empty objects:

sage: RSK(Permutation([]))
[[], []]
sage: RSK(Word([]))
[[], []]
sage: RSK(matrix([[]]))
[[], []]
sage: RSK([], [])
[[], []]
sage: RSK([[]])
[[], []]
sage: RSK(Word([]), insertion='EG')
[[], []]
sage.combinat.rsk.robinson_schensted_knuth_inverse(p, q, output='array', insertion='RSK')

Return the generalized permutation corresponding to the pair of tableaux (p,q) under the inverse of the Robinson-Schensted-Knuth algorithm.

For more information on the bijeciton, see RSK().

INPUT:

  • p, q – Two semi-standard tableaux of the same shape

  • output – (Default: 'array') if q is semi-standard:

    • 'array' – as a two-line array (i.e. generalized permutation or biword)
    • 'matrix' – as an integer matrix

    and if q is standard, we can have the output:

    • 'word' – as a word

    and additionally if p is standard, we can also have the output:

    • 'permutation' – as a permutation
  • insertion – (Default: RSK) The insertion algorithm used in the bijection. Currently only 'RSK' and 'EG' (Edelman-Greene) are supported.

EXAMPLES:

If both p and q are standard:

sage: t1 = Tableau([[1, 2, 5], [3], [4]])
sage: t2 = Tableau([[1, 2, 3], [4], [5]])
sage: RSK_inverse(t1, t2)
[[1, 2, 3, 4, 5], [1, 4, 5, 3, 2]]
sage: RSK_inverse(t1, t2, 'word')
word: 14532
sage: RSK_inverse(t1, t2, 'matrix')
[1 0 0 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 1 0 0]
[0 1 0 0 0]
sage: RSK_inverse(t1, t2, 'permutation')
[1, 4, 5, 3, 2]
sage: RSK_inverse(t1, t1, 'permutation')
[1, 4, 3, 2, 5]
sage: RSK_inverse(t2, t2, 'permutation')
[1, 2, 5, 4, 3]
sage: RSK_inverse(t2, t1, 'permutation')
[1, 5, 4, 2, 3]

If the first tableau is semistandard:

sage: p = Tableau([[1,2,2],[3]]); q = Tableau([[1,2,4],[3]])
sage: ret = RSK_inverse(p, q); ret
[[1, 2, 3, 4], [1, 3, 2, 2]]
sage: RSK_inverse(p, q, 'word')
word: 1322

In general:

sage: p = Tableau([[1,2,2],[2]]); q = Tableau([[1,3,3],[2]])
sage: RSK_inverse(p, q)
[[1, 2, 3, 3], [2, 1, 2, 2]]
sage: RSK_inverse(p, q, 'matrix')
[0 1]
[1 0]
[0 2]

Using the Edelman-Greene insertion:

sage: pq = RSK([2,1,2,3,2], insertion='RSK'); pq
[[[1, 2, 2], [2, 3]], [[1, 3, 4], [2, 5]]]
sage: RSK_inverse(*pq, insertion='EG')
[2, 1, 2, 3, 2]

Note

Currently the constructor of Tableau accept as input lists that are not even tableaux but only filling of a partition diagram. This feature should not be used with RSK_inverse.

TESTS:

From empty tableaux:

sage: RSK_inverse(Tableau([]), Tableau([]))
[[], []]

Check that RSK_inverse() is the inverse of RSK() on the different types of inputs/outputs:

sage: f = lambda p: RSK_inverse(*RSK(p), output='permutation')
sage: all(p == f(p) for n in range(7) for p in Permutations(n))
True
sage: all(RSK_inverse(*RSK(w), output='word') == w for n in range(4) for w in Words(5, n))
True
sage: from sage.combinat.integer_matrices import IntegerMatrices
sage: M = IntegerMatrices([1,2,2,1], [3,1,1,1])
sage: all(RSK_inverse(*RSK(m), output='matrix') == m for m in M)
True

sage: n = ZZ.random_element(200)
sage: p = Permutations(n).random_element()
sage: is_fine = True if p == f(p) else p ; is_fine
True

Same for Edelman-Greene (but we are checking only the reduced words that can be obtained using the reduced_word() method from permutations):

sage: g = lambda w: RSK_inverse(*RSK(w, insertion='EG'), insertion='EG', output='permutation')
sage: all(p.reduced_word() == g(p.reduced_word()) for n in range(7) for p in Permutations(n))
True

sage: n = ZZ.random_element(200)
sage: p = Permutations(n).random_element()
sage: is_fine = True if p == f(p) else p ; is_fine
True

Both tableaux must be of the same shape:

sage: RSK_inverse(Tableau([[1,2,3]]), Tableau([[1,2]]))
Traceback (most recent call last):
...
ValueError: p(=[[1, 2, 3]]) and q(=[[1, 2]]) must have the same shape
sage.combinat.rsk.to_matrix(t, b)

Return the integer matrix corresponding to a two-line array.

INPUT:

  • t – The top line of the array
  • b – The bottom line of the array

OUTPUT:

An m \times n-matrix (where m and n are the maximum entries in t and b respectively) whose (i, j)-th entry, for any i and j, is the number of all positions k satisfying t_k = i and b_k = j.

EXAMPLES:

sage: from sage.combinat.rsk import to_matrix
sage: to_matrix([1, 1, 3, 3, 4], [2, 3, 1, 1, 3])
[0 1 1]
[0 0 0]
[2 0 0]
[0 0 1]