\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Marc A. A. van Leeuwen}
%
%
\medskip
\noindent
%
%
{\bf Double Crystals of Binary and Integral Matrices}
%
%
\vskip 5mm
\noindent
%
%
%
%
We introduce a set of operations that we call crystal operations on matrices
with entries either in $\{0,1\}$ or in~$\bffam 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-Schensted correspondence for pictures. Crystal
operations shed new light on the method of growth diagrams for describing the
RSK and related correspondences: organising 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. The Sch\"utzenberger involution
and its relation to the other correspondences arise naturally in this
context. Finally we define a version of Greene's poset invariant for both of
the types of matrices considered, and show directly that crystal operations
leave it unchanged, so that for such questions in the setting of matrices
they can take play the role that elementary Knuth transformations play for
words.
\bye