Séminaire Lotharingien de Combinatoire 53 (2006), Article B53h

MATRIX REALIZATIONS OF PAIRS OF YOUNG TABLEAUX, KEYS AND SHUFFLES

Olga Azenhas^{1} and Ricardo Mamede^{1}

Departamento de Matemática, Universidade de Coimbra 3001-454 Coimbra, Portugal

Abstract. A key H 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 H this result has been already applied to exhibit a matrix realization, over a local principal ideal domain, of a pair of tableaux (T , H), where T is a skew-tableau whose word is in the Knuth class of H. Generalized Lascoux–Schützenberger operators, based on nonstandard matching of parentheses, arise in the matrix realization, over local principal ideal domain, of a pair (T , H) on a two-letter alphabet, and they are used to show that, over a t-letter alphabet, the pair (T , H) has a matrix realization only if the word of T is in the Knuth class of H.

1. Introduction

Given an n by n non-singular matrix A, with entries in a local principal ideal domain with prime p, by Gaußian elimination, one can reduce A to a diagonal matrix with diagonal entries p^{λ_{1}}, …, p^{λ_{n}}, for unique nonnegative integers λ_{1} ≥ … ≥ λ_{n}, called the Smith normal form of A. The sequence p^{λ_{1}}, …, p^{λ_{n}} defines the invariant factors of A, and (λ_{1}, …, λ_{n}) the invariant partition of A. It is known that α, β, γ 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 T of type (α, β, γ), that is, a skew-tableau of shape γ/α whose word is in the Knuth class of the key H of evaluation β (Yamanouchi tableau β). This matrix problem is equivalent to the existence of pmodules A, B, and C with invariant partitions α, β, γ such that B ⊆ C and C/B ≅ A [18]. (Interestingly, the eigenvalues of a sum of Hermitian matrices A + B = C are characterized by the same condition [10, 27].) 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 [14, 15, 18, 13, 24, 30, 5, 29]. (For an overview see [10, 11, 12].) One can solve this problem by introducing the notion of a matrix realization of a pair (T , H) where T is a skew-tableau with the same evaluation as the key H [5, 2, 1] [see Section 5, Definition 5.1] which is equivalent, in the module setting, to the existence of a chain of p-submodules (0) = B_{t} ⊆ ⋯ ⊆ B_{1} ⊆ B_{0} = B ⊆ C such that the sequence of invariant partitions of C/B_{k}, 0 ≤ k ≤ t, defines a Littlewood–Richardson tableau of shape γ/α and evaluation given by the weight of the invariant partitions of B_{k−1}/B_{k}, 1 ≤ k ≤ t [18]. Within this notion it is natural to ask under which conditions does there exist a matrix realization of a pair (T , H_{σ}), where H_{σ} is a key associated with σ ∈ S_{t} [8, 9, 22, 23]. In the case of the reverse permutation in S_{t} [4], or any permutation in S_{3} [6], or any adjacent transposition [3, 25], it has been shown that (T , H_{σ}) has a matrix realization if and only if the word of T is in the plactic class of H_{σ}. For these permutations, the elements of the plactic class of H_{σ} are shuffles of the columns of H_{σ} and this property has been used to exhibit a matrix realization (T , H_{σ}). Here, in Theorem 5.3, we show that, for any σ ∈ S_{t}, t ≥ 1, (T , H_{σ}) has a matrix realization only if the word of T is in the plactic class of H_{σ}.

1Work supported by CMUC/FCT.

Due to the embedding of the symmetric group in the set of tableaux, originally defined by Ehresmann in [8], the symmetric group acts on the set of keys H_{σ}, σ ∈ S_{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ützenberger in the plactic monoid [21, 20], 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 H_{σ} and H_{s_{i}σ}, with s_{i} the adjacent transposition of the integers i, i+1. Matrix realizations of pairs (T , H), over a two-letter alphabet, give rise to operations based on other parentheses matching than the standard one, as shown in Example 5.1 (see also [6]). Corollary 3.13 characterizes the operations, based on more general parentheses matching, which transform a word in the plactic class of H_{σ} into one in the plactic class of H_{s_{i}σ}. The proof of Theorem 5.3 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 threeletter alphabet are shuffles of their columns [6]. In the case of a four-letter alphabet this property does not remain true. Nevertheless, by Greene’s theorem [17], 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 S_{t}, t ≥ 1, are simple examples of those keys. Finally, for σ ∈ S_{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: if the columns u_{1}, …, u_{k} are pairwise comparable for the inclusion order, under which conditions is the set of all shuffles of u_{1}, …, u_{k}, denoted by Sh(u_{1}, …, u_{k}), the plactic class of u_{1} … u_{k}? Indeed, the containment of Sh(u_{1}, …, u_{k}) in the plactic class of u_{1} … u_{k} follows from Greene’s theorem [17]. 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 [8]. σ-Yamanouchi words are introduced as words congruent to a key of the permutation σ. 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ützenberger in the plactic monoid [21, 20], based on the standard parentheses matching. Operations on words based on more general parentheses matchings are considered. A criterion characterizing those which transform a σ-Yamanouchi word into a s_{i}σ-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} … u_{k} such that the plactic class of u_{1} … u_{k} is contained in Sh(u_{1}, …, u_{k}). In the case of S_{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ützenberger operations, based on nonstandard matching of parentheses, is considered. Finally, in the Appendix, the permutations in S_{5} and S_{6} giving a positive answer to the question raised in Section 2 are listed.

2. Words, shuffles and Knuth congruence

2.1. Words and tableaux. Let ℕ be the set of positive integers with the usual order “ ≤ ”. Given i, j ∈ ℕ, where i ≤ j, [i, j] is an interval in ℕ with the usual order. If t ∈ ℕ, [t] denotes the set {1, …, t}.

Let A = {a, b, …, f}, a < b < ⋯ < f, be a finite subset of ℕ. 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 ϵ.

Given a word w = x_{1} ⋯ 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 ∈ A in w. The sequence (|w|_{a}, …, |w|_{f}) is called the evaluation of w in the alphabet A. We have |w| = |w|_{a} + ⋯ + |w|_{f}, and the length of ϵ 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 column in A^{∗}. A column shall be identified with the set consisting of its entries. Given two finite subsets P = {p_{1}, p_{2}, … }, Q = {q_{1}, q_{2}, … } of ℕ with |P | ≤ |Q|, we write P ≤ Q if p_{i} ≤ q_{i} for i = 1, 2, …, |P |.

A partition λ = (λ_{1}, …, λ_{k}, …) 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 λ is called the length of λ. A partition λ is identified with its Young diagram, a left-justified arrangement of boxes, or dots, with λ_{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 λ is the partition λ′, the transpose of the Young diagram λ. It is convenient not to distinguish between two partitions which only differ by a string of zeros at the end. Sometimes we write λ = (1^{p_{1}}, 2^{p_{2}}, ⋯) to indicate that i appears p_{i} times as a part of λ. For instance, the partition (3, 2, 2, 1) = (3, 2^{2}, 1, 0) corresponds to the Young diagram

\begin{matrix}• \\ • & • \\ • & • \\ • & • & • \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 T of shape λ is a filling of the Young diagram of λ with positive integers, weakly increasing across each row and strictly increasing up each column [9, 20]. An example of a Young tableau of shape (3, 2, 2, 1) is given by

T = 5 4 5 2 2 1 1 2.

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 T = 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 T 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 λ and μ are partitions with μ ⊆ λ, that is, μ_{i} ≤ λ_{i} for all i, we define a skew-tableau of shape λ/μ as a filling of the skewdiagram λ/μ, that is, weakly increasing across each row and strictly increasing up each column [9]. A Young tableau of shape λ may be seen as a skew-tableau of shape λ/(0), where (0) denotes the empty partition. An example of a skew-tableau of shape (4, 4, 2, 1)/(3, 1) is given by

T = \begin{matrix}4 \\ 2 & 2 \\ • & 1 & 3 & 3 \\ • & • & • & 2 \end{matrix} .

The word w(T ) of a skew-tableau T 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(T ) = 42 21 3 32. As for Young tableaux, the evaluation of a skew-tableau T is the evaluation of its word. For instance, the evaluation of the skew-tableau T above is (1, 3, 2, 1).

A skew-tableau T of shape λ/μ and evaluation (m_{1}, …, m_{t}) may also be represented by a nested sequence of partitions [24] T = (λ^{0}, λ^{1}, …, λ^{t}), where μ = λ^{0} ⊆ λ^{1} ⊆ ⋯ ⊆ λ^{t} = λ, such that for k = 1, …, t, all the boxes of the skew diagram λ^{k}/λ^{k−1} are filled with k, with m_{k} = |λ^{k}| − |λ^{k−1}|. In the example above, T = (λ^{0}, λ^{1}, λ^{2}, λ^{3}, λ^{4}), where λ^{0} = μ, λ^{1} = (3, 2), λ^{2} = (4, 2, 2), λ^{3} = (4, 4, 2) and λ^{4} = λ.

2.2. 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}, …, u_{q} is the empty word ϵ 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}, …, u_{q}. Let Sh(u_{1}, u_{2}, …, u_{q}) denote the set of shuffles of u_{1}, u_{2}, …, u_{q}. By abuse of notation we write w = sh(u_{1}, u_{2}, …, u_{q}) to mean that w is some shuffle of u_{1}, u_{2}, …, 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}}, …, (u_{q})^{l_{q}}) to designate a shuffle of l_{i} words u_{i}, for i = 1, …, q. Thus, we have 4423142121 ∈ Sh(4321, (421)^{2}).

