The Robinson-Schensted-Knuth correspondence, usually called the RSK correspondence, is a combinatorial procedure in mathematics that pairs every matrix of non-negative whole numbers with a matching pair of semistandard Young tableaux having the same shape. The column sums of the matrix become the weight of one tableau and the row sums become the weight of the other, so the numeric structure of the matrix is captured entirely in the shapes and entries of the two tableaux. It extends an earlier correspondence, the Robinson-Schensted correspondence, which applied only to permutation matrices, to the broader case of matrices with any non-negative integer entries. Transposing the original matrix simply swaps the two tableaux, a symmetry that carries over unchanged from the narrower earlier version.
Connections
In Field
Source Robinson-Schensted-Knuth correspondence (Wikipedia)
Sources
Robinson-Schensted-Knuth correspondence (Wikipedia)
Lead sectionQuote, Lead section
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.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.