\documentclass[12pt,a4paper]{amsart}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
%\usepackage{pictex}
\usepackage{amssymb}
%\usepackage{tabmac}
\usepackage{multicol}
%!!!!\usepackage{multido}
%\usepackage{pstricks}
%\usepackage{pstricks-add}
\usepackage{young}
\usepackage[enableskew]{youngtab}
\usepackage{graphicx}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[british]{babel}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hoffset -10mm\addtolength{\textwidth}{25mm}
%\def\proof{\trivlist \item[\hskip \labelsep {\it Proof:}]}
%\let \endproof \endtrivlist
%\newcommand{\bdem}{\begin{proof}}
%\newcommand{\edem}{\hfill $\square$ \end{proof}}
\def\diag{\operatorname{diag}}
\def\caH{{\mathcal H}}
\def\caF{{\mathcal F}}
\def\caS{{\mathcal S}}
\def\caT{{\mathcal T}}
\def\caU{{\mathcal U}}
\def\caR{{\mathcal R}}
\def\caA{{\mathcal A}}
\def\caB{{\mathcal B}}
\def\caC{{\mathcal C}}
\def\caK{{\mathcal K}}
\def\caP{{\mathcal P}}
\def\caQ{{\mathcal Q}}
\def\sh{\mathrel\sqcup\joinrel\mathrel\sqcup\!}

\numberwithin{equation}{section}


\theoremstyle{plain}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{cor}[lemma]{Corollary}
\newtheorem{teor}[lemma]{Theorem}
\newtheorem{mteor}[lemma]{Main Theorem}
\newtheorem{prop}[lemma]{Proposition}

\theoremstyle{definition}
\newtheorem{alg}{Algorithm}[section]
\newtheorem{defi}{Definition}[section]
\newtheorem{ex}{Example}[section]
%
\theoremstyle{remark}
\newtheorem{nota}{Remark}[section]

\begin{document}

\newbox\Adr
\setbox\Adr\vbox{ \centerline{\sc Olga Azenhas$^1$ and Ricardo
Mamede$^2$} \vskip18pt \centerline{CMUC}
 \centerline{Department of Mathematics, University of Coimbra}
\centerline{3001-454 Coimbra, Portugal}}

\title[Matrix tableau-pairs]{Matrix
 tableau-pairs with key and shuffling conditions}
\author[Olga Azenhas and Ricardo Mamede]{\box\Adr}


\thanks{$^1$ Work supported by Centre for Mathematics,
University of Coimbra, CMUC/FCT, and SFRH/BSAB/515/2005,
 grant by the Portuguese Foundation of Science and Technology, FCT, at
the Combinatorics Group, Fakult\"at f\"ur Mathematik, Universit\"at
Wien, 
 Austria}
 \thanks{$^2$ Work supported by Centre for Mathematics,
University of Coimbra, CMUC/FCT}

\address{CMUC, Department of Mathematics, University of Coimbra, 3001-454
Coimbra, Portugal}


\begin{abstract}
It has been shown that the sequence of Smith invariants defined by
certain sequences of products of matrices, with entries in a local principal
ideal domain, are combinatorially described by tableau-pairs $(T,K)$
where $T$ is a tableau of skew-shape which rectifies to the
key-tableau $K$. It is a fact that the set of all shuffles of the
columns of a key-tableau is a subset of its Knuth class. Here, under
the condition that the word of $T$ is a 
shuffle of the columns of the key-tableau $K$, we show the
converse, that is, every tableau-pair under the aforesaid restrictions
has a matrix construction. 
In the case of a four-letter alphabet, since we are able to give an
explicit description of the Knuth class of a key-tableau as a union
of the shuffles of certain subsets of words containing the key-tableau
columns, our 
 construction is general. This may be seen as an indication of a
general procedure if a subset of shuffling generators of a generic
key-tableau Knuth class is provided. At the moment however, this
seems to be a very difficult 
problem.
\end{abstract}


\maketitle

\section{Introduction}


Given an $n$ by $n$ nonsingular matrix $A$, with entries in a local
principal ideal domain with prime $p$, by Gau\ss ian elimination one
can reduce $A$ to a diagonal matrix $\Delta_{a}$ with diagonal
entries $p^{a_1},\ldots,p^{a_n}$, for unique nonnegative integers
${a_1}\ge\ldots\ge {a_n}$, called the {\em Smith normal form} of
$A$. The diagonal entries $p^{a_1},\cdots,p^{a_n}$ are called the
Smith invariants or invariant 
factors of $A$, and $a=({a_1},\ldots, {a_n})$ the {\em invariant
partition} of $A$. It is known that $a$, $b$, and $c$ are invariant
partitions of nonsingular matrices $A$, $B$, and $C$ such that
$AB=C$ if and only if there exists a Littlewood--Richardson tableau
$T$ of type $(a,b, c)$, that is, a tableau of shape $c/a$ which
rectifies to the key-tableau of weight $b$ (also known as Yamanouchi tableau of
weight $b$). 
 (See \cite{ap,apwh, az5,az2,az1,f1,f2,green,klein,th}.) The
relationship between Smith invariants 
and the product of Schur functions was noticed earlier by several
authors \cite{green,klein, th}. For an overview and other
relations, see the survey by W. Fulton \cite{f2} as well as
\cite{f1,f3}.



Given a natural number $n\ge 1$, $[n]$ denotes the set $\{1,\dots ,n\}$.
 Let
$m=(m_1,\ldots,\break m_t)$ be a finite sequence of nonnegative
integers. The symmetric 
group $\mathfrak{S}_t$ acts on sequences of $t$ nonnegative integers
{\em via} the 
left action $s_i\,m=(m_1,\ldots, m_{i+1},m_i,\ldots, m_t)$ with $s_i$
the simple transpositions of $\mathfrak{S}_t$, $1\le i\le t-1$. Let
$\alpha(m)$ 
be the unique partition in the orbit $\mathfrak{S}_t m$, and $\alpha(m)'$ the
conjugate partition. $K(m)$ denotes the key-tableau \cite{keys} of
weight $m$, that is, 
the tableau of weight $m$ and {\em shape} $\alpha(m)$, and
$D_{[m_k]}$ denotes the $n$ by $n$ diagonal matrix having
 the $i$th diagonal entry equal to $p$
whenever $i\in [m_k]$ and $1$ otherwise. The conjugate invariant partition of
$D_{[m_k]}$ is the one-row partition $(m_k)$. We
identify $K(m)$ with the sequence of diagonal matrices
 $(D_{[m_1]},\dots,D_{[m_t]})$ in the following sense: the sequence
of conjugate invariant partitions associated 
 with the sequence of products of matrices
$$D_{[m_1]}, D_{[m_1]}D_{[m_2]}, \dots,  D_{[m_1]}D_{[m_2]}\cdots
 D_{[m_t]}$$ 
is the nested sequence of partitions
$({m_1})\subseteq\alpha({m_1},{m_2})\subseteq\dots \subseteq
 \alpha(m)$ which
 defines the key-tableau $K(m)$ by telling us that for each $1\le
i\le t$ the first $m_i$ columns contain the letter $i$. (We adopt the
English convention for Young diagrams.) For instance, 
 $$K(1032)=\begin{matrix}
 1&3&3&\\
 3&4&&&\\
 4&&&&\;\;\mbox{ is identified with}
\;\;(D_{[1]},D_{\emptyset},D_{[3]},D_{[2]}).\\ 
 \end{matrix}$$
Let $U$ be an $n$ by $n$ unimodular matrix, that is, the
 determinant of $U$ is not divisible by $p$. 
Put $\Delta_{a}U K(m)$ for the sequence
 $\Delta_{a},$ $\Delta_{a}U D_{[m_1]},$ $\Delta_{a}U D_{[m_1]}
D_{[m_2]}, $ 
 $\ldots,$\break $\Delta_{a}U
 D_{[m_1]}D_{[m_2]}\cdots D_{[m_t]}$. The sequence of
 conjugate invariant partitions ${a^0}'=a'\subseteq
{a^1}'\subseteq\dots\subseteq {a^t}'=c',$ associated with that
sequence of matrices, 
 is such that the skew-shape ${a^{k+1}}'/{a^{k}}'$ has $m_{k+1}$
boxes with at most one box in each column, 
 $k=0,1,\ldots,t-1$.
 Thus $\Delta_{a}U K(m)$ is identified with the tableau-pair $(T,
 K(m))$ where $T$ is the tableau of weight $m$ defined by that
nested sequence of the {\em conjugate} 
 partitions. It is shown in \cite{am2} that $T$ rectifies to $K(m)$.
The
reverse question arises naturally: {\em Given a tableau-pair
$(T,K)$ such that $K$ is a key-tableau and $T$ is a semistandard
Young tableau that rectifies to $K$, does 
there exist a matrix construction of the form $\Delta_a UK(m)$ for
that pair?}
This question has been already answered positively for
some instances of the weight in the orbit of $\mathfrak{S}_ t
\alpha(m)$ \cite{ap,az5,az2,az1,am1}. These are precisely instances
where the Knuth class of a key-tableau is equal to the set of shuffles
of its columns. In \cite{am2}, 
a necessary and sufficient condition has been given for the Knuth
class of a key-tableau to be equal to the set of the shuffles of its
columns. In particular, the shuffles of the columns of a key-tableau
are always contained in its Knuth class. 
 Here, in Section~4, an algorithm is provided for the matrix construction
 of such a tableau-pair $(T,K)$ whenever the word of $T$ is a
shuffle of the columns of $K$. It is also shown how to extend our
matrix construction
 to any pair $(T,K)$, over a four-letter alphabet, whenever
 $T $ rectifies to the key-tableau $K$. In the case of a four-letter