Knuth’s congruence ≡ [19] 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:

uxzxv ≡ uzxxv, uzzxv ≡ uzxzv, x < z,  (1)
uxzyv ≡ uzxyv, x < y < z,  (2)
uyzxv ≡ uyxzv, x < y < z.  (3)

The relations (1), (2), (3), also called plactic relations, are the algebraic version of the plactic congruence [9, 19, 20]. C. Schensted [9, 20, 28] has described an algorithm, known as 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′) [9, 19, 20]. The set of all tableaux is a 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}, …, u_{k} in A^{∗} be columns in decreasing order of length. If T = u_{1} … u_{k} is a tableau, then T is the unique tableau of Sh(u_{1}, …, u_{k}) only if the columns of the tableau T are pairwise comparable for the inclusion order; that is {u_{k}} ⊆ ⋯ ⊆ {u_{1}}. For instance, Sh(41, 3) = {3 41, 41 3, 431} has two tableaux 41 3 and 431.

An elementary Knuth transformation (1), (2), or (3) applied to a shuffle of columns, say u_{1}, …, u_{k}, involves at least two of these columns. If an elementary Knuth transformation (2) or (3) involves three distinct letters x < y < z of sh(u_{1}, …, u_{k}), each one belonging to a different column u_{i}, then the output word is still a shuffle of u_{1}, …, u_{k}.

Proposition 2.1. Let u_{1}, …, u_{k}, k ≥ 3, be columns in A^{∗}, and x, y, z, u and v as in (2), (3) such that each letter x, y and z appears in a distinct column. Then

uxzyv ∈ Sh(u_{1}, …, u_{k}) ⇔ uzxyv ∈ Sh(u_{1}, …, u_{k});
uyzxv ∈ Sh(u_{1}, …, u_{k}) ⇔ uyxzv ∈ Sh(u_{1}, …, u_{k}).

For instance, in the alphabet [5], consider the word 5\overline{2}4\underline{4}\overline{1}2\underline{2}1\underline{1} ∈ 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 ≡ \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} …, u_{q}), it is also clear that the output word is still a shuffle of u_{1} …, u_{q}.

Proposition 2.2. Let u_{1} …, u_{k}, k ≥ 2, be columns in A^{∗}, and x, z, u and v as in (1). Then

uzxxv ∈ Sh(u_{1}, …, u_{k}) ⇔ uxzxv ∈ Sh(u_{1}, …, u_{k});
uzzxv ∈ Sh(u_{1}, …, u_{k}) ⇔ uzxzv ∈ Sh(u_{1}, …, u_{k}).

Corollary 2.3. Let u_{1} …, u_{k}, k ≥ 2, be columns in a two-letter alphabet A = {a, b}, and w ∈ Sh(u_{1}, …, u_{k}) of evaluation (p, q). Then

(a) P (w) ∈ Sh(u_{1}, …, u_{k}).

(b) Sh(u_{1}, …, u_{k}) is either

(i) the plactic class of P (w) = (ba)^{q}1^{p} or P (w) = (ba)^{p}b^{q}, if the columns u_{i} are pairwise comparable for the inclusion order, for i = 1, …, k; or

(ii) the union of the plactic classes of P (w) = (ba)^{r}a^{s}b^{v}, r + s = p, r + v = q, and P (w) = (ba)^{p+q}, otherwise.

Let x < y < z ∈ A. The columns \overline{z} \overline{y} and \underline{y} \underline{x}, in the elementary Knuth transformations x \overline{z} \overline{y} ≡ \overline{z} x \overline{y} (2), and \underline{y} z \underline{x} ≡ \underline{y} \underline{x} z (3), 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 ≡ 31 4 ∉ Sh(41, 3) and 41 3 ≡ 143 ∉ Sh(3, 41). Therefore, considering, for example, the tableau 4321 41, the Knuth transformation 341 ≡ 314 implies 43\underline{4} \underline{1}21 = sh(4321, 41) ≡ 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}, …, u_{k} are columns pairwise comparable in the inclusion order, we raise the question: Under which conditions Sh(u_{1}, …, u_{k}) equals the plactic class of the tableau T = u_{1} ⋯ u_{k}?

We start by noticing that the containment Sh(u_{1}, …, u_{k}) in the Knuth class of T follows from Greene’s theorem [17]. Since u_{1} ⊇ ⋯ ⊇ u_{k}, the maximum of the sums of the lengths of j decreasing and disjoint subwords of w ∈ Sh(u_{1}, …, u_{k}) is |u_{1}| + ⋯ + |u_{j}|, for all j ≥ 1. It follows from Greene’s theorem that the conjugate shape of P (w) is (|u_{1}|, …, |u_{k}|), which means that P (w) = u_{1} ⋯ 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.

3. Keys and σ-Yamanouchi words

3.1. Parentheses matching operations. Given a set I, let S_{I} be the set of all bijections on I, and S_{t} := S_{[t]} the symmetric group of order t. The symmetric group S_{t}, t ≥ 1, is generated by the simple transpositions s_{i} = (i i + 1), i = 1, …, t − 1, which satisfy the Moore-Coxeter relations:

(I) s_{i}^{2} = id, (II) s_{i}s_{j} = s_{j}s_{i}, if |i − j| ≠ 1, and (III) s_{i}s_{i+1}s_{i} = s_{i+1}s_{i}s_{i+1},

where id denotes the identity.

