\documentclass[12pt,a4paper,reqno]{amsart}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{pictex}
\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}}
\theoremstyle{plain}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{cor}[lemma]{Corollary}
\newtheorem{teor}[lemma]{Theorem}
\newtheorem{prop}[lemma]{Proposition}
%
\theoremstyle{definition}
\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$^1$}
\vskip18pt
\centerline{Departamento de Matem\'{a}tica, Universidade de Coimbra}
\centerline{3001-454 Coimbra, Portugal}
}

\title[Matrix realizations of pairs of  Young tableaux, keys
and shuffles]{Matrix realizations of pairs of  Young tableaux, 
keys and shuffles }
\author[Olga Azenhas and Ricardo Mamede]{\box\Adr}

\thanks{$^1$Work supported by CMUC/FCT}

\address{
Departamento de Matem\'{a}tica, Universidade de Coimbra, 3001-454
Coimbra, Portugal}



\begin{abstract}

A key $\caH$ is a semi-standard tableau of partition shape whose
evaluation is a permutation of the  shape. We give a necessary and
sufficient condition that the Knuth class of a key equals the set of
shuffles of its columns. In particular, on  a  three-letter
alphabet the Knuth class of a key equals the set of shuffles of its
columns, and on a four-letter alphabet, the Knuth class of a key is
either the set of shuffles of its columns or the set of shuffles of
its distinct columns with a single word taking appropriate
multiplicities. For some instances of $\caH$
this result has been already applied to exhibit a matrix
realization, over a local principal ideal domain, of a pair of
tableaux $(\caT,\caH)$, where $\caT$ is a skew-tableau whose word is
in the Knuth class of $\caH$. Generalized Lascoux--Sch\"utzenberger
operators, based on nonstandard matching of parentheses, arise
 in the matrix realization, over local principal ideal domain, of a pair $(\caT,\caH)$ on a two-letter alphabet, and they are used
 to show that,
over a $t$-letter alphabet, the pair $(\caT,\caH)$ has a matrix
realization only if the word of $\caT$ is in the Knuth class of
$\caH$.

\end{abstract}


\maketitle


%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 53 \rms (2006), Article~B53h\hfill}
\def\thepage{}
%
%


\section{Introduction}
Given an $n$ by $n$ non-singular 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 with diagonal entries
$p^{\lambda_1},\ldots,p^{\lambda_n}$, for unique nonnegative
integers ${\lambda_1}\ge\ldots\ge {\lambda_n}$, called  the Smith
normal form of $A$. The sequence
$p^{\lambda_1},\ldots,p^{\lambda_n}$ defines the invariant factors
of $A$, and $({\lambda_1},\ldots, {\lambda_n})$ the invariant
partition of $A$. It is known that $\alpha$, $\beta$, $\gamma$ are
invariant partitions of non-singular matrices $A$, $B$, and $C$ such
that $AB=C$ if and only if there exists a Littlewood--Richardson tableau $\caT$
of type $(\alpha,\beta, \gamma)$, that is, a skew-tableau of shape
$\gamma/\alpha$ whose word is in the Knuth class of the key $\caH$
of evaluation $\beta$ (Yamanouchi tableau $\beta$).  This matrix
problem is equivalent to the existence of $p$-modules $\caA$,
$\caB$, and $\caC$ with invariant partitions $\alpha$, $\beta$,
$\gamma$ such that $\caB\subseteq \caC$ and $\caC/\caB\cong\caA$
\cite{klein}. (Interestingly, the eigenvalues of a sum of
Hermitian matrices $A+B=C$ are characterized by the same condition
\cite{fulton3, inter}.) This theory was developed, with different
approaches, by several authors, such as P.~Hall, J.~A.~Green, T.~Klein, 
I.~Gohberg, M.~A.~Kaashoek, R.~C.~Thompson
\cite{green2,green,klein,kash,mac,thompson2, az1,thijsse}. (For an
overview see \cite{fulton3,fulton5,fulton4}.) One can solve this
problem by introducing the notion of a matrix realization of a pair
$(\caT,\caH)$ where $\caT$ is a skew-tableau with the same
evaluation as the key $\caH$ \cite{az1,az5,ap} [see Section~$5$,
Definition~\ref{defMR}] which   is equivalent, in the module
setting, to the existence of a chain of $p$-submodules
$(0)=\caB_t\subseteq \cdots\subseteq \caB_1$ $\subseteq \caB_0$ $=$
$\caB$ $\subseteq\caC$ such that the sequence of invariant
partitions
 of $\caC/\caB_k$, $0\le k\le t$, defines a Littlewood--Richardson  tableau of shape $\gamma/\alpha$ and  evaluation given by the
  weight of the  invariant partitions of  $\caB_{k-1}/\caB_k$, $1\le k\le t$ \cite{klein}. Within this notion it is
natural to ask under which conditions does there exist a matrix
realization of a pair $(\caT,\caH_{\sigma})$, where $\caH_{\sigma}$
is a key associated with $\sigma\in \caS_t$
\cite{eh,ful,aretes,keys}. In the case of the reverse permutation in
$\caS_t$ \cite{az2}, or any permutation
 in $\caS_3$ \cite{am1}, or any adjacent transposition \cite{az3,RM}, it has been shown that
  $(\caT,\caH_{\sigma})$ has a matrix realization if and only if the word of
  $\caT$ is  in the plactic class of $\caH_{\sigma}$.
For these permutations,
   the elements of the
plactic class of $\caH_{\sigma}$ are   shuffles of the columns of
$\caH_{\sigma}$ and this property has been used to exhibit a matrix
realization $(\caT,\caH_{\sigma})$. Here, in Theorem~\ref{v}, we
show that, for any $\sigma\in \caS_t$, $t\geq 1$,
$(\caT,\caH_{\sigma})$ has a matrix realization only if the word of
$\caT$ is in the plactic class of $\caH_{\sigma}$.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL OLGA AZENHAS AND RICARDO MAMEDE}{\SMALL MATRIX REALIZATIONS OF PAIRS OF YOUNG TABLEAUX, KEYS AND SHUFFLES}
%
%


Due to the embedding of the symmetric group in the set of tableaux,
originally defined by Ehresmann in \cite{eh}, the symmetric group
acts on the set of keys $\caH_{\sigma}$, $\sigma\in\caS_t$, in the
obvious way. This action coincides with the one defined by the
operations on the free algebra, described by A. Lascoux and M. P.
Sch\"utzenberger in the plactic monoid \cite{schu,loth}, based on
the standard matching of parentheses, a particular parentheses
matching on words in a two-letter alphabet. As these operations
preserve the $Q$-symbol, they are bijections between the plactic
classes $\caH_{\sigma}$ and $\caH_{s_i\sigma}$, with $s_i$ the
adjacent transposition of the integers $i$, $i+1$. Matrix
realizations of pairs $(\caT,\caH)$, over a two-letter alphabet,
give rise to operations based on other parentheses matching than the
standard one, as shown in Example~\ref{ex}  (see also \cite{am1}).
Corollary~\ref{theta} characterizes the operations, based on more
general parentheses matching, which transform a word in the plactic
class of $\caH_{\sigma}$ into one in the plactic class of
$\caH_{s_i\sigma}$. The proof of Theorem~\ref{v} is based on these
operations and their characterization.









Two columns commute (in the plactic sense) if and only if they are
comparable for the inclusion order. In fact,  the words of the
plactic class of a key  over a three-letter alphabet are shuffles
of their columns \cite{am1}. In the case of a four-letter alphabet
this property does not remain true. Nevertheless, by Greene's theorem
\cite{greene}, shuffling together the columns of a key always leads
to a word in the plactic class of  this key. We characterize the
keys for which the plactic class  may be described by shuffling
together their columns. The keys associated with the identity and
the reverse permutations in $\caS_t$, $t\geq 1$, are simple examples
of those keys. Finally, for $\sigma\in\caS_4$, we show that we may
describe the plactic class of any associated key, in terms of
shuffling, by adding, in those cases where the columns of the key
are not enough, one single word $434121$.




 The paper is  organized as follows. In the next section
we collect some notation and basic notions necessary in the sequel.
The relationship between  shuffling and Knuth operations on words is
discussed. The following question is raised: {\em if
 the columns $u_1,\ldots,u_k$ are pairwise comparable for the
inclusion order, under which conditions is 
the set of all shuffles of $u_1,\dots,u_k$, denoted
by $Sh(u_1,\ldots,u_k)$, the
plactic class of $u_1\ldots u_k$}? Indeed, the containment of
$Sh(u_1,\ldots,u_k)$  in the plactic class of $u_1\ldots u_k$
follows from Greene's theorem \cite{greene}. It remains to analyze
whether the reverse inclusion holds.

In Section~$3$, the key tableaux, that is, the  tableaux with
pairwise comparable columns for the inclusion order, are considered.
They can be seen as the tableaux whose evaluation is a permutation
of the shape or as the image of the embedding of the symmetric
group in the set of tableaux, originally defined by Ehresmann
\cite{eh}. $\sigma$-Yamanouchi words are introduced as words
congruent to a key of the permutation $\sigma$. These words are
directly related with the action of the symmetric group, defined by
the operations on all words described by A. Lascoux and M. P.
Sch\"utzenberger in the plactic monoid \cite{schu,loth}, based on
the standard parentheses matching. Operations on words based on more
general parentheses matchings are considered. A   criterion
characterizing   those which transform a $\sigma$-Yamanouchi word
into a $s_i\sigma$-Yamanouchi word is given.




In Section~4, the answer to the question raised in Section~2 is given
by imposing conditions on the key $u_1\ldots u_k$ such that  the
plactic class of $u_1\ldots u_k$ is contained in
$Sh(u_1,\ldots,u_k)$. In the case of $\caS_4$, a full description of
the plactic classes of the associated keys, in terms of shuffling,
is given. In Section~5, a matrix interpretation and application of
the generalized Lascoux--Sch\"utzenberger operations, based on
nonstandard matching of parentheses, is considered. Finally, in
the Appendix, the permutations in $\caS_5$ and $\caS_6$ giving a
positive answer to the question raised in Section~2 are listed.









%----------------------------------------------------------
\section{Words, shuffles and Knuth congruence}
\subsection{Words and tableaux}


Let $\mathbb{N}$ be the set of positive integers with the usual
order ``\,$\leq$\,".  Given $i,j\in\mathbb{N}$, where $i\le j$, $[i,j]$ is an
interval in $\mathbb{N}$ with the usual order. If $t\in\mathbb{N}$,
$[t]$ denotes the set $\{1,\ldots,t\}$.

Let $A=\{a,b,\ldots,f\}$, $a<b<\cdots<f$, be a finite subset of
$\mathbb N$. We denote by $A^*$ the free monoid in the alphabet $A$;
that is, $A^*$ is the collection of all finite words over the alphabet $A$,
with the concatenation operation. The neutral element is the empty
word, denoted  by $\epsilon$.

 Given a word $w=x_1\cdots x_k$ over the alphabet $A$, 
we call $k$ the length of $w$ and denote it
by $|w|$. Furthermore, we denote by $|w|_x$
 the multiplicity of the letter $x\in A$ in $w$. The
sequence $(|w|_{a},\ldots,|w|_{f})$ is called the {\it evaluation}
of $w$ in the alphabet $A$. 
We have $|w|=|w|_{a}+\cdots+|w|_{f}$, and the length of
$\epsilon$ is zero. Given $B$ a subalphabet of $A$, $w_{|B}$ denotes
the word obtained by erasing the letters not in $B$.

 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 } in $A^*$. A column shall be identified with the set
consisting of its entries. Given two finite subsets
$P=\{p_1,p_2,\dots\}$, $Q=\{q_1,q_2,\dots\}$ of
$\mathbb N$ with $|P|\le |Q|$, we write $P\le Q$ if $p_i\le q_i$ for
$i=1,2,\dots,|P|$.



A partition $\lambda=(\lambda_1,\ldots,\lambda_k,\dots)$ is a
weakly decreasing (finite or infinite) sequence of nonnegative
integers, with only a finite number of nonzero entries. The number
of nonzero entries of $\lambda$ is called the {\em length} of
$\lambda$. A partition $\lambda$  is identified with its Young
diagram, a left-justified arrangement of boxes, or dots, 
with $\lambda_i$ boxes (dots) in the $i$-th row, where rows are
arranged from bottom to top.
(We adopt
the French notation.) The conjugate of partition $\lambda$ is the
partition $\lambda'$, the transpose of the Young diagram $\lambda$.
It is convenient not to distinguish between two partitions which
only differ by a string of zeros at the end. Sometimes we write
$\lambda=(1^{p_1}, 2^{p_2},\cdots)$ to indicate that $i$  appears $p_i$
times  as a part of $\lambda$. For instance, the partition
$(3,2,2,1)=(3,2^2,1,0)$ corresponds to the Young diagram
$$\begin{matrix}
\bullet&&\\
\bullet&\bullet&\\
\bullet&\bullet&\\
\bullet&\bullet&\bullet
\end{matrix},$$
and its conjugate partition is $(4,3,1)$. Clearly, the lengths of
the columns in weakly decreasing order define the transpose Young
diagram.

 A Young tableau $\caT$ of shape