alphabet it is shown in \cite{am2} that the Knuth class of a
key-tableau is the union of the shuffles of some subsets of words
where the set of columns is included. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%biword%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The matrix construction of a tableau-pair $(T,K)$, where the word of
$T$ is a shuffle of the columns of the key-tableau $K$, relies on the
following idea: a semistandard Young tableau, with a word of length
$\ell$, can be encoded by a biword $\Lambda$ without repeated
biletters $\displaystyle{ \binom{\pi_j}{x_j}}$ where $x_j$ is a letter
in column $\pi_j$ of $T$, for $j=1,\ldots,\ell$. Among the
semistandard Young tableaux with biword $\Lambda$ there is one in
compact form (a tableau where the number of rows of 
 size two of any two consecutive columns is maximal when shifting
down the rightmost with respect to the other). Let $c/a$ be its 
skew-shape. A semistandard Young tableau with biword $\Lambda$ has
therefore skew-shape $(c'+e)'/(a'+e)'$, for some partition $e$. As
the word of $T$ is a shuffle of the columns of $K$, we may choose a
biword $\Pi$ factorized into biwords whose bottom words are the
columns of the key-tableau $K$. These factors are identified with
east--northeastward paths in the lattice $\mathbb{N}^2$, seen as an
$\mathbb{N}$--matrix, whose vertices $(\pi_j,{x_j})$ are the
biletters $\binom{\pi_j}{x_j}$. These lattice paths do not intersect
and satisfy some properties which allow us to define an injective map
to be used in the Main Algorithm in Section~4. The Main Algorithm
depends only on the biword $\Pi$ identified with its lattice path
representation. It provides a matrix construction, for any $T$ with
that biword, based on elementary matrices $T_{ij}(x)=I+xE_{ij}$ whose
indices $\{i\,j\}$ are generated by the vertices of those lattice
paths. 
 If we want a simultaneous matrix construction of $T$ and $K$, we have
to select a specific biword that one shows to exist always. This is
achieved in Section~5 by relating certain type of vertices in the
lattice paths of the biword with the existence of a commutation
property when passing an elementary matrix $T_{ij}(x)$ past another
$T_{a b}(y)$. 




%%%%%%%%%%%%%%%%%%%%%%%%organization of the paper%%%%%%%%%%%%%%%%%%%%%%%%%%%555
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5




The paper is organized in six sections. In the next section, which in
its turn is divided into three subsections, we provide the necessary
definitions on tableau and word combinatorics. Special attention is
given, 
 in Subsection~2.2,
 to key-tableaux and, in particular, to those over a four-letter
alphabet where the description of the Knuth class is translated into
the shuffling operation. 
 In Section~3, divided into two subsections, a semistandard Young
tableau is encoded by a biword without repeated letters. When the
word of the tableau is a shuffle of the columns of a key-tableau, we
choose a biword that factorizes into biwords which are identified with
east--northeastward lattice paths in $\mathbb N^2$. These
nonintersecting lattice paths enjoy certain properties that allow us
to define in Algorithm \ref{defs} an injective map that will be an
important tool in the next section. Section~4 provides the Main
Algorithm which generates a matrix construction of $T$ whenever the
word of $T$ is a shuffle of the columns of a key-tableau $K$. Stated
informally, 
the main theorem (see Theorem~\ref{teorrm1}) is: there exists a biword
that generates simultaneously a matrix construction of $T$ and $K$
whenever the word of $T$ is a shuffle of the columns of the
key-tableau $K$. In the succeeding section, a biword obeying certain
conditions is exhibited and the proof of the main theorem is
given. Finally, in Section~6, it is shown that, over a four-letter
alphabet, every tableau-pair $(T,K)$, where $T$ rectifies to the
key-tableau $K$, has a matrix construction. In the last section, we
discuss the generalization of our construction to a $t$-letter
alphabet, for $t\ge 5$. A pertinent problem is the enumeration of the
elements of a key-tableau Knuth class which is related with the
enumeration of distinct permutation shuffles in the work of
C. S. Barnes \cite{cbarnes}. 









\section{Young tableaux, keys, and shuffles}

\subsection{ Young tableaux, words, and Knuth equivalence}

 A {\em partition} $a=(a_1, \ldots,\break a_l)$ is a weakly decreasing
sequence of positive integers. We call $l$ the {\em length} of $a$
which is denoted by $\ell(a)$. We say that $a$ is a partition of
$|a|:=a_1+\cdots+a_l$. It is convenient to set $a_k=0$ for
$k>\ell(a)$, and we identify $a$ with
$(a_1,\dots,a_{\ell(a)},0,\dots,0)$, where the tail of zeros is of
arbitrary length. The unique partition of $0$ is denoted by
$(0)$. A ({\em weak}) {\em composition} 
 $m=(m_1,\dots, m_t)$ is a finite sequence of nonnegative integers. We
also say that $m$ is a weak composition of $|m|:=m_1+\cdots+m_t$. 
 The symmetric group $\mathfrak{S}_t$ acts on (weak) compositions
with $ t$ entries {\em via} the left action $\sigma
m:=(m_{\sigma^{-1}(1)},\ldots,m_{\sigma^{-1}(t)})$, with $\sigma \in
\mathfrak{S}_t$. 
The unique partition in the orbit
$\mathfrak{S}_t m$ is denoted by $\alpha( m)$. We think of a partition
 in terms of its {\em Young diagram} consisting of a left-justified array
 of boxes that, according to the English convention, has $a_i$ boxes
in the $i$th row counting from top to bottom. 
For instance, the Young diagram of $a=(5,2,2,1)$ is
{\small
$$\yng(5,2,2,1).$$}%
\noindent The {\em conjugate partition} of $a$ is the partition $a'$ whose
Young diagram is obtained from $a$ by interchanging rows
with columns. Another way to look at the conjugate of $a$, which will
be used in the sequel, is to say that 
 if $a=(a_1,\ldots,a_t)$ and $\ell_k$ is the number of columns of
length $k$ in the Young diagram of $a$, $1\le k\le t$, then
$a'=(t^{\ell_t},\ldots,2^{\ell_2},1^{\ell_1})$, where the notation
$i^{\ell_i}$ means that the positive integer $i$ appears $\ell_i$
times in the sequence $a'$. 
 Conversely, we have
 $a_k=a_{k+1}+\ell_k$, for $k=1,\ldots,t$, with $a_{t+1}:=0$. 
%The notation $i^{\ell_i}$ in the partition $a'$ means that the
positive integer $i$ appears $\ell_i$ times in the sequence $a'$. 
For example, the conjugate partition of $a=(5,2,2,1)$
is the partition $(4,3,1,1,1)=(4,3,2^0,1^3)$, and its Young diagram is
{\small
$$\yng(4,3,1,1,1).$$}%
A partition $a$ is contained in a partition $c$, written $a\subseteq
c$, if the Young diagram 
of $a$ is contained in the Young diagram of $c$. In this case, we
define the skew-shape 
$c/a$ to be the set of boxes in the Young diagram of $c$ that remains
after we remove 
those boxes corresponding to $a$. When $a=(0)$, we obtain the Young
diagram of $c$. 


Let $\mathbb{N}$ be the set of positive integers with the usual
order $``\leq"$.
If $t\in\mathbb{N}$, $[t]$ denotes the set
$\{1,\ldots,t\}$,
and $[t]^*$ the free monoid in the alphabet $[t]$. That is, the
collection of all finite words over the alphabet $[t]$, with the
concatenation operation. A word over the alphabet $[t]$ is defined to
be a finite string of elements 
(known as letters) of the set $[t]$.


 Given the word $w=x_1\cdots x_k$ over the alphabet $[t]$, the {\it
 weight} of $w$, in the alphabet $[t]$, is the
vector $(m_{1},\ldots,m_{t})$, where $m_x$ denotes
 the multiplicity of the letter $x\in [t]$ in the word $w$. Here $k$
is the {\em length} of 
$w$, denoted by $\ell(w)$. We have $\ell(w)=m_{1}+\cdots+m_{t}$ and,
in particular, the 
length and the weight of the empty word is zero. A {\em subword} of
a word $w$ is a word obtained by deleting the letters at some (not
necessarily adjacent) positions in $w$. As usual, we write $w^k$,
$k\ge 0$, to mean the concatenation of $w$ with itself $k$ times. 
 When one writes $x_1x_2 \dots x_k=1^{m_1}2^{m_2}\dots t^{m_t} $ this
means that 
$w$ is a weakly increasing word, called a {\it row word}, and
$x_1 = \dots= x_{m_1} = 1$, $x_{m_1+1} = \dots = x_{m_1+m_2} = 2$,
$\dots $, $x_{m_1+\dots+m_{t-1}+1} = \dots = 
 x_k= t$. Similarly we have a weakly decreasing word when we write
$x_1x_2 \dots x_k=t^{m_t}\dots 2^{m_2} 1^{m_t} $. 
If the letters in $w$ are in
strictly decreasing order, that is, $x_i>x_{i+1}$ for all $i$, $w$
is called a {\it column word}. A column word is often
identified with its {\em support}, that is, with the set consisting of
its letters. For example, the word $431$ is identified with the set
$\{1,3,4\}$. 


 A (semistandard) Young tableau $T$ of
shape $c/a$ (for short skew-tableau) is a filling of the skew-shape $c/a$ with
positive integers, weakly increasing across each row and strictly
increasing down each column \cite{ful,loth}. If $a=(0)$ then $T$ is
said to be of partition shape. The 
(reading) word of $T$ is the word obtained by reading its columns from
bottom to top, starting on the left and moving to the right.
The weight of $T$ is the
weight of its word. A Young tableau of partition shape
is identified with its (reading) word.
The empty tableau
is the Young tableau of shape $(0)$ identified with the empty word.
 \begin{ex} \label{yy} A (semistandard) Young tableau $T$
of skew-shape $(4,4,2,1)/(3,2)$ with weight $(1,2,2,1)$ and word $433221$,
{\small
\begin{equation}
\young(:::1,::22,33,4).
\end{equation}}%
\end{ex}









A Young tableau $T$ of shape $c/a$ and weight $(m_1,\ldots,m_t)$ may also
be seen as a nested sequence of partitions
$T=(a^0,a^1,\ldots,a^t)$, where $a=a^0\subseteq
a^1\subseteq\cdots\subseteq a^t=c$, such that for $k=1,\ldots,t$,
the skew-diagram $a^k/a^{k-1}$ has $m_k$ boxes with at most one box in
each column, and it is filled with the letter 
$k$ \cite{mac}. In Example~\ref{yy}, we may write
$T=(a^0,a^1,a^2,a^3,a^4)$, where $a^0=(3,2)\subseteq a^1=(4,2)\subseteq
a^2=(4,4)\subseteq a^3=(4,4,2)\subseteq a^4=(4,4,2,1)$.






The Knuth or plactic congruence $\equiv$ \cite{schu,ful,k,loth} on the
words over the alphabet $[t]$
 is the congruence in $[t]^*$ defined by the transitive closure
 of the relations
\begin{equation}\label{K1}
 uxzyv\equiv
uzxyv,\;\;x\leq y< z,\nonumber
\end{equation}
\begin{equation}\label{K2}
 uyzxv\equiv
uyxzv,\;\;x<y\leq z\nonumber
,\end{equation}
where $x,y$ and $z$ are letters in $[t]$, and $u$ and $v$ are words in
$[t]^*$. Every Knuth class has one and only one Young tableau of
partition shape. Henceforth, each Knuth or plactic class consists of
all words Knuth equivalent to the unique Young tableau in the Knuth
class. Using {\em jeu de taquin slides} every semistandard tableau can
be {\em rectified} to the unique tableau in the Knuth class of its
word \cite{ful,sa,st}. In Example~\ref{yy}, $T$ is rectified to
$4321\,32\equiv 433221$. 
Two Young tableaux are said to be Knuth equivalent if they can be obtained 
from another by {\em jeu de taquin} slides. 
Equivalently, they have the same rectification.

The {\it overlap} of
a pair $(u,v)$ of column words $u$ and $v$ is the maximum number of rows of
 length two that one can obtain by putting the column $u$ to the left
of the column $v$ so that the two columns together form a skew-tableau.
For instance, the overlap of $(43,21)$ is zero while the overlap of
$(43,32)$ is one. 
A skew-tableau is said to be in {\em compact form} if the number of rows of
 size two of any two consecutive columns is the overlap of the words
comprising those columns. For instance 
the skew-tableau in Example~\ref{yy} is in compact form. Any 
skew-tableau may be put in compact form using {\em jeu de taquin} slides
in consecutive 
rows.


\subsection{Key-tableaux and shuffles}

 A {\em key-tableau}
$K$ is a tableau whose columns are pairwise
comparable in the inclusion order \cite{keys}. Given a composition $m$, the
key-tableau of weight $m$ is the tableau $K(m)$ of shape $\alpha(m)$
whose first $m_j$ columns contain the letter $j$ for all $j$. This
defines an obvious bijection between key-tableaux and compositions 
\cite{shimoz}. A
key-tableau is also a tableau whose weight is a permutation of its
shape. The key-tableau $K(m)$ 
\cite{am2,keys} may be written as
\begin{equation}\label{key}K(m)={\rm v}_{t}^{\ell_t}{\rm v}_{
{t-1}}^{\ell_{t-1}}\ldots {\rm v}_{1}^{\ell_1},\end{equation} 
\noindent where $\{1,\dots,t\}={\rm v}_{t}\varsupsetneqq {\rm v}_{t-1}
\varsupsetneqq\dots\varsupsetneqq {\rm v}_{1}\neq \emptyset$ are
column words such that
$\alpha(m)=(\ell_1+\ldots+\ell_t,\ldots,\ell_{t-1}+\ell_t,\ell_t)$,
and its conjugate is $\alpha'(m)=(t^{\ell_t},\ldots,1^ {\ell_1})$. 
 Let $\sigma\in \mathfrak{S}_t$, written as a word $a_1a_2\dots a_t$
in $[t]^*$, be such that $\{a_1,\ldots,a_i\}$ is the support of ${\rm
v}_i$, 
 for $i=1,\dots, t$. One has $\sigma\alpha(m)=m=(m_1,\ldots,m_t)$,
with $m_j=\sum_{k=\sigma^{-1}(j)}^t\ell_k$ for all $j$. Therefore the
key $K(m)$ may be encoded by a permutation $\sigma$ and a nonnegative
integral vector $(\ell_t,\ldots, \ell_1)$, that is, $K(\sigma,
(\ell_t,\ldots, \ell_1)):= {\rm v}_{t}^{\ell_t}{\rm v}_{
{t-1}}^{\ell_{t-1}}\ldots {\rm v}_{1}^{\ell_1}$. (This presentation of a
key-tableau will be used in Section~6.) 
 \begin{ex}
 The key-tableau
 $$K(1,2,2,1)=\text {\small$\begin{Young}
 1&2\cr
 2&3\cr
 3\cr
 4\cr
 \end{Young}$}=4321\,32$$
 \noindent has shape
$(2,2,1,1)$ and weight $m=(1,2,2,1)$. \end{ex}
The Knuth class of the word $433221$ of the skew-tableau $T$ in
Example~\ref{yy} is the key-tableau $K(1,2,2,1)=4321\,32$ (the
empty space means the ending of a column and the starting of a new
one) which can be encoded either by permutation $2314$ or $3214$, and
the nonnegative integral vector $(1,0,1,0)$. 






Let $w=x_1\cdots x_k\in [t]^*$. Given
$I=\{i_1<\cdots<i_r\}\subseteq[k]$, $w|I$ denotes the subword $
x_{i_1}\cdots x_{i_r}$. In particular, $w|I$ is the empty word if 
$I=\emptyset$. Two subwords $w|I$ and $w|J$ of $w$ are said to be
disjoint if 
the sets $I$ and $J$ are disjoint.

The word $w=x_1\cdots x_k$ is said to be a {\it shuffle} of the words
$u$ and $v$ 
if there exists a partition
 $\{I,J\}$ of the set $[k]$ such
that $u=w|I$ and $v=w|J$. Let
$u_1,\ldots, u_q\in [t]^*$ be $q$ words of lengths $k_1,\ldots,k_q$,
respectively. If $q=0$ the shuffle is the empty word. If $q\ge 1$, let
 $\{I_1,\ldots, I_q\}$ be a partition of the set $[k]$. Then the word
$w|\{I_1,\ldots, I_q\}$ defined by $w|I_j=u_j$, for $j=1,\ldots,q$,
is a {\it shuffle} of $u_1,\ldots,u_q$ \cite{shuf,lie}. 
The words $u_1,\ldots,u_q$ are said to be the {\it shuffle components} of
$w|\{I_1,\ldots, I_q\}$. Indeed $w|\{I_1,\ldots,
I_q\}=w|\{F_1,\ldots, F_q\}$ whenever 
$\{I_1,\ldots, I_q\}=\{F_1,\ldots, F_q\}$. However, a word may have
different shuffle decompositions 
 of the same words, that is, $w|\{I_1,\ldots,
I_q\}=w|\{J_1,\ldots, J_q\}$ with $\{I_1,\ldots,
I_q\}\neq\{J_1,\ldots, J_q\}$ set partitions 
of $[k]$. For example, if
$w=433221\in[4]^*$, we have
$w|\{\{1,2,5,6\},\{3,4\}\}= $ \linebreak $w|\{\{1,2,4,6\},\{3,5\}\}$.
The set of the shuffles of the $q$ words
$u_1,\ldots,u_q$, is the set of all words obtained by shuffling
together the $q$ words 
$u_1,\ldots,u_q$,
\begin{multline*}
\sh(u_1,\ldots,u_q)\\=
$$\{w|\{I_1,\ldots,I_q\}: \{I_1,\ldots,I_q\} \;\mbox{a set partition
of}\; [k], w|I_j=u_j, \; 1\le j\le q\}.
\end{multline*}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%
















Let $K(m)={\rm v}_{t}^{\ell_t}{\rm v}_{ {t-1}}^{\ell_{t-1}}\ldots
{\rm v}_{1}^{\ell_1}$ be the key as in \eqref{key}, and $\sigma\in
\mathfrak{S}_t$ such that $\sigma\alpha(m)=m$. 
By Greene's Theorem~\cite{greene}, the set $\sh
({\rm v}_{t}^{\ell_t},{\rm v}_{ {t-1}}^{\ell_{t-1}},\ldots,{\rm v}_{1}^{\ell_1})$ is
always a subset, 
in general proper, of the Knuth class of $K(m)$. In
\cite{am2} it was proved that, if ${\rm f}_1\supseteq {\rm f}_2\supseteq \cdots
\supseteq {\rm f}_k$ are nonempty column words, then the Knuth class of
$K={\rm f}_1\dots {\rm f}_k$ is equal to the set of all shuffles of its columns
if and only if each column is either an interval of ${\rm f}_1$, or is
obtained from an interval of ${\rm f}_1$ by removing a single letter. It
is clear that this property is true for any key $K(m)={\rm
v}_{t}^{\ell_t}{\rm v}_{ {t-1}}^{\ell_{t-1}}\cdots {\rm v}_{1}^{\ell_1}$ 
 over the alphabet $\{1,2\}$ or $\{1,2,3\}$. However,
 over the alphabet $\{1,2,3,4\}$, considering $
S:=\{1423,1432,4123,4132\}\subseteq\mathfrak{S}_4$, this property
holds if and only 
if either $\sigma\notin S$, or $\sigma\in S$ but $\ell_2=0$ or
$\ell_4=0$.

Denote by
$\widehat{{\rm v}_5}^{n_5}$ the multiset consisting of $n_5$ words
$\widehat{{\rm v}}_5:=431421\equiv K(2,1,1,2)$. The Knuth class of a
key over the alphabet $\{1,2,3,4\}$ was 
characterized in \cite{am2}, in terms of the shuffling operation, as follows.

\begin{teor}\label{t2} \cite{am2}
 Let $\sigma\in\mathfrak{S}_4$, and let $(\ell_4,\ldots, \ell_1)$
be a sequence of nonnegative integers. The Knuth class of 
 $K(\sigma,(\ell_4,\ldots, \ell_1))={\rm v}_{4}^{\ell_4}{\rm v}_{
{3}}^{\ell_{3}}{\rm v}_2^{\ell_2}{\rm v}_{1}^{\ell_1}$ is 
$$
\begin{cases}
\sh( {\rm v}_{4}^{\ell_4},{\rm v}_{ {3}}^{\ell_{3}},{\rm
v}_2^{\ell_2},{\rm
v}_{1}^{\ell_1}),&\kern-4pt
\mbox{ if }\sigma\in\mathfrak{S}_4\setminus S,\mbox{
or }\sigma\in S\mbox{ and }(\ell_2=0 \mbox{ or } \ell_4= 0),\\ 
\bigcup_{n_5=0}^{\min\{\ell_2,\ell_4\}}\sh( \widehat{{\rm
v}}_5^{\,n_5},{\rm v}_{4}^{n_4},\ldots,{\rm v}_{1}^{n_1}),&
\kern-4pt
\mbox{ if
}\sigma\in S\mbox{ and }\ell_2\neq 0, \,\ell_4\neq 0,\\ 
\end{cases}
$$
where $n_i=\ell_i$, $i=1,3$, and $n_i=\ell_i-n_5$, $i=2,4$.



\end{teor}








\section{Biwords and nonintersecting E-NE lattice paths}
\subsection{Biwords}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Our aim is, given a (skew) semistandard Young tableau in compact
form, to encode it by a biword so that, identifying their biletters
with points in the lattice $\mathbb N^2$, seen as an $\mathbb
N$--matrix, one is able to define the elementary matrices of our
matrix construction in Section~4. All the tableaux with that biword
will be related with the tableau in compact form. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 Given $n,~t\in\mathbb{N}$, a biword over the alphabet $[n]\times [t]$
is an ordered pair of words of the same length, written as 

 $$\begin{pmatrix}u\\v
\end{pmatrix}=\begin{pmatrix}
{\pi_1}&\cdots&{\pi_k}\\
x_1&\cdots&x_k
\end{pmatrix},$$ \noindent with $u=\pi_1\dots\pi_k\in [n]^*$ and
$v=x_1\dots x_k\in [t]^*$. Each biword 
$\begin{pmatrix}u\\v
\end{pmatrix}$
can also be seen as a word whose letters are the biletters $\begin{pmatrix}
{\pi_1}\\
x_1
\end{pmatrix},\dots$, $\begin{pmatrix}
{\pi_k}\\
x_k
\end{pmatrix}.$
We only consider biwords with pairwise distinct biletters, that is,
$\begin{pmatrix} 
{\pi_i}\\
x_i
\end{pmatrix}\neq \begin{pmatrix}
{\pi_j}\\
x_j
\end{pmatrix}$, for every $i\neq j$. Two biwords are said to be {\em
equivalent} if they have the same set of biletters. 
Among the biwords having the same set of biletters as $\begin{pmatrix}u\\v
\end{pmatrix}$ we consider two special ones, $\Sigma$ and
$\Sigma'$. The weakly increasing rearrangement of $\begin{pmatrix}u\\v

\end{pmatrix}$ using the anti-lexicographic order on biletters with
priority in the top entry \cite{loth}, that is, $\begin{pmatrix} 
{\pi}\\
x
\end{pmatrix}\le \begin{pmatrix}
{\pi}'\\
x'
\end{pmatrix}$ if and only if $\pi<\pi'$, or $\pi=\pi'$ and $x\ge
x'$, gives the biword 
\begin{equation}\label{sigma}
\Sigma=\begin{pmatrix}
1^{f_1}&\cdots&n^{f_n}\\
 {\rm w}_1&\cdots&{\rm w}_n
\end{pmatrix},
\end{equation}
for some integers $f_i\geq 0$, such that $w={\rm w}_1\cdots{\rm w}_n\in[t]^*$,
with ${\rm w}_i$ a column word of length $f_i$.
 The weakly decreasing rearrangement of $\begin{pmatrix}u\\v
\end{pmatrix}$ using the lexicographic order in biletters with
priority on the bottom entry \cite{loth}, that is, $\begin{pmatrix} 
{\pi}\\
x
\end{pmatrix}\ge \begin{pmatrix}
{\pi}'\\
x'
\end{pmatrix}$ if and only if $x>x'$, or $x=x'$ and $\pi\ge \pi'$,
gives the biword 
\begin{equation}\label{sigma'}
\Sigma'=\begin{pmatrix}
J_t&\cdots&J_1\\
t^{m_t}&\cdots&1^{m_1}
\end{pmatrix},
\end{equation}
for some integers $m_i\geq 0$, such that $J=J_t\cdots J_1\in[n]^*$,
with $J_i$ a column word of length $m_i$. We have then the word-pair
$(J,w)\in [n]^*\times [t]^*$ such that the weight of $w$ is equal to 
$(m_1,\ldots,m_t)=(\#J_1,\ldots,\#J_t)$ and the weight of $J$ is
$(\ell({\rm w}_1),\ldots,\ell({\rm w}_n))$. (Recall that column words are
identified with their supports.) 
 







Young tableaux in compact form are in one to one correspondence with
classes of biwords without repeated biletters. Young tableaux with
the same biword have the same word pair $(J,w)$, hence their 
skew-shapes are $(c'+e)'/(a'+e)'$, where $e$ is any partition
of length at most $n$, and $c/a$ is
the skew-shape of the compact tableau with that biword. For instance,
$\text {\small$\young(:::1,::22,33,4)$}\;\mbox{and}\;
\text {\small$\young(:::1,::22,:3,3,4)$}$ have the same biword. 
Let $ T$ be a tableau of skew-shape with $n$ columns (possibly some
are empty), where the word $w$ has 
 weight $m=(m_1,\dots, m_t)$. Let $\displaystyle \binom{\pi_j}{x_j}$
be the biletter where $x_j$ is the letter in column $\pi_j$ of
$T$, for $j=1,\dots,\ell(w)$. 
 Any biword over the alphabet $[n]\times[t]$ with these biletters
is said to be a {\em biword of $T$}. In particular, 
$\Sigma= \left(\begin{array}{ccc}
1^{f_1}&\cdots&n^{f_n}\\
 {\rm w}_1&\cdots&{\rm w}_n
\end{array}\right)$ is the biword of $T$ where
 the factor $\left(\begin{array}{c}i^{f_i}\\ {\rm
w}_i\end{array}\right)$ indicates 
that ${\rm w}_i$ is a column word of length $f_i$ filled in 
column $i$, counting from left to right, of the skew-shape $T$. For
each $i$ in $[t]$, 
$J_i\in[n]^*$ is the column word defined by the indices of the
columns of $T$ where the $m_i$ letters $i$ of $w$ are placed. The
column words $J_1,\ldots,J_t$ are called the {\it indexing sets} of
$T$ and $J=J_t\cdots J_1$ the {\it indexing-set word}.

 A biword class, over the alphabet $[n]\times [t]$, without repeated
biletters, shall be represented in the lattice $\mathbb{N}^2$ by
identifying its set of biletters $\binom{y}{i}$ with the set of 
 points $(y,i)$, where $y\in J_i$, for $i=1,\ldots,t$, called the
{\em lattice diagram} of the biword class. Those points, graphically
represented as $\bullet$, are called {\em lattice points} or {\em
vertices} of a biword in the class. For convenience, in drawing the
lattice $\mathbb{N}^2$, we 
adopt the matrix convention, that is, the first coordinate,
the row index, increases as one goes downwards, and the second
coordinate, the column index, increases as one goes from left to
right.
\begin{ex} The skew-tableau $T$ in Example~\ref{yy} has biword
$\Sigma=\begin{pmatrix} 
11\;2\;3\;44\\
43\;3\;2\;21\\
\end{pmatrix}$ and the corresponding lattice diagram, contained in
$\{1,2,3,4\}\times \{1,2,3,4\}$, is 
\begin{equation}\label{gd0}
\parbox{4cm}{$T=\text {\small$\young(:::1,::22,33,4)$}~\longleftrightarrow$}
\parbox{3cm}{\small$\young(::34,::3,:2,12)$}
\parbox{3cm}{$
\begin{pmatrix}
11\;2\;3\;44\\
43\;3\;2\;21\\
\end{pmatrix}~\leftrightarrow$}
\parbox{3.5cm}{\includegraphics[scale=0.9,trim = 0cm 19.3cm 0cm
0cm,clip]{grelha1}.} 
\end{equation}
Note that the lattice vertex marginal cardinalities, by
rows respectively columns, 
are $(2,1,1,2)$, which are the corresponding lengths
of the columns of $T$, and $(1,2,2,1)$, which are the corresponding
multiplicities of each letter in $T$. 
\end{ex}







%-------------------------------------------------------------------


\subsection{Nonintersecting E-NE lattice paths}

In this section we consider biwords where the bottom word $w$ of
$\Sigma$ is in 
the Knuth class of the key-tableau \eqref{key} and is a shuffle of
its columns, that is, $w$ is in the set $\sh ({\rm v}_t^{\ell_t},\ldots,
 {\rm v}_1^{\ell_1})$. We are interested in the biwords $\Pi$
equivalent to $\Sigma$ with bottom word the key ${\rm
v}_{t}^{\ell_t}\cdots 
{\rm v}_{1}^{\ell_1}$. They are in one to one correspondence with the
 shuffle decompositions of $w$ in
$\sh ({\rm v}_{t}^{\ell_t},\ldots,{\rm v}_{1}^{\ell_1})$. Let
$\{F^{t,\ell_t}, \ldots,F^{t,1}, \ldots,F^{1,\ell_1}, 
 \ldots,F^{1,1}\}$ be a set partition of $\{1,\dots,\sum_{k=1}^t
k\,\ell_k\}$ such that
$\displaystyle{\Sigma|F^{k,j}=\binom{I^{k,j}}{{\rm v}_k}}$, for
$k\in[t]$ and $j\in[\ell_k]$, which 
 generates the biword
\begin{equation}\label{bi5}
 \Pi=\begin{pmatrix}
I^{t,\ell_t}&\cdots&I^{t,1}&\cdots&I^{2,\ell_2}&\cdots&I^{2,1}&
I^{1,\ell_1}&\cdots&I^{1,1}\\
{\rm v}_t&\cdots& {\rm v}_t&\cdots&{\rm v}_{2}&\cdots&
{\rm v}_{2}&{\rm v}_{1}&\cdots& {\rm v}_{1}
\end{pmatrix},
\end{equation}
where each $I^{j,i}$ is a weakly increasing word with $|I^{j,i}|=j$,
for $j=1,\ldots, t$,
 and $i=1,\ldots,\ell_j$.
 In the lattice diagram of $\Pi$ we link the
vertices of any two consecutive biletters 
in the factor $\left(\begin{array}{c}
I^{j,i}\\
{\rm v}_{j}
\end{array}\right)$ of $\Pi$, for $1\le i\le \ell_j$, $1\le j\le
t$, with a straight line. 
Considering the last and the first biletters of this factor,
respectively, as the starting and the ending points, one gets a
lattice path with $j$ vertices made of eastward E and northeastward NE
steps. 
These lattice paths do not have vertices in common since the
biletters of $\Pi$ are pairwise distinct. This means that the biword
$\Pi$ 
(\ref{bi5}) is graphically represented by $\ell_t+\cdots+\ell_1$
 nonintersecting northeastward-eastward E-NE lattice paths, where
$\ell_j$ of them have length 
 $j$, for $j=1,\dots, t$.
 Conversely, every word in $\sh ({\rm v}_{t}^{\ell_t},\ldots,{\rm
v}_{1}^{\ell_1})$ may be obtained in this way using the points of the
lattice diagram of $\Pi$ to draw all the $\ell_t+\cdots+\ell_1$ 
 nonintersecting northeastward-eastward lattice paths, where $\ell_j$
of them have $j$ vertices, for $j=1, \dots, t$. 
For the rest of the paper, we identify a biword $\Pi$ with its lattice path
representation in $\mathbb{N}^2$ where each factor $\left(\begin{array}{c}
I^{j,i}\\
{\rm v}_{j}
\end{array}\right)$, for $i=1,\ldots, \ell_j$, $j=1,\ldots, t$, is
seen as the lattice path of length $j$ whose 
vertices are the biletters of this factor.

\begin{ex}\label{2ex}
The word in the second row of the biword $\Sigma$ in
\eqref{gd0} is a shuffle of $4321$ and $32$. We may sort the
biletters of $\Sigma$ in several ways, in order to obtain all biwords
$\Pi$ as in \eqref{bi5}, which is equivalent to draw in the lattice
diagram \eqref{gd0} all the sets of two nonintersecting paths of
lengths four and two using northeast-eastward steps. We have then four
types of northeast-eastward nonintersecting paths: 
\begin{equation*}
\parbox{3.8cm}{\includegraphics[scale=0.8,trim = 0cm 19.1cm 0cm
0cm,clip]{ex41},} 
\parbox{3.8cm}{\includegraphics[scale=0.8,trim = 0cm 19.1cm 0cm
0cm,clip]{ex42},} 
\parbox{3.8cm}{\includegraphics[scale=0.8,trim = 0cm 19.1cm 0cm
0cm,clip]{ex43},} 
\parbox{3.8cm}{\includegraphics[scale=0.8,trim = 0cm 19.1cm 0cm
0cm,clip]{ex44},} 
\end{equation*}
each corresponding to the biwords
\begin{equation}\label{bi3}
\Pi\!=\!\begin{pmatrix}
1144&23\\
4321&32
\end{pmatrix}\!,\,\Pi'\!=\!\begin{pmatrix}
1234\quad 14\\
4321\quad 32
\end{pmatrix}\!,\,\Pi^{\dagger}\!=\!\begin{pmatrix}
1244&13\\
4321&32
\end{pmatrix}\!\text{ and }\!\,\Pi^{\ddagger}\!=\!\begin{pmatrix}
1134\quad 24\\
4321\quad 32
\end{pmatrix},
\end{equation}
respectively.
\end{ex}






\begin{nota} \label{inclusion} As the ${\rm v}_i$'s are column words, the
lattice paths do not have northward steps. 
Recalling that the column words of a key-tableau are pairwise
 comparable for the inclusion order, the sets of
column indices of any two paths of $\Pi$ are comparable
for the inclusion order. In particular,
any pair of two lattice paths of $\Pi$ is such that, if one of the
paths has a vertex in a column of $\mathbb N^2$ and the other has
not, then the set of the indices of the columns of the latter is
contained in the set of the former. 
 The lattice paths with the longest length have vertices in all
columns of the lattice diagram of $\Pi$. We may therefore identify
$\Pi$ with a collection of nonintersecting E-NE paths in $[n]\times
[t]$ such that the sets of the indices of the columns are comparable
for the inclusion order. 
\end{nota}

We still have to fix more terminology.
Given two lattice paths $u$ and $v$ having each a vertex in column
$k$, we say that $u$ is {\it above} [respectively {\it below}] $v$
in column $k$ if the vertices $(a,k)\in u$ and $(x,k)\in v$ satisfy
$a<x$ [respectively $a>x$]. Given two consecutive vertices $(a,b)$
and $(x,y)$ of a lattice path, we say that $(a,b)$ is {\em
positively-linked} to $(x,y)$ if $b<y$ (recall that we have always $a\geq x$).
Otherwise, $(a,b)$ is said to be {\em negatively-linked} to $(x,y)$. If
$(a,b)$ is positively-linked to $(x,y)$ and $a>x$, then $(a,b)$ is
called an {\it obstacle}. An obstacle is a vertex where a
northeast step starts. A lattice path without obstacles is a 
lattice path with only east steps, that is, all the vertices of the
path are in the same row. 



For instance, in the lattice representation of $\Pi'$ \eqref{bi3}, the
path $\begin{pmatrix}1234\\4321\end{pmatrix}$ is above the path
$\begin{pmatrix}14\\32\end{pmatrix}$ in column 2, and below 
it in column 3. The vertex $(4,1)$ is an obstacle NE-linked to $(3,2)$,
 and thus the vertex $(3,2)$ is negatively linked to $(4,1)$.




We define now a map $s:\Pi\longrightarrow \mathbb{N}$ which assigns to
each vertex of $\Pi$ the index of a specific row in the lattice diagram of
$\Pi$. This map will be used in the matrix construction given by
the Main Algorithm in Section~4.
 The algorithm below defining this map is based on the following two
observations which are a consequence of Remark \ref{inclusion}. Pick a
vertex $(\tilde a,\tilde b)$ in $\Pi$. 
If $(\tilde a,\tilde b)$ is the initial vertex of a path, the first
vertex of $\Pi$ (if any) that one meets when one moves to the west
is an obstacle. 
If $(\tilde a,\tilde b)$ is not the initial vertex of a path,
 and if the first vertex of $\Pi$ one meets, when one moves to the
west, does not belong to the path containing $(\tilde a,\tilde b)$, 
 then $(\tilde a,\tilde b)$ is negatively linked to an
obstacle. Moreover, if the first vertex, that one has met in the west,
is not an obstacle but it is positively linked, say to $(\tilde
a,\tilde f)$, then $(\tilde a,\tilde b)$, or some vertex $(\tilde a,
\tilde d)$, $\tilde d\ge \tilde b$, in the same path, is itself an
obstacle in a path with a vertex in column $\tilde f>\tilde d\ge
\tilde b$. See Example~\ref{exce}. 


\begin{alg}\label{defs}
Consider the biword $\Pi$ in \eqref{bi5} and its lattice path
representation. Let $(a,b)$ be a vertex of $\Pi$. Let $y:=0$ if
$(a,b)$ is the initial vertex of 
a path, otherwise, let $y$ be the index of the column containing the
vertex positively linked to $(a,b)$. 
Write $(\tilde a,\tilde b):=(a,b)$, set $x:=\tilde a$ and implement the
following algorithm:

Begin



$1.$ Starting in $(\tilde a,\tilde b)$ move one step
$(1,0)$ in $\mathbb{N}^2$ to the west. Do $\tilde b:=\tilde b-1$.

 \qquad If $\tilde b=y$, then $x:=\tilde a$ and stop.

 \qquad Else $\tilde b>y$ and go to $2$.


$2.$ If $(\tilde a,\tilde b)$ is an obstacle of $\Pi$, then
 move northeast along the path
linking positively the obstacle $(\tilde a,\tilde b)$ to the
vertex $(\tilde c,\tilde d)\in \Pi$, with $\tilde d\leq b$. Set
$(\tilde a,\tilde b):=(\tilde 
c,\tilde d)$ and go to $1$.

\quad Else go to $3.$

$3.$
If $(\tilde a,\tilde b)$ is positively linked to some vertex $(\tilde
a,\tilde d)$ with ${\tilde b}+1<\tilde d$, then set $\tilde b:=\tilde
d$ and go to 1. 

\quad Else, go to $1.$

 End.

\end{alg}

\begin{nota}
 When applying the above algorithm, we always move to the west until we
reach column $y$, except when we meet an obstacle, as in step 2, in which
case we move northeast, or we meet a vertex positively linked to some
other vertex in the same row to the east of our current position, as
in step 3, in which 
case we move east. After an east move, in step 3, we will be forced to
make a northeast move along an obstacle. Since the number of obstacles
is finite, the algorithm 
must terminate.
\end{nota}


The last point in $\mathbb{N}\times \mathbb{Z}_{\ge 0}$ that one
reaches in the algorithm is $(x,y)$ which may or may not be in
$\Pi$. Nevertheless, $x$ is the row index of the last vertex of
$\Pi\setminus \{(x,y)\}$. 


\begin{defi} \label{path} Let $(a,b)\in \Pi$. The
sequence of vertices of $\Pi\setminus \{(x,y)\}$ that one passes in
the algorithm above from the vertex 
$(a,b) \in \Pi$ to vertex $(x,y)\in \mathbb{N}\times \mathbb{Z}_{\ge
0}$ is called the $(a,b)$-path.
\end{defi}

The $(a,b)$-path contains at least the vertex $(a,b)\in \Pi$, and has
odd length. 
This procedure defines the map $$s:\Pi\longrightarrow\mathbb{N},$$
where $s(a,b):=x$ 
is the row index of the last vertex in the $(a,b)$-path.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\begin{ex}\label{eex1}\label{eex2}
 Consider the biword $\Pi$ in \eqref{bi3}.
 The vertices in one row always belong to a unique path. Thus, we
have always $s(a,b)=a$ for every vertex $(a,b)$ in $\Pi$. 
Consider now $\Pi'$ in w\eqref{bi3}. There exists a row containing
vertices belonging to different paths. To compute the
$(4,2)$-path, notice that $(4,1)$ is an obstacle. 
 Thus, one must move along the line linking this obstacle to
$(3,2)$. Since there are no more obstacles in row 3 to the west 
 of $(3,2)$, the $(4,2)$-path is $(4,2),(4,1),(3,2)$ and $s(4,2)=3$.
Starting from any other vertex $(a,b)$ of $\Pi$, we will face no
obstacle, and thus $s(a,b)=a$. 
\end{ex}


\begin{ex}\label{exx1}
 Consider the biword $\Pi=\left(\begin{array}{c}
 22233\;1344\;345\;2\\
 54321\;5321\;531\;1\\
 \end{array}\right)$ whose lattice path representation is
 \begin{equation}\label{cvI1}
\includegraphics[scale=0.9,trim = 0cm 18.5cm 0cm 0cm,clip]{grelha10}.
\end{equation}
 We have $s(4,3)=2$ since the obstacle $(4,2)$ is linked to a vertex
in row 3, and $(3,2)$ is another obstacle that appears 
 to its left, linked to a vertex in row 2. The $(4,3)$-path is
$(4,3),(4,2),(3,3),(3,2),(2,3)$ of length five. 
 Similarly, we find that
 $s(3,3)=2$,
 $s(3,5)=1$, and $s(2,1)=1$ whose $(2,1)$-path consists only of
$(2,1)$. For any other vertex $(a,b)$ of $\Pi$, we get $s(a,b)=a$. 
\end{ex}


\begin{ex}\label{exce}
Consider now the following lattice path representation:
$$\includegraphics[scale=0.9,trim = 0cm 19.7cm 0cm 0cm,clip]{grelha11}.$$
We have $s(3,6)=s(2,6)=1$. For any other vertex $(a,b)$ of $\Pi$, we
get $s(a,b)=a$. 
\end{ex}


\begin{lemma}\label{sdef}
Let $F$ be the set of all initial vertices of lattice paths of
$\Pi$. Then the map $s:F\rightarrow \mathbb{N}$
sending $(a,b)\in F$ into $s(a,b)$ is an injection.
\end{lemma}
\begin{proof}
Let $A$ and $B$ denote the $(a,b)$ and $(c,d)$-paths, respectively,
where $(a,b)$ and $(c,d)$ are distinct initial vertices of lattice
paths in $F$. We will show that, 
 after any common vertex, the two paths $A$ and $B$ follow distinct
directions: one goes west and the other goes northeast, continuing
their way in different rows. Thereby $A$ and $B$ can not have the
last $\Pi$ vertex in the same row. If $A$ and $B$ would have the last
$\Pi$ vertices in the same row, they should coincide. But then one
goes west and stops in this row, and the other goes northeast and
stops in a row above. 
This is absurd. Hence, $s(a,b)\neq s(c,d)$.

Let $(e,f)$ in $A\cap B$. The vertex $(e,f)$ appears in $A$ either if
$e=a$, or if it is negatively linked to an obstacle in $A$, or if it
is negatively linked to a vertex $(e,f-k)$, $k\geq 2$, in $A$. 
In the first case, the vertex $(e,f)$ must be an obstacle in $A$, and
therefore when constructing the path $B$ we must move northeast by
step 2, while in $A$ we move west. 
In the second case, in the path $A$ we move west by step 1, while in
the path $B$ we move northeast, since $(e,f)$ must be an obstacle. 
If $(e,f)$ is the first vertex where the two paths meet, then $(e,f)$
has to be an obstacle. By induction assume that the paths $A$ and $B$
have never shared a common line connecting two consecutive vertices of
a path in $\Pi$. 
Finally, in the third case, the path $A$ arrives at vertex $(e,f)$
after passing through a vertex, say $(e,y)$ with $f-k<y<f$, negatively
linked to an obstacle in $A$. After $(e,f)$ we go to west by step 1
and then northeast. If $(e,f)\in B$, then the lattice path $B$ arrives
at this vertex by step 1. After this vertex, either we go northeast
along an obstacle, or go east if $(e,f)$ is positively linked to some
vertex $(e,f+k')$. In any case, after these steps, we will move
northeast using a lattice path distinct from the one used in $A$. 
Therefore, after $(e,f)$ the two paths $A$ and $B$ follow distinct
directions, and, in particular, the paths $A$ and $B$ never share a
common line connecting two consecutive vertices of a path in $\Pi$. 
As the number of vertices is finite it follows that $s(a,b)\neq s(c,d)$.
\end{proof}








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5



\section{Matrix tableau-pairs with key and shuffle conditions:
statement of results} 

Let ${\mathcal R}_p$ be a local principal ideal domain with maximal
ideal $(p)$. A unit in ${\mathcal R}_p$ is an element that is not
divisible by $p$. Every nonzero element $x$ may be written in the form
$\mu p^k$ with $k\ge 0$ and $\mu$ a unit in ${\mathcal R}_p$, both
uniquely determined by $x$. Two elements $x$ and $y$ are said to be
{\em associated} if $x=\mu y$ for some unit $\mu$ in ${\mathcal
R}_p$. In this paper, all matrices are $n$ by $ n$ and 
nonsingular with entries over $\mathcal R_p$. Given a matrix $A$,
$A^T$ denotes its transpose. A matrix is said to be unimodular if its
determinant is a unit. Let ${\mathcal U}_n$ be the group of $n$ by $
n$ 
unimodular matrices over ${\mathcal R}_p$. Given $n$ by $ n$
matrices $A$ and $B$, we say that $B$ is {\it left equivalent} to
$A$ (written $B\sim_L A$) if $B=UA$ for some $U\in \caU_n$; $B$ is
{\it right equivalent} to $A$ (written $B\sim_R A$) if $B=AV$ for
some $V\in\caU_n$; and $B$ is {\it equivalent} to $A$ (written
$B\sim A$) if $B=UAV$ for some $U,V\in\caU_n$. The relations
$\sim_L$, $\sim_R$ and $\sim$ are equivalence relations in the set
of all $n$ by $ n$ nonsingular matrices over ${\mathcal R}_p$. (For
more details see \cite{new}.) 

Let $A$ be an $n$ by $n$ nonsingular matrix. By the Smith normal form theorem,
Theorem~\cite{B,new}, there exist nonnegative integers $a_1,\dots,a_n$
with $a_1\geq\cdots\geq a_n\geq 0$ such that $A$ is equivalent to
the diagonal matrix $\diag _p(a_1,\dots,a_n)$ having $p^{a_i}$ in the
$i$-th diagonal position. The sequence $a=(a_1,\dots,a_n)$ of the 
exponents of the $p$-powers in the Smith normal form of $A$ is a
partition of length $\leq n$, uniquely determined by the matrix $A$.
We call $a$ the {\it invariant partition} of $A$. Given a subset
$J\subseteq[n]$, put $D_J:=\diag _p(\chi^J)$, where $\chi^J$ is the
nonnegative integer vector having 1 at position $i$ if $i\in J$, and
$0$ otherwise. If $\sigma\in\mathfrak{S}_n$, 
 $P_{\sigma}$ denotes the permutation matrix having
$\delta_{i\sigma(j)}$ in position $(i,j)$. As usual, if $u$ and $v$
are positive integers, $(u\;v)$ 
denotes the transposition of $u$ and $v$.



Let $(i,j)\in [n]\times [n]$. We denote by $E_{ij}$ the $n$ by $n$
matrix having a $1$ in position 
$(i,j)$ and $0's$ elsewhere, and we define the elementary unimodular
matrices $T_{ij}(x)$ as follows:
\begin{eqnarray}
 T_{ij}(x)=I+xE_{ij},&\mbox{ where }i\neq j\mbox{ and
 }x\in{\mathcal R}_p;\nonumber\\
 T_{ii}(v)=I+(v-1)E_{ii},&\mbox{ where }v\mbox{ is a unit of
 }{\mathcal R}_p.\nonumber\
\end{eqnarray}
It is obvious that $E_{ij}E_{rs}=\delta_{jr}E_{is}$. Therefore, if
$i\neq j$ and $r\neq s$, we find that
$T_{ij}(x)T_{rs}(y)=I+xE_{ij}+yE_{rs}+xy\delta_{jr}E_{is}$. The lemma
below states two kinds of rules to be used in the sequel: (I) for
commuting either two elementary 
matrices $T_{ij}(x)$, or an elementary matrix $T_{ij}(x)$ with an
elementary diagonal matrix $D_{[m]}$; (II) is concerned with the
appearance of a permutation matrix when one elementary matrix passes
past another. 
The proof is left to the reader.

\begin{lemma} \label{mtij1}
Let $i,j,r,s,m\in[n]$, and $x,y,v\in\caR_p$, such that $v$ is a
unit. Then,

\noindent {\em (I) (Commutation rules)}

\item $(i)$
$T_{ij}(x)T_{rs}(y)=T_{rs}(y)T_{ij}(x)$, whenever $i\neq s$ and
$j\neq r$.

\item $(ii)$ $T_{ij}(x)T_{js}(y)=T_{js}(y)T_{ij}(x)T_{is}(xy)$, if $i\neq
s$, $i\neq j$.

\item $(iii)$ $T_{ii}(v)T_{rs}(x)=T_{rs}(ux)T_{ii}(v)$, for some unit $u$.

\item $(iv)$
$T_{ji}(y)T_{ij}(xp)=T_{ij}(u_1xp)T_{ii}(u_2)T_{jj}(u_3)T_{ji}(u_4y)$

$\quad=T_{ij}(u_1xp)T_{ji}(u_5y)T_{ii}(u_2)T_{jj}(u_3)$,
for some units $u_i$, $i=1,\ldots,4,5$.

\item $(v)$ $T_{ij}(x)D_{[m]}=D_{[m]}T_{ij}(x)$, if $i,j>m$.

\item $(vi)$ $T_{ij}(x)D_{[m]}=D_{[m]}T_{ij}(xp)$, if $i>m\geq j\geq 1$.

\item $(vii)$ $T_{ij}(xp)D_{[m]}=D_{[m]}T_{ij}(x)$, if $j>m\geq i\geq 1$.

\noindent {\em (II) (Anti-commutation rule)}

\item $(viii)$ $T_{ji}(-1)T_{ij}(1)=T_{jj}(-1)T_{ij}(1)P_{(i\,j)}$, $i\ne j$.
\end{lemma}

The lemma says that there exists always a unimodular elementary
matrix
 $E$ such that
\begin{equation*}
T_{ji}(\tau)T_{ab}(\tau')=T_{ab}(\varrho')T_{ji}(\varrho)E,\;
\mbox{with $\varrho$, $\tau$ and $\varrho'$, $\tau'$ pairs of
associated elements,} 
\end{equation*}
whenever $\tau$, $\tau'$ are not both unities, 
or $(a,b)\neq (i,j)$ if
$i\neq j$.  Otherwise,
the passage of a matrix $T_{ij}(\tau)$, with $i\neq j$, to the left of a
matrix $T_{ji}(\tau')$, with $\tau$ and $\tau'$ both unities, leads to the
appearance of a nonidentity permutation matrix.

Following \cite{az5,az1,am1}, we introduce the
definition of a matrix realization of a pair of tableaux $({ T},{
F})$, where $T$ and ${ F}$ have the same weight $m$ and $F$ has
partition shape $b$. 
Let $B_r$ be a matrix with invariant partition
$(1^{m_r},0^{n-m_r})$, for $r=1,\ldots,t$. If $a^r$ is the conjugate
of the invariant partition of $A_0B_1\cdots B_r$, $0\leq r\leq t$,
then it is clear that $(a^0=a,a^1,\ldots,a^t=c)$ is a tableau with
weight $m=(m_1,\ldots,m_t)$ and shape $c/a$. Similarly, if $b^r$ is
the conjugate of the invariant partition of $B_1\cdots B_r$, $1\leq
r\leq t$, then $(b^1,\ldots,b^t=b)$ is a tableau of shape $b$ with
weight $(m_1,\ldots,m_t)$ as well (see \cite{am1}).

\begin{defi}\label{defMR}
 Let ${ T}=(a^0,a^1,\dots,a^t)$ and ${ F}=(0,b^1,\dots,b^t)$ be
 tableaux of weight $m=(m_1,\ldots,m_t)$.
 We say that a sequence of $n$ by $ n$ nonsingular
 matrices $A_0,B_1,\dots,B_t$ is a
 matrix realization of the pair $({ T},{ F})$ (or realizes
 $(T,F)$) if:
 \begin{enumerate}
 \item[I.] For each $r\in\{1,\dots,t\}$, the invariant partition 
of the matrix $B_r$ is\break
 $(1^{m_r}, 0^{n-m_r})$.
 \item[II.] For each $r\in\{0,1,\dots,t\}$, the invariant partition 
of the matrix
 $A_r:=\break A_0B_1\cdots B_r$ is the conjugate of $a^r$.
 \item[III.] For each $r\in\{1,\dots,t\}$, the invariant partition 
of the matrix
 $B_1\cdots B_r$ is the conjugate of $b^r$.
 \end{enumerate}
 The tableau-pair $({ T},{ F})$ is said to be a {\it matrix-tableau pair}.
\end{defi}

\begin{ex} Let $a=(3,2,1)$ and $F=11122$. The sequences 
$$\diag _p(a),U D_{[3]},  D_{\{4,5\}},$$
with $U$ running over the unimodular matrices of order five, give
rise to tableaux $T$ of skew-shape whose words $w$ are congruent with
tableaux $P$ 
running over $\{1 1 1 2 2;$ $\,21\,1 1 2;$ $\, 21\, 21
 \,1\}$ the set of all tableaux of weight $(3,2)$ with partition shape.
 For instance, for $U=I$, $U=P_{4321}$, and $U=P_{12543}P_{4321}$,
respectively, we have:

$(a)$
 $T=\text {\small$\young(:::22,::1,:1,1)$}
 $, $w= 11122;\qquad
 (b)$ $T=\text {\small$\young(:::12,::1,:1,2)$}
 $, $w= 21112$; and

$(c)$
 $T=\text {\small$\young(:::11,::2,:1,2)$}$, $w= 21211$.
\end{ex}


Actually, I and II, in Definition~\ref{defMR}, say that the
invariant partitions of 
$A_0,$ $A_0B_1,$ $\ldots,$ $A_0B_1\cdots B_t$ define $T$, while III
says that the invariant 
partitions of $B_1,$ $B_1B_2,$ $\ldots,$ $B_1B_2\cdots B_t$ define
$F$. Recall that the key 
$K(m)$ is the only tableau of weight $m=(m_1,\ldots, m_t)$ and
conjugate shape $\sum_{i=1}^t(1^{m_i})$, and when written as a
sequence of partitions it takes the form
$K(m)=(0,(1^{m_1}),\sum_{i=1}^2(1^{m_i}),\ldots,\sum_{i=1}^t(1^{m_i})).$

Thus, when $F=K(m)$, in order to verify property III, it is
sufficient to show that $B_1\cdots B_t$ has invariant partition
$(1^{m_1})+\cdots +(1^{m_t})$. For the purpose of this paper, we
shall consider only pairs $(T,K(m))$ such that the word of
$T$ is a shuffle of the columns of $K(m)$.
In \cite{am2}, it has been shown that $(T,K(m))$ is a matrix-tableau pair only
if the word of $T$ is an element of the Knuth class of $K(m)$. Therefore, the
following problem arises:

{\it Given a tableau-pair $(T,K(m))$ such that the word of $T$ is a
shuffle of the columns of the key $K(m)$, is
$(T,K(m))$ a matrix-tableau pair?}

 The next algorithm
and Theorem~\ref{teorrm1} give an answer to this problem. To this end,
we need the following definition and lemma.

\begin{defi}
 Given $\sigma\in\mathfrak{S}_n$ and $x\geq y$ in
 $[n]$, we define the $n$ by $ n$ matrix $S(x,y,\sigma)=E_{u\,v}$
if $\sigma(u)=x >\sigma(v)=y$, and the zero matrix otherwise. 
\end{defi}
Clearly, $I+S(x,y,\sigma)=T_{uv}(1)$
with $\sigma(u)=x$ and
$\sigma(v)=y$.
In particular, $I+S(x,x,\sigma)=I$.


\begin{lemma}\label{teorart2}
 Given $\sigma\in\mathfrak{S}_n$ and $x\geq y$ in $[n]$, we have,
for any partition $a$ of length $\leq 
 n$,
 \begin{equation}\label{l1}
\diag
_p(a)P_{\sigma}(I+S(x,y,\sigma))(I-S(x,y,\sigma)^T)\sim_L\diag
_p(a)P_{(x\:y)\sigma}. 
 \end{equation}
\end{lemma}
\begin{proof}
 Let $u,v\in[n]$ be such that $\sigma(u)=x$ and $\sigma(v)=y$.
 Then, $(I+S(x,y,\sigma))(I-S(x,y,\sigma)^T)=T_{uv}(1)T_{vu}(-1)$.
 By Lemma~\ref{mtij1} $(viii)$, the left hand side of (\ref{l1})
can be written as 
 \begin{equation}\label{l2}
 \diag _p(a)P_{\sigma}T_{uv}(1)T_{vu}(-1)=\diag
_p(a)P_{\sigma}T_{vv}(-1)T_{vu}(-1)P_{(uv)}. 
 \end{equation}
 Since $x\geq y$, we have
 $$(\ref{l2})\sim_L\diag _p(a_{\sigma(1)},\ldots,a_{\sigma(n)})P_{(uv)}
 \sim_L\diag _p(a)P_{\sigma}P_{(uv)}=\diag _p(a)P_{(x\,y)\sigma}.$$
\end{proof}



\noindent {\bf Main Algorithm.} \label{main}
Let $\Pi$ be the biword \eqref{bi5}. Our algorithm is presented
as a three-step definition:

\bigskip

{\it Step 1.} For each $k=t,\ldots,1$, let
$\mathrm{X}_k\subseteq\mathbb{N}^2$ be the set of initial
vertices of the $\ell_k$
lattice paths of length $k$ of $\Pi$, and define
$$s(\mathrm{X}_k):=\{s(x,j):(x,j)\in
\mathrm{X}_k\}=\{s^0_{\ell_{t+1}+\cdots+
\ell_{k+1}+1}<\cdots<s^0_{\ell_{t+1}+\cdots+
\ell_{k+1}+\ell_k}\}\subseteq[n],$$ 
where we set $\ell_{t+1}:=0$.
 Let $\sigma_1\in\mathfrak{S}_n$ such
that $\sigma_1(i)=s_i^0$, for $i\in[\ell_1+\cdots+\ell_t]$.

\bigskip

{\it Step 2.} For $k=1,\ldots,t-1$, let 
$$J'_k:=\{x\in
J_k:(x,k)\mbox{ is
positively-linked}\}=\{x^k_1<\cdots<x^k_{q_k}\}\subseteq
J_{k}$$ 
and
$\nu^k_0:=id\in\mathfrak{S}_n$. For each $k=1,\ldots,t-1$ and
$j=1,\ldots,q_k$, let $(y^k_j,k_j)$ be the vertex negatively-linked
to $(x^k_j,k)$, and define inductively
$$S_{x^k_jy^k_j}^{k+1}:=S(x^k_j,s(y^k_j,k_j),\nu^k_{j-1}\sigma_{k}),\mbox{
and }\nu^k_j:=(x^k_j~s(y^k_j,k_j))\nu^k_{j-1}.$$ Define
$\theta_{k+1}:=\nu^k_{q_k}$, $\sigma_{k+1}:=\theta_{k+1}\sigma_{k}$,
and
$$S_{k+1}:=\prod_{j=1}^{q_k}(I+S_{x^k_jy^k_j}^{k+1})
(I-S_{x^k_jy^k_j}^{k+1})^T.$$

\bigskip

{\it Step 3.} Let $T$ be a tableau with biword $\Pi$, and let
$c/a$ be its skew-shape. Let $A_0:=\diag _p(a')$, 
put $B_k:=S_kD_{[m_k]}$, for $k=1,\ldots,t$, with
$S_1:=P_{\sigma_1}$, and define inductively
 $$A_k:=A_{k-1}B_k.$$

\medskip


\begin{nota}\label{mainrem}
 $(a)$ The Main Algorithm only depends on the biword $\Pi$.

 $(b)$ Lemma~\ref{sdef} asserts that the permutation
$\sigma_1\in\mathfrak{S}_t$, given 
in Step~$1$ of the Main Algorithm, is well defined.

 $(c)$ The matrix $S_{x_j^k,y_j^k}^{k+1}$, defined in Step~$2$ of
the Main Algorithm, 
 is the zero matrix whenever $s(y_j^k,k_j)=x_j^k$, that is, if
$x_j^k=y_j^k$.
 Therefore, the sequence $A_0,B_1,\ldots,B_t$, obtained through
 the application of the Main Algorithm may be simplified if we
 use a biword $\Pi$ whose graphical representation has a reduced number of
 links between vertices in distinct rows.

 $(d)$ Fix a $k\in\{1,\ldots,t-1\}$, set $u_j:=$
$\sigma_k^{-1}(\nu_{j-1}^k)^{-1}(x_j^k)$, and 
 $v_j:= \break \sigma_k^{-1}(\nu_{j-1}^k)^{-1}\,(s(y_j^k,k_j))$. Then
 $I+S_{x_j^k,y_j^k}^{k+1}=T_{u_j\!v_j}(1)$,
$(I-S_{x^k_jy^k_j}^{k+1})^T=T_{v_j\!u_j}(-1)$, 
 and
 $$S_{k+1}=\prod_{j=1}^{q_k}T_{u_jv_j}(1)T_{v_ju_j}(-1).$$

 $(e)$ For $i=1,\ldots,t$, $|J_i|=m_i=\sum_{k=\sigma^{-1}(i)}^t\ell_k\ge 0$.

 $(f)$ Set
$I_k:=[\ell_{t+1}+\cdots+\ell_{k+1}+1,\ell_{t+1}+\cdots+\ell_{k+1}+\ell_k]$,
for all $k=1,\ldots,t$. Then, $\sigma_1(I_k)=s(X_k)$, for $1\leq 
 k\leq t$. In particular, $s(X_k)=\emptyset$ if and only if $\ell_k=0$.

 $(g)$ $\sigma_{k+1}=\theta_{k+1}\cdots\theta_2\sigma_1$.
\end{nota}

 We say that a partition $a$ {\em dominates} a partition $b$ if
$|a|=|b|$ and the Young diagram of $a$ is obtained by lifting some
boxes in the Young diagram of $b$. 

 \begin{prop}\label{prop1}
 Let $(T,K(m))$ be a tableau-pair such that $T$ rectifies to $K(m)$
and the word of $T$ is a shuffle of the columns of $K(m)$. Let $\Pi$
as in \eqref{bi5} be a biword 
 of $T$. Then the sequence
 $A_0,B_1,\ldots,B_t$ generated by the Main Algorithm
 is a matrix realization for $T$. In particular, $B_1,\ldots,B_t$
is a matrix realization of a Young tableau $F$ of weight $m$ whose
shape dominates $\alpha (m)$. 
\end{prop}
Given a tableau $T$ with rectification a key-tableau and whose word
is a shuffle of its columns, 
%$\sh({\rm v}_{t}^{\ell_t},\ldots,{\rm v}_{1}^{\ell_1})$,
there are, in
general, several shuffle decompositions for the word of $T$, each
corresponding to a biword $\Pi$.
In the next section, we show that it is always possible to choose a
biword $\Pi$ where the shuffling decomposition satisfies additional
properties 
so that the sequence $B_1,\ldots,B_t$ generated in the Main
Algorithm is also a matrix 
 realization of $K(m)$.

\begin{mteor}\label{teorrm1}
 Let $(T,K(m))$ be a tableau-pair such that the word of $T$ is a
shuffle of the columns of $K(m)$. 
 Then there exists a biword $\Pi$ of $T$ such that the sequence
 $A_0,B_1,\ldots,B_t$ generated by the Main Algorithm
 is a matrix realization for the pair $(T,K(m))$.
\end{mteor}

As already pointed out, it has been proved that $(T,K)$ is
 a matrix tableau-pair only if the word of $T$ is in the plactic class of $K$
\cite{am2}. Thus, when the plactic class of $K$ is the set of all
shuffles of
 its columns, we obtain the following characterization
 of matrix tableau-pairs $(T,K)$.
\begin{cor}
 Let $T$ be a (skew) Young tableau with rectification
 $P$.
 Let $K$ be a key whose plactic class
is equal to the set of all shuffles of its columns. Then, $(T,K)$ is
a matrix tableau-pair if and only if 
 $P=K$.
\end{cor}



Before giving the proofs of the statements above, we work out
some examples.

\begin{ex}\label{ex1}
 Consider the biword $\Pi=\left(\begin{array}{c}
1144\;23\\
4321\;32
\end{array}\right)$ as in \eqref{bi3} (see Example~\ref{2ex}). The word
 $433221$ is in $\sh( {\rm v}_{4}^1,{\rm v}_{3}^0,{\rm v}_{2}^1,
 {\rm v}_{1}^0)$.
Let $T$ be a tableau with biword
 $\Pi$. Then $T$ has word $433221$, indexing sets $J_1=\{4\}$,
$J_2=\{3,4\}$, $J_3=\{1,2\}$, $J_4=\{1\}$, and weight $(1,2,2,1)$. The
initial vertices of the 
lattice paths ${\rm v}_{4}$ and ${\rm v}_{2}$ are $(4,1)$ and
$(3,2)$, respectively. Recalling Example~\ref{eex1}, we have
$s_1^0=s(4,1)=4$ and $s_2^0=s(3,2)=3$, and thus
$s(\mathrm{X}_4)=\{4\}$ and $s(\mathrm{X}_2)=\{3\}$. Then, by Step~1
of the Main
Algorithm, we must consider $\sigma_1\in\mathfrak{S}_4$ satisfying
$\sigma_1(1)=4$ and $\sigma_1(2)=3$. Take, for instance,
$\sigma_1=(14)(23)$. Next, define
\begin{align*}
I+S_{4,4}^2&=I+S(4,4,\sigma_1)=I,\;\;\mbox{and}
\;\;\sigma_2=(4\,4)\sigma_1=\sigma_1;\nonumber\\
I+S_{3,2}^3&=I+S(3,2,\sigma_2)=T_{23}(1);\nonumber\\
I+S_{4,1}^3&=I+S(4,1,(3\:2)\sigma_2)=T_{14}(1),\;\;\mbox{and}
\;\;\sigma_3=(4\,1)(3\,2)\sigma_2;\nonumber\\
I+S_{1,1}^4&=I+S(1,1,\sigma_3)=I,\;\mbox{ and
}\;\sigma_4=(1\,1)\sigma_3=\sigma_3.\nonumber\
\end{align*}
 Finally, let $a'=(2,2,1,0)+(2,1,1,0)$ and define the
matrices $A_0=\diag _p(a')$, $B_1=P_{\sigma_1}D_{[1]}$,
$B_2=D_{[2]}$, $B_3=T_{23}(1)T_{32}(-1)$
$T_{14}(1)T_{41}(-1)D_{[2]}$, and $B_4=D_{[1]}$.

Clearly, $A_1=A_0B_1\sim \diag _p(a'+\chi^{J_1})$ and
$A_2=A_0B_1B_2\sim \diag _p(a'+\chi^{J_1}+\chi^{J_2})$. Since
$\sigma_3([2])=J_3$, by Lemma~\ref{teorart2}, we find that
\begin{align}
A_3&\sim_L\diag _p(a'+\chi^{J_1}+\chi^{J_2})P_{\sigma_2}B_3\sim_L
\diag _p(a'+\chi^{J_1}+\chi^{J_2})P_{\sigma_3}D_{[2]}\nonumber\\
&\sim_R\diag _p(a'+\chi^{J_1}+\chi^{J_2}+\chi^{J_3}).\nonumber\
\end{align}
Since $A_4\sim \diag _p(a'+\chi^{J_1}+\cdots+\chi^{J_4})$, the sequence
$A_0,B_1,\ldots,B_4$ satisfies conditions I and II of
Definition~\ref{defMR}. It remains to show that this sequence also
defines the key $K=4321\,32$. Bearing in mind Lemma~\ref{mtij1}, we
may write 
\begin{align}
B_1B_2B_3B_4 &=
P_{\sigma_1}D_{[1]}D_{[2]}T_{23}(1)T_{14}(1)
T_{32}(-1)T_{41}(-1)D_{[2]}D_{[1]}\nonumber\\
&=P_{\sigma_1}T_{23}(p)T_{14}(p^2)D_{[1]}D_{[2]}
T_{32}(-1)T_{41}(-1)D_{[2]}D_{[1]}\nonumber\\
&\sim_L D_{[1]}D_{[2]}T_{32}(-1)T_{41}(-1)D_{[2]}D_{[1]}\nonumber\\
&\sim_R D_{[1]}D_{[2]}D_{[2]}D_{[1]}.\nonumber\
\end{align}
Therefore, the sequence $A_0,B_1,B_2,B_3,B_4$ is a matrix
realization of the pair
$$(T=\text{\Small$\young(:::1,:::2,::2,:3,3,4)$},
K=\text{\Small$\young(12,23,3,4)$}).$$ 
\end{ex}


%--------------------------------------------




 In the next examples, we show that different
shuffle decompositions may give different matrix realizations of the same
tableau $T$ described in the previous example.
Moreover, there are shuffle decompositions that do not produce
 the tableau-pair $(T,K)$ in Theorem~\ref{teorrm1}. More precisely, we
shall see that some shuffle decompositions may lead in our matrix
construction of $B_1B_2\cdots B_t$ to condition~$(viii)$ in
Lemma~\ref{mtij1}, and, therefore, we are driven away from the key-tableau
$K$. 

\begin{ex}\label{ex2}
Consider the biword $\Pi^{\dagger}=\left(\begin{tabular}{cccccccccc}
 1244& 13\\
 4321&32 \\
 \end{tabular}\right)$ as in \eqref{bi3},
which is different from the
one considered in Example~\ref{ex1}. Note that $s_1^0=s(4,1)=4$
and $s_2^0=s(3,2)=3$. Following the Main Algorithm, we may
define $\sigma_1=(1\,4)(2\,3)\in\mathfrak{S}_4$, the matrices
\begin{align}
I+S_{4,4}^2&=I+S(4,4,\sigma_1)=I,\nonumber\\
I+S_{3,1}^3&=I+S(3,1,\sigma_1)=T_{24}(1),\nonumber\\
I+S_{4,2}^3&=I+S(4,2,(3\:1)\sigma_1)=T_{13}(1),\nonumber\\
I+S_{2,1}^4&=I+S(2,1,(4\:2)(3\:1)\sigma_1)=T_{12}(1),\nonumber\
\end{align}
and the permutations $\sigma_2=\sigma_1$, $\sigma_3=(4\:2)(3\:1)\sigma_1$ and
$\sigma_4=(2\:1)\sigma_3$. Finally, define
$A_0=\diag _p(a')$, $B_1=P_{\sigma_1}D_{[1]}$,
$B_2=D_{[2]}$, $B_3=T_{24}(1)T_{42}(-1)T_{13}(1)T_{31}(-1)D_{[2]}$,
and $B_4=T_{12}(1)T_{21}(-1)D_{[1]}$. Applying the same 
arguments as the ones used in Example~\ref{ex1}, we may show that the sequence
$A_0,B_1,B_2, B_3, B_4$ is a matrix realization for $(T,K)$, and
it is clearly different from the one obtained in Example~\ref{ex1}.

\end{ex}




\begin{ex}\label{exf}
Consider now
the biword $\Pi'$ as in \eqref{bi3} (see Example~\ref{2ex}).
 We shall see that, in this case, the
sequence of matrices obtained by the Main Algorithm is not a matrix
realization of $(T,K)$. Following Step~$1$ of the Main Algorithm, we may
define $\sigma_1=(14)(23)$, since $s_1^0=s(4,1)=4$ and
$s_2^0=s(4,2)=3$. By Step~$2$, we define the matrices
\begin{align}
I+S_{4,3}^2&=I+S(4,3,\sigma_1)=T_{12}(1),\nonumber\\
I+S_{3,2}^3&=I+S(3,2,(4\:3)\sigma_1)=T_{13}(1),\nonumber\\
I+S_{4,1}^3&=I+S(4,1,(3\:2)(4\:3)\sigma_1)=T_{24}(1),\nonumber\\
I+S_{2,1}^4&=I+S(2,1,(4\:1)(3\:2)(4\:3)\sigma_1)=T_{12}(1),\nonumber\
\end{align}
and the permutations $\sigma_2=(4\:3)\sigma_1$,
$\sigma_3=(4\:1)(3\:2)\sigma_2$ and $\sigma_4=(2\:1)\sigma_3$.
Finally, we define the matrices $A_0=\diag _p(a')$,
$B_1=P_{\sigma_1}D_{[1]}$, $B_2=T_{12}(1) T_{21}(-1)D_{[2]}$,
$B_3=T_{13}(1)T_{31}(-1) T_{24}(1) T_{42}(-1) D_{[2]}$, and
$B_4=T_{12}(1) T_{21}(-1) D_{[1]}$.

As in Example~\ref{ex1}, using Lemma~\ref{teorart2}, we find that
 $A_0,B_1,B_2,B_3,B_4$ satisfy conditions I and II of
Definition~\ref{defMR}. Let us now compute the invariant partition
of $B_1B_2B_3B_4$. Using Lemma~\ref{mtij1}, $(ii),(v)$, and $(vii)$,
we may write
\begin{multline}
B_1B_2B_3B_4
\sim_LD_{\{1\}}T_{21}(-1)D_{\{1,2\}}T_{31}(-1)
T_{42}(-1)D_{\{1,2\}}T_{12}(1)T_{21}(-1)D_{\{1\}}\\
=D_{\{1\}}T_{21}(-1)T_{12}(1)D_{\{1,2\}}T_{31}(-1)T_{32}(-1)T_{42}(-1)
D_{\{1,2\}}T_{21}(-1)D_{\{1\}}, \label{z1}
\end{multline}
and by Lemma~\ref{mtij1}, $(vi)$, we find that $$
(\ref{z1})\sim_RD_{\{1\}}T_{21}(-1)
T_{12}(1)D_{\{1,2\}}D_{\{1,2\}}D_{\{1\}}.$$
Since by Lemma~\ref{mtij1}, $(viii)$,
$T_{21}(-1)T_{12}(1)=T_{22}(-1)T_{12}(1)P_{(1\:2)}$, we obtain
\begin{align}
B_1B_2B_3B_4&\sim D_{\{1\}}T_{22}(-1)T_{12}(1)
P_{(1\:2)}D_{\{1,2\}}D_{\{1,2\}}D_{\{1\}}\nonumber\\
&\sim_L D_{\{1\}}P_{(1\:2)}D_{\{1,2\}}D_{\{1,2\}}D_{\{1\}}\nonumber\\
&\sim_R D_{\{1\}}D_{\{1,2\}}D_{\{1,2\}}D_{\{2\}}.\nonumber\
\end{align}

The sequence $B_1,$ $B_2,$ $B_3,$
$B_4$ gives the Young tableau $F=\text{\Small$\young(12,23,34)$}\neq
K= \text{\small$\young(12,23,3,4)$}$ and, therefore, $A_0,B_1,B_2,B_3,B_4$ is a matrix
realization for the 
pair $(T,F)$ with $F\neq K$.

\end{ex}

\section{Proof of the Main Theorem}

For any biword $\Pi$ as in \eqref{bi5},
 the sequence of matrices
 $A_0,B_1,\ldots,B_t$
 generated by the Main Algorithm always defines a tableau-pair
$(T,F)$, where $T$ is a Young tableau with biword $\Pi$ which rectifies
to a key-tableau $K(m)$, and $F$ is some Young tableau with weight $m$
whose shape dominates $\alpha(m)$. To prove that $F$ is the
rectification of $T$, we need restrictions on the 
 biword $\Pi$, as we have seen in Example~\ref{exf}.
The proof of the main theorem, Theorem~\ref{teorrm1}, has therefore
two parts. Firstly, we show that the matrix sequence
$(A_0,B_1,\ldots,B_t)$ generated in the Main Algorithm, by
a biword $\Pi$ as in \eqref{bi5}, 
 defines any Young tableau $T$ with that biword. Secondly, we show
that we may always select an appropriate biword of $T$ such that the
matrix sequence $B_1,\ldots,B_t$ defines its rectification. 

\subsection{Biwords generate matrix-tableaux}
 In this section, we only assume that we have applied the Main
Algorithm to a biword $\Pi$, without any additional conditions.





\begin{lemma}\label{lp1}
 Let $t\ge 1$ and $k\in\{1,\ldots,t\}$. Let
 $(x,k)$ and $(y,k+\varepsilon)$, $\varepsilon\geq 1$, be two
consecutive vertices of a lattice path of 
 $\Pi$. Then $\theta_{k+\varepsilon}\cdots\theta_{k+1}(x)=y$.
\end{lemma}
\begin{proof} Case $1$. Assume $s(y,k+\varepsilon)=y$. This means that
there are no vertices in positions $(y,j)$, $k<j<k+\varepsilon$.
Thus, following Step~$2$ of the Main Algorithm,
 we may write
$$\theta_{k+\varepsilon}\cdots \theta_{k+1}=\rho_2(x\:y)\rho_1,$$
for some permutations $\rho_1,\rho_2\in\mathfrak{S}_n$, such that
$\rho_1(x)=x$.

We claim that $\rho_2(y)=y$.
 Note that, for this equality to be
false, we should have a vertex $(y,j)$, with $j>k+\varepsilon$,
negatively-linked to a vertex $(a,i)$, for some
$i\in[k,k+\varepsilon-1]$, with $a>x$, and $(y,k+\varepsilon)$ should
be an obstacle. This is not possible since the sets of column
vertices of the lattice paths containing 
$(y,k+\varepsilon)$ and $(a,i)$, respectively, 
must be comparable for the inclusion order. 
 Therefore,
$\rho_2(y)=y$ and the result follows.



Case $2$. Assume now that $s(y,k+\varepsilon)\neq y$, and let
$(y,k+\varepsilon),\;(a_1,b_1),\ldots, (a_r,b_r)$ be the $(x,k)$-path
(see Definition~\ref{path}). Clearly, $s(y,k+\varepsilon)=a_r$, 
the integer $r$ is even, and, for each odd integer $i\in[r]$, the
vertices $(a_i,b_i)$ and $(a_{i+1},b_{i+1})$ are consecutive vertices
of a lattice path, with 
$a_{i-1}=a_{i}$ and $a_0=y$. Without loss of generality, assume that
$b_1\leq b_3\le \cdots\leq b_{r-1}$. 
Then, following Step~$2$ of the Main Algorithm,
 we have
$$\theta_{k+\varepsilon}\cdots\theta_{k+1}=
\rho_1(a_{1}\:a_{2})\rho_{2}(a_2\:a_3)\cdots\rho_{r-2}(a_{r-2}\:a_{r-1})
\rho_{r-1}(a_{r-1}\:a_{r})\rho_r(x\;a_r)\rho_0,$$ for some
$\rho_i\in\mathfrak{S}_n$, such that $\rho_0(x)=x$. By an argument
similar to the one used in Case 1, we find that $\rho_i(a_i)=a_i$, for
$i=1,\ldots,r$, and the result follows.\end{proof} 



\begin{lemma}\label{lemaa1} Let $t\ge 1$ and $1\le j\le t$.
 Let $(x,j)$ be the initial vertex of a lattice path.
 Then,

 $(a)$ $\sigma_j(\sigma_1^{-1}(s(x,j)))=x$.

 $(b)$ $\sigma_j[m_j]=J_j$.
\end{lemma}
\begin{proof} $(a)$ Note that
$\sigma_j(\sigma_1^{-1}(s(x,j)))=\theta_j\cdots\theta_2(s(x,j))$.
If there are no vertices in row $x$ to the left of column $j$, then
$s(x,j)=x$, $\theta_j\cdots\theta_2(x)=x$, and thus
$\sigma_j(\sigma_1^{-1}(s(x,j)))=x$.

Suppose there is a vertex in row $x$ to the left of column $j$.
Extend the biword $\Pi$ to a biword $\Pi_0$ by adding extra
biletters $\left(\begin{array}{c}n+u\\0\end{array}\right)$
 for
all $u\in[\ell_1+\cdots+\ell_t]$, such that
$\left(\begin{array}{c}x\\j\end{array}\right)$ and
$\left(\begin{array}{c}n+1\\0\end{array}\right)$
 are consecutive
vertices in $\Pi_0$, and
 the initial vertex of each lattice path is linked to a
distinct vertex $(n+u,0)$. In particular, the vertices $(x,j)$ and
$(n+1,0)$ are linked. Put $\theta_1:=\nu(n+1\:s(x,j))$, where
$\nu$ is defined as in Step~2 of the Main Algorithm. By Lemma~\ref{lp1},
$\theta_j\cdots\theta_2\theta_1(n+1)=x$, that is,
$\theta_j\cdots\theta_2(s(x,j))=x,$ and the result follows.
(As the lattice diagram of $\Pi_0$ is contained in
$([n]\cup[\ell_1+\ldots+\ell_t])\times (\{0\}\cup [t])$, in Algorithm
\ref{defs}, we have to make a shift and put $y:=-1$ in the case of
an initial vertex.) 

$(b)$ Let $k\in\{1,\ldots,t\}$. Recall that
$I_k:=[\ell_{t+1}+\cdots+\ell_{k+1}+1,\ell_{t+1}+\cdots+\ell_{k+1}+\ell_k]$
and 
$|J_j|=m_j=\sum_{k=\sigma^{-1}(j)}^t\ell_k$. Thus,
$I_k\subseteq [m_j]$ for
$k\in\{t,\ldots,\sigma^{-1}(j)\}$. We use induction on $j$ to prove
that, if $x\in J_j$ is such that $(x,j)$ is a vertex of a lattice path
of length $k$ with $k\in\{t,\ldots,\sigma^{-1}(j)\}$, 
there exists $i_x\in I_k$ such that $\sigma_j(i_x)=x$.

When $j=1$, the letters in $J_1$ correspond to initial vertices
of the lattice paths of length $k$, for
$k=t,\ldots,\varepsilon$, where $\varepsilon:=\sigma^{-1}(1)$.
Therefore, we may write
 $$\{(x,1):x\in J_1\}=\bigcup_{k=t}^{\varepsilon}\mathrm{X}_k.$$
 By the definition of $\sigma_1$, we have
 $\sigma_1(I_k)=s(\mathrm{X}_k)$. Since
$s(\mathrm{X}_k)=\{x:(x,1)\in X_k\}$, 
 for $k=t,\ldots,\varepsilon$, the result follows.

Fix now $j$ in $\{2,\ldots,t\}$, and let $y\in J_j$ be the row index
of a letter $j$ belonging to a lattice path $\textbf{\textit{v}}$ of
length $k$. 
Clearly, we must have $k\in\{t,\ldots,\sigma^{-1}(j)\}$. If $(y,j)$
is the initial vertex of $\textbf{\textit{v}}$ then, by $(a)$, we have
$\sigma_j(\sigma_1^{-1}(s(y,j)))=y$, with
$\sigma_1^{-1}(s(y,j))\in I_k$.

Assume now that $(y,j)$ is negatively-linked to a vertex
$(x,j-\varepsilon)$ with $x\geq y$, and $\varepsilon\geq 1$. By
induction, there exists $i_x\in I_k$ such that
$\sigma_{j-\varepsilon}(i_x)=x$, and by Lemma~\ref{lp1} we find that
$\theta_j\cdots\theta_{j-\varepsilon+1}(x)=y$. Thus,
$$\sigma_j(i_x)=\theta_j\cdots
\theta_{j-\varepsilon+1}\sigma_{j-\varepsilon}(i_x)=y.$$
By induction, our claim is proved. Thus, for each $x\in J_j$ there
is $i_x\in[m_j]$ such that $\sigma_j(i_x)=x$. Since $|J_j|=m_j$, we
must have $\sigma_j([m_j])=J_j$.
 \end{proof}

\begin{cor}\label{rm1}
 If $(x,j)$ is a vertex of a lattice path of length $k$
 with initial vertex $(y,j-\varepsilon)$, $\varepsilon\geq 0$,
 then
 $\sigma_j^{-1}(x)=\sigma_{j-\varepsilon}^{-1}(y)=
\sigma_1^{-1}(s(y,j-\varepsilon))\in I_k.$ 
\end{cor}
\begin{proof} This follows from the proof of the previous lemma.\end{proof}



\begin{proof}[Proof of Proposition \ref{prop1}] Let $t\ge
1$. We have to show that, 
 for each $k\in\{0,1,\ldots,t\}$, the matrix $A_k$, given by
 Step~3 of the Main Algorithm, is left equivalent to
 $\diag _p(a'+\chi^{J_0}+\chi^{J_1}\cdots+\chi^{J_k})P_{\sigma_k}$,
where $\sigma_0:=id\in\mathfrak{S}_n$ 
 and $J_0:=\emptyset$.
The proof is by induction on $k$. For $k=0$,
 $P_{id}=I$ and
 $A_0:=\diag _p(a')$, and in this case there is nothing to prove.
 So let $k$ be in $\{1,\ldots,t\}$. By
 induction, $A_{k-1}$ is left equivalent to
 $\diag _p(a'+\chi^{J_1}\cdots+\chi^{J_{k-1}})P_{\sigma_{k-1}}$.
 Therefore, by definition of $B_k$, $A_k$ is left equivalent to
 \begin{equation}\label{eql1}
 \diag
_p(a'+\chi^{J_1}\cdots+\chi^{J_{k-1}})P_{\sigma_{k-1}}S_kD_{[m_k]}. 
 \end{equation}
 Recall that $S_1=P_{\sigma_1}$ and
 $S_k=\prod_{i=1}^{q_{k-1}}(I+S_{x_i^ky_i^k}^k)(I-S_{x_i^ky_i^k}^k)^T$, 
for $k>1$. 
 Therefore, by Lemma~\ref{teorart2} and (\ref{eql1}),
 $A_k$ is left equivalent to
 \begin{equation}
 \diag _p(a'+\chi^{J_1}\cdots+\chi^{J_{k-1}})P_{\sigma_{k}}D_{[m_k]}=
 \diag
_p(a'+\chi^{J_1}\cdots+\chi^{J_{k-1}})D_{\sigma_k[m_k]}P_{\sigma_{k}}.
 \end{equation}
 By Lemma~\ref{lemaa1} $(b)$, we have $\sigma_k[m_k]=J_k$, and the result
 follows.
\end{proof}



\subsection{Biwords again: a canonical biword}

In the proof of Proposition~\ref{prop1} there are no restrictions on
 the shuffle decomposition that we have considered in $\Pi$. The
sequence of matrices 
 $A_0,B_1,\ldots,B_t$
 given by the Main Algorithm satisfies always conditions~I and II of
Definition~\ref{defMR} for 
 any biword $\Pi$ as in \eqref{bi5} of $T$. To prove that
$B_1,\ldots,B_t$ defines the rectification of $T$, we need
restrictions on the 
 biword $\Pi$, as we have seen in Example~\ref{exf}. We shall show
that we may always choose a biword equivalent to $\Pi$ obeying
conditions that are convenient for our purpose. 





In a biword $\Pi$ some vertices
 play a special role in the proof of our 
Theorem~\ref{teorrm1}. They are identified in the following definitions.



\begin{defi}
 Given distinct lattice paths
$\textbf{\textit{u}},\textbf{\textit{v}}$ of $\Pi$, 
 a vertex $(a,b)\in \textbf{\textit{u}}$ is said to be a {\it
right critical vertex} of the pair
$(\textbf{\textit{u}},\textbf{\textit{v}})$ if it is
positively-linked to a vertex 
 $(a',b')$ such that $(s(a',b'),b)$ belongs to
$\textbf{\textit{v}}$. If $b'=b+1$ the right critical vertex is of
type~I, otherwise it is of type~II. 

 Given pairwise distinct lattice paths
$\textbf{\textit{v}}_1,\ldots,\textbf{\textit{v}}_k$, $k\geq 2$, of
$\Pi$, a vertex $(a_1,b_1)\in \textbf{\textit{v}}_1$ is said to be a
right critical vertex of type~I (respectively of type~II) of
$(\textbf{\textit{v}}_1,\ldots,\textbf{\textit{v}}_k)$ with {\it
critical components}
$\textbf{\textit{v}}_2,\ldots,\textbf{\textit{v}}_{k-1}$, if 

$\bullet$ $(a_1,b_1)\in \textbf{\textit{v}}_1$ is a right critical
vertex of type~I (respectively of type~II) of
$(\textbf{\textit{v}}_1,\textbf{\textit{v}}_2)$, positively-linked to
$(a_2,b_2)$; 

 $\bullet$ for $i=2,\ldots,k-2$, $(s(a_i,b_i),b_1)$ is a right
critical vertex of $(\textbf{\textit{v}}_i,\textbf{\textit{v}}_{i+1})$
positively-linked to $(a_{i+1},b_{i+1})$, and 

 $\bullet$ $(s(a_{k-1},b_{k-1}),b_1)$ is a right critical vertex
of $(\textbf{\textit{v}}_{k-1},\textbf{\textit{v}}_k)$. 
\end{defi}

Since the lattice paths are distinct, a right critical
vertex of type~I is always an obstacle. In the case of a right critical
vertex of type~II, $b'-b>1$ and we may have $a'=a$ with an obstacle
of another lattice path between $(a,b)$ and $(a,b')$. The following
diagrams are schematic representations of right critical vertices of
types~I and II, respectively, both with one critical component,
$$\includegraphics[scale=0.9,trim = 0cm 18.3cm 0cm 0cm,clip]{pc1}.$$


\begin{defi}
 Given distinct lattice paths
$\textbf{\textit{u}},\textbf{\textit{v}}$ of $\Pi$, 
 a vertex $(a,b)\in \textbf{\textit{u}}$ is said to be a {\it left
critical vertex} of $(\textbf{\textit{u}},\textbf{\textit{v}})$ if it
is not negatively-linked to a vertex in column $b-1$ and there is an
obstacle on its left in position $(a,b-1)$ belonging to
$\textbf{\textit{v}}$. 

 Given pairwise distinct lattice paths
$\textbf{\textit{v}}_1,\ldots,\textbf{\textit{v}}_k$, $k\geq 2$, of
$\Pi$, 
 a vertex $(a_1,b)\in \textbf{\textit{v}}_1$ is a left critical
vertex of $(\textbf{\textit{v}}_1,\ldots,\textbf{\textit{v}}_k)$ with
{\it critical components}
$\textbf{\textit{v}}_2,\ldots,\textbf{\textit{v}}_{k-1}$ if 

 $\bullet$ $(a_1,b)\in \textbf{\textit{v}}_1$ is a left critical
vertex of
$(\textbf{\textit{\textit{v}}}_1,\textbf{\textit{\textit{v}}}_2)$; 

 $\bullet$ for $i=1,\ldots,k-2$, the obstacle $(a_{i},b-1)\in
\textbf{\textit{v}}_{i+1}$ is a right critical vertex of type~I of
$(\textbf{\textit{v}}_{i+1},\textbf{\textit{v}}_{i+2})$
positively-linked to a vertex $(a_{i+1},b)$, and 

 $\bullet$ $(a_{k-1},b-1)$ is an obstacle of
$(\textbf{\textit{v}}_{k-1},\textbf{\textit{v}}_k)$. 
\end{defi}
%\vspace{0.3cm}
Schematically, with $k=2$, either $(a_1,b)$ is the initial vertex of
$\textbf{\textit{v}}_1$ or it is negatively linked to a vertex not in
column $b-1$. 
$$\includegraphics[scale=0.9,trim = 0cm 18.3cm 0cm 0cm,clip]{pc2}.$$




For instance, in the biword $\Pi'$ as in \eqref{bi3} the vertices $(4,2)$
and $(2,3)$ are a left critical vertex and a right 
critical vertex of type~I
of the two lattice paths, respectively. They are the only
critical vertices in this biword. 
Consider now the biword represented in Example~\ref{exx1}.
The vertex $(4,3)$ is
a left critical vertex of
$\left(\binom{345}{531},\binom{22233}{54321}\right)$ with critical 
component $\binom{1344}{5321}$, and clearly it is also a left critical vertex
of $\left(\binom{345}{531},\binom{1344}{5321}\right)$. In this biword,
there is no other left critical 
vertex. Notice that $(4,3)$ is also a right critical vertex of
type~II of $\left(\binom{345}{531},\binom{1344}{5321}\right)$. This
example shows that a vertex may be simultaneously a left and a right
critical vertex. The vertex $(5,1)$ is a right critical vertex of
type~II of $\left(\binom{345}{531},\binom{2}{1}\right)$, and the
vertex $(4,2)$ is a right critical vertex 
of type~I of $\left(\binom{
1344}{5321},\binom{
22233}{54321}\right)$.




 In what follows, given a biword $\Pi$ as in \eqref{bi5}, we provide a
procedure to adjust the links between their vertices, 
 to form a new biword $\Pi'$ equivalent to $\Pi$, where the new
lattice path decomposition satisfies some properties needed in the
sequel. 

\medskip

\begin{alg}\label{relink} Let $\Pi$ be the biword \eqref{bi5}
identified with its lattice path representation in
$[n]\times[t]$. For each 
vertex $(a,b)$ of $\Pi$, we move along each column, from top to
bottom, and left to right, to check whether $(a,b)$ is 
a left or a right critical vertex of type~I
of a pair of lattice paths $(\textbf{\textit{u}},\textbf{\textit{v}})$
such that both have 
vertices in columns $b,b+1,\ldots,b+r$, with $r\ge 1$,
$\textbf{\textit{u}}$ is {\em below $\textbf{\textit{v}}$ in columns 
$b,\ldots,b+r-1$}, and {\em $\textbf{\textit{u}}$ is above
$\textbf{\textit{v}}$ in column $b+r$}. If so, we have two 
situations:

1- $(a,b)$ is a {\em left critical vertex} of
$(\textbf{\textit{u}},\textbf{\textit{v}})$, and then $(a,b-1)$ 
is an obstacle of $\textbf{\textit{v}}$. The lattice paths
$\textbf{\textit{u}}$ and $\textbf{\textit{v}}$, restricted to 
the vertices in columns $[b,b+r]$ and $[b-1,b+r]$, respectively,
are the factors of the sub-biword 
\begin{multline*}
\Pi_L=\textbf{\textit{u}}\textbf{\textit{v}}\\=
\left(\begin{matrix}a_{r}&a_{r-1}&\cdots&a_1&a\\
b+r&b+r-1&\cdots&b+1&b
\end{matrix}\right)\left(\begin{matrix}c_{r}&c_{r-1}&\cdots&c_1&c&a\\
b+r&b+r-1&\cdots&b+1&b&b-1 \end{matrix}\right)
\end{multline*}
of $\Pi$, respectively, where $a>c$,
$a_i>c_i$, for $i=1,\ldots,r-1$, and $a_{r}<c_{r}$. Then, relink the
vertices of $\textbf{\textit{u}}$ and $\textbf{\textit{v}}$, between
columns $b$ and $b+r$, so that 
 the sub-biword $\Pi_L$ is replaced by
$$\Pi'_L=\left(\begin{matrix}a_{r}&c_{r-1}&\cdots&c_1&c\\
b+r&b+r-1&\cdots&b+1&b\end{matrix}\right)\left(\begin{matrix}
c_{r}&a_{r-1}&\cdots&a_1&a&a\\ 
 b+r&b+r-1&\cdots&b+1&b&b-1
\end{matrix}\right),$$

$$\includegraphics[scale=0.9,trim = 0cm 19cm 0cm 0cm,clip]{pc3}.$$





2- $(a,b)$ is a {\em right critical vertex of type~I} of
$(\textbf{\textit{u}},\textbf{\textit{v}})$. The 
lattice paths $\textbf{\textit{u}}$ and $\textbf{\textit{v}}$
restricted to the vertices in columns $[b,b+r]$ are factors of 
the sub-biword
$$\Pi_R=\textbf{\textit{u}}\textbf{\textit{v}}=
\left(\begin{matrix}a_{r}&a_{r-1}&\cdots&a_1&a \\
b+r&b+r-1&\cdots&b+1&b
\end{matrix}\right)\left(\begin{matrix} c_{r}&c_{r-1}&\cdots&c_1&c \\
b+r&b+r-1&\cdots&b+1&b\end{matrix}\right)$$ of $\Pi$, where $a>c=a_1$,
$a_i>c_i$, for $i=2,\ldots,r-1$, and $a_{r}<c_{r}$. Then, relink the
vertices of $\textbf{\textit{u}}$ and $\textbf{\textit{v}}$, between
columns $b$ and $b+r$, so that 
 the sub-biword $\Pi_R$ is replaced by
$$\Pi'_R=\left(\begin{matrix}a_{r}&c_{r-1}&\cdots&c_1&a\\
b+r&b+r-1&\cdots&b+1&b
\end{matrix}\right)\left(\begin{matrix}c_{r}&a_{r-1}&\cdots&a_1&c \\
b+r&b+r-1&\cdots&b+1&b\end{matrix}\right),$$

\vspace{0.5cm}
$$\includegraphics[scale=0.9,trim = 0cm 18.8cm 0cm 0cm,clip]{pc4}.$$


\end{alg}

\vskip0.7cm





Let $\textbf{\textit{u}}'$ and $\textbf{\textit{v}}'$ be the lattice
paths obtained from $\textbf{\textit{u}}$ and $\textbf{\textit{v}}$
replacing, in the 
first case, the factor $\Pi_L$ by $\Pi'_L$, and, in the second
case, the factor $\Pi_R$ by $\Pi'_R$. In this way, we obtain
a new biword $\Pi'$ equivalent to $\Pi$, where the lattice paths
$\textbf{\textit{u}}$ and $\textbf{\textit{v}}$ were replaced by the
new lattice paths $\textbf{\textit{u}}'$ and $\textbf{\textit{v}}'$,
respectively. 
The vertex $(a,b)$ belonging to the new lattice path
$\textbf{\textit{u}}'$ is no longer a critical vertex of
$(\textbf{\textit{u}}',\textbf{\textit{v}}')$. Moreover, during this
process no new 
critical points will occur in the vertices already checked. Before
moving to the top of the next column, we 
continue this analysis, restarting with the same vertex $(a,b)$ and
moving down along column $b$. 

As there is only a finite number of vertices, this algorithm
produces a new biword $\Pi'$, equivalent to $\Pi$, under the conditions
of \eqref{bi5},
 satisfying the following proposition.


\begin{prop}\label{a1}
 The biword $\Pi'$ obtained by the application of Algorithm \ref{relink} to
 $\Pi$ is such that, if $\textbf{\textit{u}}$ and $\textbf{\textit{v}}$
are two lattice paths each having vertices in all columns
$b,\ldots,b+r$, 
 for some $b,b+r\in[t]$, with $r\geq 1$, and, if
 $(a,b)$ is either a left critical vertex, or a right critical
vertex of type~I of $(\textbf{\textit{u}},\textbf{\textit{v}})$, 
 then the vertices of $\textbf{\textit{u}}$ are below the vertices
of $\textbf{\textit{v}}$ 
in columns $b,b+1,\ldots,b+r$.
\end{prop}


\begin{nota} A biword $\Pi$ satisfies trivially the conditions of the
proposition above if 
either $(1)$ two vertices in the same row belong to the same lattice
path; or, $(2)$ if $(a,b')$ and $(a,b)$, $b'<b$, are two vertices of 
$\Pi$ in distinct lattice paths, then $(a,b')$ is single or only
negatively linked, that is, $s(a,b)=a$.

When $T$ rectifies to $ K(\sigma\alpha(m))$, with $\sigma$ the
identity, or the reverse permutation in $ \mathfrak{S}_t$, or 
$\sigma\in \mathfrak{S}_3$,
the conditions in the proposition above are satisfied
\cite{az2,az1,am1}.
\end{nota}

\begin{ex} $(1)$ The biword $\Pi$ as in \eqref{bi3} used in the matrix
construction of Example~\ref{ex1} satisfies Proposition~\ref{a1}. 


\noindent $(2)$ In Example~\ref{exf} the biword $\Pi'$ as in \eqref{bi3} was
used in the matrix construction, but the sequence $B_1,\ldots,B_4$
generated in the Main Algorithm
does not define $K$. Notice that both lattice paths
$\textbf{\textit{u}}=\binom{14}{32}$ and
$\textbf{\textit{v}}=\binom{1234}{4321}$ have vertices in columns $3$
and $2$; the 
 vertex in position $(4,2)$ is a left critical vertex of
$(\textbf{\textit{u}},\textbf{\textit{v}})$, and $\textbf{\textit{u}}$
is above $\textbf{\textit{v}}$ in column $3$. Therefore $\Pi'$ does
not satisfy Proposition~\ref{a1}. Applying the algorithm above, we get
$\Pi^\dagger$ as in \eqref{bi3}, which already satisfies the conditions of
Proposition~\ref{a1}, 
 \begin{equation}\label{gd33}
 \includegraphics[scale=0.9,trim = 0cm 19.3cm 0cm 0cm,clip]{pc5}.
\end{equation}

\noindent
$\Pi^\dagger$ was used in the matrix construction of Example~\ref{ex2}
where the sequence $B_1, \ldots,  B_t$ produces $K$. 





\noindent $(3)$ Consider now the lattice path representation of the biword
$$\begin{pmatrix}
 11355777\;444466\;223345\\
 87654321\;865431\;865431
\end{pmatrix}.$$ This biword does not satisfy the conditions of
Proposition~\ref{a1}, since, for example, the vertex $(7,3)$ is a
right critical vertex of the lattice paths
$\textbf{\textit{u}}=\binom{11355777}{87654321}$ and
$\textbf{\textit{v}}=\binom{444466}{865431}$. Both have vertices in
columns $3,4,\ldots,7$, and $\textbf{\textit{u}}$ is above
$\textbf{\textit{v}}$ in column $7$. Below are the successive steps of
the application of Algorithm \ref{relink} to this biword. Notice that
the lattice path representation of the final biword satisfies the
conditions of Proposition~\ref{a1}, 

$$\includegraphics[scale=0.8,trim = 0cm 17.5cm 0cm 0cm,clip]{pc6},$$

$$\includegraphics[scale=0.8,trim = 0cm 17.7cm 0cm 0cm,clip]{pc7}.$$
\end{ex}



%-------------------------------------------------------------------
In the following, we assume that the biword $\Pi$ satisfies the
conditions of 
Proposition~\ref{a1}.
Recall that we have encoded the tableau $T$ by a biword which we identify
with its lattice path representation. This lattice path representation is
used in the Main Algorithm to construct a sequence of matrices
$A_0,B_1,\ldots,B_t$, for which we have already proved that they 
define the tableau
$T$. In order to show that $A_0,B_1,\ldots,B_t$ is a matrix realization
for the pair $(T,K)$, with $K$ the rectification of $T$, we must show that
$B_1,\ldots,B_t$ defines the key $K$. The main pieces of our matrix
construction, 
 as observed in Remark \ref{mainrem} $(d)$, are the elementary
matrices $T_{ij}(1)$ whose indices $i,\,j$ depend on the lattice
path representation of $\Pi$. The next 
lemmas characterize these elementary matrices by relating their
indices $i,j$ with 
the particular lattice path representation that we have chosen in
Proposition~\ref{a1}. This allows 
us to use the commutation rules of Lemma~\ref{mtij1}, and it allows
us to avoid any
occurrence of the situation $(viii)$ in Lemma~\ref{mtij1}, and,
thereby, to show 
that the invariant partition of $B_1,\ldots, B_t$ is exactly the
shape of the key-tableau $K$. 








\begin{lemma}\label{lemaa3}
 Let $(x,k)$ and $(y,k+\varepsilon)$, $\varepsilon\geq 1$, be two
consecutive vertices of a lattice path of length $q$ in $\Pi$ with 
 initial vertex $(u,k')$. Then the permutation
 $\nu$ and the matrix
 $$S^{k+1}_{x,y}=S(x,s(y,k+\varepsilon),\nu\sigma_k)$$ defined in
Step~$2$ of the Main Algorithm satisfy: 

 $(a)$ $\nu(x)=x$.

 $(b)$ $\nu^{-1}(s(y,k+\varepsilon))\notin J'_k=\{a\in
J_k:\,(a,k)\mbox{ is a positively-linked vertex}\}$. 

 $(c)$ $I+S_{x,y}^{k+1}=T_{ij}(1)$, with $i=\sigma_k^{-1}(x)=
 \sigma_1^{-1}(s(u,k'))\in I_q\subseteq[m_k]$, and
 $j\notin[|J'_k|]$.
\end{lemma}
\begin{proof} $(a)$ and $(b)$ are obvious. To prove $(c)$, recall that by
the definition of the matrix $I+S_{x,y}^{k+1}=(s_{ij})$, we have
$s_{ij}\neq 0$ only if
 $\nu\sigma_k(i)=x$ and $\nu\sigma_k(j)=s(y,k+\varepsilon)$. Using $(a)$ and
 Corollary~\ref{rm1}, we obtain
 $$i=\sigma_k^{-1}(x)=
 \sigma_1^{-1}(s(u,k'))\in I_q\subseteq[m_k].$$
Now, by $(b)$, we find that
$\sigma_k(j)=\nu^{-1}(s(y,k+\varepsilon))\notin J'_k$. If
$\sigma_k(j)\notin J_k$, by Lemma~\ref{lemaa1}~$(b)$, we must have
$j\notin[m_k]$. Assume now that $\sigma_k(j)\in J_k\setminus J'_k$.
Then, we must have $\sigma_k(j)=a$, where $(a,k)$ is a not
positively-linked vertex of a lattice path of length $q'$,
with $q>q'$. Thus $j=\sigma_k^{-1}(a)\in I_q\subseteq [m_k]\setminus[|J'_k|].$
 \end{proof}

\begin{cor}\label{algcord}
 Each matrix $I+S_{x,y}^{k+1}=T_{ij}(1)$,
 defined in Step~$2$ of the Main Algorithm, is upper triangular
 with
 $i\in[m_k]$ and $j>i$.
 Moreover, $j\in[m_k]$ if and only if there is a vertex
 $(a,k)$, not positively-linked, belonging to a lattice path
$\textbf{\textit{v}}$, and such that $(x,k)$ 
 is a right critical vertex of type~I or II of
$(\textbf{\textit{u}},\textbf{\textit{v}})$, where
$\textbf{\textit{u}}$ is the lattice path containing $(x,k)$. 
\end{cor}


\begin{ex}\label{exam1}
 Let $\Pi=\left(\begin{array}{c}
1112223\;2233\;1\\
7654321\;7542\;4
\end{array}\right)$ and its lattice path representation
\begin{equation}\label{ex3}
\includegraphics[scale=0.9,trim = 0cm 19.7cm 0cm 0cm,clip]{grelha12}.
\end{equation}



Applying the Main Algorithm, we must set $\sigma_1=(13)$, since
$s_1^0=s(3,1)=3, s_2^0=s(3,2)=2$ and
$s_3^0=s(1,4)=1$, and thus
 $\sigma_i=(3\,2)\sigma_1$, for $i=2,3,4$ and
$\sigma_5=(3\,2)(2\,1)\sigma_4$. Consider the matrices
$S_{3,2}^2=S(3,s(2,2),\sigma_2)$,
 $S_{2,1}^5=S(2,s(1,5),\sigma_4)$, and
 $S_{3,2}^5=S(2,s(2,5),(2\,1)\sigma_4)$, produced in Step~$2$
 of the Main Algorithm.
Since $s(2,2)=2$, $s(1,5)=1$ and $s(2,5)=2$, we get
\begin{equation}\label{mat}
 I+S_{3,2}^2=T_{12}(1),\,\,\,I+S_{2,1}^5=T_{13}(1),\,\mbox{ and
 }I+S_{3,2}^5=T_{23}(1).
\end{equation}
Each matrix in (\ref{mat}) is upper triangular and satisfies
Lemma~\ref{lemaa3}. Notice that in the last two matrices the column
index 
$3\in[3]=[m_4]$. 
 This is consistent with the previous corollary,
 since the vertex $(1,4)$ is not positively-linked, and $(2,4)$ and $(3,4)$ are
 right critical vertices of type~I of
$\left(\begin{pmatrix}1112223\\7654321\end{pmatrix},
\begin{pmatrix}1\\4\end{pmatrix}\right)$
and of
$\left(\begin{pmatrix}2233\\7542\end{pmatrix},
\begin{pmatrix}1\\4\end{pmatrix}\right)$,
respectively.
\end{ex}



In the next lemmas, we analyse the relationship between the critical
vertices of our chosen biword $\Pi$ and the matrices defined in 
Step~$2$ of the Main Algorithm. This analysis is important in order to prove
that the invariant partition of $B_1,\ldots,B_t$ is the shape of $K$.


\begin{lemma}\label{la1}
 For $q=1,\,r$, let $(x_q,k)$ and $(y_q,k+\varepsilon_q)$
 be a pair of
 linked vertices belonging to the lattice path
$\textbf{\textit{u}}_q$, with $x_1<x_r$, and consider the 
 matrices
 $I+S(x_q,s(y_q,k+\varepsilon_q),\nu_q\sigma_k)=T_{i_qj_q}(1)$.
 Then $j_1=j_r$ if and only if $(x_r,k)$ is a right critical
vertex of type~I or II of 
$(\textbf{\textit{u}}_r,\ldots,\textbf{\textit{u}}_2,\textbf{\textit{u}}_1)$,
$k\geq 2$, with critical components
$\textbf{\textit{u}}_{r-1},\ldots,\textbf{\textit{u}}_{2}$. 
\end{lemma}
\begin{proof} The {\it if} part. Without loss of generality assume that
$(x_2,k)$ is a right critical vertex of type~I or II of
$(\textbf{\textit{u}}_2,\textbf{\textit{u}}_1)$, 
without critical components. Then $x_1=s(y_2,k+\varepsilon_2)$
and we may write
$\nu_2\sigma_k=\theta(x_1\:s(y_1,k+\varepsilon_1))\nu_1\sigma_k,$
where $\theta\in\mathfrak{S}_n$ satisfy $\theta(x_1)=x_1$. Since
$\nu_2\sigma_k(j_1)=x_1$ we get 
$\nu_2\sigma_k(j_1)=\theta(x_1)=x_1$, and the result follows.


\medskip
The {\it only if} part.
 Without loss of generality, assume that in
the matrix $B_k$, defined in steps 2 and 3 of the Main Algorithm,
there are no matrices $T_{ij_1}(1)$ between 
$T_{i_1j_1}(1)$ and $T_{i_2j_1}(1)$. Then, we may write
$\nu_2\sigma_k=\theta(x_1\:s(y_1,k+\varepsilon_1))\nu_1\sigma_k,$
for some permutation $\theta\in\mathfrak{S}_n$ satisfying $\theta(x_1)=x_1$.
By definition, we must have
$\nu_2\sigma_k(j_1)=s(y_2,k+\varepsilon_2)$. On the other hand,
$\nu_2\sigma_k(j_1)= \theta(x_1\:s(y_1,k+\varepsilon_1))$
$\nu_1 \sigma_k(j_1) =x_1.$ Therefore, we find that
$x_1=s(y_2,k+\varepsilon_2)$, and this equality means that
$(x_2,k)$ is a right critical vertex of 
type~I or II of $(\textbf{\textit{u}}_2,\textbf{\textit{u}}_1)$.
 \end{proof}







\begin{lemma}\label{la2}
 Suppose $m_k<m_{k+1}$, and let $(x,k)$ and $(y,k+1)$ be consecutive
vertices of the lattice path 
 $\textbf{\textit{v}}_l$. Then $I+S(x,y,\nu\sigma_k)=T_{ij}(1)$ with
$m_k<j\leq m_{k+1}$ 
 if and only if there is a vertex $(a,k+1)$
 belonging to a lattice path $\textbf{\textit{v}}_1$ which is a
left critical 
 vertex of $(\textbf{\textit{v}}_1,\ldots,\textbf{\textit{v}}_l)$,
with $\sigma_{k+1}^{-1}(a)=j$. 
\end{lemma}
\begin{proof} The {\it if} part. Without loss of generality, assume
that $(x,k+1)$ is a left critical vertex of
$(\textbf{\textit{u}},\textbf{\textit{v}})$, with no critical 
components. Since $\sigma_{k+1}([m_{k+1}])=J_{k+1}$, there is
$j\in[m_{k+1}]$ such that $\sigma_{k+1}(j)=x$. Consider the matrix
$S(x,y,\nu\sigma_k)$. Clearly, we may write
$\sigma_{k+1}=\theta(x\:y)\nu\sigma_k,$ where $\theta\in\mathfrak{S}_n$
satisfy $\theta(x)=x$. Therefore,
$\nu\sigma_k(j)=(x\:y)\theta^{-1}\sigma_{k+1}(j)=y$, and thus
$I+S(x,y,\nu\sigma_k)=T_{ij}(1),$ for some integer $i\in[m_k]$.
Finally, note that since the lattice path $\textbf{\textit{v}}$ has no
vertex in column $k$, 
all vertices in column $k$ must be positively-linked. Thus, by
Lemma~\ref{lemaa3}, we find $m_k<j$. 


\medskip
The {\it only if} part. Assume now that
$I+S(x,y,\nu\sigma_k)=T_{ij}(1),$ for some integer $m_k<j\leq
m_{k+1}$. Again, it is clear that we must have
$$\sigma_{k+1}=\rho(x_r\:x_{r-1})\cdots(x_2\:x_1)(x_1\:x)(x\:y)\nu\sigma_k,$$
for some integers $x_r>\cdots>x_1>x>y$ and a permutation
$\rho\in\mathfrak{S}_n$ such that $\rho(x_r)=x_r$. Thus,
$\sigma_{k+1}(j)=x_r\in J_{k+1}$, since $j\in[m_{k+1}]$. Denote by
$\textbf{\textit{v}}$ the lattice path containing the vertex
$(x_r,k+1)$, and note 
that since $\rho(x_r)=x_r$, $\textbf{\textit{v}}$ cannot have a vertex
in column $k$. Thus, 
$(x_r,k+1)$ is a left critical vertex of
$(\textbf{\textit{u}},\textbf{\textit{v}})$. 
 \end{proof}



Compare this result with Example~\ref{exam1}, where the subindex $2$
of $T_{12}(1)=I+S_{3,2}^2$ satisfies $1=m_1<2=m_2$, and $(3,2)$ 
is a left critical vertex of
$\left(\binom{2233}{7542},\binom{1112223}{7654321}\right)$. 

\medskip

We are now ready to start the proof of our Main Theorem.

\begin{proof}[Proof of Theorem \ref{teorrm1}]
It was shown in Proposition~\ref{prop1} that $A_0,B_1,\ldots,B_t$
satisfy conditions I and II of Definition~\ref{defMR}. So it remains
to show that $B_1\cdots B_t$ is equivalent to the diagonal matrix
$D_{[m_1]}\cdots D_{[m_t]}$, that is, $B_1,\ldots,B_t$ is a matrix
construction of the 
key with weight $(m_1,\ldots,m_t)$. Using Corollary~\ref{rm1},
Lemma~\ref{la1}, and the commutation rules in Lemma~\ref{mtij1}, we
may write each matrix 
$$B_k=\prod_{l=1}^{q_{k-1}}(T_{i_lj_l}(1)T_{j_li_l}(-1))D_{[m_k]},$$
$k=2,\ldots,t$, as
$$B_k=\left(\prod_{l=1}^{q_{k-1}}T_{i_lj_l}(1)\right)C_kD_k
\left(\prod_{l=1}^{q_{k-1}}T_{j_li_l}(-1)\right)D_{[m_k]},$$
where each $C_{k+1}$ [respectively $D_{k+1}$] is a product of upper
[respectively lower] triangular elementary matrices $T_{ij}(1)$,
with
 $i\!,j\!\in\!\!\{i_1,\ldots,i_{q_k}\}$, $i\neq j$.
Moreover, note that
 $T_{ij}(1)$ is a factor of $C_{k+1}D_{k+1}$ only if there are
lattice paths $\textit{\textbf{u}}_l$ with vertices $(a_l,k)$ 
 such that $\sigma_{k}^{-1}(a_l)=l$, for $l=i,j$, and where
 $(a_i,k)$ is a right critical vertex of type~I or II of
 $(\textbf{\textit{u}}_i,\textbf{\textit{u}}_j)$.
We will refer to $T_{i_lj_l}(1)$ and $T_{j_li_l}(-1)$,
$l=1,\ldots,q_{k-1}$, as original matrices of $B_k$, and we call the
triangular matrices in $C_kD_k$ secondary matrices.

Denote by $\textbf{\textit{u}}_l$ the lattice path for which
$\sigma_0^{-1}(u_l^0)=l$, with $u_l^0$ the column index of its initial
vertex, for $l\in [\ell_1+\cdots+\ell_t]$. Next, for $k=2,\ldots,t$,
using Lemma~\ref{la2} write 
\begin{equation}\label{eqphi}
B_k=\left(\prod_{l=1}^{q_{k-1}}T_{i_lj_l}(1)\right)
C_kD_kD_{[m_k]}\left(\prod_{l=1}^{q_{k-1}}T_{j_li_l}(\phi_l)\right),
\end{equation}
 where $\phi_l=-1$ if $T_{j_li_l}(-1)=S(x,y,\nu\sigma_k)$, if
 $(x,k)$ and $(y,k+1)$ are linked vertices of $\textbf{\textit{u}}_{i_l}$
and there is a vertex 
 $(a,k+1)\in \textbf{\textit{u}}_{j_l}$, which is a left critical
vertex of $(\textbf{\textit{u}}_{j_l},\textbf{\textit{u}}_{i_l})$; 
 otherwise $\phi_l=-p$.

The next step consists in using the commutation rules in
Lemma~\ref{mtij1} and Corollary~\ref{algcord} to eliminate, by left
equivalence, the left most upper 
triangular matrix $T_{ij}(x)$ in $D_{[m_1]}B_2\cdots B_t$. Notice
that this operation may generate new matrices $T_{uv}(y)$. Repeat
this operation, eliminating all upper triangular matrices.


By Lemma~\ref{mtij1}, there exists always a unimodular elementary
matrix
 $E$ such that
\begin{equation*}
T_{ji}(\tau)T_{ab}(\tau')=T_{ab}(\varrho')T_{ji}(\varrho)E,\;
\mbox{with $\varrho$, $\tau$ and $\varrho'$, $\tau'$ pairs of
associated elements,} 
\end{equation*}
whenever $\tau$, $\tau'$ are not both unities, or $(a,b)\neq (i,j)$ if
$i\neq j$. Thus,
{\em the matrix operations described in the previous paragraph are
feasible if they do not involve 
the passage of a matrix $T_{ij}(\tau)$, with $i<j$, to the left of a
matrix $T_{ji}(\tau')$, with $\tau=-\tau'=\pm 1$.}

We begin by noticing that
$D_{[m_{l}]}T_{ij}(1)=T_{ij}(p)D_{[m_{l}]},$ whenever $m_l<j$. Thus,
the situation described above only happens if the diagonal matrices,
say $D_{[m_{k+1}]},\ldots,\break D_{[m_{k+\varepsilon}]}$, between
$T_{ji}(\tau')$ and $T_{ij}(\tau)$ satisfy $j\leq
m_{k+1},\ldots,m_{k+\varepsilon}$. If
$T_{ji}(\tau')=I-S(x,y,\nu\sigma_{k-1})^T$ is a original matrix of
$B_{k}$, \eqref{eqphi} implies the existence of a left critical
vertex $(a,k+1)\in \textbf{\textit{u}}_j$ of
$(\textbf{\textit{u}}_j,\textbf{\textit{u}}_i)$. If $T_{ji}(\tau')$ is
a 
secondary matrix of $B_{k+1}$, by Lemma~\ref{la1}, there is a right
critical vertex of type~I of $\textbf{\textit{u}}_j$, in column $k$,
of $(\textbf{\textit{u}}_j,\textbf{\textit{u}}_i)$. 
By \eqref{eqphi} and Lemma~\ref{mtij1}, any other case implies the
existence of a sequence of matrices
\begin{equation}\label{ef1}
 T_{i_0i_1}(\tau_0),\,T_{i_1i_2}(\tau_1),\ldots,T_{i_si_{s+1}}(\tau_s),
\end{equation}
with $i_l\leq m_{k+1},\ldots,m_{k+\varepsilon}$, for
$l=0,1,\ldots,s+1$, $s\geq 1$, which generates the matrix
$T_{ji}(\tau')$ by the process of elimination described above. By
Corollary~\ref{algcord}, and Lemmas~\ref{la1} and \ref{la2}, the
matrices in \eqref{ef1} are the result of left or right critical
vertices of type~I. In particular, we find that
$\textbf{\textit{u}}_{i_0}$ is below 
$\textbf{\textit{u}}_{i_1}$ in columns $k+1,\ldots,k+\varepsilon$,
$\textbf{\textit{u}}_i$ is above 
$\textbf{\textit{u}}_{i_1}$ in columns $k+\zeta,\ldots,k+\varepsilon$
and $\textbf{\textit{u}}_j$ is 
below $\textit{\textbf{u}}_{i_0}$ in columns
$k+\xi,\ldots,k+\varepsilon$, for some 
$\varepsilon\ge\zeta,\xi\geq 1$. In any case, the existence of
$T_{ji}(\tau')$ means that $\textbf{\textit{u}}_j$ is below
$\textbf{\textit{u}}_i$ in columns 
$k+\varepsilon',\ldots,k+\varepsilon$, for some $\varepsilon\ge
\varepsilon'\geq 
1$.

The same reasoning shows that the existence of
$T_{ij}(\tau)$ means that $\textbf{\textit{u}}_i$ is below
$\textbf{\textit{u}}_j$ in column 
$k+\varepsilon$, contradicting Proposition~\ref{a1}. Therefore,
whenever $T_{ji}(\tau)$, $i<j$, is on the left of $D_{[m_{k+1}]}$
and satisfies $j\leq m_{k+1}$, any elementary matrix $T_{ij}(x)$ is
transformed, during the process of its elimination
by left equivalence, into $T_{ij}(xp)$ when reaching the diagonal matrix
$D_{[m_{k+1}]}$. We may thus eliminate all upper triangular matrices,
and obtain
\begin{equation}\label{algeq1} B_1\cdots B_t\sim_E
D_{[m_1]}T_2D_{[m_2]}\cdots T_tD_{[m_t]},
\end{equation}
 where each $T_k$ is a product of lower elementary triangular
matrices, $k=2,\ldots,t$. Finally, 
 using Lemma~\ref{mtij1}, together with Corollary~\ref{algcord}, we
may eliminate 
by right equivalence all these lower elementary triangular matrices,
beginning with the right most triangular matrix in \eqref{algeq1},
and ending in the left most triangular matrix in $T_2$. Therefore,
 \eqref{algeq1} is equivalent to $D_{[m_1]}\cdots
D_{[m_t]}$. 
\end{proof}

\section{Matrix tableau-pairs with key condition over a four-letter alphabet}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\subsection{An injection of the Knuth class of a key over the
four-letter alphabet into a key over the
six-letter alphabet}

According to Theorem~\ref{t2}, in the case of a four-letter alphabet,
the problem of a matrix construction of a tableau-pair $(T,K)$, where
$T$ rectifies to the key-tableau $K$, is reduced to the key-tableau
$K(\sigma,(\ell_4,\ldots,\ell_1))$ with $\sigma\in S$, $\ell_2>0$, and
$\ell_4>0$, since 
 its Knuth class is the union of the sets
$\sh(\widehat{{\rm v}}_5^{n_5},{\rm v}_{4}^{\ell_4-n_5},{\rm
v}_{3}^{\ell_3},{\rm v}_{2}^{\ell_2-n_5},{\rm v}_{1}^{\ell_1})$ for $0\leq
n_5\leq \min\{\ell_2,\ell_4\}$. Recall, from Section~2, that
$\widehat{{\rm v}}_5=431421$ and $S=\{1423,1432,4123,4132\}$. 


 Consider $w\in\sh(\widehat{{\rm v}}_5^{n_5},{\rm
v}_{4}^{n_4},\ldots,{\rm v}_{1}^{n_1}),$ 
for some $0\leq n_5\leq \min\{\ell_2,\ell_4\}$, $n_i=\ell_i$, $i=1,3$, and
$n_i=\ell_i-n_5$, $i=2,4$. Let
 $\{X^{n_5}_5,\ldots,X^1_5,\ldots, X^{n_1}_1,
\ldots,X^1_1\}$ be a set partition of
$\big[\sum_{i=1}^4 in_i+6n_5\big]$, with $w{|X_j^i}={\rm v}_j$,
$i\in[n_j]$, $j\in\{1,2,3,4\}$, and $w{|X_5^i}=\widehat{{\rm v}}_5$,
$i\in[n_5]$. 
 Let
 $I^{j,i}$ be a row of length
$j$, for $i\in[n_j]$, $j=1,\ldots,4$, and
 $I^{5,i}=a^i b^i c^i d^i e^i f^i$, with
$a^i\leq b^i\leq c^i<d^i\leq e^i\leq f^i$, for $i\in[n_5]$.
 We consider the biword
\begin{equation}\label{pi+}
\Pi^+=\left(\begin{matrix}
 I^{5,n_5}&\cdots&I^{5,1}\\
 \widehat{\rm v}_5&\cdots&\widehat{\rm v}_5
 \end{matrix}\right|\left.
 \begin{matrix}
 I^{4,n_4}&\cdots&I^{4,1}&\cdots&I^{1,n_1}&\cdots&I^{1,1}\\
 {\rm v}_4&\cdots&{\rm v}_4&
 \cdots&{\rm v}_1&\cdots&{\rm v}_1
 \end{matrix}\right)
\end{equation}
with bottom row $\widehat{\rm v}_5^{n_5}{\rm v}_4^{n_4}\cdots
{\rm v}_1^{n_1}$.
The lattice path representation
 $\Pi^+$ as in \eqref{pi+} consists of
$n_5+\cdots+n_1$ nonintersecting
 lattice paths: the $n_j$ lattice paths $\left(\begin{array}{c}
I^{j,i}\\
{\rm v}_j
\end{array}\right)$ of length $j$ have nonnegative slope, for
 $i\in[n_j]$, $j\in\{1,2,3,4\}$, and the $n_5$ lattice paths
$\left(\begin{array}{c} 
I^{5,i}\\
\widehat{\rm v}_5
\end{array}\right)$, $i\in[n_5]$, of length $6$, are such that
 the line linking the vertices $\left(\begin{array}{c}
c^{i}\\
1
\end{array}\right)$ and $\left(\begin{array}{c}
d^{i}\\
4
\end{array}\right)$ has negative slope.

Given a biword $\Pi^+$ \eqref{pi+} it is a simple task
to adjust, if necessary, the links between the vertices of this
biword in order to form a new biword $\widehat\Pi^+$
satisfying the conditions of the following lemma. (To avoid
cumbersome notation we shall drop the super indices in this
statement.)


\begin{lemma}\label{bw}
 There is a biword $\widehat\Pi^+$ equivalent to $\Pi^+$ as in \eqref{pi+}
 satisfying the following conditions:

 \noindent $(a)$ Any two lattice paths have no critical vertices.

 \noindent $(b)$ If $\left(\begin{array}{c}
abcdef\\
431421
\end{array}\right)$ is a lattice path of $\widehat\Pi^+$ then:

 $(i)$ in row $c$ there is at most one more vertex, placed in
 column $4$, which must be negatively-linked to a vertex in
 column $3$;

 $(ii)$ if $d\neq e$, in row $d$ there is at most one more vertex, placed in
 column $1$, which must be positively-linked;

 $(iii)$ if $d\neq e$, in row $e$, to the right of $(e,2)$, there
 are no vertices.
\end{lemma}
\begin{proof} We prove only condition $(b)(iii)$. All other conditions are
proven in a similar way. Recall that we must have $a\leq b\leq
c<d\le e\leq f$. If $(e,3)$ is also a vertex of $\Pi^+$, then it
must belong to one of the words $431421,4321$ or $431$. In these
cases, $\Pi^+$ must have a sub-biword either of the form
$$
 \Gamma=\left(\begin{array}{cc}
 abcdef&gehjkl\\
 431421&431421
\end{array}\right),\mbox{ or }\Delta=\left(\begin{array}{cc}
 abcdef&gehi\\
 431421&4321
\end{array}\right),\mbox{ or }\Lambda=\left(\begin{array}{cc}
 abcdef&geh\\
 431421&431
\end{array}\right),
$$
with $g\leq e\leq h\leq i<j\leq k\leq l$. We may re-link the
vertices of the lattice paths of $\Gamma$, $\Delta$, or $\Lambda$ such
that they are replaced in $\Pi^+$ by
$$\left(\begin{array}{ccc}
 abcjkl&geef&dh\\
 431421&4321&41
\end{array}\right),\left(\begin{array}{cc}
 abcdhi&geef\\
 431421&4321
\end{array}\right),\mbox{ or }\left(\begin{array}{ccc}
 geef&abc&dh\\
 4321&431&41
\end{array}\right),$$
respectively.
 In either case, the vertex $(e,2)$ belongs now to the
new lattice path $\displaystyle{\binom{geef}{4321}}$, and it is
linked to $(e,3)$. We have only 
changed the links in the two lattice paths. Therefore, we may
assume, without loss of generality, that, if $(e,2)$ is a vertex of a
lattice path $\left(\begin{array}{c}
I^{5,i}\\
\widehat{\rm v}_5
\end{array}\right)$, there is no vertex in position
$(e,3)$.

Assume now that $(e,4)$ is a vertex, but $(e,3)$ is not. An analysis
similar to the one done above shows that if $(e,4)$ is a vertex of
$\left(\begin{array}{c} 
I^{5,i}\\
\widehat{\rm v}_5
\end{array}\right)$ or $\left(\begin{array}{c}
I^{j,i}\\
{\rm v}_j
\end{array}\right)$, for some $j=1,\ldots,4$, then
we may re-link the vertices of the corresponding lattice paths in
such a way that the vertex $(e,2)$ is linked to $(e,4)$. Therefore,
we may assume that $(e,4)$ is not a vertex of $\Pi^+$. \end{proof}


\begin{ex}\label{lex21}
The biword $\Pi^+=\left(\begin{array}{ccc} 113566&2234&3\\
431421&4321&4\\\end{array}\right)$, whose lattice path representation
is given below, fails to satisfy condition $(b)(i)$ of the lemma
above, since the vertex $(3,1)$ belongs to the lattice path of
$\left(\begin{array}{ccc} 113566\\ 
431421\end{array}\right)$, and there is a vertex in row $3$, column
$2$\begin{equation}\label{exx2}
\includegraphics[scale=0.8,trim = 0cm 18cm 0cm 0cm,clip]{grelha13}
.\end{equation} 
Rearranging the links between the vertices, we obtain the biword
$$\widehat\Pi^+= 
\left(\begin{array}{ccc} 114566&2233&3\\
431421&4321&4\\\end{array}\right),$$ which satisfy all the required
conditions of Lemma~\ref{bw}
\begin{equation}\label{lex2}
\includegraphics[scale=0.8,trim = 0cm 18cm 0cm
0cm,clip]{grelha14}. \end{equation} 
\end{ex}


In what follows, we assume that our biword $\Pi^+$
satisfies the conditions of\break Lemma~\ref{bw}.

\begin{cor}\label{bw1}
 $(a)$ If $(a,i)$ is the initial vertex of a
 lattice path of length $k$, then $s(a,i)\neq a$
 only if $\sigma\in\{4123,4132\}$, $i=4$, $k=1$, and the
 nearest vertex in row $a$ is either in column $1$, which is the
 rightmost vertex of the lattice path $\left(\begin{array}{c}
I^{5,i}\\
\widehat{\rm v}_5
\end{array}\right)$ or of $\left(\begin{array}{c}
I^{j,i}\\
{\rm v}_j
\end{array}\right)$, for some $j=1,\ldots,4$, or in column $2$,
 which is a vertex of $\left(\begin{array}{c}
I^{4,i}\\
{\rm v}_4
\end{array}\right)$.

 \noindent $(b)$ If $(b,j),\,(a,i)$ are consecutive vertices of a
 lattice path of length $k$, then $s(a,i)\neq a$
 only if $j=1$, $i=4$, and the nearest vertex in row $a$ is in
 column $2$, and it is a vertex of $\left(\begin{array}{c}
I^{4,i}\\
v_4
\end{array}\right)$.
\end{cor}
\begin{proof} This follows from Lemma~\ref{bw} $(a)$.\end{proof}

%%%
%%%
%%%





For each $\sigma=\sigma(1)\sigma(2)\sigma(3)\sigma(4)$ in $\mathfrak{S}_4$,
consider the permutation
$$\overline{\sigma}(1)\overline{\sigma}(2) \overline{\sigma}(3)
\overline{\sigma}(4)34\in\mathfrak{S}_6,$$
where
$$\overline{\sigma}(k)=\begin{cases}
\sigma(k),&\text {if }\sigma(k)=1,2,\\
\sigma(k)+2,&\text {if }\sigma(k)=3,4.
\end{cases}
$$
This correspondence is a bijection between $\mathfrak{S}_4$ and the set
$\{\overline{\sigma}=\alpha34\in\mathfrak{S}_6:\alpha \in
\mathfrak{S}_{\{1256\}}\}$ 
$\subseteq\mathfrak{S}_6.$ In particular, $S=\{1423,1432,4123,4132\}$ is
transformed into $\{162534,$ $165234,$ $612534,$ $615234\}\subseteq
\mathfrak{S}_6$. Let 
$\rho:\{\widehat{\rm v}_5,{\rm v}_j:j\in[4]\}\rightarrow\{{\overline{\rm
v}_j}:j\in[6]\},$
such that $\rho(\widehat{\rm v}_5)=\overline{\rm v}_6$ and
$\rho({\rm v}_j)={\overline{\rm v}_j}$, $j=1,2,3,4$, where $\overline{\rm
v}_6,\ldots,\overline{\rm v}_1$ are the columns of the key encoded by the
permutation $\overline{\sigma}$ and the vector $(1^6)$.


 For each
$n_5=0,\ldots,\min\{\ell_2,\ell_4\}$, the map $\rho$ can be extended, by
shuffling, to a bijection between the sets $\sh(
\widehat{\rm v}_5^{n_5},{\rm v}_4^{n_4},\ldots,{\rm v}_1^{n_1})$
and $\sh(
{\overline{\rm v}_6}^{n_5},{\overline{\rm
v}_4}^{n_4},\ldots,{\overline{\rm v}_1}^{n_1})$. This last set is a subset
of the plactic class of the key encoded by the permutation
$\overline{\sigma}$ and the vector $(n_5,0,n_4,n_3,n_2,n_1)$. Thus
every word in the plactic class of $K(\sigma\alpha(m))$,
$\sigma\in\mathfrak{S}_4$, has a copy in the shuffle of the columns of
some key over
the alphabet $[6]$. Let $w\in \sh(
\widehat{\rm v}_5^{n_5},{\rm v}_4^{n_4},\ldots,{\rm v}_1^{n_1})$.
Fix an equivalent biword
$\Pi^+$ as in (\ref{pi+}) satisfying the conditions of Lemma~\ref{bw}, and
let
\begin{equation}\label{s4}
\overline{\Pi}^+=\begin{pmatrix}
I^{5,n_5}&\cdots&I^{5,1}&I^{4,n_4}&\cdots&I^{4,1}&
\cdots&I^{1,n_1}&\cdots&I^{1,1}\\
{\overline{\rm v}_6}&\cdots&{\overline{\rm v}_6}&{\overline{\rm
v}_4}&\cdots&{\overline{\rm v}_4}&\cdots
&{\overline{\rm v}_1}&\cdots&{\overline{\rm v}_1}
\end{pmatrix}
\end{equation}
 be the biword that we obtain when we transform
each lattice path $\begin{pmatrix}
I^{j,i}\\
{\rm v}_j
\end{pmatrix}$ and
$\begin{pmatrix}a^ib^ic^id^ie^if^i\\\!\!\!4\,3\,1\;4\;2\;1\end{pmatrix}$
of $\Pi^+$ into $\begin{pmatrix}
I^{j,i}\\
{\overline{\rm v}_j}
\end{pmatrix}$ and
$\left(\begin{array}{c}a^ib^ic^id^ie^if^i\\\!\!\!6\,5\,4\;3\;2\;1
\end{array}\right)$,
respectively, where $a^i\leq b^i\leq c^i<d^i\leq e^i\leq f^i$. Let
$\overline{\Sigma}$ be the biword obtained
 by sorting the biletters of ${\overline\Pi}^+$ by
weakly increasing rearrangement with respect to 
the anti-lexicographic order with
priority in the first row. The second row of $\overline{\Sigma}$,
denoted $\rho(w)$, is a shuffle of columns
${\overline{\rm v}_j}$, $j=6,4,3,2,1$. Under this injection the lattice path
$\begin{pmatrix}a^ib^ic^id^ie^if^i\\\!\!\!4\,3\,1\;4\;2\;1
\end{pmatrix}$, which has some negative slope steps,
 is stretched northeastward to
$\left(\begin{array}{c}a^ib^ic^id^ie^if^i\\\!\!\!6\,5\,4\;3\;2\;1
\end{array}\right)$,
where now every step has nonnegative slope. 

\begin{ex}\label{ex6} Let $\sigma=4123$ and
consider the biword $\widehat\Pi^+=
\left(\begin{array}{ccc} 114566&2233&3\\
431421&4321&4\\\end{array}\right)$ in Example~\ref{lex21}.
We have $\overline{\sigma}=612534$. Applying the map $\rho$, we
obtain the biword $\overline{\widehat\Pi}^+=
\left(\begin{array}{ccc} 114566&2233&3\\
654321&6521&6\\\end{array}\right)$, whose lattice path representation
is given below
\begin{equation}\label{exx3}
\includegraphics[scale=0.8,trim = 0cm 18cm 0cm 0cm,clip]{grelha15}.
\end{equation}



The bottom word of the biword $\overline{\widehat\Sigma}$, defined
above, and equivalent 
to $\overline{\widehat\Pi}^+$, is $\rho(w)=65656214321$, a shuffle
of the columns $654321$, $6521$ and $6$, which are exactly the words read
along the lattice paths, now all having nonnegative
slope.
\end{ex}

In the next proposition, we state some properties of the biword
$\overline{\Pi}^+$.

\begin{prop}\label{prop1+}
 Let $\overline{\Pi}^+$ be the biword defined above, and let
$\left(\begin{array}{c}
abcdef\\
654321
\end{array}\right)$ be one of its lattice paths. Then

 $(a)$ $\overline{\Pi}^+$ has no critical vertices.

 $(b)$ There are no vertices in
row $c$ to the left of $(c,4)$, nor are there in row $d$ to the right of
$(d,3)$, nor in row $e$ to the right of $(e,2)$.
\end{prop}
\begin{proof} This is a consequence of the definition of $\overline{\Pi}^+$
 and Lemma~\ref{bw}. \end{proof}

We are now in position to prove the following result.


\begin{teor}
 Let $T$ be a Young tableau over a four-letter alphabet with rectification
 $P$, and let
 $K$ be the key with the same weight as $T$. Then, $(T,K)$
 is a matrix tableau-pair if and only if $P=K$.
\end{teor}
\begin{proof} The {\em ``only if"} part was proved in \cite{am2}.
Conversely, assume $K=K(\sigma\alpha(m))$, for some
$\sigma\in\{1423,1432,4123,4132\}$ and $\ell_4,\ell_2>0$. Recall that in
any other case the plactic class of $K(\sigma\alpha(m))$ is the set
of all shuffles of its columns and, thus, by Theorem~\ref{teorrm1},
$(T,K(\sigma\alpha(m)))$ is a matrix-tableau pair. 

Without loss of generality let $w$ be the word of $T$
 in the set $\sh(
\widehat{\rm v}_5^{n_5},{\rm v}_4^{n_4},\ldots,{\rm v}^{n_1}),$
for some $0<n_5\leq \min\{\ell_2,\ell_4\}$, where $n_i=\ell_i$, $i=1,3$, and
$n_i=\ell_i-n_5$, $i=2,4$. Notice that either
$m_1=2n_5+n_4+n_3+n_2+n_1$ and $m_4=2n_5+n_4+n_3+n_2$, if
$\sigma\in\{1423,1432\}$, or $m_4=2n_5+n_4+n_3+n_2+n_1$ and
$m_1=2n_5+n_4+n_3+n_2$ otherwise. Let $\Pi^+$ be the biword
\eqref{pi+} of $T$ satisfying Lemma~\ref{bw}.
Consider the injection $\rho$ and the corresponding biword
$\overline{\Pi}^+$ as in \eqref{s4}, whose bottom word is the key
$K(\overline{\sigma},(n_5,0,n_4,n_3,n_2,n_1)$. Let
$\overline{T}$ be the Young tableau with the same skew-shape as $T$ and biword $\overline{\Pi}^+$. For each
$i=1,\ldots,n_5$, let
$\left(\begin{array}{c}a^ib^ic^id^ie^if^i\\\!\!\!6\,5\,4\;3\;2\;1
\end{array}\right)$
be a lattice path of $\overline{\Pi}^+$. Then, if $J_4,J_3,J_2,J_1$
are the indexing sets of $T$, and if
$\overline{J}_6,\cdots,\overline{J}_1$ are the indexing sets of
$\overline{T}$, we have
$\overline{J}_1=J_1\setminus\{c^i:i\in[n_5]\}$,
$\overline{J}_2=J_2$, $\overline{J}_5=J_3$,
$\overline{J_3}=\{d^i:i\in[n_5]\}$,
$\overline{J}_4=\{c^i:i\in[n_5]\}$, and
$\overline{J}_6=J_4\setminus\{d^i:i\in[n_5]\}$. Note also that, by
Proposition~\ref{prop1+}, there are no vertices in row $c^i$ to the
left of $(c^i,4)$, nor are there in row $d^i$, to the right of $(d^i,3)$.
Then, we may apply the Main Algorithm to $\overline{\Pi}^+$, choosing a
permutation $\sigma_1\in\mathfrak{S}_n$ satisfying 
the conditions of Step~$1$, and
satisfying in addition that $\sigma_1(n_1+\cdots+n_5+i)=c^i,$ for
$i=1,\ldots,n_5$. Denote by $A_0,B_1,\ldots,B_6$ the sequence of
 matrices obtained by this procedure. Then
$A_0=\diag _p({a'})$, $B_1=P_{\sigma_1}D_{[m_1-n_5]}$,
$B_2=S_2D_{[m_2]}$, $B_k=S_{k}D_{[n_5]}$, for $k=3,4$,
$B_5=S_5D_{[m_3]}$, and $B_6=S_6D_{[m_4-n_5]}$.
 By Theorem~\ref{teorrm1}, this sequence is a matrix realization for the
pair $(\overline{T},K(\overline{\sigma},(n_5,0,n_4,n_3,n_2,n_1))$. In
particular, this means that
\begin{eqnarray}
 &\sigma_1([m_1-n_5])=J_1\setminus\{c^i:i\in[n_5]\},
 \;\sigma_2([m_2])=J_2,\label{s1}\\
 &\sigma_3([n_5])=\{d^i:i\in[n_5]\},
 \;\sigma_4([n_5])=\{c^i:i\in[n_5]\},\label{s2}\\
 &\sigma_5([m_3])=J_3,\mbox{ and }
 \;\sigma_6([m_4-n_5])=J_4\setminus\{d^i:i\in[n_5]\}.\label{s3}\
\end{eqnarray}

Consider the sequence of matrices
$A'_0,B'_1,B'_2,B'_3,B'_4,$
 defined by $A'_0=\diag _p(a')$,
$B'_1:=P_{\sigma_1}D_{\Gamma_1}$, $B'_2:=B_2$,
$B'_3:=S_3S_4S_5D_{[m_3]}$, and $B'_4:=S_6D_{\Gamma_4}$, where
$\Gamma_1=[m_1],
\Gamma_4=[m_4-n_5]\cup\{m_4+n_1+1,\ldots,m_4+n_1+n_5\}$ if
$\sigma\in\{1423,1432\}$, and
$\Gamma_1=[m_1-n_5]\cup\{m_1+n_1+1,\ldots,m_1+n_1+n_5\},
\Gamma_4=[m_4]$ otherwise.

By (\ref{s1}) and the definition of $\sigma_1$, it is clear that
$$A'_0B'_1=\diag _p(a')P_{\sigma_1}D_{\Gamma_1}=
\diag _p(a'+\chi^{J_1})P_{\sigma_1},$$ 
and 
$$A'_0B'_1B'_2\sim_L
\diag _p(a'+\chi^{J_1})P_{\sigma_2}D_{[m_2]}=
\diag _p(a'+\chi^{J_1}+\chi^{J_2})P_{\sigma_2}.$$ 
Next, by (\ref{s2})
and (\ref{s3}), we find that
$$A'_0B'_1B'_2B'_3\sim_L\diag _p(a+\chi^{J_1}+\chi^{J_2})
P_{\sigma_5}D_{[m_3]}=
\diag _p(a'+\chi^{J_1}+\chi^{J_2}+\chi^{J_3})P_{\sigma_5}.$$ 
Finally, consider the product 
$$A'_0B'_1B'_2B'_3B'_4\sim
\diag
_p(a'+\chi^{J_1}+\chi^{J_2}+\chi^{J_3})P_{\sigma_6}D_{\Gamma_4},$$
and notice that, for each $i=1,\ldots,n_5$, we may write
$\sigma_6=\alpha_2^i(c^id^i)\alpha_1^i$, with $(c^id^i)$ the
transposition of $c^i$ with $d^i$, for some
$\alpha_2^i,\alpha_1^i\in\mathfrak{S}_n$ satisfying $\alpha_1^i(c^i)=c^i$
and $\alpha_2^i(d^i)=d^i$, since by Lemma~\ref{prop1+} there are no
vertices of $\overline{\Pi}^+$ nor are there in row $c^i$ to the left of
$(c^i,4)$, nor in row $d^i$ to the right of $(d^i,3)$. Therefore,
$$\sigma_6(\{m_4+n_1+1,\ldots,m_4+n_1+n_5\})=\{d^i:i\in[n_5]\},$$ 
and, by (\ref{s3}), we must have
$$A'_0B'_1B'_2B'_3B'_4\sim_L\diag
_p(a'+\chi^{J_1}+\chi^{J_2}+\chi^{J_3}+\chi^{J_4}).$$ 

Thus, $A'_0,B'_1,B'_2,B'_3,B'_4$ satisfy conditions I and II of
Definition~\ref{defMR}. It remains to show that $B'_1\cdots B'_4$ is
equivalent to the diagonal matrix $D_{[m_1]}\cdots D_{[m_4]}$. We
start by using Lemma~\ref{mtij1} to write, for $k=2,3,4$,
$$B'_k=\prod_{l=1}^{q_{k-1}}T_{i_lj_l}(1)C_kD_k
\prod_{l=1}^{q_{k-1}}T_{j_li_l}(-1)D_{\Gamma_k},$$
where $\Gamma_l=[m_l]$ for $l=2,3$, $C_kD_k$ is the identity matrix
for $k=2,4$, and $C_3$ [respectively $D_3$] is a product of upper
[respectively lower] elementary matrices $T_{jj'}(\tau)$, for some
integers $j,j'\in[m_2]$, and $\tau=\pm 1$. Next, use again
Lemma~\ref{mtij1} to write $B'_1\cdots B'_4$ as 
\begin{multline}
 \prod_{l=1}^{q_1}T_{i_lj_l}(p^{\nu_l})D_{[\Gamma_1]}
 \prod_{l=1}^{q_1}T_{j_li_l}(-1)\prod_{l=1}^{q_2}T_{i_lj_l}(p)D_{[m_2]}
 C_3D_3\prod_{l=1}^{q_2}T_{j_li_l}(-1)\\
 \cdot\prod_{l=1}^{q_3}T_{i_lj_l}(p)D_{[m_3]}
\prod_{l=1}^{q_3}T_{j_li_l}(-1)D_{[\Gamma_4]},\label{eqf1}\ 
\end{multline}
for some $\nu_l\geq 0$. Notice that we may eliminate 
any upper triangular matrix $T_{ij}(p^{\nu})$, $\nu>0$, by left
equivalence,
using Lemma~\ref{mtij1}. This operation may create new elementary
matrices $T_{uv}(p^{\nu'})$, but, as we have mentioned, using
Lemma~\ref{mtij1}, we may assume without loss of generality that this
is not the case. Thus, we may write
\begin{equation}
(\ref{eqf1})\sim_LD_{[\Gamma_1]}\prod_{l=1}^{q_1}T_{j_li_l}(-1)D_{[m_2]}
 C_3D_3\prod_{l=1}^{q_2}T_{j_li_l}(-1)
 D_{[m_3]}\prod_{l=1}^{q_3}T_{j_li_l}(-1)D_{[\Gamma_4]}.
\end{equation}
Use again Lemma~\ref{mtij1} to eliminate all
upper triangular matrices in $C_3$ by left
equivalence. New elementary matrices
 may be created. Among these, eliminate 
all those by left
equivalence which are upper triangular. Finally, starting
from right and moving to the left, eliminate all
lower triangular matrices left in the product by right equivalence. 
It is now clear that
$B_1\cdots B_4$ is equivalent to the diagonal matrix
$D_{[\Gamma_1]}D_{[m_2]}D_{[m_3]}D_{[\Gamma_4]}$. Since $m_k\leq
n_5+n_4+n_3+n_2$, $k=2,3$, and $\Gamma_1\subseteq\Gamma_4$ or
 $\Gamma_4\subseteq\Gamma_1$, we find that this last diagonal matrix
 is equivalent to $D_{[m_1]}\cdots D_{[m_4]}$.
\end{proof}









%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%









\section{Concluding remarks and open questions}


The Main Algorithm in Section~4 generates a matrix realization for the pair
$(T,K)$ whenever the word of $T$ is a shuffle of the columns of the
key-tableau $K$. In particular, when the Knuth class of $K$ is the
set of shuffles of its columns, we may construct a matrix realization
for the pair $(T,K)$ whenever $T$ rectifies to $K$.
Over a four-letter alphabet, there are key-tableaux whose plactic
class is bigger 
than the set of the shuffles of its columns. However, in those
cases, we just add the single word $431421$ to the set of the columns
of the key-tableau $K$ in order to describe its Knuth class as the
union of the shuffles of subsets of words 
 comprising the columns of $K$ and the word $431421$.


Working out some examples gives us an indication that this
procedure might be 
generalized to a $t$-letter alphabet, $t\geq 5$, once shuffling
generators for the Knuth class are known. 
Unfortunately one rapidly sees that the number of words needed to describe the
Knuth class of a key-tableau, for $t\ge 5$, as a set of shuffles
containing the shuffles of its columns, increases very 
fast. For example, over the alphabet $[5]$, we need to add the words
$5415321$ and $5431521$ to the columns of the key-tableau
$K=54321\,51$ to describe its 
Knuth class. If we instead consider the key-tableau
$K=54321\,54321\,51$, we now need to add 17 new words to the columns of
 $K$ in order to describe its Knuth class. Nevertheless, a
simple adaptation of the procedure used over a four-letter alphabet
works also fine. 



Although it seems to be a difficult problem, it would be interesting to
describe the Knuth class of a key-tableau $K$ as the union of 
shuffles of subsets of words 
 where the set of columns of $K$ is included.
 With this description, one believes that the general problem of finding a
matrix construction for the pair $(T,K)$, when $T$ is Knuth
equivalent to $K$, can be solved using a technique similar to that
which we used over a four-letter alphabet.
We point out that recently the enumeration of the distinct shuffles of
two permutations of any given lengths has been provided in
\cite{cbarnes}. In particular, this result gives the number of
distinct shuffles of the columns ${\rm v}_1$ and ${\rm v}_2$ in the Knuth
class of the key 
$K={\rm v}_2{\rm v}_1$ with only two columns. This number is exactly the
number of elements of the 
Knuth class when the support of ${\rm v}_1$ is either an interval or is
obtained from an interval by removing a single letter (see
Theorem~4.1 in \cite{am2}).








\begin{thebibliography}{99}
\bibitem{ap}
G.~Appleby, \emph{A simple approach to matrix realizations for
 {Littlewood--Richardson} sequences}, Linear and Multilinear Algebra
 \textbf{291} (1999), 1--14.

\bibitem{apwh}
G.~Appleby and T.~Whitehead, \emph{Matrix pairs over discrete valuation
rings determine Littlewood--Richardson fillings}, 
Linear Algebra and Its Applications \textbf{432} (2010), 1277--1298.

\bibitem{az5}
O.~Azenhas, \emph{Realiza\c c\~oes {M}atriciais de {Q}uadros de
{Y}oung e
 {S}uas {F}ormas {C}an\'onicas (in {Portuguese})}, Ph.D. thesis, Universidade
 de Coimbra, 1991.

\bibitem{az2}
O.~Azenhas, \emph{Opposite {Littlewood--Richardson} sequences and
their matrix
 realizations}, Linear Algebra and Its Applications \textbf{225} (1995),
 91--116.

\bibitem{az1}
O.~Azenhas and E.~Marques de S\'a, \emph{Matrix realizations of
 {Littlewood--Richardson} sequences}, Linear and Multilinear Algebra
 \textbf{27} (1990), 229--242.

\bibitem{am2}
O.~Azenhas and R.~Mamede, \emph{Matrix realizations of pairs of
{Y}oung tableaux, keys and shuffles}, S\'{e}minaire Lotharingien de
Combinatoire {\bf53} (2006), Article~B53h, 22~pp. (electronic).

\bibitem{am1}
O.~Azenhas and R.~Mamede, \emph{Actions of the symmetric group on
sets of skew-tableaux with
 prescribed matrix realization}, Linear Algebra and Its Applications
 \textbf{401} (2005), 221--275.

\bibitem{cbarnes}
C.~S.~Barnes, \emph{Enumeration of the distinct shuffles of
permutations}, Discrete Mathematics and Theoretical Computer Science
Proc. AK (2009), 155--166. 

\bibitem{B}
W.~C.~Brown, \emph{Matrices over Commutative Rings}, Monographs and
Textbooks
 in Pure and Applied Mathematics, Marcel Dekker, New York, 1993.


\bibitem{ful}
W.~Fulton, \emph{Young {Tableaux}}, London Mathematical Society
Student Texts,
 vol.~35, Cambridge University Press, Cambridge, 1997.

\bibitem{f1} W. Fulton, \emph{Eigenvalues of sums of {H}ermitian
matrices (after {K}lyachko)}, {S\'eminaire Bourbaki}
vol.~1997/98, Ast\'erisque {\bf 252} (1998), pp.~255--269.

 \bibitem{f2} W.~Fulton, \emph{Eigenvalues, invariant factors,
highest weights, and {S}chubert calculus}, 
Bulletin of the American Mathematical Society \textbf{7} (2000),
209--249.


\bibitem{f3} W. Fulton, \emph{Eigenvalues of majorized Hermitian
matrices and Littlewood--Richardson coefficients}, 
Linear Algebra and Its Applications \textbf{319} (2000), 23--36.

\bibitem{green}
J.~A. Green, \emph{Symmetric Functions and $p$-Modules}, Lecture
notes, University of Manchester, Manchester, 1961.


\bibitem{shuf}
J.~A. Green, \emph{Shuffle {A}lgebras, {L}ie {A}lgebras and
{Q}uantum
 {G}roups}, Textos de {M}atem\'atica, {S}\'erie B, vol.~9, Departamento de
 {M}atem\'atica, {U}niversidade de {C}oimbra, {C}oimbra, 1995.

\bibitem{greene}
C.~Greene, \emph{An extension of Schensted's theorem}, Advances in
Mathematics
 \textbf{14} (1974), 254--265.


\bibitem{klein}{T.~Klein},
\emph {The multiplication of {S}chur functions and extensions of
$p$-modules},
 {Journal of the London Mathematical Society}
{\bf 43} (1968), 280--282.


\bibitem{k}
D.~E.~Knuth, \emph{Permutations, {matrices}, and generalized {Young
tableaux}},
 Pacific Journal of Mathematics \textbf{34} (1970), 709--727.

\bibitem{loth}
A.~Lascoux, B.~Leclerc and J.~-Y.~Thibon, \emph{The plactic monoid},
in M.
 Lothaire (ed.), Algebraic Combinatorics on Words, Vol. 90 of Encyclopedia of
 Mathematics and its Applications, Cambridge University Press,
 Cambridge, 2002, pp.~164--196.

\bibitem{schu}
A.~Lascoux and M.~-P.~Sch\"utzenberger, \emph{Le mono\"{i}de
plaxique},
 Noncommutative structures in algebra and geometric combinatorics, (Naples,
 1978), Quaderni de "La Ricerca Scientifica" \textbf{109} (1981),
129--156.


\bibitem{keys}
A.~Lascoux and M.~-P.~Sch\"utzenberger, \emph{Keys and standard
bases}, Invariant theory and tableaux
 (Minneapolis, MN, 1988) IMA, Math. Appl., vol.~19, Springer, New York--Berlin,
 1990, pp.~125--144.


\bibitem{mac}
I.~G.~Macdonald, \emph{Symmetric {F}unctions and {Hall}
{P}olynomials}, Oxford
 University Press, Oxford, 1995.


\bibitem{new}
M.~Newman, \emph{Integral {Matrices}}, Academic Press, New York,
1972.


\bibitem{shimoz}
V.~Reiner and M.~Shimozono \emph{ Key polynomials and a flagged
Littlewood--Richardson rule}, Journal of Combinatorial Theory 
Series~A {\bf 70} (1995), 107--143.

\bibitem{lie}
C.~Reutenauer, \emph{Free {Lie} Algebras}, Oxford University Press,
Oxford,
 1993.

 \bibitem{sa} B.~E.~Sagan, \emph{The Symmetric Group. Representations,
Combinatorial Algorithms, and Symmetric Functions}, 
Springer Verlag, New York, 2001.

\bibitem{st}
R.~Stanley, \emph{Enumerative Combinatorics}, vol.~2, Cambridge
University Press, Cambridge, United Kingdom, 2001.


\bibitem{th}{R.~C.~Thompson},
\emph{Smith invariants of a product of integral matrices},
 Linear algebra and its role in systems theory (Brunswick, Maine,
1984), Contemp. Math., 47, 
 Amer. Math. Soc., Providence, RI, 1985, pp.~401--435.
\end{thebibliography}

\end{document}

