Description
Title: The Robinson-Schensted-Knuth Algorithm for Real Matrices
Abstract: The Robinson-Schensted-Knuth (RSK) correspondence is a bijection
from the set of matrices with non-negative integer entries onto the set of
pairs of semistandard Young tableaux (SSYT) of the same shape. SSYT can be
expressed as integral Gelfand-Tsetlin patterns. We will show how Viennot's
light-and-shadows algorithm for computing the RSK correspondence can be
extended from matrices with non-negative integer entries to matrices with
non-negative real entries, giving rise to real Gelfand-Tsetlin patterns.
This real version of the RSK correspondence is piecewise-linear. Indeed,
interesting combinatorial problems count lattice points in polyhedra, and
interesting bijections are induced by volume-preserving piecewise-linear
maps.