$\lambda$ is a filling of the Young diagram of $\lambda$ with
positive integers,   weakly increasing across each row and strictly
increasing up each column \cite{ful,loth}. An example of a Young
tableau of shape $(3,2,2,1)$ is given by
$$\caT=\begin{matrix}
    5&&\\
    4&5&\\
    2&2&\\
    1&1&2
\end{matrix}.$$
The word of a Young tableau is the word obtained by reading its
columns from top to bottom, starting on the left and moving to the
right. A Young tableau shall be identified with its word. In the
example above, we have $\caT=5421\,521\,2$ (the empty spaces only indicate
the end of a column and the starting of a new one).
The evaluation of a Young tableau $\caT$ is
the evaluation of its word. For instance, the evaluation of the
Young tableau above is $(2,3,1,2)$.

A skew-diagram is the diagram obtained by removing a smaller Young
diagram from a larger one that contains it. If $\lambda$ and $\mu$
are partitions with $\mu\subseteq\lambda$, that is,
$\mu_i\leq\lambda_i$ for all $i$, we define a skew-tableau of shape
$\lambda/\mu$ as a filling of the skew-diagram $\lambda/\mu$, that
is, weakly increasing across each row and strictly increasing up
each column \cite{ful}. A Young tableau of shape $\lambda$ may be
seen as a skew-tableau of shape $\lambda/(0)$, where $(0)$ denotes
the empty partition. An example of a skew-tableau of shape
$(4,4,2,1)/(3,1)$ is given by
$$\caT=\begin{matrix}
4&&&\\
2&2&&\\
\bullet&1&3&3\\
\bullet&\bullet&\bullet&2
\end{matrix}\ .$$
The word $w(\caT)$ of a skew-tableau $\caT$ is the word obtained by
reading its columns from top to bottom, starting on the left and
moving to the right. In the example above we have
$w(\caT)=42\,21\,3\,32$. As for Young tableaux,
the evaluation of a skew-tableau $\caT$ is
the evaluation of its word. For instance, the evaluation of the
skew-tableau $\caT$ above is $(1,3,2,1)$.

A skew-tableau $\caT$ of shape $\lambda/\mu$ and evaluation
$(m_1,\ldots,m_t)$ may also be represented by a nested sequence of
partitions \cite{mac} $\caT=(\lambda^0,\lambda^1,\ldots,\lambda^t)$,
where $\mu=\lambda^0\subseteq \lambda^1\subseteq\cdots\subseteq
\lambda^t=\lambda$, such that for $k=1,\ldots,t$, all the boxes
of the skew diagram
$\lambda^k/\lambda^{k-1}$ are filled with $k$, with
$m_k=|\lambda^k|-|\lambda^{k-1}|$. In the example above,
$\caT=(\lambda^0,\lambda^1,\lambda^2,\lambda^3,\lambda^4)$, where
$\lambda^0=\mu$, $\lambda^1=(3,2)$, $\lambda^2=(4,2,2)$,
$\lambda^3=(4,4,2)$ and $\lambda^4=\lambda$.

\subsection{Shuffles and Knuth congruence}

A word $w$ contains $u$ as a subword if $w$, as a sequence of
letters, contains $u$ as a subsequence. A word $w$ is a shuffle of
the words $u$ and $v$ if $u$ and $v$ can be embedded as subwords of $w$
that occupy complementary sets of positions within $w$. A shuffle
$w$ of the words $u_1,u_2,\ldots, u_q$ is the empty word $\epsilon$
for $q=0$, the word $u_1$ for $q=1$, and is, otherwise, a shuffle of
$u_1$ with some shuffle of the words $u_2,\ldots,u_q$. Let
$Sh(u_1,u_2,\ldots,u_q)$ denote the set of shuffles of
$u_1,u_2,\ldots,u_q$. By abuse of notation we write
$w=sh(u_1,u_2,\ldots,u_q)$ to mean that $w$ is some shuffle of
$u_1,u_2,\ldots,u_q$.


For example, it is simple to check that $4423142121$ is a shuffle of
 $4321,421$ and $421$. When there is no danger of confusion, to avoid
cumbersome notation, we shall write
$sh((u_1)^{l_1},\ldots,(u_q)^{l_q})$ to designate a shuffle of $l_i$
words $u_i$, for $i=1,\ldots,q$. Thus, we have $4423142121\in
Sh(4321,(421)^2)$.


%-----------------------------------------------------
Knuth's  congruence $\equiv$ \cite{k} on words over the alphabet $A$
 is the congruence  generated by the so-called
elementary transformations, where $x$, $y$, $z$ are letters  and
$u$, $v$ are words in $A$:
\begin{equation}\label{K3}
uxzxv\equiv uzxxv,\;\;\; uzzxv\equiv uzxzv,\;\;x< z,
 \end{equation}
\begin{equation}\label{K1}
 uxzyv\equiv
uzxyv,\;\;x< y< z,
\end{equation}
\begin{equation}\label{K2}
 uyzxv\equiv
uyxzv,\;\;x<y< z.
\end{equation}

The relations (\ref{K3}), (\ref{K1}), (\ref{K2}),  also called
{\em plactic relations}, are the algebraic version of  the plactic
congruence
 \cite{ful,k,loth}.
C. Schensted  \cite{ful,loth,sch} has described an algorithm, known
as {\it Schensted's insertion algorithm}, which associates to each
word $w$ a tableau $P(w)$.
 Two words $w,w'$ are plactic equivalent if and only if $P(w)=P(w')$
\cite{ful,k,loth}.  The set of all tableaux is a {\em section} of
the plactic congruence. This means that every word   can be obtained
by a finite sequence of elementary Knuth transformations from a
tableau.

Let $u_1,\ldots, u_k$ in $A^*$ be columns in decreasing order of
length. If ${\mathcal{T}}=u_1\ldots u_k$ is a tableau, then ${\mathcal{T}}$
is the unique tableau
  of $Sh(u_1,\ldots,u_k)$ only if
 the columns of the tableau $\mathcal{T}$ are pairwise comparable
for the inclusion order; that is  $\{u_k\}\subseteq \cdots\subseteq
\{u_1\}$. For instance, $Sh(41,3)=\{3\,41, 41\,3,431\}$ has
two tableaux $41\,3$ and $431$.










 An elementary Knuth
transformation (\ref{K3}), (\ref{K1}), or (\ref{K2}) applied to a shuffle of
columns, say $u_1,\dots,u_k$, involves at least two of these
columns. If an elementary Knuth transformation (\ref{K1}) or
(\ref{K2}) involves three distinct letters $x<y<z$ of
$sh(u_1,\dots,u_k)$, each one belonging to a different column
$u_i$, then the output word is still a shuffle of $u_1,\ldots,u_k$.

\begin{prop}\label{k} Let $u_1,\ldots,u_k$, $k\ge 3$, be columns in $A^*$,
 and $x,y,z$, $u$ and $v$ as in {\em(\ref{K1}), (\ref{K2})} such that
each letter $x$, $y$ and $z$ appears in a distinct column. Then
 $$uxzyv\in
Sh(u_1,\ldots,u_k)\Leftrightarrow uzxyv\in Sh(u_1,\ldots,u_k);$$
$$uyzxv\in
Sh(u_1,\ldots,u_k)\Leftrightarrow uyxzv\in Sh(u_1,\ldots,u_k).$$

\end{prop}

  For instance, in the
alphabet $[5]$, consider the word
$5\:\overline{2}\:4\:\underline{4}\:\overline{1}\:2\:\underline{2}\:1\:
\underline{1}\in Sh(5421,421,21)$, where the underlined letters
define the word $421$, the overlined letters define the word $21$,
and the remaining letters define the word $5421$. The application
of the elementary Knuth transformation
$\underline{4}\:\overline{1}\:2\equiv
\overline{1}\:\underline{4}\:2$ to
$5\:\overline{2}\:4\:\underline{4}\:\overline{1}\:2\:\underline{2}\:1\:
\underline{1}$ gives the word
$w=5\:\overline{2}\:4\:\overline{1}\:\underline{4}\:2\:\underline{2}\:1\:
\underline{1}$, which is still a shuffle of $5421$, $421$ and
$21$.

If the Knuth transformation involves only two distinct letters of
$sh(u_1\ldots,u_q)$,  it is also clear that the output word is
still a shuffle of $u_1\ldots,u_q$.
\begin{prop} \label{s2} Let $u_1\ldots,u_k$, $k\ge 2$, be columns in $A^*$,
and $x$, $z$, $u$ and $v$ as in {\em(\ref{K3})}. Then
$$uzxxv\in Sh(u_1,\ldots,u_k)\Leftrightarrow uxzxv\in
Sh(u_1,\ldots,u_k);$$
$$uzzxv\in Sh(u_1,\ldots,u_k)\Leftrightarrow uzxzv\in
Sh(u_1,\ldots,u_k).$$
\end{prop}
%Suppose the rows  by decreasing order of the their length.


\begin{cor} Let $u_1\ldots,u_k$, $k\ge 2$, be columns in a two-letter alphabet $A=\{a,b\}$,
  and $w\in Sh(u_1,\ldots,u_k)$ of evaluation $(p,q)$. Then

{\em(a)} $P(w)\in Sh(u_1,\ldots,u_k)$.

{\em(b)} $Sh(u_1,\ldots,u_k)$ is either

\begin{enumerate}
\item[(i)]
 the plactic class of $P(w)=(ba)^q1^p$ or $P(w)=(ba)^pb^q$, if
the columns $u_{i}$ are pairwise comparable for the inclusion order,
for $i=1,\ldots, k$; or
\item[(ii)]
the  union of the plactic classes of $P(w)=(ba)^ra^sb^v$,
$r+s=p$, $r+v=q$, and $P(w)=(ba)^{p+q}$, otherwise.
\end{enumerate}
\end{cor}

Let $x<y<z\in A$. The columns $\overline{z}\:\overline{y}$ and
$\underline{y}\:\underline{x}$, in the elementary Knuth
transformations $x\:\overline{z}\:\overline{y}\equiv
\overline{z}\:x\:\overline{y}$ (\ref{K1}), and
$\underline{y}\:z\:\underline{x}\equiv\underline{y}\:\underline{x}\:z$
(\ref{K2}), respectively, are not broken by these transformations
and, therefore, the shuffle of $\overline{z}\:\overline{y}$ and $x$,
and $\underline{y}\:\underline{x}$ and $z$
 is preserved. The only column that is
broken by these Knuth transformations is $zx$ which is transformed
into $xz$. Consider again the columns  $41$ and $3$. We have
$Sh(41,3)=\{3\,41, 41\,3, 431\}$,  but $3\,41\equiv 31\,4\notin
Sh(41,3)$ and $41\,3\equiv 143\notin Sh(3,41)$. Therefore,
considering, for example,
  the tableau $4321\,41$, the
Knuth transformation $341\equiv 314$ implies
$43\underline{4}\:\underline{1}21=sh(4321,41)\equiv
43\underline{1}\:\underline{4}21$, but
$43\underline{1}\:\underline{4}21$ can not be obtained  by a shuffle
of the columns $4321$ and $41$.


Supposing that $u_1,\ldots,u_k$ are columns pairwise comparable in
the inclusion order, we raise the question:
 {\em Under which conditions $Sh(u_1,\ldots,u_k)$ equals the plactic
class of the tableau ${\mathcal{T}}=u_1\cdots u_k$?}


We start by noticing that the containment $Sh(u_1,\ldots,u_k)$ in
the Knuth class of $\caT$ follows from Greene's theorem
\cite{greene}. Since $u_1\supseteq\cdots\supseteq u_k$, the maximum
of the sums of the lengths of $j$ decreasing and disjoint subwords
of $w\in Sh(u_1,\ldots,u_k)$ is $|u_1|+\cdots+|u_j|$, for all $j\geq
1$. It follows from Greene's theorem  that the conjugate shape of
$P(w)$ is $(|u_1|,\ldots,|u_k|)$, which means that $P(w)=u_1\cdots
u_k$. But as we have
 seen above, in general, we do not have equality. In Section~$4$ we
determine the conditions for which equality holds.


%----------------------------------------------------------------------------
\section{Keys and $\sigma$-Yamanouchi words}

\subsection{ Parentheses matching operations}

Given a set $I$, let $\caS_I $ be the set of all bijections on $I$,
and $\caS_t:=\caS_{[t]}$ the symmetric group of order $t$.
 The symmetric group $\caS_t$,
$t\geq 1$, is generated by the simple transpositions
$s_i=(i\:i+1)$, $i=1,\ldots,t-1$, which satisfy the Moore-Coxeter
relations:
$$\text {(I)}\:s_i^2=id,\:\:\text {(II)}\:s_is_j=s_js_i,\mbox{ if }|i-j|\neq
1,\mbox{ and (III)}\:s_is_{i+1}s_i=s_{i+1}s_is_{i+1},$$ where $id$
denotes the identity.

