Double Crystals of Binary and Integral M

We introduce a set of operations that we call crystal operations on matrices with entries either in {0, 1} or in N. There are horizontal and vertical forms of these operations, which commute with each other, and they give rise to two different structures of a crystal graph of type A on these sets of matrices. They provide a new perspective on many aspects of the RSK correspondence and its dual, and related constructions. Under a straightforward encoding of semistandard tableaux by matrices, the operations in one direction correspond to crystal operations applied to tableaux, while the operations in the other direction correspond to individual moves occurring during a jeu de taquin slide. For the (dual) RSK correspondence, or its variant the Burge correspondence, a matrix M can be transformed by horizontal respectively vertical crystal operations into each of the matrices encoding the tableaux of the pair associated to M, and the inverse of this decomposition can be computed using crystal operations too. This decomposition can also be interpreted as computing Robinson’s correspondence, as well as the Robinson-Schenssted correspondence for pictures. Crystal operations shed new light on the method of growth diagrams for describing the RSK and related correspondences: organizing the crystal operations in a particular way to determine the decomposition of matrices, one finds growth diagrams as a method of computation, and their local rules can be deduced from the definition of crystal operations.