Let w be a word over the alphabet [t] and i, i + 1 ∈ [t]. An operation θ_{i} on w [6] 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 θ_{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^{2}2^{1}. Thus, θ_{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^{1}2^{2}. Finally, θ_{1}(w) = 3 1 3 2 4 2 2 2 4 1 1.

A. Lascoux and M. P. Schützenberger [21, 20] have introduced the following involutions θ_{i}^{∗}, for i = 1, …, 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 θ_{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 θ_{i}^{∗}, 1 ≤ i ≤ t − 1, satisfy the Moore-Coxeter relations [21, 20] and define an action of S_{t} over [t]^{∗}.

Let w = 31314221412 as above. To compute θ_{1}^{∗}(w), we get v = 112(21)12, v_{1} = 11(21)2 and v_{2} = 112 = 1^{2}2^{1}. Thus, θ_{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^{1}2^{2}.

The operations θ_{i}^{∗}, 1 ≤ i ≤ t − 1, are compatible with the plactic equivalence and preserve the Q-symbol.

Proposition 3.1. [21, 20] Let w, w′ be words in [t]^{∗}, and let i ∈ [t]. Then, w ≡ w′ if and only if θ_{i}^{∗}(w) ≡ θ_{i}^{∗}(w′). In particular, P (θ_{i}^{∗}(w)) = θ_{i}^{∗}(P (w)).

Note that in the examples above we have θ_{1}(w) ≢ θ_{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 θ_{i}(w) ≡ θ_{i}^{∗}(w).

3.2. Keys and σ-Yamanouchi words. By definition, a key is a tableau such that its columns are pairwise comparable in the inclusion order [23]. 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}, …, l_{2}, l_{1}) be a sequence of nonnegative integers. Then, m = (l_{1} + ⋯ + l_{t}, …, l_{t−1} + l_{t}, l_{t}) is a partition and (t^{l_{t}}, …, 2^{l_{2}}, 1^{l_{1}}) its conjugate. For instance, (1, 1, …, 1) defines the self-conjugate partition (t, t − 1, …, 1).

Let σ ∈ S_{t} written as a word a_{1} ⋯ a_{t} in [t]^{∗}. For k = 1, …, t, denote by r_{σ,k} the column with underlying set {a_{1}, …, a_{k}}. In particular, when σ = 12 … t, we get r_{k} = k … 21. Clearly, {r_{t}} ⊇ {r_{σ,t−1}} ⊇ … ⊇ {r_{σ,1}}.

Definition 3.1. Key of a permutation [23]. To each pair consisting of a permutation σ ∈ S_{t} and a sequence of nonnegative integers (l_{t}, …, l_{1}), Ehresmann [8] associated a key of shape m, here denoted by H_{σ(l_{t},...,l_{1})}, by taking the sequence (r_{t})^{l_{t}}, (r_{σ,t−1})^{l_{t−1}}, …, (r_{σ,1})^{l_{1}} of left reordered factors of σ; that is,

H_{σ(l_{t},...,l_{1})} := (r_{t})^{l_{t}} (r_{σ,t−1})^{l_{t−1}} ⋯ (r_{σ,1})^{l_{1}},

is the key of σ of shape m. In particular, H_{(l_{t},...,l_{1})} = (t ⋯ 21)^{l_{t}} ⋯ (21)^{l_{2}} (1)^{l_{1}}.

For i = 1, …, t, the letter a_{i} appears only in the columns r_{t}, …, r_{σ,i}. Hence, the multiplicity of a_{i} in H_{σ(l_{t},...,l_{1})} = (r_{t})^{l_{t}} (r_{σ,t−1})^{l_{t−1}} … (r_{σ,1})^{l_{1}} is ∑_{k=i}^{t} l_{k}, for i = 1, …, t. We put σm = (m_{1}, …, m_{t}), where m_{i} = ∑_{k=σ^{−1}(i)}^{t} l_{k}, i = 1, …, t. Hence H_{σ(l_{t},...,l_{1})} := (r_{t})^{l_{t}} (r_{σ,t−1})^{l_{t−1}} … (r_{σ,1})^{l_{1}} is also the key of σ with evaluation σm; equivalently, the unique tableau of evaluation σm and shape m.

Note that H_{σ(l_{j}e_{j})} = (r_{σ,j})^{l_{j}}, and H_{σ(l_{t},...,l_{1})} = (H_{σ(l_{t}e_{t})})^{l_{t}} … (H_{σ(l_{1}e_{1})})^{l_{1}}, with e_{j} = (δ_{i,j}), j = 1, …, t.

On the other hand, if T = q_{t} … q_{2} q_{1} is a key, with q_{t} = t … 2 1 and |q_{t−1}| > … > |q_{1}|, we get that column q_{k} is such that {q_{k}} = {q_{t}} \ {a_{t}, …, a_{k+1}} with {a_{t}, …, a_{k+1}} ⊆ {1, …, t}, 1 ≤ k ≤ t − 1. Putting σ := a_{1} … a_{t} this shows that H_{σ(1,...,1)} = T . Therefore, given a sequence (l_{t}, …, l_{1}) of positive integers,

σ ⟶ H_{σ(l_{t},...,l_{2},l_{1})} = (r_{t})^{l_{t}} (r_{σ,t−1})^{l_{t−1}} … (r_{σ,1})^{l_{1}},

defines an embedding of S_{t} into the set of tableaux of conjugate shape (t^{l_{t}}, …, 2^{l_{2}}, 1^{l_{1}}). For example, with σ = 3124 ∈ S_{4}, we have r_{4} = 4321, r_{s_{2},3} = 321, r_{s_{2},2} = 31, r_{s_{2},1} =

3, H_{σ(1,1,1,1)} = 4 3 3 2 2 3 1 1 1 3, and H_{σ(1,1,2,0)} = (4321)^{1}(321)^{1}(31)^{2}(3)^{0} = 4 3 3 2 2 3 3 1 1 1 1.

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

H_{s_{2}(1,1,2,0)} = (4321)^{1}(321)^{1}(31)^{2}(1)^{0} = 4 3 3 2 2 3 3 1 1 1 1 = H_{σ(1,1,2,0)}.

Let I := [t] \ {i}, with i ∈ [t], and let σ_{|I} := a_{1} … a_{t}_{|I} ∈ S_{I}. If σ^{−1}(i) = p, then letter a_{p} = i appears only in columns r_{t} …, r_{σ,p}. Hence, when we erase letter i in column r_{σ,p}, we obtain column r_{σ,p−1}, and we have

H_{σ(l_{t},...,l_{1})}_{|I} = H_{(σ_{|I})(l_{t},...,l_{p+1},l_{p}+l_{p−1},...,l_{1})}.

With σ = 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

H_{s_{4}(0,1,1,2,1)} = (54321)^{0}(5321)^{1}(321)^{1}(21)^{2}(1)^{1} = 5 3 3 2 2 2 2 1 1 1 1 1;

and with I = [5] \ {2},

(H_{s_{4}(0,1,1,2,1)})_{|I} = H_{(s_{4}_{|I})(0,1,1,2+1)} = (5431)^{0}(531)^{1}(31)^{1}(1)^{3} = 5 3 3 1 1 1 1 1.

Proposition 3.2. Let θ^{∗} ∈< θ_{1}^{∗} … θ_{t−1}^{∗} >, and let σ be a permutation in S_{t} with the same reduced decomposition. Then

(a) θ^{∗}(r_{k}) = r_{σ,k}, 1 ≤ k ≤ t.

(b) θ^{∗}(H_{(l_{t},...,l_{1})}) = H_{σ(l_{t},...,l_{1})} = (θ^{∗}(r_{t}))^{l_{t}} (θ^{∗}(r_{t−1}))^{l_{t−1}} ⋯ (θ^{∗}(r_{1}))^{l_{1}}.

Proof: Follows from Definition 3.1. □

When there is no danger of confusion, we will drop the ”(l_{t}, …, l_{1})” in the notation H_{σ(l_{t},...,l_{1})}, to denote a key of σ.

A word w over the alphabet [t] is said to be Yamanouchi [20] if any right factor v of w satisfies |v|_{1} ≥ |v|_{2} ≥ ⋯ ≥ |v|_{t}. This is equivalent to saying that w ∈ Sh((r_{t})^{l_{t}}, ⋯, (r_{1})^{l_{1}}), where (|v|_{1}, |v|_{2}, ⋯, |v|_{t}) = (l_{1} + ⋯ + l_{t}, …, l_{t−1} + l_{t}, l_{t}). Thus, for each (l_{t}, …, l_{2}, l_{1}), the key H_{(l_{t},...,l_{2},l_{1})} is a Yamanouchi tableau. Clearly, any shuffle of a Yamanouchi word is still a Yamanouchi word.

Proposition 3.3. [20, Lemma 5.4.7] The set of Yamanouchi words with evaluation m forms a single plactic class, whose representative word is the tableau H_{(l_{t},...,l_{2},l_{1})}.

Thus, the set of words obtained by shuffling the columns of H_{(l_{t},...,l_{2},l_{1})} and the one obtained by applying a finite sequence of Knuth transformations on the tableau H_{(l_{t},...,l_{2},l_{1})} are the same.

The dual of a tableau T is defined as the tableau with same shape and reverse evaluation, obtained by applying the Schützenberger involution to T . Thus the dual of H is H_{op}. On the other hand, if w ≡ H then w^{∗} ≡ H^{∗} ≡ H_{op}, where w^{∗} denotes the dual word of w. The characterization of Yamanouchi words given by Proposition 3.3 leads to the following definition.

Definition 3.2. Let t ≥ 1 and σ ∈ S_{t}. A word w over the alphabet [t] is said to be σ-Yamanouchi if w ≡ H_{σ}. In particular, when σ is the identity, w is a Yamanouchi word, and when σ is the reverse permutation, w is a dual Yamanouchi word.

Since the operations θ_{i}^{∗} are compatible with the plactic equivalence, we may characterize σ-Yamanouchi words using the operations θ_{i}^{∗} [21, 20] as well.

Proposition 3.4. Let t ≥ 1 and σ ∈ S_{t}. Let w be a word over the alphabet [t]. Then, w is a σ-Yamanouchi word if and only if θ_{i_{r}}^{∗} ⋯ θ_{i_{1}}^{∗}(w) is a Yamanouchi word, where s_{i_{1}} ⋯ s_{i_{r}} is a reduced decomposition of σ.

Proof: We have w ≡ H_{σ} if and only if θ^{∗}(w) ≡ θ^{∗}(H_{σ}) = H, where θ^{∗} = θ_{i_{r}}^{∗} ⋯ θ_{i_{1}}^{∗}. □

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

Proposition 3.5. Let σ ∈ S_{t}. If w and w′ are σ-Yamanouchi words over the alphabet [t], then any word in Sh(w, w′) is also a σ-Yamanouchi word.

Proof: Let u ∈ Sh(w, w′), and assume that w ≡ H(σ, (l_{t}, …, l_{1})) and w′ ≡ H(σ, (l′_{t}, …, l′_{1})). By Greene’s theorem [17], we find that the conjugate shape of P (u) is (t^{l_{t}+l′_{t}}, …, 1^{l_{1}+l′_{1}}), that is, P (u) = H(σ, (l_{t} + l′_{t}, …, l_{1} + l′_{1})). □

By induction, we may easily extend Proposition 3.5 to a shuffle of k σ-Yamanouchi words, for every k ∈ ℕ.

Corollary 3.6. Let i ∈ {1, …, t − 1}, w = sh((r_{t}))^{l_{t}}, …, (r_{1})^{l_{1}}) and let θ̃_{i}(w) = sh((θ_{i}^{∗}(r_{t}))^{l_{t}}, …, (θ_{i}^{∗}(r_{1}))^{l_{1}}). Then θ̃_{i}(w) is a s_{i}-Yamanouchi word.

Proposition 3.7. [23, 20] If B is an interval of A, then

w ≡ w′ implies w_{|B} ≡ w′_{|B}.

Corollary 3.8. Let w be a word over the alphabet A, and let A′ = A \ {f}. Then, P (w_{|A′}) = P (w)_{|A′}.

Proof: From the previous proposition, we have w_{|A′} ≡ P (w)_{|A′}. Thus P (w_{|A′}) is obtained from P (w) by removing the letters f. □

If w is a σ-Yamanouchi word then the word w_{|{i,i+1}} ≡ H_{σ}_{|{i,i+1}} and, thus, w_{|{i,i+1}} is either a Yamanouchi or dual Yamanouchi word for 1 ≤ i ≤ t−1. (Consider a shift of the alphabet {1, 2}.) Moreover, if w has evaluation (m_{1}, …, m_{t}), then w = sh(u, t^{m_{t}}) with u ≡ H_{σ(l_{t},...,l_{2},l_{1})}_{|[t−1]} and w_{|{t−1,t}} a Yamanouchi or dual Yamanouchi word.

The word 3121 ≡ 321 1 is a s_{1}-Yamanouchi word and 434 a dual Yamanouchi word. Nevertheless, considering the words in {w ∈ Sh(3121, 44) : w_{|{3,4}} = 434} = \{\underline{4}3\underline{4}121 ≡ 4321 41, \underline{4}31\underline{4}21 ≡ 4321 41, \underline{4}312\underline{4}1 ≡ 4321 1 4, \underline{4}3121\underline{4} ≡ 4321 1 4\} we find that \underline{4}312\underline{4}1, \underline{4}3121\underline{4} are not σ-Yamanouchi words, for any σ ∈ \{4213; 2413; 2143; 2134} ⊆ S_{4}.

This leads to the following question: given I = [t]\{i}, with i ∈ [t], and u ∈ I^{∗} congruent to the key of evaluation (m_{1}, …, m_{i−1}, m_{i+1}, …, m_{t}), under which conditions can u be embedded in a word congruent to the key of evaluation (m_{1}, …, m_{t})?

The answer is given by the following proposition.

Proposition 3.9. Let w ∈ [t]^{∗} and σ ∈ S_{t}. Given i ∈ [t], let I = [t] \ {i}, and suppose w_{|I} ≡ H_{σ}_{|I}. Then, w is a σ-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 θ_{j}^{∗}(w)_{|[j]} ≡ H_{s_{j}σ}_{|[j]}, for j = i − 1, …, t − 1.

Proof: 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 θ_{j}^{∗}(w)_{|[j]} ≡ H_{s_{j}σ}_{|[j]}, for j = i − 1, …, t − 1.

We start with the case i = t, and thus, I = [t − 1]. Consider (m_{1}, …, m_{t}), the evaluation of w, and assume without loss of generality that m_{t−1} ≥ m_{t}. From the equality P (w_{|_{[t−1]}}) = P (w)_{|[t−1]} = H_{σ}_{|[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}} ≡ 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 (θ_{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 (θ_{t−1}^{∗}(w)) = θ_{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 (θ_{t−1}^{∗}(w)_{|[t−1]}) = H_{s_{t−1}σ}_{|[t−1]}. This is absurd.

Assume now that i ≠ t. Then, w_{|[i−1]} ≡ H_{σ}_{|[i−1]}, and since w_{|{i−1,i}} is either a Yamanouchi or a dual Yamanouchi word, and θ_{i−1}^{∗}(w)_{|[i−1]} ≡ H_{s_{i−1}σ}_{|[i−1]}, by the case i = t we find that

w_{|[i]} ≡ H_{σ}_{|[i]}.

Next, note that w_{|{i,i+1}} is either a Yamanouchi or a dual Yamanouchi word, and that θ_{i}^{∗}(w)_{|[i]} ≡ H_{s_{i}σ}_{|[i]}. Thus, again by the case i = t, we must have

w_{|[i+1]} ≡ H_{σ}_{|[i+1]}.

Noticing that, since w_{|I} ≡ H_{σ}_{|I}, the word w_{|{j,j+1}} is either Yamanouchi or dual Yamanouchi, for j = i + 1, …, t − 1, we may repeat the process described above for j = i + 1, …, t − 1, obtaining w_{|[t]} ≡ H_{σ}_{|[t]}. □

For instance, in the alphabet [5], let I := [5] \ {3}, σ = 51324 ∈ S_{5}, and consider the key H_{σ(1,0,2,0,1)} = 543215315315, associated with σ and (1, 0, 2, 0, 1), and the word w_{|I} := 555415211 ≡ H_{σ(1,0,2,0,1)}_{|I}. Define w = 553541352131. Since w_{|{2,3}} = 3323 is dual Yamanouchi, w_{|{3,4}} = 3433 is Yamanouchi, θ_{2}^{∗}(w)_{|[2]} = 212121 ≡ H_{s_{2}σ}_{|[2]}, θ_{3}^{∗}(w)_{|[3]} = 13211 ≡ H_{s_{3}σ}_{|[3]}, and θ_{4}^{∗}(w)_{|[4]} = 44341342131 ≡ H_{s_{4}σ}_{|[4]}, by the previous theorem the word w is σ-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, θ_{2}^{∗}(w)_{|[2]} = 221211 ≡ H_{s_{2}σ}_{|[2]}, and θ_{3}^{∗}(w)_{|[3]} = 13211 ≡ H_{s_{3}σ}_{|[3]}, w′ is not a σ-Yamanouchi word since θ_{4}^{∗}(w′)_{|[4]} = 43344134211 is not in the plactic class of H_{s_{4}σ}_{|[4]}.

Given the word w = w_{1}w_{2} ⋯ w_{k} ∈ A^{∗} and P = {i_{1}, …, i_{l}} ⊆ [k], we define the restriction of w to the set P by w|P := w_{i_{1}} ⋯ w_{i_{l}}. If w, w′ ∈ A^{∗} have lengths k and k′, respectively, and P ⊆ [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 [16]. 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}.

Corollary 3.10. Let w = sh_{P} (t^{r}, u) ≡ H_{σ} with u ∈ [t − 1]^{∗}. If w′ = sh_{Q}(t^{r}, u) with Q ≤ P, then w′ ≡ H_{σ}.

Proof: By induction on t. If t = 1, 2, the claim is obvious. Let t ≥ 3 and write

θ_{t−1}^{∗}(w)_{|[t−1]} = shP̃((t − 1)^{r}, w_{|[t−2]}) ≡ H_{s_{t−1}σ}_{|[t−1]},
θ_{t−1}^{∗}(w′)_{|[t−1]} = shQ̃((t − 1)^{r}, w_{|[t−2]}).

Clearly, we must have Q̃ ≤ P̃. Then, by induction, it follows that θ_{t−1}^{∗}(w′)_{|[t−1]} ≡ H_{s_{t−1}σ}_{|[t−1]}, and by the previous proposition, we find that w′ ≡ H_{σ}. □

An operation θ_{i} may not act on the set {H_{σ} : σ ∈ S_{t}}. For example, consider H = 4321 21, and θ_{2}(H) = θ_{2}(4321 21) = 433121 ∉ {H_{σ} : σ ∈ S_{t}}. Although 433121 ≡ 4321 31 = H_{s_{2}}, we may have even worse w = 314321 ≡ H_{s_{2}s_{1}} and θ_{2}(w) = 314221 ≡ 321 41 2 ∉ {H_{σ} : σ ∈ S_{t}}. Nevertheless, it is possible to give a criterion on θ_{i} such that if w ≡ H_{σ} then θ_{i}(w) ≡ H_{s_{i}σ}.

The criterion given by the previous proposition can be generalized to the operations θ_{i}.

Lemma 3.11. Let w ∈ [t]^{∗} and w_{|{t−1,t}} a Yamanouchi or dual Yamanouchi word. Let u = θ_{t−1}(w), z = θ_{t−1}^{∗}(w) and v = w_{|[t−2]}. Then

w_{|[t−1]} = sh_{P} (u_{|{t−1}}, v) and w_{|[t−1]} = sh_{Q}(z_{|{t−1}}, v), with Q ≤ P.

Proof: It is enough to consider the cases w_{|{t−1,t}} = tt−1t−1 and w_{|{t−1,t}} = ttt−1. Therefore, if θ_{t−1} ≠ θ_{t−1}^{∗}, we have

θ_{t−1}(t t − 1 t − 1) = t t \underline{t − 1},
θ_{t−1}^{∗}(t t − 1 t − 1) = t \underline{t − 1} t,

and

θ_{t−1}(t t t − 1) = t \underline{t − 1} \underline{t − 1},
θ_{t−1}^{∗}(t t t − 1) = \underline{t − 1} t \underline{t − 1}.
□

Theorem 3.12. Let w ∈ [t]^{∗} and σ ∈ S_{t}. Given i ∈ [t], let I = [t] \ {i}, and suppose that w_{|I} ≡ H_{σ}_{|I}. Then, w is a σ-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 θ_{j}(w)_{|[j]} ≡ H_{s_{j}σ}_{|[j]}, for some operation θ_{j}, j = i − 1, …, t − 1.

Proof: According to the previous lemma and corollary, if θ_{j}(w)_{|[j]} ≡ H_{s_{j}σ}_{|[j]}, then θ_{j}^{∗}(w)_{|[j]} ≡ H_{s_{j}σ}_{|[j]}, for j = i − 1, …, t − 1. By the previous proposition, it follows that w ≡ H_{σ}. □

Corollary 3.13. Let w ∈ [t]^{∗}, t ≥ 2, and σ ∈ S_{t}. If w ≡ H_{σ}, then θ_{i}(w) ≡ H_{s_{i}σ} if and only if (θ_{i}w)_{|{i+1,i+2}} is either a Yamanouchi or a dual Yamanouchi word, θ_{i}(w)_{|[i]} ≡ H_{s_{i}σ}_{|[i]}, and θ_{j}(θ_{i}(w))_{|[j]} ≡ H_{s_{j}s_{i}σ}_{|[j]}, for some operation θ_{j}, j = i+1, …, t− 1.

Proof: Taking θ_{j} = θ_{j}^{∗}, j = i + 1, …, 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, θ_{i}(w)_{|[i]} ≡ H_{s_{i}σ}_{|[i]}, and θ_{j}(θ_{i}(w))_{|[j]} ≡ H_{s_{j}s_{i}σ}_{|[j]}, for j = i + 1, …, t − 1.

Since θ_{i}(w)_{|[i]} ≡ H_{s_{i}σ}_{|[i]}, θ_{i}w_{|{i,i+1}} is either a Yamanouchi or a dual Yamanouchi word, and θ_{i}(θ_{i}(w)_{|[i]}) = w_{|[i]} ≡ H_{σ}_{|[i]}, by the previous theorem we must have

θ_{i}(w)_{|[i+1]} ≡ H_{s_{i}σ}_{|[i+1]}.

Now, since (θ_{i}w)_{|{i+1,i+2}} is either a Yamanouchi or a dual Yamanouchi word, and there is an operation θ_{i+1} such that θ_{i+1}(θ_{i}(w))_{|[i+1]} ≡ H_{s_{i+1}s_{i}σ}_{|[i+1]}, again by the previous theorem, we find that

θ_{i}(w)_{|[i+2]} ≡ H_{s_{i}σ}_{|[i+2]}.

Finally, note that, since θ_{i}(w)_{|{j,j+1}} = w_{|{j,j+1}}, the word θ_{i}(w)_{|{j,j+1}} is either a Yamanouchi or a dual Yamanouchi word, for j = i+2, …, t−1. Therefore, repeating the process above for j = i + 2, …, t − 1, we obtain θ_{i}(w)_{|[t]} ≡ H_{s_{i}σ}_{|[t]}. □

Remark 3.1. In particular, it follows from the previous theorem and the corresponding statement for dual words, that θ_{1}(w) ≡ H_{s_{1}σ} if and only if θ_{1}(w)_{|[2,t]} ≡ H_{s_{1}σ}_{|[2,t]}.

Consider w = 43143213321 a σ-Yamanouchi word, where σ = 3124, and the keys H_{σ(2,0,1,1)} = 4321 4321 31 3 and H_{s_{2}σ(2,0,1,1)} = 4321 4321 21 2. We have θ_{2}^{∗}(w) = 42143212321 ≡ H_{s_{2}σ}, but θ_{2}(w) = 43142213221 is not a s_{2}σ-Yamanouchi word. Note that although θ_{2}(w)_{|{3,4}} = 4343 is Yamanouchi, θ_{2}(w)_{|[2]} = 1221221 is not in the plactic class of H_{s_{2}σ}_{|[2]}. The word θ′_{2}(w) = 42143213221 is a s_{2}σ-Yamanouchi word, since θ′_{2}(w)_{|{3,4}} = 4433 is Yamanouchi, θ′_{2}(w)_{|[2]} = 2121221 ≡ H_{s_{2}σ}_{|[2]}, and θ_{3}^{∗}(θ′_{2}(w))_{|[3]} = θ′_{2}(w)_{|[3]} = 213213221 ≡ H_{s_{3}s_{2}σ}_{|[3]}.

4. σ-Yamanouchi words as shuffles of columns of a key

It has been shown in [6] that, when t ≤ 3, a word in [t]^{∗} of evaluation m is σ-Yamanouchi if and only if it is a shuffle of the columns of H_{σ(l_{t},...,l_{1})}. For t ≥ 4 this is no longer true in general. For example, consider the Yamanouchi tableau 4321 21 and 421321 = sh(4321, 21). We have θ_{3}^{∗}θ_{2}^{∗}(421321) = θ_{3}^{∗}(431321) = 431421 ≡ sh(4321, 41), but 431421 is not a shuffle of the columns of s_{3}s_{2}-Yamanouchi tableau 4321 41. We have already seen that shuffling together the columns of H_{σ} has the same effect as performing Knuth transformations on the tableau H_{σ}. 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}, …, u_{k}), k ≥ 2, where u_{1}, …, u_{k} are columns pairwise comparable in the inclusion order. From Propositions 2.1 and 2.2 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} ⊆ {u}.

Lemma 4.1. Let u_{1}, u_{2} be columns in A^{∗}, and x, z ∈ A such that zu_{1}u_{2}x is a column. Then,

(i) sh(u_{2}, u_{1}u_{2}x) ∈ Sh(u_{2}x, u_{1}u_{2}).

(ii) sh(u_{1}, zu_{1}u_{2}) ∈ Sh(zu_{1}, u_{1}u_{2}).

Proof: (i) Write u_{2} = a_{1} ⋯ a_{r}, and sh(u_{2}, u_{1}u_{2}x) = c_{1} ⋯ c_{l}. For each j = 1, …, r, let p_{j} := min{i : c_{i} = a_{j}}, and let p′ ∈ [l] such that c_{p′} = z. Then, it is clear that

sh(u_{2}, u_{1}u_{2}x) = sh_{P} (u_{2}x, u_{1}u_{2}),

where P := {p_{1}, …, p_{r}, p′}.

(ii) Write u_{1} = a_{1} ⋯ a_{r}, and sh(u_{1}, zu_{1}u_{2}) = c_{1} ⋯ c_{l}. For each j = 1, …, r, let p_{j} := max{i : c_{i} = a_{j}}, and let p′ ∈ [l] such that c_{p′} = x. Then, we have

sh(u_{1}, zu_{1}u_{2}) = sh_{P} (zu_{1}, u_{1}u_{2}),

where P := {p_{1}, …, p_{r}, p′}. □

Lemma 4.2. Let u and v be columns in A^{∗} with u = u_{1}u_{2}zyxu_{3}u_{4} and v = u_{2}zxu_{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.

Proof: As before, the only cases to consider are the application of the elementary Knuth transformations zxy ≡ xzy and yzx ≡ 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_{1}u_{2}z) and w_{2} = sh(xu_{3}u_{4}, u_{3}).

In the case of the elementary Knuth transformation zxy ≡ xzy, we have

sh(u, v) = w_{1}\underline{z} \underline{x} \overline{y}w_{2} ≡ w_{1}\underline{x} \underline{z} \overline{y}w_{2},  (4)

where w_{1} = sh(u_{2}, u_{1}u_{2}z), w_{2} = sh(xu_{3}u_{4}, u_{3}). By Lemma 4.1 (i), we must have w_{1} = sh_{P} (u_{2}z, u_{1}u_{2}), for some set P. Thus, we have for the right-hand side of (4) that

w_{1}xzyw_{2} = sh(u_{2}z\underline{x}u_{3}, u_{1}u_{2}\underline{z} \overline{y} xu_{3}u_{4}) ∈ Sh(u, v).

The case of the elementary Knuth transformation yzx ≡ yxz is analogous to the previous one. □

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 ≡ 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.

Definition 4.1. Let w ∈ A^{∗} be a column. We say that w has a gap of size q ≥ 0, with respect to the alphabet A, if there exists a factor j + k j, k ≥ 1, of w such that |[j + 1, j + k − 1] ∩ A| = q.

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}.

Theorem 4.3. Let H be a key with first column A. Then, the Knuth class of H 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.

Proof: The only if part. Assume that each column of H is either an interval of A or is obtained from an interval of A by removing a single letter, and let w ≡ H. We may assume, without loss of generality, that w is obtained by performing a single elementary Knuth transformation xzy ≡ zxy, or yzx ≡ yxz, with x < y < z, on a shuffle of two columns of H, say u and v, such that zx is a factor of v and y is a letter of u. Since {v} ⊆ {u}, we must have u = u_{1}u_{2}zyxu_{3}u_{4}, and v = u_{2}zxu_{3}, for some columns u_{i}, i = 1, 2, 3, 4. Since, by Lemma 4.2, the set Sh(u, v) is closed under Knuth transformations, we find that w is still a shuffle of the columns of H.

The if part. Suppose that the key H = Av_{2} ⋯ 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 ≤ i ≤ k. Without loss of generality, we may assume that in these cases, v_{i} has one of the following forms:

(i) v_{i} = u_{2}dau_{3}, where u_{2} = s(s − 1) ⋯ d + 1, u_{3} = (a − 1) ⋯ (r + 1)r, with s, r, d, a ∈ [t] such that d − a = 3;

(ii) v_{i} = u_{2}fdu_{3}cau_{4}, where u_{2} = s(s − 1) ⋯ (f + 1), u_{3} = (d − 1) ⋯ (c + 1), and u_{4} = (a − 1) ⋯ (r + 1)r, with f − d, c − a = 2.

Let w_{1} = v_{2} ⋯ v_{i−1}v_{i+1} ⋯ v_{k}. In case (i), write A = u_{1}u_{2}dcbau_{3}u_{4} and consider the word

H ≡ w_{1}\underline{u}_{2} u_{1} u_{2} d c (\underline{d} \underline{a} b) a u_{3} u_{4} \underline{u}_{3},  (5)

where the underlined letters define column v_{i} and the remaining define column A. Applying the transformation dab ≡ adb on (5), we get

(5) ≡ w_{1}\overline{u}_{2} u_{1} u_{2} d c (\overline{a} \overline{d} b) a u_{3} u_{4} \overline{u}_{3}.  (6)

Clearly, the right-hand side of (6) is in the plactic class of H, but is not a shuffle of its columns.

In case (ii), write A = u_{1}u_{2}fedu_{3}cbau_{4}u_{5}, and consider the following word

H ≡ w_{1}u_{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},  (7)

where the underlined letters define column v_{i}. Applying the transformation cab ≡ acb on (7), we get

(7) ≡ w_{1}u_{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}.  (8)

As in case (i), it is clear that the right-hand side of (8) is in the plactic classe of H, but is not a shuffle of its columns. □

Corollary 4.4. [6] If σ = id or the reverse permutation t t − 1 ⋯ 2 1, a word over the alphabet [t] is a σ-Yamanouchi word if and only if it is a shuffle of the columns of H_{σ}.

Corollary 4.5. (a) If H is a key over a three-letter alphabet, then the Knuth class of H equals the set of shuffles of its columns.

(b) [6] If σ ∈ S_{t}, t = 2, 3, a word over the alphabet [t] is a σ-Yamanouchi word if and only if it is a shuffle of the columns of H_{σ}.

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 H be a key of evaluation (m_{1}, …, m_{t}) and consider the planar representation obtained by drawing m_{i} bullets in row i, for i = 1, …, t. After deleting empty rows we are in the ambient alphabet of the first column of H and the condition stated in Theorem 4.3 says that the plactic class of H 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 H(σ, (0, 1, …, 1)), with σ = 5716432 ∈ S_{6}, is

\begin{aligned}7 & • & • & • & • & • \\ 6 & • & • & • \\ 5 & • & • & • & • & • & • \\ 4 & • & • \\ 3 & • \\ 1 & • & • & • & • \\ & 2 & 3 & 4 & 5 & 6 & 7 \end{aligned} .

The conjugate shape of H(σ, (0, 1, …, 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 H_{σ,(0,1,...,1)} is not the set of all shuffles of its columns. On the other hand, the plactic class of H_{σ,(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),

7 • • •
6 • •
5 • • • •
4 • •
3 •
1 • •
2 3 6 7

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 S_{t}, t > 3, there are permutations for which the associated keys do not satisfy the conditions of Theorem 4.3. For s_{3}s_{2} = 1423 ∈ S_{4} we have H_{s_{3}s_{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_{3}s_{2}- Yamanouchi word and is not a shuffle of the columns of the tableau H_{s_{3}s_{2}} = 4321 41. It is easy to check that in S_{4}, the only permutations for which there are associated keys that fail to satisfy the conditions of Theorem 4.3 are 1423, 1432, 4123 and 4132.

Corollary 4.6. (a) Let H be a key with first column A = {a, b, c, d}. Then the plactic class of H is the shuffle of its columns if and only if H does not contain the column d a.

(b) Let σ ∈ S_{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 H_{σ(l_{4},l_{3},l_{2},l_{1})} is Sh((r_{4})^{l_{4}}, (r_{σ,3})^{l_{3}}, (r_{σ,2})^{l_{2}}, (r_{σ,1})^{l_{1}}) if and only if σ is in S_{4} \ {1423, 1432, 4123, 4132}.

In the Appendix, the permutations of S_{5} and S_{6}, such that the set Sh((r_{t})^{l_{t}}, (r_{σ,t−1})^{l_{t−1}}, …, (r_{σ,2})^{l_{2}}, (r_{σ,1})^{l_{1}}), with l_{i} > 0, i = 1, …, t, t = 5, 6, is not the whole plactic class of H_{σ}, are listed.

For t > 3 the columns of H_{σ} are not enough to characterize the σ-Yamanouchi words in terms of shuffling them together. In the case of S_{4}, the next theorem shows that it is necessary and sufficient to include the word 431421 in the set of distinct columns of H_{σ(l_{4},...,l_{1})}, l_{4}, l_{2} > 0, to characterize by shuffle operations the σ-Yamanouchi words over the alphabet [4], for any σ ∈ {1423, 1432, 4123, 4132}.

Theorem 4.7. Let σ ∈ S_{4}, and let (l_{4}, …, l_{1}) be a sequence of nonnegative integers with l_{4} > 0. Then, the plactic class of H_{σ(l_{4},...,l_{1})} is

Sh((r_{4})^{l_{4}}, (r_{σ,3})^{l_{3}}, (r_{σ,2})^{l_{2}}, (r_{σ,1})^{l_{1}}), if l_{2} = 0 or σ ∈ S_{4} \{1423, 1432, 4123, 4132}, (9)

and, otherwise,

Sh((r_{4})^{l_{4}}, (r_{σ,3})^{l_{3}}, (r_{σ,2})^{l_{2}}, (r_{σ,1})^{l_{1}}) ∪ Sh((431421)^{n_{5}}, (r_{4})^{n_{4}}, (r_{σ,3})^{n_{3}}, (r_{σ,2})^{n_{2}}, (r_{σ,1})^{n_{1}}),

(10)

where ∑_{j=1}^{4} l_{j}|r_{σ,j}|_{i} = n_{5}|431421|_{i} + ∑_{j=1}^{4} n_{j}|r_{σ,j}|_{i}, for i = 1, 2, 3, 4.

Proof: Assume l_{2} > 0, otherwise the conditions of Theorem 4.3 hold. When σ ∈ S_{4} \{1423, 1432, 4123, 4132}, we have already proved in Corollary 4.6 that the plactic class of H_{σ(l_{4},...,l_{1})} is the set

Sh(H_{σ(l_{4},...,l_{1})}) = Sh((r_{4})^{l_{4}}, (r_{σ,3})^{l_{3}}, (r_{σ,2})^{l_{2}}, (r_{σ,1})^{l_{1}}).

Assume now that σ ∈ {1423, 1432, 4123, 4132}, noticing that r_{σ,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 H_{σ(l_{t},...,l_{1})}, is when the Knuth transformation zxy ≡ xzy or yzx ≡ yxz involves three distinct letters, z > y > x, with zx a factor of a column, and y a letter of another column of H_{σ}. Thus, using Lemma 4.2, we find that any word obtained by application of a single Knuth transformation on a shuffle of two columns of H_{σ(l_{4},...,l_{1})}, other than sh(r_{4}, r_{σ,2}) = 43\underline{4}\underline{1}21, is still a shuffle of the columns of H_{σ(l_{4},...,l_{1})}.

In the case of the shuffle sh(r_{4}, r_{σ,2}) = 43\underline{4}\underline{1}21, the application of the transformation 341 ≡ 314 or 412 ≡ 142 gives the word 431421, which is not a shuffle of the columns of H_{σ(l_{4},...,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_{σ,3}, r_{σ,2}, r_{σ,1}}, shows that the resulting word is still a shuffle of two, or more, words of this set.

Thus, if w ≡ H_{σ(l_{4},...,l_{1})}, w is obtained by a finite number of Knuth transformations on H_{σ(l_{4},...,l_{1})}. Hence, it must be a shuffle of the words 431421, r_{4}, r_{σ,3}, r_{σ,2}, and r_{σ,1}, with appropriate multiplicities. □

5. Matrix realizations of pairs of tableaux

Let R_{p} be a local principal ideal domain with maximal ideal (p). The matrices under consideration have entries in R_{p}. Let U_{n} be the group of n × n unimodular matrices over R_{p}. Given n×n matrices A and B, we say that B is left equivalent to A (written B ∼_{L} A) if B = UA for some unimodular matrix U; B is right equivalent to A (written B ∼_{R} A) if B = AV for some unimodular matrix V; and B is equivalent to A (written B ∼ A) if B = UAV for some unimodular matrices U, V. The relations ∼_{L}, ∼_{R} and ∼ are equivalence relations on the set of all n × n matrices over R_{p}.

Let A be an n×n non-singular matrix. By the Smith normal form theorem [7, 26], there exist nonnegative integers λ_{1}, ..., λ_{n} with λ_{1} ≥ ... ≥ λ_{n} such that A is equivalent to the diagonal matrix

diag(p^{λ_{1}}, ..., p^{λ_{n}}).

The sequence λ = (λ_{1}, ..., λ_{n}) of exponents of the p-powers in the Smith normal form of A is a partition of length ≤ n uniquely determined by the matrix A. The partition λ is a full invariant of the equivalence class containing A and we call λ the 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 ⊆ [n], we write χ^{J} = (f_{1}, ..., f_{n}) with f_{i} = 1 if i ∈ J and 0 otherwise, thus, we put D_{J} := diag_{p}(χ^{J}). Given a partition λ of length ≤ n, we write Δ_{λ} = diag_{p}(λ). If λ = (0), Δ_{(0)} = I_{n} the identity matrix of order n.

Let σ ∈ S_{t}, t ≥ 1, and let m be a partition of length t such that σm = (m_{1}, …, m_{t}). In what follows, T will denote a skew-tableau of evaluation (m_{1}, ..., m_{t}) and shape λ/μ where the length of λ is ≤ n. Next we define the matrix realization of a pair of Young tableaux (T , F), with F a tableau of evaluation (m_{1}, ..., m_{t}) and shape ν, following [5, 6, 4]. (Note that in this paper the tableaux are strictly increasing up along columns.)

Definition 5.1. Let T = (λ^{0}, λ^{1}, ..., λ^{t}) and F = (0, μ^{1}, ..., μ^{t}) be tableaux, both of evaluation (m_{1}, ..., m_{t}). We say that a sequence of n × n non-singular matrices A_{0}, B_{1}, ..., B_{t} is a matrix realization of the pair of tableaux (T , F) (or realizes (T , F)) if:

I. For each r ∈ {1, ..., t}, the matrix B_{r} has invariant partition (1^{m_{r}}, 0^{n−m_{r}}). II. For each r ∈ {0, 1, ..., t}, the matrix A_{r} := A_{0}B_{1}...B_{r} has invariant partition

the conjugate of λ^{r}. III. For each r ∈ {1, ..., t}, the matrix B_{1}...B_{r} has invariant partition the conjugate

of μ^{r}. (T , F) is called an admissible pair of tableaux.

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 (T , H_{σ(l_{t},...,l_{1})}). The next theorem, proved in [6, 4], shows that, without loss of generality, we may consider matrix realizations of (T , H_{σ(l_{t},...,l_{1})}) with a particular simple form.

Theorem 5.1. The following conditions are equivalent:

(a) (T , H_{σ(l_{t},...,l_{1})}) is an admissible pair.

(b) There exists U ∈ U_{n} such that Δ_{λ}U, D_{[m_{1}]}, ..., D_{[m_{t}]} realizes (T , H_{σ(l_{t},...,l_{1})}).

The characterization of σ-Yamanouchi words as shuffles of the columns H_{σ} has been used to determine necessary and sufficient conditions for the admissibility of a pair of Young tableaux (T , H_{σ(l_{t},...,l_{1})}), when σ is the identity or the reverse permutation in S_{t}, t ≥ 1 [4, 5], or any permutation in S_{3} [6]. In these cases, the pair (T , H_{σ(l_{t},...,l_{1})}) is admissible only if the word of T is in the Knuth class of H_{σ(l_{t},...,l_{1})}). The next theorem extends the necessary condition of this result to any σ ∈ S_{t}, t ≥ 1, and verifies the recursive criterion for σ-Yamanouchi words given in Theorem 3.12. The proof of this theorem needs the following proposition, proved in [6].

Proposition 5.2. [6] Let (m_{1}, m_{2}) be a partition. Let w and w′ be the words of the tableaux realized by the sequences Δ_{λ}U, D_{[m_{1}]}, D_{[m_{2}]} and Δ_{λ}U, D_{[m_{2}]}, D_{[m_{1}]}, respectively. Then, there exists an operation θ_{1} such that w′ = θ_{1}(w).

The following example shows that the operation θ_{1} in the previous proposition is not necessarily θ_{1}^{∗}.

Example 5.1. Let U = P_{4321}T_{14}(p), where P_{4321} is the permutation matrix associated with 4321 ∈ S_{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 λ = (2, 1) and U = P_{4321}T_{14}(p), the sequences Δ_{λ}U, D_{[3]}, D_{[2]} and Δ_{λ}U, D_{[2]}, D_{[3]} are matrix realizations for the pairs (T , H(id, (2, 1))) and (T′, H(s_{1}, (2, 1)), where

T = \begin{matrix}2 \\ • & 1 & 2 \\ • & • & 1 & 1 \end{matrix} and T′ = \begin{matrix}2 \\ • & 2 & 2 \\ • & • & 1 & 1 \end{matrix}. The words w(T ) = 21211 and w(T′) = 22211

satisfy θ_{1}(w(T )) = w(T′), where θ_{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ützenberger. However, if we choose U′ = P_{3241}T_{24}(p), the sequences Δ_{λ}U′, D_{[3]}, D_{[2]} and Δ_{λ}U′, D_{[2]}, D_{[3]} are matrix real-

izations for the pairs (T , H(id, (2, 1))) and (T′′, H(s_{1}, (2, 1)), where T′′ = \begin{matrix}2 \\ • & 1 & 2 \\ • & • & 1 & 2 \end{matrix}.

In this case, we have θ_{1}^{∗}(w(T )) = w(T′′) = 21212 ≠ θ_{1}(T ) = 22211.

Theorem 5.3. Let σ ∈ S_{t}, and let (l_{t}, ⋯, l_{1}) be a sequence of nonnegative integers. The pair (T , H_{σ(l_{t},...,l_{1})}) is admissible only if w(T ) ≡ H_{σ(l_{t},...,l_{1})}.

Proof: By induction on t ≥ 1. When t = 1 there is nothing to prove, and the case t = 2 has been proved in [5, 4]. Assume the claim for t − 1 ≥ 2. Thanks to Theorem 5.1 we may assume the existence of an unimodular matrix U ∈ U_{n} such that Δ_{λ}, UD_{[m_{1}]}, …, D_{[m_{t}]} realizes (T , H_{σ(l_{t},...,l_{1})}). Put w := w(T ). By the inductive step, the word w_{|[t−1]} of the tableau realized by the sequence

Δ_{λ}, UD_{[m_{1}]}, …, D_{[m_{t−1}]}

satisfies P (w_{|[t−1]}) = H_{σ}_{|[t−1]}.

We consider the case m_{t−1} ≥ m_{t}, the other one is similar. There exists an unimodular matrix U′ ∈ U_{n} such that

Δ_{λ}UD_{[m_{1}]} ⋯ D_{[m_{t−1}]}D_{[m_{t}]} ∼_{L} Δ′U′D_{[m_{t−1}]}D_{[m_{t}]},

where Δ′ = diag_{p}(λ + χ^{J_{1}} + ⋯ + χ^{J_{t−2}}). Since m_{t−1} ≥ m_{t}, by the case t = 2, the sequence Δ′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

Δ_{λ}U, D_{[m_{1}]}, ⋯, 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′ = (θ_{t−1}(w))_{|[t−1]}, for some operation θ_{t−1}, and by the inductive step, P (w′) = H_{s_{t−1}σ}_{|[t−1]}. By Theorem 3.12, we find that w is a σ-Yamanouchi word. □

6. Appendix

Below we list the permutations σ in S_{5} and S_{6} for which the set Sh((r_{t})^{l_{t}}, (r_{σ,t−1})^{l_{t−1}}, …, (r_{σ,2})^{l_{2}}, (r_{σ,1})^{l_{1}}), with l_{i} > 0, i = 1, …, t, t = 5, 6, is not the whole plactic class of H_{σ}.

S_{5}

w4w′, w ∈ S_{{2,5}}, w′ ∈ S_{{1,3}};
w3w′, w ∈ S_{{2,5}}, w′ ∈ S_{{1,4}};
ww′, w ∈ S_{{1,4,5}}, w′ ∈ S_{{2,3}};
ww′, w ∈ S_{{1,3,5}}, w′ ∈ S_{{2,4}};
w3w′, w ∈ S_{{1,4}}, w′ ∈ S_{{2,5}};
w2w′, w ∈ S_{{1,4}}, w′ ∈ S_{{3,5}};
ww′, w ∈ S_{{1,2,5}}, w′ ∈ S_{{3,4}}.

S_{6}

ww′w′′, w ∈ S_{{3,6}}, w′ ∈ S_{{4,5}}, w′′ ∈ S_{{1,2}};
ww′w′′, w ∈ S_{{2,5}}, w′ ∈ S_{{3,4}}, w′′ ∈ S_{{1,6}};
ww′w′′, w ∈ S_{{1,4}}, w′ ∈ S_{{2,3}}, w′′ ∈ S_{{5,6}};
w4w′, w ∈ S_{{2,5,6}}, w′ ∈ S_{{1,3}};
w5w′, w ∈ S_{{2,4,6}}, w′ ∈ S_{{1,3}};
w46w′, w ∈ S_{{2,5}}, w′ ∈ S_{{1,3}};
w52w′, w ∈ S_{{3,6}}, w′ ∈ S_{{1,4}};
w3w′, w ∈ S_{{2,5,6}}, w′ ∈ S_{{1,4}};
w5w′, w ∈ S_{{2,3,6}}, w′ ∈ S_{{1,4}};
w36w′, w ∈ S_{{2,5}}, w′ ∈ S_{{1,4}};
w42w′, w ∈ S_{{3,6}}, w′ ∈ S_{{1,5}};
w3w′, w ∈ S_{{2,4,6}}, w′ ∈ S_{{1,5}};
w4w′, w ∈ S_{{2,3,6}}, w′ ∈ S_{{1,5}};
ww′, w ∈ S_{{1,4,5,6}}, w′ ∈ S_{{2,3}};
ww′, w ∈ S_{{1,3,5,6}}, w′ ∈ S_{{2,4}};
ww′, w ∈ S_{{1,3,4,6}}, w′ ∈ S_{{2,5}};
w3w′, w ∈ S_{{1,4,5}}, w′ ∈ S_{{2,6}};
w4w′, w ∈ S_{{1,3,5}}, w′ ∈ S_{{2,6}};
w35w′, w ∈ S_{{1,4}}, w′ ∈ S_{{2,6}};
ww′, w ∈ S_{{1,2,5,6}}, w′ ∈ S_{{3,4}};
ww′, w ∈ S_{{1,2,4,6}}, w′ ∈ S_{{3,5}};
w41w′, w ∈ S_{{2,5}}, w′ ∈ S_{{3,6}};
w2w′, w ∈ S_{{1,4,5}}, w′ ∈ S_{{3,6}};

\begin{matrix}w4w′, & w ∈ S_{\{1,2,5\}}, & w′ ∈ S_{\{3,6\}}; \\ w25w′, & w ∈ S_{\{1,4\}}, & w′ ∈ S_{\{3,6\}}; \\ ww′, & w ∈ S_{\{1,2,3,6\}}, & w′ ∈ S_{\{4,5\}}; \\ w31w′, & w ∈ S_{\{2,5\}}, & w′ ∈ S_{\{4,6\}}; \\ w2w′, & w ∈ S_{\{1,3,5\}}, & w′ ∈ S_{\{4,6\}}; \\ w3w′, & w ∈ S_{\{1,2,5\}}, & w′ ∈ S_{\{4,6\}}. \end{matrix}

There are a total of 52 permutations in S_{5} and 488 permutations in S_{6} that fail to satisfy the conditions of Theorem 4.3.

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 [17].

References

[1] G. Appleby, A simple approach to matrix realizations for Littlewood–Richardson sequences, Linear and Multilinear Algebra 291 (1999), 1–14.

[2] O. Azenhas, Realizações Matriciais de Quadros de Young e suas Formas Canónicas (in Portuguese), Ph.D. thesis, Universidade de Coimbra, Coimbra, 1991.

[3] , A regra de Littlewood–Richardson: Generalizações e realizações matriciais (in Portuguese), Proceedings of the Third Meeting of the Portuguese Algebraists, Coimbra, 1993.

[4] , Opposite Litlewood–Richardson sequences and their matrix realizations, Linear Algebra and its Applications 225 (1995), 91–116.

[5] O. Azenhas and E. Marques de Sá, Matrix realizations of Littlewood–Richardson sequences, Linear and Multilinear Algebra 27 (1990), 229–242.

[6] O. Azenhas and R. Mamede, Actions of the symmetric group on sets of skew-tableaux with prescribed matrix realization, Linear Algebra and its Applications 401 (2005), 221–275.

[7] W. C. Brown, Matrices Over Commutative Rings, Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, New York, 1993.

[8] C. Ehresmann, Sur la topologie de certains espaces homogènes, Annals of Mathematics, (2) 35 (1934), 396–443.

[9] W. Fulton, Young Tableaux: With Applications to Representation Theory and Geometry, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, Cambridge, 1997.

[10] , Eigenvalues of sums of Hermitiam matrices (after Klyachko), Séminaire Bourbaki 845 (1998), 1997–98.

[11] , Eigenvalues, invariant factors, highest weigths, and Schubert calculus, Bulletin of the American Mathematical Society 37 (2000), 209–249.

[12] , Eigenvalues of majorized Hermitiam matrices and Littlewood–Richardson coefficients, Linear Algebra and its Applications 319 (2000), 23–36.

[13] I. Gohberg and M. A. Kaashoek, Unsolved problems in matrix and operator theory II. Partial multiplicities of a product, Integral Equations Operator Theory 319 (1979), 116–120.

[14] J. A. Green, Les polynômes de Hall et les caractères des groupes gl(n, q), Colloque d’Algèbre Supérieure, Librairie Gauthier–Villars, Paris, 1957.

[15] , Symmetric Function and p-Modules, Lecture notes, University of Manchester, Manchester, 1961.

[16] , Shuffle Algebras, Lie Algebras and Quantum Groups, Textos de Matemática, Série B, vol. 9, Departamento de Matemática, Universidade de Coimbra, Coimbra, 1995.

[17] C. Greene, An extension of Schensted’s theorem, Advances in Mathematics 14 (1974), 254–265.

[18] T. Klein, The multiplication of Schur functions and extensions of p-modules, Journal of London Mathematical Society 43 (1968), 280–282.

[19] D. E. Knuth, Permutations, matrices, and generalized Young tableaux, Pacific Journal of Mathematics 34 (1970), 709–727.

[20] A. Lascoux, B. Leclerc, and J.-Y. Thibon, 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.

[21] A. Lascoux and M. P. Schützenberger, Le monoïde plaxique, Noncommutative structures in algebra and geometric combinatorics, (Naples, 1978), Quaderni de ”La Ricerca Scientifica” 109 (1981).

[22] , Arêtes et tableaux, Séminaire Lotharingien de Combinatoire 20 (1988), 125–144.

[23] , Keys and standard bases, Invariant theory and tableaux (Minneapolis, MN,1988) IMA, Math. Appl., vol. 19, Springer, New York–Berlin, 1990.

[24] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, Oxford, 1995.

[25] R. Mamede, Permutações de Sequências de Littlewood–Richardson e suas Realizações Matriciais (in Portuguese), Master’s thesis, Universidade de Coimbra, Coimbra, 2000.

[26] M. Newman, Integral Matrices, Academic Press, New York, 1972.

[27] J. F. Queiró, E. Marques de Sá, A. P. Santana, and O. Azenhas, Interlacing of eigenvalues and invariant factors, Mathematical Inequalities and Applications 3 (2000), 149–154.

[28] C. Schensted, Longest increasing and decreasing subsequences, Canadian Journal of Mathematics 13 (1961), 179–191.

[29] G. P. A. Thijsse, The local invariant factors of a product of holomorphic matrix functions, the order 4 case, Integral Equations Operator Theory 16 (1993), 277–304.

[30] R. C. Thompson, Smith invariants of a product of integral matrices, Contemporary Mathematics 47 (1985), 401–435.

Departamento de Matemática, Universidade de Coimbra, 3001-454 Coimbra, Portugal