Let $w$ be a word over the alphabet $[t]$ and $i,i+1\in [t]$. An
operation  $\theta_i$   on  $w$ \cite{am1} consists of $(a)$ a
longest matching on $w_{|\{i,i+1\}}$ between letters $i+1$ and
letters $i$ to their right, by putting a left parenthesis on the
left of each letter $i+1$, and a right parenthesis on the right of
each letter $i$, such that the unmatched right and left parentheses
indicate a subword of the form $i^s(i+1)^r$; $(b)$ this subword will
be replaced in $w_{|\{i,i+1\}}$ with $i^r(i+1)^s$. By abuse of
notation, we write $\theta_i(w)$ to refer to any  word which is related
with $w$ in the defined way.



Let $w=31314221412$ be a word over the alphabet $[4]$. For example,
inserting parentheses on the right of the letters $1$ and on the
left of the letters $2$ of the word $w_{|\{1,2\}}=1122211$, we get
$1)1)(2(2(21)1)$. We may match the two left most letters $2$ with
the letters $1$ to their right. The unmatched letters indicate the
subword $w'=112=1^22^1$. Thus,
$\theta_1(w_{|\{1,2\}})=\underline{1}\:\underline{2}\:2\:2\underline{2}\:1\:1$,
where the underlined word is the subword $w'$ replaced with
$1^12^2$. Finally,
$\theta_1(w)=3\,{1}\,3\,2\,4\,2\,{2}\,2\,4\,1\,1$.

A. Lascoux and M. P. Sch\"utzenberger \cite{schu,loth} have
introduced the following involutions $\theta_i^*$, for
$i=1,\ldots,t-1$,  on all words over the alphabet $[t]$, based on
the standard matching of parentheses on words over a two-letter
alphabet, a particular matching of parentheses. Let $w$ be a word
over the alphabet $[t]$. To compute $\theta_i^*(w)$, first extract
from $w$ the subword $v$ containing the letters $i$ and $i+1$ only.
Second, bracket every factor $i+1\:i$ of $v$. The letters which are
not bracketed constitute a subword $v_1$ of $v$. Then bracket every
factor $i+1\:i$ of $v_1$. There remains a subword $v_2$. Continue
this procedure until it stops, giving a word $v_k$ of type
$i^r\:(i+1)^s$. Then, replace it with the word $i^s\:(i+1)^r$ and,
after this, recover all the removed letters of $w$, including the
ones different from $i$ and $i+1$. The operations
$\theta_i^*$, $1\leq i\leq t-1$, satisfy the Moore-Coxeter relations
\cite{schu,loth} and define an action of $\caS_t$ over $[t]^*$.

Let $w=31314221412$ as above. To compute $\theta_1^*(w)$, we get
$v=112(21)12$, $v_1=11(21)2$ and $v_2=112=1^22^1$. Thus,
$\theta_1^*(w)=3\:\underline{1}\:3\:\underline{2}\:4\:2\:2\:1\:4\:1\:\underline{2},$
where the underlined word is the subword $v_2$ replaced with
$1^12^2$.

The operations $\theta_i^*$, $1\leq i\leq t-1$, are compatible with
the plactic equivalence and preserve the $Q$-symbol.

\begin{prop}{\em\cite{schu,loth}} \label{tet}
    Let $w,w'$ be words in $[t]^*$, and let $i\in[t]$. Then, $w\equiv w'$
    if and only if $\theta_i^*( w)\equiv \theta_i^* (w')$. In
    particular, $P(\theta^*_i(w))=\theta^*_i(P(w))$.
\end{prop}
Note that in the examples above we have $\theta_1(w)\not\equiv
\theta^*_1(w)$. In the case of words $w$ congruent to a tableau
whose columns are comparable in the inclusion order, we will give a
criterion such that $\theta_i(w)\equiv \theta^*_i(w)$.



\subsection{Keys and  $\sigma$-Yamanouchi words}
By definition, a {\em key} is a tableau such that its columns are
pairwise comparable in the inclusion order \cite{keys}.
Equivalently, a key is a tableau whose evaluation is a permutation
of its shape. For instance, over the alphabet $[6]$,
$65431\,641\,41$ is a key of shape $(3,3,2,1,1)$ and evaluation
$(3,0,1,3,1,2)$.

Let $(l_t,\ldots,l_2,l_1)$ be a sequence of nonnegative integers.
Then, $m=(l_1+\cdots+l_t,\ldots,l_{t-1}+l_t,l_t)$ is a partition
and $(t^{l_t},\ldots,2^{l_2},1^ {l_1})$ its conjugate. For
instance, $(1,1,\ldots,1)$ defines the self-conjugate partition
$(t,t-1,\ldots,1)$.





Let $\sigma \in{\caS}_t$ written as a word $a_1\cdots a_t$ in
$[t]^*$. For $k=1,\ldots,t$, denote by $r_{\sigma,k}$ the column
with underlying set $\{a_1,\ldots, a_k\}$.
%The evaluation of
%$r_{\sigma,k}$ is $\sigma {\bf e_k}$, for $k=1,\ldots,t$.
 In particular, when $\sigma=12\ldots t$, we get $r_k=k\ldots
21$. Clearly, $\{r_t\}\supseteq \{r_{\sigma,t-1}\}$ $
\supseteq\ldots$ $\supseteq \{r_{\sigma,1}\}$.


\begin{defi} {\em Key of a permutation} \cite{keys}. To each pair consisting of a
permutation $\sigma\in\caS_t$ and a sequence of nonnegative integers
$(l_t,\ldots,$ $l_1)$, Ehresmann \cite{eh} associated a key of shape
$m$,
%$(t^{l_t}\ldots,$ $2^{l_2},$ $1^ {l_1})$,
here denoted by
$\caH_{\sigma(l_t,\ldots,l_1)}$, by taking the sequence
$(r_t)^{l_t},\,(r_{\sigma, {t-1}})^{l_{t-1}},\ldots,$ $
(r_{\sigma,1})^{l_1}$ of left reordered factors of $\sigma$;
 that is,
$$\caH_{\sigma(l_t,\ldots,l_1)}:=(r_t)^{l_t}\,(r_{\sigma,
{t-1}})^{l_{t-1}}\cdots (r_{\sigma,1})^{l_1},$$ is the key of
$\sigma$ of shape $m$.
% $(t^{l_t}\ldots,2^{l_2},$ $1^ {l_1})$.
 In
particular, $\caH_{(l_t,\ldots,l_1)}=(t\cdots
21)^{l_t}\cdots(21)^{l_2}$ $(1)^{l_1}$.\end{defi}

For $i=1,\ldots,t$, the letter $a_i$ appears only in the columns
$r_t,\ldots,r_{\sigma,i}$.
 Hence, the multiplicity of $a_i$ in
$\caH_{\sigma(l_t,\ldots,l_1)}=(r_t)^{l_t}\,(r_{\sigma,
{t-1}})^{l_{t-1}}\ldots (r_{\sigma,1})^{l_1}$ is
$\sum_{k=i}^tl_k$, for $i=1,\dots,t$. We put $\sigma
m=(m_1,\ldots,$ $m_t)$, where
 $m_i=\sum_{k=\sigma^{-1}(i)}^tl_k$, $i=1,\ldots,t$.
Hence $\caH_{\sigma(l_t,\ldots,l_1)}:=(r_t)^{l_t}\,(r_{\sigma,
{t-1}})^{l_{t-1}}\ldots (r_{\sigma,1})^{l_1}$  is also the key of
$\sigma$ with evaluation $\sigma m$;
%\linebreak $(\sum^t_{k= \sigma^{-1}(1)}l_k,$
%$\ldots,\sum^t_{k=\sigma^{-1}(t-1)}l_k,\sum^t_{k=\sigma^{-1}(t)}l_k)$;
equivalently, the unique tableau of evaluation $\sigma m$ and shape
$m$.
%$\sum_{i=1}^t (1^{m_i})$.

Note that $\caH_{\sigma (l_je_j) }= (r_{\sigma,j})^{l_j},$ and
$\caH_{\sigma (l_t,\ldots,l_1)}=(\caH_{\sigma (l_t
e_t)})^{l_t}\dots (\caH_{\sigma
 (l_1e_1)})^{l_1},$ with $e_j=(\delta_{i,j})$, $j=1,\ldots,t$.


On the other hand, if ${\caT}=q_t\ldots q_2\, q_1$
 is a key,  with $q_t=t\ldots 2\,1$  and
  $|q_{t-1}|>\ldots >|q_1|$, we get that  column $q_k$ is such that
$\{q_k\}=\{q_t\}\setminus \{a_t,\ldots,a_{k+1}\}$ with
$\{a_t,\ldots,a_{k+1}\}\subseteq \{1,\ldots,t\}$, $1\le k\le t-1$.
Putting $\sigma:=a_1\ldots a_t$  this shows that ${\caH}_{\sigma
(1,\ldots, 1)}={\caT}$. Therefore,  given a sequence
$(l_t,\ldots,l_1)$ of positive integers,
$$\sigma\longrightarrow
 \caH_{\sigma(l_t,\ldots,l_2,l_1)}=(r_t)^{l_t}\,(r_{\sigma,
{t-1}})^{l_{t-1}}\ldots (r_{\sigma,1})^{l_1},$$ defines an
embedding of $\caS_t$ into the set of tableaux of
 conjugate shape $(t^{l_t},\ldots,{2}^{l_2},{1}^{l_1})$.





 For example,
  with
$\sigma=3124\in\caS_4$, we have
    $r_{4}=4321,
    r_{s_2,3}=321,
    r_{s_2,2}=31$,
    $r_{s_2,1}=3$,
$\caH_{\sigma(1,1,1,1)}=\begin{matrix}
                  4&&&\\
                  3&3&&\\
                  2&2&3&\\
                  1&1&1&3
\end{matrix},$ and
$\caH_{\sigma (1,1,2,0)}=(4321)^1 (321)^1 (31)^2 (3)^0=
\begin{matrix}
  4 &  &  &  \\
  3 & 3 &  &  \\
  2 & 2 & 3 & 3 \\
  1 & 1 & 1 & 1
\end{matrix}.$
 With  $s_2=1324$, we have
    $r_{4}=4321,
    r_{s_2,3}=321,
    r_{s_2,2}=31$,
    $r_{s_2,1}=1$, and
$$\caH_{s_2(1,1,2,0)}=(4321)^1 (321)^1 (31)^2 (1)^0=\begin{matrix}
  4 &  &  &  \\
  3 & 3 &  &  \\
  2 & 2 & 3 & 3 \\
  1 & 1 & 1 & 1
\end{matrix}=\caH_{\sigma (1,1,2,0)}.$$


Let $I:=[t]\setminus\{i\}$, with $i\in[t]$, and let
$\sigma_{|I}:={a_1\ldots a_t}_{|I}\in\caS_{I}$. If
$\sigma^{-1}(i)=p$, then letter $a_p=i$ appears only in columns
$r_t\ldots,r_{\sigma,p}$. Hence, when we erase letter $i$ in column
$r_{\sigma,p}$, we obtain column $r_{\sigma, p-1}$, and we have
$${\caH_{\sigma(l_t,\ldots,l_1)}}_{|I}= \caH_{(\sigma_{|I})
(l_t,\ldots,l_{p+1},l_p+l_{p-1},\ldots,l_1)}.$$


  With
 $\sigma=s_4=12354$, we have
    $r_{5}=54321,
    r_{s_4,4}=5321,
    r_{s_4,3}=321$,
    $r_{s_4,2}=21$,
    $r_{s_4,1}=1$ and
$$\caH_{s_4(0,1,1,2,1)}=(54321)^0 (5321)^1 (321)^1 (21)^2 (1)^1=
\begin{matrix}
  5 &  &  &  \\
  3 & 3 &  & & \\
  2 & 2&2&2&\\
  1&1&1&1&1
\end{matrix};$$
and with $I=[5]\setminus\{2\}$,
$$(\caH_{s_4(0,1,1,2,1)})_{|I}=\caH_{({s_4}_{|I})(0,1,1,2+1)}=(5431)^0
(531)^1(31)^1(1)^3=\begin{matrix}
  5 &  &  &&  \\
  3 & 3&&&\\
  1&1&1&1&1
\end{matrix}.$$


\begin{prop}\label{yl3}
Let $\theta^*\in <\theta^*_{1}\ldots \theta^*_{t-1}>$, and let
$\sigma$ be a permutation in ${\caS}_t$ with the same reduced 
decomposition. Then

 $(a)$
    $\theta^*(r_{k})=r_{\sigma,k}$, $1\le k\le t$.

$(b)$ $\theta^*({\caH}_{ (l_t,\ldots,l_1)})=\caH_{\sigma
(l_t,\ldots,l_1)} =$ $(\theta^*(r_{t}))^{l_t}$
$(\theta^*(r_{t-1}))^{l_{t-1}}$ $\cdots
 (\theta^*(r_{1}))^{l_1}.$
\end{prop}
\bdem Follows from  Definition~\ref{tet}.\edem

When there is no danger of confusion, we will drop the
"$(l_t,\ldots,l_1)$" in the notation $\caH_{\sigma
(l_t,\ldots,l_1)}$, to denote a key of $\sigma$.





























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







 A word $w$ over the alphabet $[t]$ is said
to be {\em Yamanouchi}  \cite{loth} if any right factor $v$ of $w$
satisfies $|v|_1\geq|v|_2\geq\cdots\geq|v|_t$.  This is equivalent
to saying that $w\in Sh((r_{t})^{l_t},\cdots,(r_1)^{l_1})$, where 
$(|v|_1,|v|_2,\cdots,|v|_t)=(l_1+\dots+l_t,\ldots,l_{t-1}+l_t,l_t)$.
 Thus, for each  $(l_t,\ldots,l_2,l_1)$, the
key $\caH_{(l_t,\ldots,l_2,l_1)}$
 is a Yamanouchi tableau.
 Clearly, any
shuffle of a Yamanouchi word is still a Yamanouchi word.




\begin{prop}{\em \cite[Lemma~5.4.7]{loth}}\label{y1}
    The set of Yamanouchi words with evaluation $m$
forms a single plactic class, whose representative word is the
tableau $\caH_{(l_t,\ldots,l_2,l_1)}$.
\end{prop}

Thus, the set of words obtained by shuffling the columns of
$\caH_{(l_t,\ldots,l_2,l_1)}$ and the one obtained by applying  a
finite sequence of Knuth transformations on the tableau
$\caH_{(l_t,\ldots,l_2,l_1)}$ are the same.

The dual of a tableau $\caT$ is defined as 
the tableau with same shape and
reverse evaluation, obtained by applying the Sch\"utzenberger involution
to $\caT$. Thus the dual of $\caH$ is $\caH_{op}$. On the other
hand, if $w\equiv \caH$ then $w^*\equiv \caH^*$ $\equiv \caH_{op}$,
where $w^*$ denotes the dual word of $w$. The characterization of
Yamanouchi words given by Proposition~\ref{y1}
leads to the following definition.

\begin{defi}\label{dsy}
    Let $t\geq 1$ and $\sigma\in\caS_t$.
    A word $w$ over the alphabet $[t]$
    is said to be $\sigma$-Yamanouchi  if $w\equiv
    \caH_{\sigma }$. In particular, when $\sigma$ is the identity, $w$ is a Yamanouchi word, and when $\sigma$
    is the reverse permutation,  $w$ is a dual Yamanouchi word.
\end{defi}



Since the operations $\theta_i^*$
    are compatible with the plactic equivalence, we may
 characterize $\sigma$-Yamanouchi words using
the  operations
 $\theta_i^*$ \cite{schu,loth} as well.


\begin{prop}\label{lema1Yama}
    Let $t\geq 1$ and $\sigma\in\caS_t$. Let $w$ be a word over the alphabet $[t]$.
    Then, $w$ is a $\sigma$-Yamanouchi word if and only if
    $\theta_{i_r}^*\cdots\theta_{i_1}^*(w)$
    is a Yamanouchi word, where $s_{i_1}\cdots s_{i_r}$ is a reduced decomposition of
    $\sigma$.% in the alphabet $\{s_1,\ldots,s_{t-1}\}$.
\end{prop}
\bdem We have
    $w\equiv \caH_{\sigma}$ if and only if
    $\theta^*(w)\equiv\theta^*(\caH_{\sigma})=\caH$, where
    $\theta^*=\theta_{i_r}^*\cdots\theta_{i_1}^*$.
\edem

As in the case of Yamanouchi words, we find that a shuffle of
$\sigma$-Yamanouchi words is still a $\sigma$-Yamanouchi word.

\begin{prop}\label{prop2sy1}
    Let  $\sigma\in \caS_t$.
    If $w$ and $w'$ are $\sigma$-Yamanouchi words over the alphabet $[t]$,
     then any word in $Sh(w,w')$ is also
    a $\sigma$-Yamanouchi word.
\end{prop}
\bdem
    Let $u\in Sh(w,w')$, and assume that
    $w\equiv\caH(\sigma,(l_t,\ldots,l_1))$ and
    $w'\equiv\caH(\sigma,(l'_t,\break\ldots,l'_1))$.
    By Greene's theorem \cite{greene},
we find that the conjugate shape of $P(u)$ is
    $(t^{l_t+l'_t},\ldots,1^{l_1+l'_1})$, that is,
    $P(u)=\caH(\sigma,(l_t+l'_t,\ldots,l_1+l'_1))$.
 \edem

By induction, we may easily extend Proposition~\ref{prop2sy1} to a
shuffle of $k$ $\sigma$-Yamanouchi words, for every
$k\in\mathbb{N}$.

\begin{cor}
Let $i\in\{1,\ldots,t-1\}$, $w=sh((r_t))^{l_t},$ $\ldots,$
$(r_1)^{l_1})$ and let $\widetilde{\theta}_i(w)=$ $sh(
(\theta^*_i(r_t))^{l_t},$ $\ldots,$ $ (\theta^*_i(r_1))^{l_1})$.
Then $\widetilde{\theta}_i(w)$ is a $s_i$-Yamanouchi word.
\end{cor}


\begin{prop} {\em \cite{keys, loth}} If $B$ is an interval of $A$, then
$$w\equiv w'\quad \text {implies}\quad  w_{|B}\equiv w'_{|B}.$$
\end{prop}




\begin{cor}\label{sl1}
    Let $w$ be a word over the alphabet $A$, and let $A'=A\setminus\{f\}$. Then, $P(w_{|A'})=P(w)_{|A'}$.
\end{cor}
\bdem From the previous proposition, we have $w_{|A'}\equiv
P(w)_{|A'}$.
     Thus $P(w_{|A'})$ is obtained from
    $P(w)$ by removing the letters $f$.
\edem



If $w$ is a $\sigma$-Yamanouchi word  then the word
$w_{|\{i,i+1\}}\equiv {\caH_{\sigma}}_{|\{i,i+1\}}$ and, thus,
$w_{|\{i,i+1\}}$ is either a Yamanouchi or dual Yamanouchi word for
$1\le i\le t-1$. (Consider a shift of the alphabet $\{1,2\}$.)
Moreover,  if $w$ has evaluation $(m_1,\ldots,m_t)$, then
$w=sh(u,t^{m_t})$ with $u\equiv{\caH_{\sigma
(l_t,\ldots,l_2,l_1)}}_{|[t-1]}$ and $w_{|\{t-1,t\}}$ a Yamanouchi
or dual Yamanouchi word.

The word $3121\equiv 321\, 1$ is a $s_1$-Yamanouchi word and $434$ a
dual Yamanouchi word. Nevertheless, considering the words in $\{w\in
Sh(3121,44):w_{|\{3,4\}}=434\}=$ $\{
 {\underline 4}3{\underline
 4}121\equiv 4321\, 41, {\underline 4}31{\underline 4}21\equiv 4321\, 41,
 {\underline 4}312{\underline
 4}1\equiv 4321\, 1\, 4,
 {\underline 4}3121{\underline 4} \equiv 4321\, 1\, 4\}$ we find that ${\underline 4}312{\underline
 4}1$,
 ${\underline 4}3121{\underline 4} $ are not
 $\sigma$-Yamanouchi words, for any $\sigma\in \{4213;2413;2143;\break2134\}\subseteq \caS_4$.

 This leads to the following question: {\em given
$I=[t]\setminus\{i\}$, with $i\in[t]$, and $u\in I^*$
 congruent to the key of evaluation $(m_1,\ldots,m_{i-1},m_{i+1},\ldots,m_t)$, under
which conditions can
 $u$ be embedded in  a word  congruent to the key
 of evaluation $(m_1,\ldots,m_{t})$?}

 The answer is given by the following proposition.

\begin{prop}\label{sh02}
    Let $w\in[t]^*$ and $\sigma \in \caS_t$.
Given $i\in[t]$, let $I=[t]\setminus\{i\}$, and
    suppose $w_{|{I}}\equiv {\caH_{\sigma}}_{|I}$. Then, $w$ is a
    $\sigma$-Yamanouchi word if and only if $w_{|{\{j,j+1\}}}$ is either a Yamanouchi or a dual
Yamanouchi word, for $j=i-1,i$, and
${\theta^*_j(w)}_{|{[j]}}\equiv{\caH_{s_j\sigma}}_{|[j]}$, for
$j=i-1,\ldots,t-1$.
\end{prop}
\bdem The conditions are clearly necessary. Suppose now that
$w_{|_{\{j,j+1\}}}$ is either a Yamanouchi or a dual Yamanouchi
word, for $j=i-1,i$, and
${\theta^*_j(w)}_{|{[j]}}\equiv{\caH_{s_j\sigma}}_{|[j]}$, for
$j=i-1,\ldots,t-1$.

We start with the case $i=t$, and thus, $I=[t-1]$. Consider
$(m_1,\ldots,m_t)$, the evaluation of $w$, and assume without loss of
generality that $m_{t-1}\ge m_t$. From the equality
$P(w_{|_{[t-1]}})=P(w)_{|[t-1]}={\caH_{\sigma}}_{|[t-1]}$, we find
that the letters $t-1$ of $w$ are in the first $m_{t-1}$
columns of $P(w)$.



Since $w_{|{\{t-1,t\}}}\equiv P(w)_{|\{t-1,t\}}$ is a Yamanouchi
word, the $m_t$ letters $t$ of $w$ are displayed in the first
$m_{t-1}$ columns of $P(w)$. On the other hand, the tableau
$P(\theta^*_{t-1}(w)_{|{[t-1]}})$ is obtained by erasing the
$m_{t-1}$ letters $t$ in the first $m_{t-1}$ columns of the tableau
$P(\theta^*_{t-1}(w))=\theta^*_{t-1}(P(w))$. So if the letters $t$
in tableau $P(w)$ are not in the first $m_t$ columns, the letters
$t-1$ are not in the first $m_t$ columns of
$P(\theta^*_{t-1}(w)_{|{[t-1]}})={\caH_{s_{t-1}\sigma}}_{|[t-1]}$.
This is absurd.


Assume now that $i\neq t$. Then,
$w_{|{[i-1]}}\equiv{\caH_{\sigma}}_{|[i-1]}$, and since
$w_{|{\{i-1,i\}}}$ is either a Yamanouchi or a dual Yamanouchi
word, and
${\theta^*_{i-1}(w)}_{|{[i-1]}}\equiv{\caH_{s_{i-1}\sigma}}_{|[i-1]}$,
by the case $i=t$ we find that
$$w_{|{[i]}}\equiv{\caH_{\sigma}}_{|[i]}.$$
Next, note that $w_{|{\{i,i+1\}}}$ is either a Yamanouchi or a
dual Yamanouchi word, and that
${\theta^*_{i}(w)}_{|{[i]}}\equiv{\caH_{s_i\sigma}}_{|[i]}$. Thus,
again by the case $i=t$, we must have
$$w_{|{[i+1]}}\equiv{\caH_{\sigma}}_{|[i+1]}.$$
Noticing that, since $w_{|{I}}\equiv {\caH_{\sigma}}_{|I}$, the
word $w_{|{\{j,j+1\}}}$ is either Yamanouchi or dual Yamanouchi,
for $j=i+1,\ldots,t-1$, we may repeat the process described above
for $j=i+1,\ldots,t-1$, obtaining
$w_{|{[t]}}\equiv{\caH_{\sigma}}_{|[t]}$. \edem


For instance, in the alphabet $[5]$, let $I:=[5]\setminus\{3\}$,
$\sigma=51324\in\caS_5$, and consider the key
$\caH_{\sigma(1,0,2,0,1)}=54321\:531\:531\:5$, associated with
$\sigma$ and $(1,0,2,0,1)$, and the word
$w_{|I}:=555415211\equiv{\caH_{\sigma(1,0,2,0,1)}}_{|I}$. Define
$w=553541352131$. Since $w_{|\{2,3\}}=3323$ is dual Yamanouchi,
$w_{|\{3,4\}}=3433$ is Yamanouchi,
${\theta_2^*(w)}_{|[2]}=212121\equiv{\caH_{s_2\sigma}}_{|[2]}$,
${\theta_3^*(w)}_{|[3]}=13211\equiv{\caH_{s_3\sigma}}_{|[3]}$, and
${\theta_4^*(w)}_{|[4]}=44341342131\equiv{\caH_{s_4\sigma}}_{|[4]}$,
by the previous theorem the word $w$ is $\sigma$-Yamanouchi, and has
$w_{|I}$ as a subword. Consider now the word $w'=533554135211$,
which also has $w_{|I}$ as a subword. Although $w'_{|\{2,3\}}=3332$
is dual Yamanouchi, $w'_{|\{3,4\}}=3343$ is Yamanouchi,
 ${\theta_2^*(w)}_{|[2]}=221211\equiv{\caH_{s_2\sigma}}_{|[2]}$, and
${\theta_3^*(w)}_{|[3]}=13211\equiv{\caH_{s_3\sigma}}_{|[3]}$,
 $w'$ is not a $\sigma$-Yamanouchi word since
$\theta_4^*(w')_{|[4]}=43344134211$ is not in the plactic class of
${\caH_{s_4\sigma}}_{|[4]}$.
%------------------------------------------------------------------


 Given the word $w=w_1w_2\cdots w_k\in A^*$ and
$P=\{i_1,\ldots,i_l\}\subseteq[k]$, we define the restriction of $w$
to the set $P$ by $w|P:=w_{i_1}\cdots w_{i_l}$. If $w,w'\in A^*$
have lengths $k$ and $k'$, respectively, and $P\subseteq[k+k']$ has
cardinality $k$, we denote by $sh_P(w,w')$ the shuffle of $w$ and
$w'$ satisfying $sh_P(w,w')|P=w$ \cite{shuf}. For instance, with
$P=\{1,4\}$, we have $sh_P(81,321)=83211$. Clearly, different sets
$P$ and $Q$ may give the same word $sh_P(w,w')=sh_Q(w,w')$. In the
example above, we also have $sh_P(81,321)=sh_Q(81,321)$, with
$Q=\{1,5\}$.

%------------------------------------------------------------------
\begin{cor} Let $w=sh_P(t^r,u)\equiv {\mathcal H}_{\sigma}$ with $u\in
[t-1]^*$. If $w'=sh_Q(t^r,u)$ with $Q\le P$, then $w'\equiv{\mathcal
H}_{\sigma}$.
\end{cor}
\bdem By induction on $t$. If $t=1,2$, the claim is obvious. Let $t\geq 3$
    and write
    \begin{align}
    \theta^*_{t-1}(w)_{|{[t-1]}}&=sh_{\widetilde{P}}((t-1)^r,w_{|{[t-2]}})\equiv
    {\caH_{s_{t-1}\sigma}}_{|{[t-1]}},\nonumber\\
    \theta^*_{t-1}(w')_{|{[t-1]}}&=sh_{\widetilde{Q}}((t-1)^r,w_{|{[t-2]}}).\nonumber\
    \end{align}
     Clearly, we must have $\widetilde{Q}\leq \widetilde{P}$.
    Then,
    by induction, it follows that $\theta^*_{t-1}(w')_{|{[t-1]}}\equiv
    {\caH_{s_{t-1}\sigma}}_{|{[t-1]}}$, and by the previous
    proposition, we find that $w'\equiv \caH_{\sigma}$.
\edem

An  operation $\theta_i$ may not  act on the set $\{\caH_{\sigma
}:\sigma\in {\caS}_t\}$. For example,
 consider ${\caH}=4321\,21$, and
$\theta_2({\caH})=\theta_2(4321\,21)=433121\notin \{\caH_{\sigma
}:\sigma\in {\caS}_t\}$. Although $433121\equiv
4321\,31=\caH_{s_2}$, we may have even worse $w=314321\equiv
\caH_{s_2s_1}$ and $\theta_2(w)=314221\equiv 321\:41\:2\notin
\{\caH_{\sigma }:\sigma\in {\caS}_t\}$. Nevertheless, it is possible
to give a criterion on $\theta_i$ such that if
$w\equiv\caH_{\sigma}$ then $\theta_i(w)\equiv\caH_{s_i\sigma}$.


The criterion given by the previous proposition can be generalized to
the operations $\theta_i$.


\begin{lemma} Let $w\in [t]^*$ and
$w_{|\{t-1,t\}}$ a Yamanouchi or dual Yamanouchi word. Let
$u=\theta_{t-1}(w)$, $z=\theta^*_{t-1}(w)$ and $v=w_{|[t-2]}$.
Then
$$
w_{|[t-1]}=sh_P(u_{|\{t-1\}},v)\;\;\mbox{and}\;\;
w_{|[t-1]}=sh_Q(z_{|\{t-1\}},v), \;\;\mbox{with}\;\; Q\le P.$$

\end{lemma}
\bdem It is enough to consider the cases
$w_{|{\{t-1,t\}}}=t\:t-1\:t-1$ and $w_{|{\{t-1,t\}}}=t\:t\:t-1$.
Therefore, if $\theta_{t-1}\neq \theta^*_{t-1}$, we have
\begin{align}
    \theta_{t-1}(t\:t-1\:t-1)&=t\:t\:\underline{t-1},\nonumber\\
    \theta^*_{t-1}(t\:t-1\:t-1)&=t\:\underline{t-1}\:t,\nonumber\
\end{align}
and
\begin{align}
    \theta_{t-1}(t\:t\:t-1)&=t\:\underline{t-1}\:\underline{t-1},\nonumber\\
    \theta^*_{t-1}(t\:t\:t-1)&=\underline{t-1}\:t\:\underline{t-1}.\nonumber\
\end{align}\edem

\begin{teor}\label{theta0}
    Let $w\in[t]^*$ and $\sigma \in \caS_t$.
Given $i\in[t]$, let $I=[t]\setminus\{i\}$, and
    suppose that $w_{|{I}}\equiv {\caH_{\sigma}}_{|I}$. Then, $w$ is a
    $\sigma$-Yamanouchi word if and only if $w_{|{\{j,j+1\}}}$ is either a Yamanouchi or a dual
Yamanouchi word, for $j=i-1,i$, and
${\theta_j(w)}_{|{[j]}}\equiv{\caH_{s_j\sigma}}_{|[j]}$, for some
operation $\theta_j$, $j=i-1,\ldots,t-1$.
\end{teor}
\bdem According to the previous lemma and corollary, if
${\theta_{j}(w)}_{|{[j]}}\equiv{\caH_{s_{j}\sigma}}_{|[j]}$, then
${\theta^*_{j}(w)}_{|{[j]}}\equiv{\caH_{s_{j}\sigma}}_{|[j]}$, for
$j=i-1,\ldots,t-1$. By the previous proposition, it follows that
$w\equiv{\caH_{\sigma}}$.\edem




\begin{cor} \label{theta} Let $w\in[t]^*$, $t\geq 2$, and $\sigma\in\caS_t$. If $w\equiv
    \caH_{\sigma}$, then $\theta_i(w)\equiv\caH_{s_i\sigma}$ if
    and only if $(\theta_iw)_{|{\{i+1,i+2\}}}$ is either a Yamanouchi or a dual
Yamanouchi word,  $\theta_i(w)_{|{[i]}}\equiv
{\caH_{s_i\sigma}}_{|[i]}$, and
$\theta_j({\theta_i(w)})_{|{[j]}}\equiv{\caH_{s_js_i\sigma}}_{|[j]}$,
for some operation $\theta_j$, $j=i+1,\ldots,t-1$.
\end{cor}

\bdem Taking $\theta_j=\theta^*_j$, $j=i+1,\ldots,t-1$, we find
that the conditions are clearly necessary. Assume now that
$w_{|{\{i+1,i+2\}}}$ is either a Yamanouchi or a dual Yamanouchi
word, $\theta_i(w)_{|{[i]}}\equiv {\caH_{s_i\sigma}}_{|[i]}$, and
$\theta_j({\theta_i(w)})_{|{[j]}}\equiv{\caH_{s_js_i\sigma}}_{|[j]}$,
for $j=i+1,\ldots,t-1$.

Since $\theta_i(w)_{|{[i]}}\equiv {\caH_{s_i\sigma}}_{|[i]}$,
$\theta_iw_{|{\{i,i+1\}}}$ is either a Yamanouchi or a dual
Yamanouchi word, and
$\theta_i(\theta_i(w)_{|{[i]}})=w_{|{[i]}}\equiv
{\caH_{\sigma}}_{|[i]}$, by the previous theorem we must have
$$\theta_i(w)_{|{[i+1]}}\equiv {\caH_{s_i\sigma}}_{|[i+1]}.$$
Now, since $(\theta_iw)_{|{\{i+1,i+2\}}}$ is either a Yamanouchi
or a dual Yamanouchi word, and there is an operation
$\theta_{i+1}$ such that
$\theta_{i+1}({\theta_i(w)})_{|{[i+1]}}\equiv{\caH_{s_{i+1}s_i\sigma}}_{|[i+1]}$,
again by the previous theorem, we find that
$$\theta_i(w)_{|{[i+2]}}\equiv {\caH_{s_i\sigma}}_{|[i+2]}.$$
Finally, note that, since
$\theta_i(w)_{|{\{j,j+1\}}}=w_{|{\{j,j+1\}}}$, the word
$\theta_i(w)_{|{\{j,j+1\}}}$ is either a Yamanouchi or a dual
Yamanouchi word, for $j=i+2,\ldots,t-1$. Therefore, repeating the
process above for $j=i+2,\ldots,t-1$, we obtain
$\theta_i(w)_{|{[t]}}\equiv {\caH_{s_i\sigma}}_{|[t]}$. \edem


\begin{nota}
In particular, it follows from the previous theorem and  the corresponding statement for dual words, that
$\theta_1(w)\equiv {\caH_{s_{1}\sigma}}$ if and only if $\theta_1(w)_{|[2,t]}\equiv
{\caH_{s_{1}\sigma}}_{|[2,t]}$.
\end{nota}

\medskip

 Consider $w=43143213321$  a
$\sigma$-Yamanouchi word, where $\sigma=3124$, and the keys
$\caH_{\sigma(2,0,1,1)}=4321\,4321\,31\,3$ and
$\caH_{s_2\sigma(2,0,1,1)}=4321\,4321\,21\,2$. We have
$\theta_2^*(w)=42143212321$ $\equiv $ $\caH_{s_2\sigma}$, but
$\theta_2(w)=43142213221$ is not a $s_2\sigma$-Yamanouchi word. Note
that although $\theta_2(w)_{|\{3,4\}}=4343$ is Yamanouchi,
$\theta_2(w)_{|[2]}=1221221$ is not in the plactic class of
${\caH_{s_2\sigma}}_{|[2]}$. The word $\theta_2'(w)=42143213221$ is
a $s_2\sigma$-Yamanouchi word, since $\theta_2'(w)_{|\{3,4\}}=4433$
is Yamanouchi,
$\theta_2'(w)_{|[2]}=2121221\equiv{\caH_{s_2\sigma}}_{|[2]}$, and
$\theta_3^*(\theta_2'(w))_{|[3]}=\theta_2'(w)_{|[3]}=213213221\equiv{\caH_{s_3s_2\sigma}}_{|[3]}$.






\section{$\sigma$-Yamanouchi words as shuffles of columns of  a key}

 It has
been shown in \cite{am1} that, when $t\leq 3$,  a word in $[t]^*$ of
evaluation $m$ is  $\sigma$-Yamanouchi  if and only if it is a shuffle of the
columns of $\caH_{\sigma(l_t,\ldots,l_1)}$. For $t\ge 4$ this is no
longer true in general. For example, consider the Yamanouchi
tableau $4321\,21$ and $421321=sh(4321,21)$. We have
$\theta^*_3\theta^*_2(421321)=\theta_3^*(431321)=431421\equiv
sh(4321,41)$, but $431421$ is not a shuffle of the columns of
$s_3s_2$-Yamanouchi tableau $4321\,41$. We have already seen that
shuffling together  the columns of $\caH_{\sigma}$ has the same
effect as performing Knuth transformations on the tableau
$\caH_{\sigma}$. The reciprocal is not true in general. In what
follows, we identify the keys for which Knuth transformations on the
key tableau   and shuffling together its columns lead to the same
words.

 Let $w$ be a word obtained by
applying an elementary Knuth transformation to $sh(u_1,$ $
\ldots,u_k)$, $k\geq 2$, where $u_1,\ldots,u_k$ are  columns
pairwise comparable in the inclusion order.
 From Propositions~\ref{k} and \ref{s2} and the discussion therein, we may assume
that $w$ is obtained by applying an
elementary Knuth transformation to a shuffle of two of these columns, 
$u$ and $v$ say, where the transformation involves three distinct letters
$x<y<z$, with
$zx$ a factor of $v$ and $y$ a letter of $u$. Since the letter $y$
is in $u$, but not in $v$, and $u$ and $v$ are comparable in the
inclusion order, we have $\{v\}\subseteq \{u\}$.




\begin{lemma}\label{shz}
    Let $u_1,u_2$ be columns in $A^*$, and $x,z\in A$ such
    that $zu_1u_2x$ is a column. Then,

    {\em(i)} $sh(u_2,u_1u_2x)\in
    Sh(u_2x,u_1u_2)$.

    {\em(ii)} $sh(u_1,zu_1u_2)\in
    Sh(zu_1,u_1u_2)$.
\end{lemma}
\bdem (i) Write $u_2=a_1\cdots a_r$, and
$sh(u_2,u_1u_2x)=c_1\cdots c_l$. For each $j=1,\ldots,r$, let
 $p_j:=\min \{i:c_i=a_j\},$
 and let $p'\in[l]$ such that $c_{p'}=z$. Then, it is clear that
 $$sh(u_2,u_1u_2x)=sh_P(u_2x,u_1u_2),$$
 where $P:=\{p_1,\ldots,p_r,p'\}$.

(ii) Write $u_1=a_1\cdots a_r$, and $sh(u_1,zu_1u_2)=c_1\cdots
c_l$. For each $j=1,\ldots,r$, let
 $p_j:=\max \{i:c_i=a_j\},$
 and let $p'\in[l]$ such that $c_{p'}=x$. Then, we have
 $$sh(u_1,zu_1u_2)=sh_P(zu_1,u_1u_2),$$
 where $P:=\{p_1,\ldots,p_r,p'\}$.
 \edem




\begin{lemma}\label{sh1}
    Let $u$ and $v$ be columns in $A^*$ with
    $u=u_1u_2zyxu_3u_4$ and $v=u_2zxu_3$, where $x,y,z$ are
    letters. Then, $Sh(u,v)$ is closed under Knuth transformations,
    that is,
     $Sh(u,v)$ is the Knuth class of the two-column key $u\,v$.
\end{lemma}

\bdem As before, the only cases to consider are the application of
the elementary Knuth transformations $zxy\equiv xzy$ and
$yzx\equiv yxz$, respectively, to
$sh(u,v)=w_1\:\underline{z}\:\underline{x}\:\overline{y}\:w_2$ and
$sh(u,v)=w_1\:\overline{y}\:\underline{z}\:\underline{x}\:w_2$,
where  $y$ is a letter of $u$,  $zx$ a factor of $v$,
$w_1=sh(u_2,u_1u_2z)$ and $w_2=sh(xu_3u_4,u_3)$.


In the case of the elementary Knuth transformation $zxy\equiv
xzy$, we have
\begin{equation}\label{shz1}
sh(u,v)=w_1\underline{z}\:\underline{x}\:\overline{y}w_2\equiv
w_1\underline{x}\:\underline{z}\:\overline{y}w_2,
\end{equation}
where $w_1=sh(u_2,u_1u_2z)$, $w_2=sh(xu_3u_4,u_3)$. By 
Lemma~\ref{shz} (i), we must have $w_1=sh_P(u_2z,u_1u_2)$, for some
set $P$. Thus, we have for the right-hand side of (\ref{shz1}) that
$$w_1xzyw_2=sh(u_2z\underline{x}u_3,u_1u_2\underline{z}\:\overline{y}\:xu_3u_4)\in
Sh(u,v).$$

The case of the elementary Knuth transformation $yzx\equiv yxz$ is
analogous to the previous one.
 \edem



As an illustration of the lemma above, consider, in the alphabet
$[6]$, the columns $u=654321$ and $v=542$, and let
$sh(u,v)=\underline{5}\:6\:5\:4\:\underline{4}\:\underline{2}\:3\:2\:1$,
where the underlined letters define the word $v$, and the remaining
letters define $u$. Applying the Knuth transformation $423\equiv
243$, to $sh(u,v)$, we get the word
$\underline{5}\:6\:5\:\underline{4}\:\underline{2}\:4\:3\:2\:1$,
which is also a shuffle of $u$ and $v$.

Next, we identify keys for which Knuth transformations on the key
tableau are equivalent to shuffling together its columns.
 First, however, we need the
following definition.

 \begin{defi} Let $w\in A^*$ be a column. We say that $w$ has a {\em gap} of size $q\ge
 0$,
 with respect to the alphabet $A$, if
 there exists a factor $j+k\,j$, $k\ge 1$, of $w$ such that $|[j+1,j+k-1]\cap
 A|=q$.
\end{defi}

For instance, the column $41$ has a gap of size $2$ with respect to
the alphabet $[5]$, but has only a gap of size $1$ with respect to
the alphabet $\{1,2,4,5\}$. The column $531$ has two gaps of size 1
with respect to the alphabet $[6]$, but has no gap if we consider
the alphabet to be $\{1,3,5,6\}$. In this case, $531$ is an interval
of  the ordered alphabet $\{1,3,5,6\}$.

\begin{teor}\label{prop1sy}
    Let $\caH$ be a key with first column $A$. Then, the Knuth class
    of $\caH$ is equal to the set of all shuffles of its columns if and
    only if each of its column is either an interval of $A$ or is obtained from an interval of $A$ by removing a single
    letter.
\end{teor}
\bdem The {\em only if} part. Assume that each column of $\caH$  is
either an interval of $A$ or is obtained from an interval of $A$ by
removing a single
    letter, and
let
    $w\equiv \caH$.  We may assume, without loss of
generality, that $w$ is obtained by performing a single elementary
Knuth transformation $xzy\equiv zxy$, or $yzx\equiv yxz$, with
$x<y<z$, on a shuffle of two columns of $\caH$, say $u$ and $v$,
such that $zx$ is a factor of $v$ and $y$ is a letter of $u$. Since
$\{v\}\subseteq \{u\}$, we must have $u=u_1u_2zyxu_3u_4$, and
$v=u_2zxu_3$, for some columns $u_i$, $i=1,2,3,4$.
 Since, by Lemma~\ref{sh1}, the set $Sh(u,v)$ is closed under Knuth transformations,  we find that $w$
is still a shuffle of the columns of $\caH$.

The {\em if part}. Suppose that the key $\caH=Av_2\cdots v_k$ is such
that the column $v_i$ has (i) a gap of size at least two or (ii)
two or more gaps, both with respect to the ambient alphabet $A$, for
some $2\leq i\leq k$. Without loss of generality, we may assume that
in these cases, $v_i$ has one of the following forms:

(i) $v_i=u_2dau_3$, where  $u_2=s(s-1)\cdots d+1$,
$u_3=(a-1)\cdots (r+1)r$,  with $s,r,d,a\in[t]$ such that $d-a=3$;

(ii) $v_i=u_2fdu_3cau_4$, where $u_2=s(s-1)\cdots (f+1)$,
$u_3=(d-1)\cdots(c+1)$, and  $u_4=(a-1)\cdots (r+1)r$, with
$f-d,c-a=2$.


Let $w_1=v_2\cdots v_{i-1}v_{i+1}\cdots v_k$. In case (i), write
$A=u_1u_2dcbau_3u_4$ and consider the word
\begin{equation}\label{eqs1}
  \caH\equiv w_1\underline{u}_2\:u_1\:u_2\:
   d\:
   c\:(\underline{d}\:\underline{a}\:b)\:a\:u_3\:u_4\:\underline{u}_3,
\end{equation}
where the underlined letters define column $v_i$ and the remaining
define column $A$. Applying the transformation $dab\equiv adb$ on
(\ref{eqs1}), we get
\begin{equation}\label{eqs2}
 (\ref{eqs1})\equiv w_1\overline{u}_2\:u_1\:u_2\:
   d\:
   c\:(\overline{a}\:\overline{d}\:b)\:a\:u_3\:u_4\:\overline{u}_3.
 \end{equation}
Clearly, the right-hand side of (\ref{eqs2}) is in the plactic class of
$\caH$, but is not a shuffle of its columns.







In case (ii), write $A=u_1u_2fedu_3cbau_4u_5$, and consider the
following word
\begin{equation}\label{eqs3}
   \caH\equiv w_1u_1\:u_2\:f\:e\:d\:u_3\:c\:\underline{u}_2\:\underline{f}\:
    \underline{d}\:\underline{u}_3(\underline{c}\:\underline{a}\:b)\:\underline{u}_4\:a\:u_4\:u_5,
\end{equation}
where the underlined letters define column $v_i$. Applying the
transformation $cab\equiv acb$ on (\ref{eqs3}), we get
\begin{equation}\label{eqs4}
    (\ref{eqs3})\equiv w_1u_1\:u_2\:f\:e\:d\:u_3\:c\:\overline{u}_2\:\overline{f}\:
    \overline{d}\:\overline{u}_3(\overline{a}\:\overline{c}\:b)\:\overline{u}_4\:a\:u_4\:u_5.
\end{equation}
    As in case (i), it is clear that the right-hand side of (\ref{eqs4}) is in the plactic classe of $\caH$, but is not
    a shuffle of its columns.
 \edem









\begin{cor}\cite{am1}
    If $\sigma=id$ or the reverse permutation $t\:t-1\cdots 2\:1$, a word over the alphabet $[t]$ is a
    $\sigma$-Yamanouchi word if and only if it is a shuffle of the
    columns of $\caH_{\sigma}$.
\end{cor}



\begin{cor}
$(a)$  If $\caH$ is a key over a three-letter alphabet, then the
Knuth class of $\caH$ equals the set of shuffles of its columns.

 $(b)$ \cite{am1} If $\sigma\in\caS_t$, $t=2,3$, a word over the alphabet $[t]$ is a
    $\sigma$-Yamanouchi word if and only if it is a shuffle of the
    columns of $\caH_{\sigma}$.
\end{cor}

As keys are characterized by their evaluation, we may consider the
planar representation of the evaluation 
to check whether the condition  of the previous
theorem is satisfied. Let $\caH$ be a key of evaluation
$(m_1,\ldots,m_t)$ and consider the planar representation obtained
by drawing $m_i$ bullets in row $i$, for  $i=1,\ldots,t$. After
deleting empty rows we are in the ambient alphabet of the first
column of $\caH$ and the condition stated in Theorem~\ref{prop1sy}
says that the plactic class of $\caH$ is the set of all shuffles of
its columns if and only if each column has, at most, a single gap of
size 1 with respect to the ambient alphabet given by the first
column. For instance, the planar representation of the evaluation
$(4,0,1,2,6,3,5)$ of the key $\caH(\sigma,(0,1,\ldots,1))$, with
$\sigma=5716432\in\caS_6$, is
$$\begin{tabular}{c|cccccc}
7&$\bullet$&$\bullet$&$\bullet$&$\bullet$&$\bullet$&\\
6&$\bullet$&$\bullet$&$\bullet$&&&\\
5&$\bullet$&$\bullet$&$\bullet$&$\bullet$&$\bullet$&$\bullet$\\
4&$\bullet$&$\bullet$&&&&\\
3&$\bullet$&&&&&\\
1&$\bullet$&$\bullet$&$\bullet$&$\bullet$&&\\
\hline &2&3&4&5&6&7\\
\end{tabular}.$$
The conjugate shape of $\caH(\sigma,(0,1,\ldots,1))$ is
$(7^0,6,5,4,3,2,1)$, the number of bullets in each column of the
planar representation of the evaluation. The third column of this
representation has a gap of size 2, and the fourth column has two
gaps with respect to the first column. Thus, the plactic class of
$\caH_{\sigma,(0,1,\ldots,1)}$ is not the set of all shuffles of its
columns. On the other hand, the plactic class of
$\caH_{\sigma,(0,1,1,0,0,1,1)}$ is the shuffle of its columns, since
the columns of the planar representation of the evaluation
$(2,0,1,2,4,2,3)$,
$$\begin{tabular}{c|cccc}
7&$\bullet$&$\bullet$&$\bullet$&\\
6&$\bullet$&$\bullet$&&\\
5&$\bullet$&$\bullet$&$\bullet$&$\bullet$\\
4&$\bullet$&$\bullet$&&\\
3&$\bullet$&&&\\
1&$\bullet$&$\bullet$&&\\
\hline &2&3&6&7\\
\end{tabular}$$
has, at most, one gap of size 1. Each column is either an interval of
$A=\{1,3,4,5,6,7\}$ or is obtained from an interval of $A$ by removing
one letter.

 As we have seen in the example above, in $\caS_t$, $t>3$,
 there are permutations for which the associated keys do not satisfy
the conditions of Theorem~\ref{prop1sy}. For $s_3s_2=1423\in\caS_4$
we have $\caH_{s_3s_2}=(4321)^{l_4}(421)^{l_3}(41)^{l_2}1^{l_1}$ and
column $41$ has a gap of length $2$ with respect to the column
$4321$.
 The word $w=431421$ is a $s_3s_2$-Yamanouchi word
and is not a shuffle of the columns of the tableau
$\caH_{s_3s_2}=4321\,41$. It is easy to check that in $\caS_4$, the
only permutations for which there are associated keys that fail to
satisfy the conditions of Theorem~\ref{prop1sy} are $1423$, $1432$,
$4123$ and $4132$.



\begin{cor}\label{c1} $(a)$  Let $\caH$ be a key with first column $A=\{a,b,c,d\}$.
Then the plactic class of $\caH$ is the shuffle of its columns if and
only if
$\caH$ does not contain the column $d\,a$.

$(b)$ Let $\sigma\in\caS_4$, and let $(l_4,l_3,l_2,l_1) $ be a sequence of
nonnegative  integers with $l_4,l_2>0$. The plactic
 class of $\caH_{\sigma (l_4,l_3,l_2,l_1) }$ is
$Sh((r_{ 4})^{l_4},$ $(r_{\sigma, 3})^{l_3},$
$(r_{\sigma,2})^{l_2},(r_{\sigma,1})^{l_1})$ if and only if $\sigma$
is  in $\caS_4\setminus\{1423,$ $1432,$ $4123,4132\}$.
\end{cor}

In the Appendix, the permutations of $\caS_5$ and $\caS_6$, such that
the set $Sh((r_t)^{l_t},$ $ (r_{\sigma,t-1})^{l_{t-1}},$ $
\ldots,(r_{\sigma,2})^{l_2},$ $ (r_{\sigma,1})^{l_1})$, with
$l_i>0$, $i=1,\ldots,t$, $t=5,6$, is not the whole plactic  class
of $\caH_{\sigma}$, are listed.

 For $t>3$ the columns of
$\caH_{\sigma}$ are not enough to characterize the
$\sigma$-Yamanouchi words in terms of shuffling them together. In
the case of $\caS_4$, the next theorem shows that it is necessary and
sufficient to include  the word $431421$ in the set of 
distinct columns
of $\caH_{\sigma (l_4,\ldots,l_1)}$, $l_4,l_2>0$, to characterize by
shuffle operations the $\sigma$-Yamanouchi words over the alphabet
$[4]$, for any $\sigma\in\{1423,$ $1432,$ $4123,4132\}$.


\begin{teor}
    Let $\sigma\in\caS_4$, and let $(l_4,\ldots,l_1)$ be a sequence of nonnegative integers with $l_4>0$. Then,
    the plactic
     class of $\caH_{\sigma (l_4,\ldots,l_1)}$ is

  \begin{equation}
  Sh((r_4)^{l_4},(r_{\sigma,3})^{l_3},(r_{\sigma,2})^{l_2},
  (r_{\sigma,1})^{l_1}),\:\:\mbox{ if} \:\:\:l_2=0\:\:\mbox{or}\:\:
    \sigma\in\caS_4\setminus\{1423,1432,4123,4132\},\end{equation}
     and, otherwise,
\begin{equation}
Sh((r_4)^{l_4},(r_{\sigma,3})^{l_3},(r_{\sigma,2})^{l_2},
    (r_{\sigma,1})^{l_1})\cup
    Sh((431421)^{n_5},(r_4)^{n_4},(r_{\sigma,3})^{n_3},(r_{\sigma,2})^{n_2},
    (r_{\sigma,1})^{n_1}),
    \end{equation}
      where
    $\sum_{j=1}^4l_j|r_{\sigma,j}|_i=n_5|431421|_i+\sum_{j=1}^4n_j|r_{\sigma,j}|_i$,
    for $i=1,$ $2,$ $3,4$.
\end{teor}
\bdem Assume $l_2>0$, otherwise the  conditions of 
Theorem~\ref{prop1sy} hold. When
$\sigma\in\caS_4\setminus\{1423,1432,4123,4132\}$, we have already
proved in Corollary~\ref{c1} that the plactic class of $\caH_{\sigma
(l_4,\ldots,l_1)}$ is the set
$$Sh(\caH_{\sigma(l_4,\ldots,l_1)})=
Sh((r_4)^{l_4},(r_{\sigma,3})^{l_3},(r_{\sigma,2})^{l_2},(r_{\sigma,1})^{l_1}).$$

Assume now that $\sigma\in \{1423,1432,4123,4132\}$, noticing that
 $r_{\sigma,2}=41$.
As discussed before, the only case to consider, when analyzing the
effect of a single Knuth transformation on a shuffle of the columns
of $\caH_{\sigma (l_t,\ldots,l_1)}$, is when the Knuth
transformation $zxy\equiv xzy$ or $yzx\equiv yxz$ involves three
distinct letters, $z>y>x$, with $zx$ a factor of a column, and $y$
a letter of another column of $\caH_{\sigma }$. Thus, using 
Lemma~\ref{sh1}, we find that any word obtained by application of a single
Knuth transformation on a shuffle of two columns of $\caH_{\sigma
(l_4,\ldots,l_1)}$, other than
$sh(r_4,r_{\sigma,2})=43\:\underline{4}\:\underline{1}\:21$, is
still a shuffle of the columns of $\caH_{\sigma (l_4,\ldots,l_1)}$.

In the case of the shuffle
$sh(r_4,r_{\sigma,2})=43\:\underline{4}\:\underline{1}\:21$, the
application of the transformation $341\equiv 314$ or $412\equiv
142$ gives the word
 $431421$, which is not a shuffle of the columns of
$\caH_{\sigma (l_4,\ldots,l_1)}$.

Now, an exhaustive analysis of the effect of a single Knuth
transformation on all possible shuffles between any two words from
the set $\{431421,r_4,r_{\sigma,3},r_{\sigma,2},r_{\sigma,1}\}$,
shows that the resulting word is still a shuffle of two, or more,
words of this set.

Thus, if $w\equiv \caH_{\sigma (l_4,\ldots,l_1)}$, $w$ is obtained
by a finite number of Knuth transformations on $\caH_{\sigma
(l_4,\ldots,l_1)}$. Hence, it must be a shuffle of the words
$431421,r_4,r_{\sigma,3},r_{\sigma,2},$ and $r_{\sigma,1}$, with
appropriate multiplicities.
 \edem










\section{Matrix realizations of pairs of tableaux}

 Let ${\mathcal R}_p$ be a local principal ideal domain
with maximal ideal $(p)$. The matrices under consideration  have
entries in ${\mathcal R}_p$.
%In this section, we exhibit a matrix translation, over ${\mathcal
%R}_p$, of operations $\theta_i$ and Lemma~\ref{sh02}.
Let ${\mathcal U}_n$ be the group of $n\times n$ unimodular matrices
over ${\mathcal R}_p$. Given $n\times 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 unimodular matrix $U$; $B$ is {\it right
equivalent} to $A$ (written $B\sim_R A$) if $B=AV$ for some
unimodular matrix $V$; and $B$ is {\it equivalent} to $A$ (written
$B\sim A$) if $B=UAV$ for some unimodular matrices $U,V$. The
relations $\sim_L$, $\sim_R$ and $\sim$ are equivalence relations
on the set of all $n\times n$ matrices over ${\mathcal R}_p$.

Let $A$ be an $n\times n$ non-singular matrix. By the Smith normal
form theorem \cite{B,new}, there exist nonnegative integers
$\lambda_1,...,\lambda_n$ with $\lambda_1\geq...\geq\lambda_n$ such
that $A$ is equivalent to the diagonal matrix
$$\diag(p^{\lambda_1},...,p^{\lambda_n}).$$ The sequence $\lambda=(\lambda_1,...,\lambda_n)$ of
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$.
The partition $\lambda$ is a full invariant of the equivalence class
containing $A$ and  we call $\lambda$ the {\it invariant partition}
of $A$. More generally, if we are given a sequence $(f_1,...,f_n)$
of nonnegative integers, the following notation for $p$-powered
diagonal matrices will be used:
$$\diag_p(f_1,...,f_n):=\diag(p^{f_1},...,p^{f_n}).$$
Given $J\subseteq [n]$, we write $\chi^J=(f_1,...,f_n)$ with $f_i=1$
if $i\in J$ and $0$ otherwise, thus, we put $D_J:=\diag_p(\chi^J)$.
Given  a partition $\lambda$ of length $\leq n$, we write
$\Delta_{\lambda}=\diag_p(\lambda)$. If $\lambda=(0)$,
$\Delta_{(0)}=I_n$ the identity matrix of order $n$.







Let $\sigma\in\caS_t$, $t\geq 1$, and let $m$ be a partition of
length $t$ such that $\sigma m=(m_1,\ldots, m_t)$. In what follows,
$\caT$ will denote a skew-tableau of evaluation $(m_1,...,m_t)$ and
shape $\lambda/\mu$ where the length of  $\lambda$ is $\leq n$. Next
we define the matrix realization of a pair of Young
tableaux $({\mathcal T},{\mathcal F})$, with ${\mathcal F}$ a tableau of
evaluation $(m_1,...,m_t)$ and shape $\nu$, following
\cite{az1,am1,az2}. (Note that in this paper  the tableaux are
strictly increasing up along columns.)

\begin{defi}    \label{defMR}
    Let ${\mathcal T}=(\lambda^0,\lambda^1,...,\lambda^t)$ and ${\mathcal F}=(0,\mu^1,...,\mu^t)$ be   tableaux, both of
    evaluation
    $(m_1,$ $...,m_t)$.
    We say that a sequence of $n\times n$ non-singular
    matrices $A_0,B_1,...,B_t$ is a
    {\it matrix realization} of the pair of  tableaux $({\mathcal T},{\mathcal F})$ (or realizes
    $({\mathcal T},{\mathcal F})$) if:
    \begin{enumerate}
        \item[I.] For each $r\in\{1,...,t\}$, the matrix $B_r$ has
        invariant partition $(1^{m_r},0^{n-m_r})$.
        \item[II.] For each $r\in\{0,1,...,t\}$, the matrix
        $A_r:=A_0B_1...B_r$ has invariant partition the conjugate of $\lambda^r$.
        \item[III.] For each $r\in\{1,...,t\}$, the matrix
        $B_1...B_r$ has invariant partition the conjugate of $\mu^r$.
    \end{enumerate}
    $({\mathcal T},{\mathcal F})$ is called an {\it admissible pair} of tableaux.
\end{defi}

Conditions  (I) and (II) alone are trivially feasible. But,
 in conjunction with condition (III), they impose a 
non-trivial restriction on the concept of matrix realization. Here, we
restrict ourselves to pairs $(\caT,\caH_{\sigma (l_t,\ldots,l_1)})$.
The next theorem, proved in \cite{am1,az2}, shows that, without loss of
generality, we may consider matrix realizations of
$(\caT,\caH_{\sigma (l_t,\ldots,l_1)})$ with a particular simple
form.





\begin{teor}\label{teorm1}
    The following conditions are equivalent:
    \begin{enumerate}
        \item[(a)] $({\mathcal T},\caH_{\sigma (l_t,\ldots,l_1)})$ is an admissible pair.
        \item[(b)] There exists $U\in{\mathcal U}_n$
        such that $\Delta_{\lambda}
        U,D_{[m_1]},...,D_{[m_t]}$ realizes $(\caT,\caH_{\sigma (l_t,\ldots,l_1)})$.
    \end{enumerate}
\end{teor}


 The characterization of $\sigma$-Yamanouchi words as shuffles of
the columns  $\caH_{\sigma}$ has been used to determine necessary
and sufficient conditions for the admissibility of a pair of Young
tableaux $(\caT,\caH_{\sigma (l_t,\ldots,l_1)})$, when $\sigma$ is
the identity or the reverse permutation in $\caS_t$, $t\geq 1$
\cite{az2,az1}, or any permutation in $\caS_3$ \cite{am1}. In these
cases, the pair $(\caT,\caH_{\sigma (l_t,\ldots,l_1)})$ is
admissible only if the word of $\caT$ is in the Knuth class of
$\caH_{\sigma (l_t,\ldots,l_1)})$.
The next theorem extends the necessary
condition  of this result to any $\sigma\in\caS_t$, $t\geq 1$, and
verifies the recursive criterion for $\sigma$-Yamanouchi words given
in Theorem~\ref{theta0}. The proof of this theorem needs the
following proposition, proved in \cite{am1}.

\begin{prop}{\em\cite{am1}}\label{ar1}
    Let  $(m_1,m_2)$ be a partition. Let  $w$ and $w'$ be the words of the
    tableaux
     realized by the
    sequences $\Delta_{\lambda} U,D_{[m_1]},D_{[m_2]}$ and
    $\Delta_{\lambda} U,D_{[m_2]},D_{[m_1]},$
    respectively. Then, there exists an
    operation $\theta_1$ such that $w'=\theta_1(w)$.
\end{prop}

The following example shows that the operation $\theta_1$ in the
previous proposition is not necessarily $\theta_1^*$.
\begin{ex} \label{ex} Let $U=P_{4321}T_{14}(p),$ where $P_{4321}$ is the permutation matrix
associated with $4321\in\caS_4$ and $T_{14}(p)$ is the elementary
matrix obtained from the identity by placing the prime $p$ in
position $(1,4)$. It is a simple task to check that, with
$\lambda=(2,1)$ and $U=P_{4321}T_{14}(p),$  the sequences
$\Delta_{\lambda}U,D_{[3]},D_{[2]}$ and
$\Delta_{\lambda}U,D_{[2]},D_{[3]}$
 are matrix realizations for the
pairs $\left(\caT,\caH(id,(2,1))\right)$ and
$(\caT',\caH(s_1,(2,1))$, where $\caT=\begin{matrix}
 2&&&\\
 \bullet&1&2&\\
 \bullet&\bullet&1&1
\end{matrix}$ and $\caT'=\begin{matrix}
 2&&&\\
 \bullet&2&2&\\
 \bullet&\bullet&1&1
\end{matrix}$. The words
$w(\caT)=21211$ and $w(\caT')=22211$ satisfy
$\theta_1(w(\caT))=w(\caT')$, where $\theta_1$ is the operation
based on a parentheses matching defined  as $(21(21)1)$.

Thus, the matrix setting generates parentheses matching operations,
different from the standard ones defined by Lascoux and
Sch\"utzenberger. However, if we choose $U'=P_{3241}T_{24}(p)$, the
sequences $\Delta_{\lambda}U',D_{[3]},D_{[2]}$ and
$\Delta_{\lambda}U',D_{[2]},D_{[3]}$ are matrix realizations for the
pairs $\left(\caT,\caH(id,(2,1))\right)$ and
$(\caT'',\caH(s_1,(2,1))$, where $\caT''=\begin{matrix}
 2&&&\\
 \bullet&1&2&\\
 \bullet&\bullet&1&2
\end{matrix}$. In this case, we have
$\theta^*_1(w(\caT))=w(\caT'')=21212\neq
\theta_1(\caT)=22211$.\end{ex}



\begin{teor}\label{v}
    Let $\sigma\in \caS_t$, and let $(l_t,\cdots, l_1)$ be a sequence of nonnegative integers. The pair $(\caT,\caH_{\sigma (l_t,\ldots,l_1)})$ is admissible only if
    $w(\caT)\equiv \caH_{\sigma (l_t,\ldots,l_1)}$.
\end{teor}

\bdem By induction on $t\geq 1$. When $t=1$ there is nothing to
prove, and the case $t=2$ has been proved in \cite{az1,az2}. Assume
the claim for $t-1\geq 2$. Thanks to Theorem~\ref{teorm1} we may
assume the existence of an unimodular matrix $U\in\caU_n$ such that
$\Delta_{\lambda},UD_{[m_1]},\ldots,D_{[m_t]}$ realizes
$(\caT,\caH_{\sigma (l_t,\ldots,l_1)})$. Put $w:=w(\caT)$.
 By the inductive step, the word $w_{|{[t-1]}}$ of the
tableau realized by the sequence
$$\Delta_{\lambda},UD_{[m_{1}]},\ldots,D_{[m_{t-1}]}$$ satisfies
$P(w_{|{[t-1]}})={\caH_{\sigma }}_{|[t-1]}$.

We consider the case $m_{t-1}\geq m_t$, the other one is similar.
There exists an unimodular matrix $U'\in\caU_n$ such that
 $$\Delta_{\lambda}UD_{[m_{1}]}\cdots
D_{[m_{t-1}]}D_{[m_{t}]}\sim_L\Delta'U'D_{[m_{t-1}]}D_{[m_{t}]},$$
where $\Delta'=\diag_p(\lambda+\chi^{J_1}+\cdots+\chi^{J_{t-2}})$.
 Since
$m_{t-1}\geq m_{t}$, by the case $t=2$, the sequence
$\Delta'U',D_{[m_{t-1}]},D_{[m_{t}]}$ realizes a tableau whose
word $w_{|{\{t-1,t\}}}$ is a Yamanouchi word.
 Finally, consider the sequence
$$\Delta_{\lambda}U,D_{[m_1]},\cdots,D_{[m_{t-2}]},D_{[m_t]},$$ and let
$w'$ be the word of the corresponding tableau. According to the
previous proposition, we must have
$w'=(\theta_{t-1}(w))_{|{[t-1]}}$, for some operation
$\theta_{t-1}$, and by the inductive step,
$P(w')={\caH_{s_{t-1}\sigma }}_{|[t-1]}$. By Theorem~\ref{theta0},
we find that $w$ is a $\sigma$-Yamanouchi word. \edem


\section{Appendix}

Below we list the permutations $\sigma$ in $\caS_5$ and $\caS_6$ for which the set $Sh((r_t)^{l_t},$ $
(r_{\sigma,t-1})^{l_{t-1}},$ $ \ldots,(r_{\sigma,2})^{l_2},$ $ (r_{\sigma,1})^{l_1})$, with $l_i>0$,
$i=1,\ldots,t$, $t=5,6$, is not the whole plactic class of $\caH_{\sigma}$.

\vskip10pt

\begin{tabular}{lll}
  $\caS_5$ &\\
  \hline
  $w4w'$,&$w\in\caS_{\{2,5\}},$&$w'\in\caS_{\{1,3\}}$;\\
  $w3w'$,&$w\in\caS_{\{2,5\}},$&$ w'\in\caS_{\{1,4\}};$\\
  $ww'$,&$w\in\caS_{\{1,4,5\}},$&$w'\in\caS_{\{2,3\}};$\\
  $ww'$,&$w\in\caS_{\{1,3,5\}},$&$w'\in\caS_{\{2,4\}};$\\
  $w3w'$,&$w\in\caS_{\{1,4\}},$&$w'\in\caS_{\{2,5\}};$\\
  $w2w'$,&$w\in\caS_{\{1,4\}},$&$w'\in\caS_{\{3,5\}};$\\
  $ww'$,&$w\in\caS_{\{1,2,5\}},$&$w'\in\caS_{\{3,4\}}.$\\
\end{tabular}

%\medskip

\begin{tabular}{llll}
  $\caS_6$ &\\
  \hline
  $ww'w''$,&$w\in\caS_{\{3,6\}},$&$w'\in\caS_{\{4,5\}},$&$w''\in\caS_{\{1,2\}}$;\\
  $ww'w''$,&$w\in\caS_{\{2,5\}},$&$w'\in\caS_{\{3,4\}},$&$w''\in\caS_{\{1,6\}};$\\
  $ww'w''$,&$w\in\caS_{\{1,4\}},$&$w'\in\caS_{\{2,3\}},$&$w''\in\caS_{\{5,6\}};$\\
  $w4w'$,&$w\in\caS_{\{2,5,6\}},$&$w'\in\caS_{\{1,3\}};$&\\
  $w5w'$,&$w\in\caS_{\{2,4,6\}},$&$w'\in\caS_{\{1,3\}};$&\\
  $w46w'$,&$w\in\caS_{\{2,5\}},$&$w'\in\caS_{\{1,3\}};$&\\
  $w52w'$,&$w\in\caS_{\{3,6\}},$&$w'\in\caS_{\{1,4\}};$&\\
  $w3w'$,&$w\in\caS_{\{2,5,6\}},$&$w'\in\caS_{\{1,4\}};$&\\
  $w5w'$,&$w\in\caS_{\{2,3,6\}},$&$w'\in\caS_{\{1,4\}};$&\\
  $w36w'$,&$w\in\caS_{\{2,5\}},$&$w'\in\caS_{\{1,4\}};$&\\
  $w42w'$,&$w\in\caS_{\{3,6\}},$&$w'\in\caS_{\{1,5\}};$&\\
  $w3w'$,&$w\in\caS_{\{2,4,6\}},$&$w'\in\caS_{\{1,5\}};$&\\
  $w4w'$,&$w\in\caS_{\{2,3,6\}},$&$w'\in\caS_{\{1,5\}};$&\\
  $ww'$,&$w\in\caS_{\{1,4,5,6\}},$&$w'\in\caS_{\{2,3\}};$&\\
  $ww'$,&$w\in\caS_{\{1,3,5,6\}},$&$w'\in\caS_{\{2,4\}};$&\\
  $ww'$,&$w\in\caS_{\{1,3,4,6\}},$&$w'\in\caS_{\{2,5\}};$&\\
  $w3w'$,&$w\in\caS_{\{1,4,5\}},$&$w'\in\caS_{\{2,6\}};$&\\
  $w4w'$,&$w\in\caS_{\{1,3,5\}},$&$w'\in\caS_{\{2,6\}};$&\\
  $w35w'$,&$w\in\caS_{\{1,4\}},$&$w'\in\caS_{\{2,6\}};$&\\
  $ww'$,&$w\in\caS_{\{1,2,5,6\}},$&$w'\in\caS_{\{3,4\}};$&\\
  $ww'$,&$w\in\caS_{\{1,2,4,6\}},$&$w'\in\caS_{\{3,5\}};$&\\
  $w41w'$,&$w\in\caS_{\{2,5\}},$&$w'\in\caS_{\{3,6\}};$&\\
  $w2w'$,&$w\in\caS_{\{1,4,5\}},$&$w'\in\caS_{\{3,6\}};$&\\
\end{tabular}

\begin{tabular}{llll}
  $w4w'$,&$w\in\caS_{\{1,2,5\}},$&$w'\in\caS_{\{3,6\}};$&\\
  $w25w'$,&$w\in\caS_{\{1,4\}},$&$w'\in\caS_{\{3,6\}};$&\\
  $ww'$,&$w\in\caS_{\{1,2,3,6\}},$&$w'\in\caS_{\{4,5\}};$&\\
  $w31w'$,&$w\in\caS_{\{2,5\}},$&$w'\in\caS_{\{4,6\}};$&\\
  $w2w'$,&$w\in\caS_{\{1,3,5\}},$&$w'\in\caS_{\{4,6\}};$&\\
  $w3w'$,&$w\in\caS_{\{1,2,5\}},$&$w'\in\caS_{\{4,6\}}.$&\\
\end{tabular}

\medskip

There are a total of $52$ permutations in $\caS_5$ and $488$
permutations in $\caS_6$ that fail to satisfy the conditions of
Theorem~\ref{prop1sy}.

\vskip1cm \noindent{\bf Acknowledgments.} We thank the referee for
helpful comments and useful suggestions. In particular, we are
grateful for pointing out to us Greene's theorem in \cite{greene}.

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}

\begin{thebibliography}{10}

\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{az5}
O.~Azenhas, \emph{Realiza\c c\~oes {M}atriciais de {Q}uadros de {Y}oung e suas
  {F}ormas {C}an\'onicas \em{(in {Portuguese})}}, Ph.D. thesis, Universidade de
  Coimbra, Coimbra, 1991.

\bibitem{az3}
\bysame, \emph{A regra de {Littlewood--Richardson}: Generaliza\c c\~oes e
  realiza\c c\~oes matriciais \em{(in Portuguese)}}, Proceedings of the Third
  Meeting of the Portuguese Algebraists, Coimbra, 1993.

\bibitem{az2}
\bysame, \emph{Opposite {Litlewood--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{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{B}
W.~C. Brown, \emph{Matrices {Over} {Commutative} {Rings}}, Monographs and
  Textbooks in Pure and Applied Mathematics, Marcel Dekker, New York, 1993.

\bibitem{eh}
C.~Ehresmann, \emph{Sur la topologie de certains espaces homog\`enes}, Annals
  of Mathematics, (2) \textbf{35} (1934), 396--443.

\bibitem{ful}
W.~Fulton, \emph{Young {Tableaux}: With {Applications} to {Representation
  Theory and Geometry}}, London Mathematical Society Student Texts, vol.~35,
  Cambridge University Press, Cambridge, 1997.

\bibitem{fulton3}
\bysame, \emph{Eigenvalues of sums of {H}ermitiam matrices (after {K}lyachko)},
  S\'eminaire Bourbaki \textbf{845} (1998), 1997--98.

\bibitem{fulton5}
\bysame, \emph{Eigenvalues, invariant factors, highest weigths, and {S}chubert
  calculus}, Bulletin of the American Mathematical Society \textbf{37} (2000),
  209--249.

\bibitem{fulton4}
\bysame, \emph{Eigenvalues of majorized {H}ermitiam matrices and
  {L}ittlewood--{R}ichardson coefficients}, Linear Algebra and its Applications
  \textbf{319} (2000), 23--36.

\bibitem{kash}
I.~Gohberg and M.~A. Kaashoek, \emph{Unsolved problems in matrix and operator
  theory {II}. {Partial} multiplicities of a product}, Integral Equations
  Operator Theory \textbf{319} (1979), 116--120.

\bibitem{green2}
J.~A. Green, \emph{Les polyn\^omes de {Hall} et les caract\`eres des groupes
  ${\rm gl}(n,\,q)$}, Colloque d'Alg\`ebre Sup\'erieure, Librairie
  Gauthier--Villars, Paris, 1957.

\bibitem{green}
\bysame, \emph{Symmetric {F}unction and p-{M}odules}, Lecture notes, University
  of Manchester, Manchester, 1961.

\bibitem{shuf}
\bysame, \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 {S}chensted'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-{m}odules}, Journal of London Mathematical Society \textbf{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, pp.~164--196, Cambridge University Press,
  Cambridge, 2002.

\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).

\bibitem{aretes}
\bysame, \emph{Ar\^etes et tableaux}, S\'eminaire Lotharingien de Combinatoire
  \textbf{20} (1988), 125--144.

\bibitem{keys}
\bysame, \emph{Keys and standard bases}, Invariant theory and tableaux
  (Minneapolis, MN,1988) IMA, Math. Appl., vol.~19, Springer, New York--Berlin,
  1990.

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

\bibitem{RM}
R.~Mamede, \emph{Permuta\c c\~oes de {S}equ\^encias de {Littlewood--Richardson}
  e suas {R}ealiza\c c\~oes {M}atriciais \em{(in Portuguese)}}, Master's
  thesis, Universidade de Coimbra, Coimbra, 2000.

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

\bibitem{inter}
J.~F. Queir\'o, E.~Marques de~S\'a, A.~P. Santana, and O.~Azenhas,
  \emph{Interlacing of eigenvalues and invariant factors}, Mathematical
  Inequalities and Applications \textbf{3} (2000), 149--154.

\bibitem{sch}
C.~Schensted, \emph{Longest increasing and decreasing subsequences}, Canadian
  Journal of Mathematics \textbf{13} (1961), 179--191.

\bibitem{thijsse}
G.~P.~A. Thijsse, \emph{The local invariant factors of a product of holomorphic
  matrix functions, the order $4$ case}, Integral Equations Operator Theory
  \textbf{16} (1993), 277--304.

\bibitem{thompson2}
R.~C. Thompson, \emph{Smith invariants of a product of integral matrices},
  Contemporary Mathematics \textbf{47} (1985), 401--435.

\end{thebibliography}



\end{document}