MATRIX TABLEAU-PAIRS WITH KEY AND SHUFFLING CONDITIONS

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

CMUC Department of Mathematics, University of Coimbra 3001-454 Coimbra, Portugal

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

1. Introduction

Given an n by n nonsingular 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 Δ_{a} with diagonal entries p^{a_{1}}, …, p^{a_{n}}, for unique nonnegative integers a_{1} ≥ … ≥ a_{n}, called the Smith normal form of A. The diagonal entries p^{a_{1}}, ⋯, p^{a_{n}} are called the Smith invariants or invariant factors of A, and a = (a_{1}, …, a_{n}) the invariant partition of A. It is known that a, b, and c are invariant partitions of nonsingular matrices A, B, and C such that AB = C if and only if there exists a Littlewood– Richardson tableau T of type (a, b, c), that is, a tableau of shape c/a which rectifies to the key-tableau of weight b (also known as Yamanouchi tableau of weight b). (See [1, 2, 3, 4, 5, 11, 12, 14, 17, 28].) The relationship between Smith invariants and the product of Schur functions was noticed earlier by several authors [14, 17, 28]. For an overview and other relations, see the survey by W. Fulton [12] as well as [11, 13].

1 Work supported by Centre for Mathematics, University of Coimbra, CMUC/FCT, and SFRH/BSAB/515/2005, grant by the Portuguese Foundation of Science and Technology, FCT, at the Combinatorics Group, Fakultät für Mathematik, Universität Wien, Austria.

2 Work supported by Centre for Mathematics, University of Coimbra, CMUC/FCT.

Given a natural number n ≥ 1, [n] denotes the set {1, …, n}. Let m = (m_{1}, …, m_{t}) be a finite sequence of nonnegative integers. The symmetric group 𝔖_{t} acts on sequences of t nonnegative integers via the left action s_{i} m = (m_{1}, …, m_{i+1}, m_{i}, …, m_{t}) with s_{i} the simple transpositions of 𝔖_{t}, 1 ≤ i ≤ t − 1. Let α(m) be the unique partition in the orbit 𝔖_{t}m, and α(m)′ the conjugate partition. K(m) denotes the key-tableau [21] of weight m, that is, the tableau of weight m and shape α(m), and D_{[m_{k}]} denotes the n by n diagonal matrix having the ith diagonal entry equal to p whenever i ∈ [m_{k}] and 1 otherwise. The conjugate invariant partition of D_{[m_{k}]} is the one-row partition (m_{k}). We identify K(m) with the sequence of diagonal matrices (D_{[m_{1}]}, …, D_{[m_{t}]}) in the following sense: the sequence of conjugate invariant partitions associated with the sequence of products of matrices

D_{[m_{1}]}, D_{[m_{1}]}D_{[m_{2}]}, …, D_{[m_{1}]}D_{[m_{2}]} ⋯ D_{[m_{t}]}

is the nested sequence of partitions (m_{1}) ⊆ α(m_{1}, m_{2}) ⊆ ⋯ ⊆ α(m) which defines the key-tableau K(m) by telling us that for each 1 ≤ i ≤ t the first m_{i} columns contain the letter i. (We adopt the English convention for Young diagrams.) For instance,

K(1032) = 1 3 3 3 4 4 is identified with (D_{[1]}, D_{∅}, D_{[3]}, D_{[2]}).

Let U be an n by n unimodular matrix, that is, the determinant of U is not divisible by p. Put Δ_{a}UK(m) for the sequence Δ_{a}, Δ_{a}UD_{[m_{1}]}, Δ_{a}UD_{[m_{1}]}D_{[m_{2}]}, …, Δ_{a}UD_{[m_{1}]}D_{[m_{2}]} ⋯ D_{[m_{t}]}. The sequence of conjugate invariant partitions a^{0}′ = a′ ⊆ a^{1}′ ⊆ ⋯ ⊆ a^{t}′ = c′, associated with that sequence of matrices, is such that the skew-shape a^{k+1}′/a^{k}′ has m_{k+1} boxes with at most one box in each column, k = 0, 1, …, t − 1. Thus Δ_{a}UK(m) is identified with the tableau-pair (T, K(m)) where T is the tableau of weight m defined by that nested sequence of the conjugate partitions. It is shown in [6] that T rectifies to K(m). The reverse question arises naturally: Given a tableau-pair (T, K) such that K is a key-tableau and T is a semistandard Young tableau that rectifies to K, does there exist a matrix construction of the form Δ_{a}UK(m) for that pair? This question has been already answered positively for some instances of the weight in the orbit of 𝔖_{t}α(m) [1, 3, 4, 5, 7]. These are precisely instances where the Knuth class of a key-tableau is equal to the set of shuffles of its columns. In [6], a necessary and sufficient condition has been given for the Knuth class of a key-tableau to be equal to the set of the shuffles of its columns. In particular, the shuffles of the columns of a key-tableau are always contained in its Knuth class. Here, in Section 4, an algorithm is provided for the matrix construction of such a tableau-pair (T, K) whenever the word of T is a shuffle of the columns of K. It is also shown how to extend our matrix construction to any pair (T, K), over a four-letter alphabet, whenever T rectifies to the key-tableau K. In the case of a four-letter alphabet it is shown in [6] that the Knuth class of a key-tableau is the union of the shuffles of some subsets of words where the set of columns is included.

The matrix construction of a tableau-pair (T, K), where the word of T is a shuffle of the columns of the key-tableau K, relies on the following idea: a semistandard Young tableau, with a word of length ℓ, can be encoded by a biword Λ without repeated

biletters \binom{π_{j}}{x_{j}} where x_{j} is a letter in column π_{j} of T, for j = 1, …, ℓ. Among the

semistandard Young tableaux with biword Λ there is one in compact form (a tableau where the number of rows of size two of any two consecutive columns is maximal when shifting down the rightmost with respect to the other). Let c/a be its skew-shape. A semistandard Young tableau with biword Λ has therefore skew-shape (c′+e)′/(a′+e)′, for some partition e. As the word of T is a shuffle of the columns of K, we may choose a biword Π factorized into biwords whose bottom words are the columns of the keytableau K. These factors are identified with east–northeastward paths in the lattice ℕ^{2}, seen as an ℕ–matrix, whose vertices (π_{j}, x_{j}) are the biletters \binom{π_{j}}{x_{j}}. These lattice paths do not intersect and satisfy some properties which allow us to define an injective map to be used in the Main Algorithm in Section 4. The Main Algorithm depends only on the biword Π identified with its lattice path representation. It provides a matrix construction, for any T with that biword, based on elementary matrices T_{ij}(x) = I + xE_{ij} whose indices {i j} are generated by the vertices of those lattice paths. If we want a simultaneous matrix construction of T and K, we have to select a specific biword that one shows to exist always. This is achieved in Section 5 by relating certain type of vertices in the lattice paths of the biword with the existence of a commutation property when passing an elementary matrix T_{ij}(x) past another T_{ab}(y).

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

2. Young tableaux, keys, and shuffles

2.1. Young tableaux, words, and Knuth equivalence. A partition a = (a_{1}, …, a_{l}) is a weakly decreasing sequence of positive integers. We call l the length of a which is denoted by ℓ(a). We say that a is a partition of |a| := a_{1} + ⋯ + a_{l}. It is convenient to set a_{k} = 0 for k > ℓ(a), and we identify a with (a_{1}, …, a_{ℓ(a)}, 0, …, 0), where the tail of zeros is of arbitrary length. The unique partition of 0 is denoted by (0). A (weak) composition m = (m_{1}, …, m_{t}) is a finite sequence of nonnegative integers. We also say that m is a weak composition of |m| := m_{1} + ⋯ + m_{t}. The symmetric group 𝔖_{t} acts on (weak) compositions with t entries via the left action σm := (m_{σ^{−1}(1)}, …, m_{σ^{−1}(t)}), with σ ∈ 𝔖_{t}. The unique partition in the orbit 𝔖_{t}m is denoted by α(m). We think of a partition in terms of its Young diagram consisting of a left-justified array of boxes that, according to the English convention, has a_{i} boxes in the ith row counting from top to bottom. For instance, the Young diagram of a = (5, 2, 2, 1) is

.

The conjugate partition of a is the partition a′ whose Young diagram is obtained from a by interchanging rows with columns. Another way to look at the conjugate of a, which will be used in the sequel, is to say that if a = (a_{1}, …, a_{t}) and ℓ_{k} is the number of columns of length k in the Young diagram of a, 1 ≤ k ≤ t, then a′ = (t^{ℓ_{t}}, …, 2^{ℓ_{2}}, 1^{ℓ_{1}}), where the notation i^{ℓ_{i}} means that the positive integer i appears ℓ_{i} times in the sequence a′. Conversely, we have a_{k} = a_{k+1} + ℓ_{k}, for k = 1, …, t, with a_{t+1} := 0. positive integer i appears ℓ_{i} times in the sequence a′. For example, the conjugate partition of a = (5, 2, 2, 1) is the partition (4, 3, 1, 1, 1) = (4, 3, 2^{0}, 1^{3}), and its Young diagram is

.

A partition a is contained in a partition c, written a ⊆ c, if the Young diagram of a is contained in the Young diagram of c. In this case, we define the skew-shape c/a to be the set of boxes in the Young diagram of c that remains after we remove those boxes corresponding to a. When a = (0), we obtain the Young diagram of c.

Let ℕ be the set of positive integers with the usual order “ ≤ ”. If t ∈ ℕ, [t] denotes the set {1, …, t}, and [t]^{∗} the free monoid in the alphabet [t]. That is, the collection of all finite words over the alphabet [t], with the concatenation operation. A word over the alphabet [t] is defined to be a finite string of elements (known as letters) of the set [t].

Given the word w = x_{1} ⋯ x_{k} over the alphabet [t], the weight of w, in the alphabet [t], is the vector (m_{1}, …, m_{t}), where m_{x} denotes the multiplicity of the letter x ∈ [t] in the word w. Here k is the length of w, denoted by ℓ(w). We have ℓ(w) = m_{1}+⋯+m_{t} and, in particular, the length and the weight of the empty word is zero. A subword of a word w is a word obtained by deleting the letters at some (not necessarily adjacent) positions in w. As usual, we write w^{k}, k ≥ 0, to mean the concatenation of w with itself k times. When one writes x_{1}x_{2} … x_{k} = 1^{m_{1}}2^{m_{2}} … t^{m_{t}} this means that w is a weakly increasing word, called a row word, and x_{1} = ⋯ = x_{m_{1}} = 1, x_{m_{1}+1} = ⋯ = x_{m_{1}+m_{2}} = 2, …, x_{m_{1}+···+m_{t−1}+1} = ⋯ = x_{k} = t. Similarly we have a weakly decreasing word when we write x_{1}x_{2} … x_{k} = t^{m_{t}} … 2^{m_{2}}1^{m_{t}}. If the letters in w are in strictly decreasing order, that is, x_{i} > x_{i+1} for all i, w is called a column word. A column word is often identified with its support, that is, with the set consisting of its letters. For example, the word 431 is identified with the set {1, 3, 4}.

A (semistandard) Young tableau T of shape c/a (for short skew-tableau) is a filling of the skew-shape c/a with positive integers, weakly increasing across each row and strictly increasing down each column [10, 19]. If a = (0) then T is said to be of partition shape. The (reading) word of T is the word obtained by reading its columns from bottom to top, starting on the left and moving to the right. The weight of T is the weight of its word. A Young tableau of partition shape is identified with its (reading) word. The empty tableau is the Young tableau of shape (0) identified with the empty word.

Example 2.1. A (semistandard) Young tableau T of skew-shape (4, 4, 2, 1)/(3, 2) with weight (1, 2, 2, 1) and word 433221,

(2.1)  1 2 2 3 3 4 .

A Young tableau T of shape c/a and weight (m_{1}, …, m_{t}) may also be seen as a nested sequence of partitions T = (a^{0}, a^{1}, …, a^{t}), where a = a^{0} ⊆ a^{1} ⊆ ⋯ ⊆ a^{t} = c, such that for k = 1, …, t, the skew-diagram a^{k}/a^{k−1} has m_{k} boxes with at most one box in each column, and it is filled with the letter k [22]. In Example 2.1, we may write T = (a^{0}, a^{1}, a^{2}, a^{3}, a^{4}), where a^{0} = (3, 2) ⊆ a^{1} = (4, 2) ⊆ a^{2} = (4, 4) ⊆ a^{3} = (4, 4, 2) ⊆ a^{4} = (4, 4, 2, 1).

The Knuth or plactic congruence ≡ [20, 10, 18, 19] on the words over the alphabet [t] is the congruence in [t]^{∗} defined by the transitive closure of the relations

uxzyv ≡ uzxyv, x ≤ y < z,
uyzxv ≡ uyxzv, x < y ≤ z,

where x, y and z are letters in [t], and u and v are words in [t]^{∗}. Every Knuth class has one and only one Young tableau of partition shape. Henceforth, each Knuth or plactic class consists of all words Knuth equivalent to the unique Young tableau in the Knuth class. Using jeu de taquin slides every semistandard tableau can be rectified to the unique tableau in the Knuth class of its word [10, 26, 27]. In Example 2.1, T is rectified to 4321 32 ≡ 433221. Two Young tableaux are said to be Knuth equivalent if they can be obtained from another by jeu de taquin slides. Equivalently, they have the same rectification.

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

2.2. Key-tableaux and shuffles. A key-tableau K is a tableau whose columns are pairwise comparable in the inclusion order [21]. Given a composition m, the keytableau of weight m is the tableau K(m) of shape α(m) whose first m_{j} columns contain the letter j for all j. This defines an obvious bijection between key-tableaux and compositions [24]. A key-tableau is also a tableau whose weight is a permutation of its shape. The key-tableau K(m) [6, 21] may be written as

(2.2)  K(m) = v_{t}^{ℓ_{t}}v_{t−1}^{ℓ_{t−1}} … v_{1}^{ℓ_{1}},

where {1, …, t} = v_{t} ⫌ v_{t−1} ⫌ ⋯ ⫌ v_{1} ≠ ∅ are column words such that α(m) = (ℓ_{1} + … + ℓ_{t}, …, ℓ_{t−1} + ℓ_{t}, ℓ_{t}), and its conjugate is α′(m) = (t^{ℓ_{t}}, …, 1^{ℓ_{1}}). Let σ ∈ 𝔖_{t}, written as a word a_{1}a_{2} … a_{t} in [t]^{∗}, be such that {a_{1}, …, a_{i}} is the support of v_{i}, for i = 1, …, t. One has σα(m) = m = (m_{1}, …, m_{t}), with m_{j} = ∑_{k=σ^{−1}(j)}^{t} ℓ_{k} for all j. Therefore the key K(m) may be encoded by a permutation σ and a nonnegative integral vector (ℓ_{t}, …, ℓ_{1}), that is, K(σ, (ℓ_{t}, …, ℓ_{1})) := v_{t}^{ℓ_{t}}v_{t−1}^{ℓ_{t−1}} … v_{1}^{ℓ_{1}}. (This presentation of a key-tableau will be used in Section 6.)

Example 2.2. The key-tableau

K(1, 2, 2, 1) = 1 2 2 3 3 4 = 4321 32

has shape (2, 2, 1, 1) and weight m = (1, 2, 2, 1).

The Knuth class of the word 433221 of the skew-tableau T in Example 2.1 is the key-tableau K(1, 2, 2, 1) = 4321 32 (the empty space means the ending of a column and the starting of a new one) which can be encoded either by permutation 2314 or 3214, and the nonnegative integral vector (1, 0, 1, 0).

Let w = x_{1} ⋯ x_{k} ∈ [t]^{∗}. Given I = {i_{1} < ⋯ < i_{r}} ⊆ [k], w|I denotes the subword x_{i_{1}} ⋯ x_{i_{r}}. In particular, w|I is the empty word if I = ∅. Two subwords w|I and w|J of w are said to be disjoint if the sets I and J are disjoint.

The word w = x_{1} ⋯ x_{k} is said to be a shuffle of the words u and v if there exists a partition {I, J} of the set [k] such that u = w|I and v = w|J. Let u_{1}, …, u_{q} ∈ [t]^{∗} be q words of lengths k_{1}, …, k_{q}, respectively. If q = 0 the shuffle is the empty word. If q ≥ 1, let {I_{1}, …, I_{q}} be a partition of the set [k]. Then the word w|{I_{1}, …, I_{q}} defined by w|I_{j} = u_{j}, for j = 1, …, q, is a shuffle of u_{1}, …, u_{q} [15, 25]. The words u_{1}, …, u_{q} are said to be the shuffle components of w|{I_{1}, …, I_{q}}. Indeed w|{I_{1}, …, I_{q}} = w|{F_{1}, …, F_{q}} whenever {I_{1}, …, I_{q}} = {F_{1}, …, F_{q}}. However, a word may have different shuffle decompositions of the same words, that is, w|{I_{1}, …, I_{q}} = w|{J_{1}, …, J_{q}} with {I_{1}, …, I_{q}} ≠ {J_{1}, …, J_{q}} set partitions of [k]. For example, if w = 433221 ∈ [4]^{∗}, we have w|{{1, 2, 5, 6}, {3, 4}} = w|{{1, 2, 4, 6}, {3, 5}}. The set of the shuffles of the q words u_{1}, …, u_{q}, is the set of all words obtained by shuffling together the q words u_{1}, …, u_{q},

⊔⊔(u_{1}, …, u_{q}) ={w|{I_{1}, …, I_{q}} : {I_{1}, …, I_{q}} a set partition of [k], w|I_{j} = u_{j}, 1 ≤ j ≤ q}.

Let K(m) = v_{t}^{ℓ_{t}}v_{t−1}^{ℓ_{t−1}} … v_{1}^{ℓ_{1}} be the key as in (2.2), and σ ∈ 𝔖_{t} such that σα(m) = m. By Greene’s Theorem [16], the set ⊔⊔ (v_{t}^{ℓ_{t}}, v_{t−1}^{ℓ_{t−1}}, …, v_{1}^{ℓ_{1}}) is always a subset, in general proper, of the Knuth class of K(m). In [6] it was proved that, if f_{1} ⊇ f_{2} ⊇ ⋯ ⊇ f_{k} are nonempty column words, then the Knuth class of K = f_{1} … f_{k} is equal to the set of all shuffles of its columns if and only if each column is either an interval of f_{1}, or is obtained from an interval of f_{1} by removing a single letter. It is clear that this property is true for any key K(m) = v_{t}^{ℓ_{t}}v_{t−1}^{ℓ_{t−1}} ⋯ v_{1}^{ℓ_{1}} over the alphabet {1, 2} or {1, 2, 3}. However, over the alphabet {1, 2, 3, 4}, considering S := {1423, 1432, 4123, 4132} ⊆ 𝔖_{4}, this property holds if and only if either σ ∉ S, or σ ∈ S but ℓ_{2} = 0 or ℓ_{4} = 0.

Denote by v̂_{5}^{n_{5}} the multiset consisting of n_{5} words v̂_{5} := 431421 ≡ K(2, 1, 1, 2). The Knuth class of a key over the alphabet {1, 2, 3, 4} was characterized in [6], in terms of the shuffling operation, as follows.

Theorem 2.1. [6] Let σ ∈ 𝔖_{4}, and let (ℓ_{4}, …, ℓ_{1}) be a sequence of nonnegative integers. The Knuth class of K(σ, (ℓ_{4}, …, ℓ_{1})) = v_{4}^{ℓ_{4}}v_{3}^{ℓ_{3}}v_{2}^{ℓ_{2}}v_{1}^{ℓ_{1}} is

\begin{cases}⊔⊔(v_{4}^{ℓ_{4}}, v_{3}^{ℓ_{3}}, v_{2}^{ℓ_{2}}, v_{1}^{ℓ_{1}}), & if σ ∈ 𝔖_{4} \ S, or σ ∈ S and (ℓ_{2} = 0 or ℓ_{4} = 0), \\ ⋃_{n_{5}=0}^{min\{ℓ_{2},ℓ_{4}\}} ⊔⊔(v̂_{5}^{n_{5}}, v_{4}^{n_{4}}, …, v_{1}^{n_{1}}), & if σ ∈ S and ℓ_{2} ≠ 0, ℓ_{4} ≠ 0, \end{cases}

where n_{i} = ℓ_{i}, i = 1, 3, and n_{i} = ℓ_{i} − n_{5}, i = 2, 4.

3. Biwords and nonintersecting E-NE lattice paths

3.1. Biwords. Our aim is, given a (skew) semistandard Young tableau in compact form, to encode it by a biword so that, identifying their biletters with points in the lattice ℕ^{2}, seen as an ℕ–matrix, one is able to define the elementary matrices of our matrix construction in Section 4. All the tableaux with that biword will be related with the tableau in compact form.

Given n, t ∈ ℕ, a biword over the alphabet [n] × [t] is an ordered pair of words of the same length, written as

(\begin{matrix}u \\ v \end{matrix}) = (\begin{matrix}π_{1} & ⋯ & π_{k} \\ x_{1} & ⋯ & x_{k} \end{matrix}) ,

with u = π_{1} … π_{k} ∈ [n]^{∗} and v = x_{1} … x_{k} ∈ [t]^{∗}. Each biword (\begin{matrix}u \\ v \end{matrix}) can also be

seen as a word whose letters are the biletters (\begin{matrix}π_{1} \\ x_{1} \end{matrix}) , …, (\begin{matrix}π_{k} \\ x_{k} \end{matrix}) . We only consider

biwords with pairwise distinct biletters, that is, (\begin{matrix}π_{i} \\ x_{i} \end{matrix}) ≠ (\begin{matrix}π_{j} \\ x_{j} \end{matrix}), for every i ≠ j. Two

biwords are said to be equivalent if they have the same set of biletters. Among the biwords having the same set of biletters as (\begin{matrix}u \\ v \end{matrix}) we consider two special ones, Σ and

Σ′. The weakly increasing rearrangement of (\begin{matrix}u \\ v \end{matrix}) using the anti-lexicographic order

on biletters with priority in the top entry [19], that is, (\begin{matrix}π \\ x \end{matrix}) ≤ (\begin{matrix}π′ \\ x′ \end{matrix}) if and only if

π < π′, or π = π′ and x ≥ x′, gives the biword

(3.1)  Σ = (\begin{matrix}1^{f_{1}} & ⋯ & n^{f_{n}} \\ w_{1} & ⋯ & w_{n} \end{matrix}) ,

for some integers f_{i} ≥ 0, such that w = w_{1} ⋯ w_{n} ∈ [t]^{∗}, with w_{i} a column word

of length f_{i}. The weakly decreasing rearrangement of (\begin{matrix}u \\ v \end{matrix}) using the lexicographic

order in biletters with priority on the bottom entry [19], that is, (\begin{matrix}π \\ x \end{matrix}) ≥ (\begin{matrix}π′ \\ x′ \end{matrix}) if and

only if x > x′, or x = x′ and π ≥ π′, gives the biword

(3.2)  Σ′ = (\begin{matrix}J_{t} & ⋯ & J_{1} \\ t^{m_{t}} & ⋯ & 1^{m_{1}} \end{matrix}) ,

for some integers m_{i} ≥ 0, such that J = J_{t} ⋯ J_{1} ∈ [n]^{∗}, with J_{i} a column word of length m_{i}. We have then the word-pair (J, w) ∈ [n]^{∗} × [t]^{∗} such that the weight of w is equal to (m_{1}, …, m_{t}) = (#J_{1}, …, #J_{t}) and the weight of J is (ℓ(w_{1}), …, ℓ(w_{n})). (Recall that column words are identified with their supports.)

Young tableaux in compact form are in one to one correspondence with classes of biwords without repeated biletters. Young tableaux with the same biword have the same word pair (J, w), hence their skew-shapes are (c′ + e)′/(a′ + e)′, where e is any partition of length at most n, and c/a is the skew-shape of the compact tableau with

that biword. For instance, 1 2 2 3 3 4 and 1 2 2 3 3 4 have the same biword. Let T be

a tableau of skew-shape with n columns (possibly some are empty), where the word

w has weight m = (m_{1}, …, m_{t}). Let \binom{π_{j}}{x_{j}} be the biletter where x_{j} is the letter in

column π_{j} of T, for j = 1, …, ℓ(w). Any biword over the alphabet [n]×[t] with these

biletters is said to be a biword of T. In particular, Σ = ( \begin{matrix}1^{f_{1}} & ⋯ & n^{f_{n}} \\ w_{1} & ⋯ & w_{n} \end{matrix} ) is the

biword of T where the factor ( \begin{matrix}i^{f_{i}} \\ w_{i} \end{matrix} ) indicates that w_{i} is a column word of length f_{i}

filled in column i, counting from left to right, of the skew-shape T. For each i in [t], J_{i} ∈ [n]^{∗} is the column word defined by the indices of the columns of T where the m_{i} letters i of w are placed. The column words J_{1}, …, J_{t} are called the indexing sets of T and J = J_{t} ⋯ J_{1} the indexing-set word.

A biword class, over the alphabet [n] × [t], without repeated biletters, shall be represented in the lattice ℕ^{2} by identifying its set of biletters \binom{y}{i} with the set of points (y, i), where y ∈ J_{i}, for i = 1, …, t, called the lattice diagram of the biword class. Those points, graphically represented as •, are called lattice points or vertices of a biword in the class. For convenience, in drawing the lattice ℕ^{2}, we adopt the matrix convention, that is, the first coordinate, the row index, increases as one goes downwards, and the second coordinate, the column index, increases as one goes from left to right.

Example 3.1. The skew-tableau T in Example 2.1 has biword Σ = (\begin{matrix}11 2 3 44 \\ 43 3 2 21 \end{matrix})

and the corresponding lattice diagram, contained in {1, 2, 3, 4} × {1, 2, 3, 4}, is

(3.3) T = 1 2 2 3 3 4 ⟷ 3 4 3 2 1 2  (\begin{matrix}11 2 3 44 \\ 43 3 2 21 \end{matrix}) ↔  .

Note that the lattice vertex marginal cardinalities, by rows respectively columns, are (2, 1, 1, 2), which are the corresponding lengths of the columns of T, and (1, 2, 2, 1), which are the corresponding multiplicities of each letter in T.

3.2. Nonintersecting E-NE lattice paths. In this section we consider biwords where the bottom word w of Σ is in the Knuth class of the key-tableau (2.2) and is a shuffle of its columns, that is, w is in the set ⊔⊔(v_{t}^{ℓ_{t}}, …, v_{1}^{ℓ_{1}}). We are interested in the biwords Π equivalent to Σ with bottom word the key v_{t}^{ℓ_{t}} ⋯ v_{1}^{ℓ_{1}}. They are in one to one correspondence with the shuffle decompositions of w in ⊔⊔ (v_{t}^{ℓ_{t}}, …, v_{1}^{ℓ_{1}}). Let {F^{t,ℓ_{t}}, …, F^{t,1}, …, F^{1,ℓ_{1}}, …, F^{1,1}} be a set partition of {1, …, ∑_{k=1}^{t} k ℓ_{k}} such that

Σ|F^{k,j} = \binom{I^{k,j}}{v_{k}}, for k ∈ [t] and j ∈ [ℓ_{k}], which generates the biword

(3.4)  Π = (\begin{matrix}I^{t,ℓ_{t}} & ⋯ & I^{t,1} & ⋯ & I^{2,ℓ_{2}} & ⋯ & I^{2,1} & I^{1,ℓ_{1}} & ⋯ & I^{1,1} \\ v_{t} & ⋯ & v_{t} & ⋯ & v_{2} & ⋯ & v_{2} & v_{1} & ⋯ & v_{1} \end{matrix}) ,

where each I^{j,i} is a weakly increasing word with |I^{j,i}| = j, for j = 1, …, t, and i = 1, …, ℓ_{j}. In the lattice diagram of Π we link the vertices of any two consecutive

biletters in the factor ( \begin{matrix}I^{j,i} \\ v_{j} \end{matrix} ) of Π, for 1 ≤ i ≤ ℓ_{j}, 1 ≤ j ≤ t, with a straight line.

Considering the last and the first biletters of this factor, respectively, as the starting and the ending points, one gets a lattice path with j vertices made of eastward E and northeastward NE steps. These lattice paths do not have vertices in common since the biletters of Π are pairwise distinct. This means that the biword Π (3.4) is graphically represented by ℓ_{t} + ⋯ + ℓ_{1} nonintersecting northeastward-eastward E-NE lattice paths, where ℓ_{j} of them have length j, for j = 1, …, t. Conversely, every word in ⊔⊔ (v_{t}^{ℓ_{t}}, …, v_{1}^{ℓ_{1}}) may be obtained in this way using the points of the lattice diagram of Π to draw all the ℓ_{t} + ⋯ + ℓ_{1} nonintersecting northeastward-eastward lattice paths, where ℓ_{j} of them have j vertices, for j = 1, …, t. For the rest of the paper, we identify a biword Π with its lattice path representation in ℕ^{2} where each

factor ( \begin{matrix}I^{j,i} \\ v_{j} \end{matrix} ), for i = 1, …, ℓ_{j}, j = 1, …, t, is seen as the lattice path of length j

whose vertices are the biletters of this factor. Example 3.2. The word in the second row of the biword Σ in (3.3) is a shuffle of 4321 and 32. We may sort the biletters of Σ in several ways, in order to obtain all biwords Π as in (3.4), which is equivalent to draw in the lattice diagram (3.3) all the sets of two nonintersecting paths of lengths four and two using northeast-eastward steps. We have then four types of northeast-eastward nonintersecting paths:

,  ,  ,  ,

each corresponding to the biwords (3.5)

Π=(\begin{matrix}1144 & 23 \\ 4321 & 32 \end{matrix}), Π′ =(\begin{matrix}1234 14 \\ 4321 32 \end{matrix}), Π^{†} =(\begin{matrix}1244 & 13 \\ 4321 & 32 \end{matrix}) and Π^{‡} =(\begin{matrix}1134 24 \\ 4321 32 \end{matrix}) ,

respectively. Remark 3.1. As the v_{i}’s are column words, the lattice paths do not have northward steps. Recalling that the column words of a key-tableau are pairwise comparable for the inclusion order, the sets of column indices of any two paths of Π are comparable for the inclusion order. In particular, any pair of two lattice paths of Π is such that, if one of the paths has a vertex in a column of ℕ^{2} and the other has not, then the set of the indices of the columns of the latter is contained in the set of the former. The lattice paths with the longest length have vertices in all columns of the lattice diagram of Π. We may therefore identify Π with a collection of nonintersecting E-NE paths in [n] × [t] such that the sets of the indices of the columns are comparable for the inclusion order.

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

For instance, in the lattice representation of Π′ (3.5), the path (\begin{matrix}1234 \\ 4321 \end{matrix}) is above

the path (\begin{matrix}14 \\ 32 \end{matrix}) in column 2, and below it in column 3. The vertex (4, 1) is an obstacle

NE-linked to (3, 2), and thus the vertex (3, 2) is negatively linked to (4, 1).

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

Algorithm 3.1. Consider the biword Π in (3.4) and its lattice path representation. Let (a, b) be a vertex of Π. Let y := 0 if (a, b) is the initial vertex of a path, otherwise, let y be the index of the column containing the vertex positively linked to (a, b). Write (ã, b̃) := (a, b), set x := ã and implement the following algorithm:

Begin

1. Starting in (ã, b̃) move one step (1, 0) in ℕ^{2} to the west. Do b̃:= b̃ − 1. If b̃ = y, then x := ã and stop. Else b̃ > y and go to 2.

2. If (ã, b̃) is an obstacle of Π, then move northeast along the path linking positively the obstacle (ã, b̃) to the vertex (c̃, d̃) ∈ Π, with d̃ ≤ b. Set (ã, b̃) := (c̃, d̃) and go to 1.

Else go to 3.

3. If (ã, b̃) is positively linked to some vertex (ã, d̃) with b̃ + 1 < d̃, then set b̃:= d̃ and go to 1.

Else, go to 1. End.

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

The last point in ℕ × ℤ_{≥0} that one reaches in the algorithm is (x, y) which may or may not be in Π. Nevertheless, x is the row index of the last vertex of Π \ {(x, y)}.

Definition 3.1. Let (a, b) ∈ Π. The sequence of vertices of Π \ {(x, y)} that one passes in the algorithm above from the vertex (a, b) ∈ Π to vertex (x, y) ∈ ℕ × ℤ_{≥0} is called the (a, b)-path.

The (a, b)-path contains at least the vertex (a, b) ∈ Π, and has odd length. This procedure defines the map

s : Π ⟶ ℕ,

where s(a, b) := x is the row index of the last vertex in the (a, b)-path.

Example 3.3. Consider the biword Π in (3.5). The vertices in one row always belong to a unique path. Thus, we have always s(a, b) = a for every vertex (a, b) in Π. Consider now Π′ in w(3.5). There exists a row containing vertices belonging to different paths. To compute the (4, 2)-path, notice that (4, 1) is an obstacle. Thus, one must move along the line linking this obstacle to (3, 2). Since there are no more obstacles in row 3 to the west of (3, 2), the (4, 2)-path is (4, 2), (4, 1), (3, 2) and s(4, 2) = 3. Starting from any other vertex (a, b) of Π, we will face no obstacle, and thus s(a, b) = a.

Example 3.4. Consider the biword Π = ( \begin{matrix}22233 1344 345 2 \\ 54321 5321 531 1 \end{matrix} ) whose lattice path

representation is

(3.6)  .

We have s(4, 3) = 2 since the obstacle (4, 2) is linked to a vertex in row 3, and (3, 2) is another obstacle that appears to its left, linked to a vertex in row 2. The (4, 3)-path is (4, 3), (4, 2), (3, 3), (3, 2), (2, 3) of length five. Similarly, we find that s(3, 3) = 2, s(3, 5) = 1, and s(2, 1) = 1 whose (2, 1)-path consists only of (2, 1). For any other vertex (a, b) of Π, we get s(a, b) = a.

Example 3.5. Consider now the following lattice path representation:

.

We have s(3, 6) = s(2, 6) = 1. For any other vertex (a, b) of Π, we get s(a, b) = a.

Lemma 3.1. Let F be the set of all initial vertices of lattice paths of Π. Then the map s : F → ℕ sending (a, b) ∈ F into s(a, b) is an injection.

Proof. Let A and B denote the (a, b) and (c, d)-paths, respectively, where (a, b) and (c, d) are distinct initial vertices of lattice paths in F. We will show that, after any common vertex, the two paths A and B follow distinct directions: one goes west and the other goes northeast, continuing their way in different rows. Thereby A and B can not have the last Π vertex in the same row. If A and B would have the last Π vertices in the same row, they should coincide. But then one goes west and stops in this row, and the other goes northeast and stops in a row above. This is absurd. Hence, s(a, b) ≠ s(c, d).

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

4. Matrix tableau-pairs with key and shuffle conditions: statement of results

Let R_{p} be a local principal ideal domain with maximal ideal (p). A unit in R_{p} is an element that is not divisible by p. Every nonzero element x may be written in the form μp^{k} with k ≥ 0 and μ a unit in R_{p}, both uniquely determined by x. Two elements x and y are said to be associated if x = μy for some unit μ in R_{p}. In this paper, all matrices are n by n and nonsingular with entries over R_{p}. Given a matrix A, A^{T} denotes its transpose. A matrix is said to be unimodular if its determinant is a unit. Let U_{n} be the group of n by n unimodular matrices over R_{p}. Given n by n matrices A and B, we say that B is left equivalent to A (written B ∼_{L} A) if B = UA for some U ∈ U_{n}; B is right equivalent to A (written B ∼_{R} A) if B = AV for some V ∈ U_{n}; and B is equivalent to A (written B ∼ A) if B = UAV for some U, V ∈ U_{n}. The relations ∼_{L}, ∼_{R} and ∼ are equivalence relations in the set of all n by n nonsingular matrices over R_{p}. (For more details see [23].)

Let A be an n by n nonsingular matrix. By the Smith normal form theorem, Theorem [9, 23], there exist nonnegative integers a_{1}, …, a_{n} with a_{1} ≥ ⋯ ≥ a_{n} ≥ 0 such that A is equivalent to the diagonal matrix diag_{p}(a_{1}, …, a_{n}) having p^{a_{i}} in the ith diagonal position. The sequence a = (a_{1}, …, a_{n}) of the exponents of the p-powers in the Smith normal form of A is a partition of length ≤ n, uniquely determined by the matrix A. We call a the invariant partition of A. Given a subset J ⊆ [n], put D_{J} := diag_{p}(χ^{J}), where χ^{J} is the nonnegative integer vector having 1 at position i if i ∈ J, and 0 otherwise. If σ ∈ 𝔖_{n}, P_{σ} denotes the permutation matrix having δ_{iσ(j)} in position (i, j). As usual, if u and v are positive integers, (u v) denotes the transposition of u and v.

Let (i, j) ∈ [n] × [n]. We denote by E_{ij} the n by n matrix having a 1 in position (i, j) and 0′s elsewhere, and we define the elementary unimodular matrices T_{ij}(x) as follows:

T_{ij}(x) = I + xE_{ij}, where i ≠ j and x ∈ R_{p};
T_{ii}(v) = I + (v − 1)E_{ii}, where v is a unit of R_{p}.

It is obvious that E_{ij}E_{rs} = δ_{jr}E_{is}. Therefore, if i ≠ j and r ≠ s, we find that T_{ij}(x)T_{rs}(y) = I + xE_{ij} + yE_{rs} + xyδ_{jr}E_{is}. The lemma below states two kinds of rules to be used in the sequel: (I) for commuting either two elementary matrices T_{ij}(x), or an elementary matrix T_{ij}(x) with an elementary diagonal matrix D_{[m]}; (II) is concerned with the appearance of a permutation matrix when one elementary matrix passes past another. The proof is left to the reader.

Lemma 4.1. Let i, j, r, s, m ∈ [n], and x, y, v ∈ R_{p}, such that v is a unit. Then, (I) (Commutation rules)

(i) T_{ij}(x)T_{rs}(y) = T_{rs}(y)T_{ij}(x), whenever i ≠ s and j ≠ r. (ii) T_{ij}(x)T_{js}(y) = T_{js}(y)T_{ij}(x)T_{is}(xy), if i ≠ s, i ≠ j. (iii) T_{ii}(v)T_{rs}(x) = T_{rs}(ux)T_{ii}(v), for some unit u. (iv) T_{ji}(y)T_{ij}(xp) = T_{ij}(u_{1}xp)T_{ii}(u_{2})T_{jj}(u_{3})T_{ji}(u_{4}y)

= T_{ij}(u_{1}xp)T_{ji}(u_{5}y)T_{ii}(u_{2})T_{jj}(u_{3}), for some units u_{i}, i = 1, …, 4, 5.

(v) T_{ij}(x)D_{[m]} = D_{[m]}T_{ij}(x), if i, j > m. (vi) T_{ij}(x)D_{[m]} = D_{[m]}T_{ij}(xp), if i > m ≥ j ≥ 1. (vii) T_{ij}(xp)D_{[m]} = D_{[m]}T_{ij}(x), if j > m ≥ i ≥ 1. (II) (Anti-commutation rule) (viii) T_{ji}(−1)T_{ij}(1) = T_{jj}(−1)T_{ij}(1)P_{(i j)}, i ≠ j.

The lemma says that there exists always a unimodular elementary matrix E such that

T_{ji}(τ)T_{ab}(τ′) = T_{ab}(ϱ′)T_{ji}(ϱ)E, with ϱ, τ and ϱ′, τ′ pairs of associated elements,

whenever τ, τ′ are not both unities, or (a, b) ≠ (i, j) if i ≠ j. Otherwise, the passage of a matrix T_{ij}(τ), with i ≠ j, to the left of a matrix T_{ji}(τ′), with τ and τ′ both unities, leads to the appearance of a nonidentity permutation matrix.

Following [3, 5, 7], we introduce the definition of a matrix realization of a pair of tableaux (T, F), where T and F have the same weight m and F has partition shape b. Let B_{r} be a matrix with invariant partition (1^{m_{r}}, 0^{n−m_{r}}), for r = 1, …, t. If a^{r} is the conjugate of the invariant partition of A_{0}B_{1} ⋯ B_{r}, 0 ≤ r ≤ t, then it is clear that (a^{0} = a, a^{1}, …, a^{t} = c) is a tableau with weight m = (m_{1}, …, m_{t}) and shape c/a. Similarly, if b^{r} is the conjugate of the invariant partition of B_{1} ⋯ B_{r}, 1 ≤ r ≤ t, then (b^{1}, …, b^{t} = b) is a tableau of shape b with weight (m_{1}, …, m_{t}) as well (see [7]).

Definition 4.1. Let T = (a^{0}, a^{1}, …, a^{t}) and F = (0, b^{1}, …, b^{t}) be tableaux of weight m = (m_{1}, …, m_{t}). We say that a sequence of n by n nonsingular matrices A_{0}, B_{1}, …, B_{t} is a matrix realization of the pair (T, F) (or realizes (T, F)) if:

I. For each r ∈ {1, …, t}, the invariant partition of the matrix B_{r} is

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

A_{0}B_{1} ⋯ B_{r} is the conjugate of a^{r}.

III. For each r ∈ {1, …, t}, the invariant partition of the matrix B_{1} ⋯ B_{r} is the

conjugate of b^{r}. The tableau-pair (T, F) is said to be a matrix-tableau pair.

Example 4.1. Let a = (3, 2, 1) and F = 11122. The sequences

diag_{p}(a), UD_{[3]}, D_{{4,5}},

with U running over the unimodular matrices of order five, give rise to tableaux T of skew-shape whose words w are congruent with tableaux P running over {11122; 21 112; 21 21 1} the set of all tableaux of weight (3, 2) with partition shape. For instance, for U = I, U = P_{4321}, and U = P_{12543}P_{4321}, respectively, we have:

(a) T = 2 2 1 1 1 , w = 11122;  (b) T = 1 2 1 1 2 , w = 21112; and

(c) T = 1 1 2 1 2 , w = 21211.

Actually, I and II, in Definition 4.1, say that the invariant partitions of A_{0}, A_{0}B_{1}, …, A_{0}B_{1} ⋯ B_{t} define T, while III says that the invariant partitions of B_{1}, B_{1}B_{2}, …, B_{1}B_{2} ⋯ B_{t} define F. Recall that the key K(m) is the only tableau of weight m = (m_{1}, …, m_{t}) and conjugate shape ∑_{i=1}^{t}(1^{m_{i}}), and when written as a sequence of partitions it takes the form K(m) = (0, (1^{m_{1}}), ∑_{i=1}^{2}(1^{m_{i}}), …, ∑_{i=1}^{t}(1^{m_{i}})).

Thus, when F = K(m), in order to verify property III, it is sufficient to show that B_{1} ⋯ B_{t} has invariant partition (1^{m_{1}}) + ⋯ + (1^{m_{t}}). For the purpose of this paper, we shall consider only pairs (T, K(m)) such that the word of T is a shuffle of the columns of K(m). In [6], it has been shown that (T, K(m)) is a matrix-tableau pair only if the word of T is an element of the Knuth class of K(m). Therefore, the following problem arises:

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

The next algorithm and Theorem 4.4 give an answer to this problem. To this end, we need the following definition and lemma.

Definition 4.2. Given σ ∈ 𝔖_{n} and x ≥ y in [n], we define the n by n matrix S(x, y, σ) = E_{u v} if σ(u) = x > σ(v) = y, and the zero matrix otherwise.

Clearly, I + S(x, y, σ) = T_{uv}(1) with σ(u) = x and σ(v) = y. In particular, I + S(x, x, σ) = I.

Lemma 4.2. Given σ ∈ 𝔖_{n} and x ≥ y in [n], we have, for any partition a of length ≤ n,

(4.1)  diag_{p}(a)P_{σ}(I + S(x, y, σ))(I − S(x, y, σ)^{T}) ∼_{L} diag_{p}(a)P_{(x y)σ}.

Proof. Let u, v ∈ [n] be such that σ(u) = x and σ(v) = y. Then, (I + S(x, y, σ))(I − S(x, y, σ)^{T}) = T_{uv}(1)T_{vu}(−1). By Lemma 4.1 (viii), the left hand side of (4.1) can be written as

(4.2)  diag_{p}(a)P_{σ}T_{uv}(1)T_{vu}(−1) = diag_{p}(a)P_{σ}T_{vv}(−1)T_{vu}(−1)P_{(uv)}.

Since x ≥ y, we have

(4.2) ∼_{L} diag_{p}(a_{σ(1)}, …, a_{σ(n)})P_{(uv)} ∼_{L} diag_{p}(a)P_{σ}P_{(uv)} = diag_{p}(a)P_{(x y)σ}.
□

Main Algorithm. Let Π be the biword (3.4). Our algorithm is presented as a three-step definition:

Step 1. For each k = t, …, 1, let X_{k} ⊆ ℕ^{2} be the set of initial vertices of the ℓ_{k} lattice paths of length k of Π, and define

s(X_{k}) := {s(x, j) : (x, j) ∈ X_{k}} = {s_{ℓ_{t+1}+···+ℓ_{k+1}+1}^{0} < ⋯ < s_{ℓ_{t+1}+···+ℓ_{k+1}+ℓ_{k}}^{0}} ⊆ [n],

where we set ℓ_{t+1} := 0. Let σ_{1} ∈ 𝔖_{n} such that σ_{1}(i) = s_{i}^{0}, for i ∈ [ℓ_{1} + ⋯ + ℓ_{t}].

Step 2. For k = 1, …, t − 1, let

J′_{k} := {x ∈ J_{k} : (x, k) is positively-linked} = {x_{1}^{k} < ⋯ < x_{q_{k}}^{k}} ⊆ J_{k}

and ν_{0}^{k} := id ∈ 𝔖_{n}. For each k = 1, …, t − 1 and j = 1, …, q_{k}, let (y_{j}^{k}, k_{j}) be the vertex negatively-linked to (x_{j}^{k}, k), and define inductively

S_{x_{j}^{k}y_{j}^{k}}^{k+1} := S(x_{j}^{k}, s(y_{j}^{k}, k_{j}), ν_{j−1}^{k}σ_{k}), and ν_{j}^{k} := (x_{j}^{k} s(y_{j}^{k}, k_{j}))ν_{j−1}^{k}.

Define θ_{k+1} := ν_{q_{k}}^{k}, σ_{k+1} := θ_{k+1}σ_{k}, and

S_{k+1} := ∏_{j=1}^{q_{k}}(I + S_{x_{j}^{k}y_{j}^{k}}^{k+1})(I − S_{x_{j}^{k}y_{j}^{k}}^{k+1})^{T} .

Step 3. Let T be a tableau with biword Π, and let c/a be its skew-shape. Let A_{0} := diag_{p}(a′), put B_{k} := S_{k}D_{[m_{k}]}, for k = 1, …, t, with S_{1} := P_{σ_{1}}, and define inductively

A_{k} := A_{k−1}B_{k}.

Remark 4.1. (a) The Main Algorithm only depends on the biword Π.

(b) Lemma 3.1 asserts that the permutation σ_{1} ∈ 𝔖_{t}, given in Step 1 of the Main Algorithm, is well defined.

(c) The matrix S_{x_{j}^{k},y_{j}^{k}}^{k+1}, defined in Step 2 of the Main Algorithm, is the zero matrix

whenever s(y_{j}^{k}, k_{j}) = x_{j}^{k}, that is, if x_{j}^{k} = y_{j}^{k}. Therefore, the sequence A_{0}, B_{1}, …, B_{t}, obtained through the application of the Main Algorithm may be simplified if we use a biword Π whose graphical representation has a reduced number of links between vertices in distinct rows.

(d) Fix a k ∈ {1, …, t − 1}, set u_{j} := σ_{k}^{−1}(ν_{j−1}^{k})^{−1}(x_{j}^{k}), and v_{j} := σ_{k}^{−1}(ν_{j−1}^{k})^{−1} (s(y_{j}^{k}, k_{j})). Then I + S_{x_{j}^{k},y_{j}^{k}}^{k+1} = T_{u_{j}v_{j}}(1), (I − S_{x_{j}^{k}y_{j}^{k}}^{k+1})^{T} = T_{v_{j}u_{j}}(−1), and

S_{k+1} = ∏_{j=1}^{q_{k}} T_{u_{j}v_{j}}(1)T_{v_{j}u_{j}}(−1).

(e) For i = 1, …, t, |J_{i}| = m_{i} = ∑_{k=σ^{−1}(i)}^{t} ℓ_{k} ≥ 0.

(f) Set I_{k} := [ℓ_{t+1} + ⋯ + ℓ_{k+1} + 1, ℓ_{t+1} + ⋯ + ℓ_{k+1} + ℓ_{k}], for all k = 1, …, t. Then, σ_{1}(I_{k}) = s(X_{k}), for 1 ≤ k ≤ t. In particular, s(X_{k}) = ∅ if and only if ℓ_{k} = 0.

(g) σ_{k+1} = θ_{k+1} ⋯ θ_{2}σ_{1}.

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

Proposition 4.3. Let (T, K(m)) be a tableau-pair such that T rectifies to K(m) and the word of T is a shuffle of the columns of K(m). Let Π as in (3.4) be a biword of T. Then the sequence A_{0}, B_{1}, …, B_{t} generated by the Main Algorithm is a matrix realization for T. In particular, B_{1}, …, B_{t} is a matrix realization of a Young tableau F of weight m whose shape dominates α(m).

Given a tableau T with rectification a key-tableau and whose word is a shuffle of its columns, there are, in general, several shuffle decompositions for the word of T, each corresponding to a biword Π. In the next section, we show that it is always possible to choose a biword Π where the shuffling decomposition satisfies additional properties so that the sequence B_{1}, …, B_{t} generated in the Main Algorithm is also a matrix realization of K(m).

Main Theorem 4.4. Let (T, K(m)) be a tableau-pair such that the word of T is a shuffle of the columns of K(m). Then there exists a biword Π of T such that the sequence A_{0}, B_{1}, …, B_{t} generated by the Main Algorithm is a matrix realization for the pair (T, K(m)).

As already pointed out, it has been proved that (T, K) is a matrix tableau-pair only if the word of T is in the plactic class of K [6]. Thus, when the plactic class of K is the set of all shuffles of its columns, we obtain the following characterization of matrix tableau-pairs (T, K).

Corollary 4.5. Let T be a (skew) Young tableau with rectification P. Let K be a key whose plactic class is equal to the set of all shuffles of its columns. Then, (T, K) is a matrix tableau-pair if and only if P = K.

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

Example 4.2. Consider the biword Π = ( \begin{matrix}1144 23 \\ 4321 32 \end{matrix} ) as in (3.5) (see Example 3.2).

The word 433221 is in ⊔⊔ (v_{4}^{1}, v_{3}^{0}, v_{2}^{1}, v_{1}^{0}). Let T be a tableau with biword Π. Then T has word 433221, indexing sets J_{1} = {4}, J_{2} = {3, 4}, J_{3} = {1, 2}, J_{4} = {1}, and weight (1, 2, 2, 1). The initial vertices of the lattice paths v_{4} and v_{2} are (4, 1) and (3, 2), respectively. Recalling Example 3.3, we have s_{1}^{0} = s(4, 1) = 4 and s_{2}^{0} = s(3, 2) = 3, and thus s(X_{4}) = {4} and s(X_{2}) = {3}. Then, by Step 1 of the Main Algorithm, we must consider σ_{1} ∈ 𝔖_{4} satisfying σ_{1}(1) = 4 and σ_{1}(2) = 3. Take, for instance, σ_{1} = (14)(23). Next, define

I + S_{4,4}^{2} = I + S(4, 4, σ_{1}) = I, and σ_{2} = (4 4)σ_{1} = σ_{1};
I + S_{3,2}^{3} = I + S(3, 2, σ_{2}) = T_{23}(1);
I + S_{4,1}^{3} = I + S(4, 1, (3 2)σ_{2}) = T_{14}(1), and σ_{3} = (4 1)(3 2)σ_{2};
I + S_{1,1}^{4} = I + S(1, 1, σ_{3}) = I, and σ_{4} = (1 1)σ_{3} = σ_{3}.

Finally, let a′ = (2, 2, 1, 0) + (2, 1, 1, 0) and define the matrices A_{0} = diag_{p}(a′), B_{1} = P_{σ_{1}}D_{[1]}, B_{2} = D_{[2]}, B_{3} = T_{23}(1)T_{32}(−1) T_{14}(1)T_{41}(−1)D_{[2]}, and B_{4} = D_{[1]}.

Clearly, A_{1} = A_{0}B_{1} ∼ diag_{p}(a′ + χ^{J_{1}}) and A_{2} = A_{0}B_{1}B_{2} ∼ diag_{p}(a′ + χ^{J_{1}} + χ^{J_{2}}). Since σ_{3}([2]) = J_{3}, by Lemma 4.2, we find that

A_{3} ∼_{L} diag_{p}(a′ + χ^{J_{1}} + χ^{J_{2}})P_{σ_{2}}B_{3} ∼_{L} diag_{p}(a′ + χ^{J_{1}} + χ^{J_{2}})P_{σ_{3}}D_{[2]}
∼_{R} diag_{p}(a′ + χ^{J_{1}} + χ^{J_{2}} + χ^{J_{3}}).

Since A_{4} ∼ diag_{p}(a′ +χ^{J_{1}} +⋯+χ^{J_{4}}), the sequence A_{0}, B_{1}, …, B_{4} satisfies conditions I and II of Definition 4.1. It remains to show that this sequence also defines the key K = 4321 32. Bearing in mind Lemma 4.1, we may write

B_{1}B_{2}B_{3}B_{4} = P_{σ_{1}}D_{[1]}D_{[2]}T_{23}(1)T_{14}(1)T_{32}(−1)T_{41}(−1)D_{[2]}D_{[1]}
= P_{σ_{1}}T_{23}(p)T_{14}(p^{2})D_{[1]}D_{[2]}T_{32}(−1)T_{41}(−1)D_{[2]}D_{[1]}
∼_{L} D_{[1]}D_{[2]}T_{32}(−1)T_{41}(−1)D_{[2]}D_{[1]}
∼_{R} D_{[1]}D_{[2]}D_{[2]}D_{[1]}.

Therefore, the sequence A_{0}, B_{1}, B_{2}, B_{3}, B_{4} is a matrix realization of the pair

(T = ^{1 2 2 3 3 4} , K = ^{1 2 2 3 3 4} ).

In the next examples, we show that different shuffle decompositions may give different matrix realizations of the same tableau T described in the previous example. Moreover, there are shuffle decompositions that do not produce the tableau-pair (T, K) in Theorem 4.4. More precisely, we shall see that some shuffle decompositions may lead in our matrix construction of B_{1}B_{2} ⋯ B_{t} to condition (viii) in Lemma 4.1, and, therefore, we are driven away from the key-tableau K.

Example 4.3. Consider the biword Π^{†} = ( \begin{matrix}1244 & 13 \\ 4321 & 32 \end{matrix} ) as in (3.5), which is different

from the one considered in Example 4.2. Note that s_{1}^{0} = s(4, 1) = 4 and s_{2}^{0} = s(3, 2) = 3. Following the Main Algorithm, we may define σ_{1} = (1 4)(2 3) ∈ 𝔖_{4}, the matrices

I + S_{4,4}^{2} = I + S(4, 4, σ_{1}) = I,
I + S_{3,1}^{3} = I + S(3, 1, σ_{1}) = T_{24}(1),
I + S_{4,2}^{3} = I + S(4, 2, (3 1)σ_{1}) = T_{13}(1),
I + S_{2,1}^{4} = I + S(2, 1, (4 2)(3 1)σ_{1}) = T_{12}(1),

and the permutations σ_{2} = σ_{1}, σ_{3} = (4 2)(3 1)σ_{1} and σ_{4} = (2 1)σ_{3}. Finally, define A_{0} = diag_{p}(a′), B_{1} = P_{σ_{1}}D_{[1]}, B_{2} = D_{[2]}, B_{3} = T_{24}(1)T_{42}(−1)T_{13}(1)T_{31}(−1)D_{[2]}, and B_{4} = T_{12}(1)T_{21}(−1)D_{[1]}. Applying the same arguments as the ones used in Example 4.2, we may show that the sequence A_{0}, B_{1}, B_{2}, B_{3}, B_{4} is a matrix realization for (T, K), and it is clearly different from the one obtained in Example 4.2.

Example 4.4. Consider now the biword Π′ as in (3.5) (see Example 3.2). We shall see that, in this case, the sequence of matrices obtained by the Main Algorithm is not a matrix realization of (T, K). Following Step 1 of the Main Algorithm, we may define σ_{1} = (14)(23), since s_{1}^{0} = s(4, 1) = 4 and s_{2}^{0} = s(4, 2) = 3. By Step 2, we define the matrices

I + S_{4,3}^{2} = I + S(4, 3, σ_{1}) = T_{12}(1),
I + S_{3,2}^{3} = I + S(3, 2, (4 3)σ_{1}) = T_{13}(1),
I + S_{4,1}^{3} = I + S(4, 1, (3 2)(4 3)σ_{1}) = T_{24}(1),
I + S_{2,1}^{4} = I + S(2, 1, (4 1)(3 2)(4 3)σ_{1}) = T_{12}(1),

and the permutations σ_{2} = (4 3)σ_{1}, σ_{3} = (4 1)(3 2)σ_{2} and σ_{4} = (2 1)σ_{3}. Finally, we define the matrices A_{0} = diag_{p}(a′), B_{1} = P_{σ_{1}}D_{[1]}, B_{2} = T_{12}(1)T_{21}(−1)D_{[2]}, B_{3} = T_{13}(1)T_{31}(−1)T_{24}(1)T_{42}(−1)D_{[2]}, and B_{4} = T_{12}(1)T_{21}(−1)D_{[1]}.

As in Example 4.2, using Lemma 4.2, we find that A_{0}, B_{1}, B_{2}, B_{3}, B_{4} satisfy conditions I and II of Definition 4.1. Let us now compute the invariant partition of B_{1}B_{2}B_{3}B_{4}. Using Lemma 4.1, (ii), (v), and (vii), we may write

(4.3) B_{1}B_{2}B_{3}B_{4} ∼_{L} D_{{1}}T_{21}(−1)D_{{1,2}}T_{31}(−1)T_{42}(−1)D_{{1,2}}T_{12}(1)T_{21}(−1)D_{{1}} = D_{{1}}T_{21}(−1)T_{12}(1)D_{{1,2}}T_{31}(−1)T_{32}(−1)T_{42}(−1)D_{{1,2}}T_{21}(−1)D_{{1}},

and by Lemma 4.1, (vi), we find that

(4.3) ∼_{R} D_{{1}}T_{21}(−1)T_{12}(1)D_{{1,2}}D_{{1,2}}D_{{1}}.

Since by Lemma 4.1, (viii), T_{21}(−1)T_{12}(1) = T_{22}(−1)T_{12}(1)P_{(1 2)}, we obtain

B_{1}B_{2}B_{3}B_{4} ∼ D_{{1}}T_{22}(−1)T_{12}(1)P_{(1 2)}D_{{1,2}}D_{{1,2}}D_{{1}}
∼_{L} D_{{1}}P_{(1 2)}D_{{1,2}}D_{{1,2}}D_{{1}}
∼_{R} D_{{1}}D_{{1,2}}D_{{1,2}}D_{{2}}.

The sequence B_{1}, B_{2}, B_{3}, B_{4} gives the Young tableau F = ^{1 2 2 3 3 4} ≠ K = 1 2 2 3 3 4 and, therefore, A_{0}, B_{1}, B_{2}, B_{3}, B_{4} is a matrix realization for the pair (T, F) with F ≠ K.

5. Proof of the Main Theorem

For any biword Π as in (3.4), the sequence of matrices A_{0}, B_{1}, …, B_{t} generated by the Main Algorithm always defines a tableau-pair (T, F), where T is a Young tableau with biword Π which rectifies to a key-tableau K(m), and F is some Young tableau with weight m whose shape dominates α(m). To prove that F is the rectification of T, we need restrictions on the biword Π, as we have seen in Example 4.4. The proof of the main theorem, Theorem 4.4, has therefore two parts. Firstly, we show that the matrix sequence (A_{0}, B_{1}, …, B_{t}) generated in the Main Algorithm, by a biword Π as in (3.4), defines any Young tableau T with that biword. Secondly, we show that we may always select an appropriate biword of T such that the matrix sequence B_{1}, …, B_{t} defines its rectification.

5.1. Biwords generate matrix-tableaux. In this section, we only assume that we have applied the Main Algorithm to a biword Π, without any additional conditions.

Lemma 5.1. Let t ≥ 1 and k ∈ {1, …, t}. Let (x, k) and (y, k + ε), ε ≥ 1, be two consecutive vertices of a lattice path of Π. Then θ_{k+ε} ⋯ θ_{k+1}(x) = y.

Proof. Case 1. Assume s(y, k + ε) = y. This means that there are no vertices in positions (y, j), k < j < k + ε. Thus, following Step 2 of the Main Algorithm, we may write

θ_{k+ε} ⋯ θ_{k+1} = ρ_{2}(x y)ρ_{1},

for some permutations ρ_{1}, ρ_{2} ∈ 𝔖_{n}, such that ρ_{1}(x) = x.

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

Case 2. Assume now that s(y, k + ε) ≠ y, and let (y, k + ε), (a_{1}, b_{1}), …, (a_{r}, b_{r}) be the (x, k)-path (see Definition 3.1). Clearly, s(y, k + ε) = a_{r}, the integer r is even, and, for each odd integer i ∈ [r], the vertices (a_{i}, b_{i}) and (a_{i+1}, b_{i+1}) are consecutive vertices of a lattice path, with a_{i−1} = a_{i} and a_{0} = y. Without loss of generality, assume that b_{1} ≤ b_{3} ≤ ⋯ ≤ b_{r−1}. Then, following Step 2 of the Main Algorithm, we have

θ_{k+ε} ⋯ θ_{k+1} = ρ_{1}(a_{1} a_{2})ρ_{2}(a_{2} a_{3}) ⋯ ρ_{r−2}(a_{r−2} a_{r−1})ρ_{r−1}(a_{r−1} a_{r})ρ_{r}(x a_{r})ρ_{0},

for some ρ_{i} ∈ 𝔖_{n}, such that ρ_{0}(x) = x. By an argument similar to the one used in Case 1, we find that ρ_{i}(a_{i}) = a_{i}, for i = 1, …, r, and the result follows. □

Lemma 5.2. Let t ≥ 1 and 1 ≤ j ≤ t. Let (x, j) be the initial vertex of a lattice path. Then,

(a) σ_{j}(σ_{1}^{−1}(s(x, j))) = x.

(b) σ_{j}[m_{j}] = J_{j}.

Proof. (a) Note that σ_{j}(σ_{1}^{−1}(s(x, j))) = θ_{j} ⋯ θ_{2}(s(x, j)). If there are no vertices in row x to the left of column j, then s(x, j) = x, θ_{j} ⋯ θ_{2}(x) = x, and thus σ_{j}(σ_{1}^{−1}(s(x, j))) = x.

Suppose there is a vertex in row x to the left of column j. Extend the biword Π

to a biword Π_{0} by adding extra biletters ( \begin{matrix}n + u \\ 0 \end{matrix} ) for all u ∈ [ℓ_{1} + ⋯ + ℓ_{t}], such

that ( \begin{matrix}x \\ j \end{matrix} ) and ( \begin{matrix}n + 1 \\ 0 \end{matrix} ) are consecutive vertices in Π_{0}, and the initial vertex of

each lattice path is linked to a distinct vertex (n + u, 0). In particular, the vertices (x, j) and (n + 1, 0) are linked. Put θ_{1} := ν(n + 1 s(x, j)), where ν is defined as in Step 2 of the Main Algorithm. By Lemma 5.1, θ_{j} ⋯ θ_{2}θ_{1}(n + 1) = x, that is, θ_{j} ⋯ θ_{2}(s(x, j)) = x, and the result follows. (As the lattice diagram of Π_{0} is contained in ([n] ∪ [ℓ_{1} + … + ℓ_{t}]) × ({0} ∪ [t]), in Algorithm 3.1, we have to make a shift and put y := −1 in the case of an initial vertex.)

(b) Let k ∈ {1, …, t}. Recall that I_{k} := [ℓ_{t+1} + ⋯ + ℓ_{k+1} + 1, ℓ_{t+1} + ⋯ + ℓ_{k+1} + ℓ_{k}] and |J_{j}| = m_{j} = ∑_{k=σ^{−1}(j)}^{t} ℓ_{k}. Thus, I_{k} ⊆ [m_{j}] for k ∈ {t, …, σ^{−1}(j)}. We use induction on j to prove that, if x ∈ J_{j} is such that (x, j) is a vertex of a lattice path of length k with k ∈ {t, …, σ^{−1}(j)}, there exists i_{x} ∈ I_{k} such that σ_{j}(i_{x}) = x.

When j = 1, the letters in J_{1} correspond to initial vertices of the lattice paths of length k, for k = t, …, ε, where ε := σ^{−1}(1). Therefore, we may write

{(x, 1) : x ∈ J_{1}} = ⋃_{k=t}^{ε} X_{k}.

By the definition of σ_{1}, we have σ_{1}(I_{k}) = s(X_{k}). Since s(X_{k}) = {x : (x, 1) ∈ X_{k}}, for k = t, …, ε, the result follows.

Fix now j in {2, …, t}, and let y ∈ J_{j} be the row index of a letter j belonging to a lattice path v of length k. Clearly, we must have k ∈ {t, …, σ^{−1}(j)}. If (y, j) is the initial vertex of v then, by (a), we have σ_{j}(σ_{1}^{−1}(s(y, j))) = y, with σ_{1}^{−1}(s(y, j)) ∈ I_{k}.

Assume now that (y, j) is negatively-linked to a vertex (x, j − ε) with x ≥ y, and ε ≥ 1. By induction, there exists i_{x} ∈ I_{k} such that σ_{j−ε}(i_{x}) = x, and by Lemma 5.1 we find that θ_{j} ⋯ θ_{j−ε+1}(x) = y. Thus,

σ_{j}(i_{x}) = θ_{j} ⋯ θ_{j−ε+1}σ_{j−ε}(i_{x}) = y.

By induction, our claim is proved. Thus, for each x ∈ J_{j} there is i_{x} ∈ [m_{j}] such that σ_{j}(i_{x}) = x. Since |J_{j}| = m_{j}, we must have σ_{j}([m_{j}]) = J_{j}. □

Corollary 5.3. If (x, j) is a vertex of a lattice path of length k with initial vertex (y, j − ε), ε ≥ 0, then σ_{j}^{−1}(x) = σ_{j−ε}^{−1}(y) = σ_{1}^{−1}(s(y, j − ε)) ∈ I_{k}.

Proof. This follows from the proof of the previous lemma. □

Proof of Proposition 4.3. Let t ≥ 1. We have to show that, for each k ∈ {0, 1, …, t}, the matrix A_{k}, given by Step 3 of the Main Algorithm, is left equivalent to diag_{p}(a′ + χ^{J_{0}} + χ^{J_{1}} ⋯ + χ^{J_{k}})P_{σ_{k}}, where σ_{0} := id ∈ 𝔖_{n} and J_{0} := ∅. The proof is by induction on k. For k = 0, P_{id} = I and A_{0} := diag_{p}(a′), and in this case there is nothing to prove. So let k be in {1, …, t}. By induction, A_{k−1} is left equivalent to diag_{p}(a′ + χ^{J_{1}} ⋯ + χ^{J_{k−1}})P_{σ_{k−1}}. Therefore, by definition of B_{k}, A_{k} is left equivalent to

(5.1)  diag_{p}(a′ + χ^{J_{1}} ⋯ + χ^{J_{k−1}})P_{σ_{k−1}}S_{k}D_{[m_{k}]}.

Recall that S_{1} = P_{σ_{1}} and S_{k} = ∏_{i=1}^{q_{k−1}}(I + S_{x_{i}^{k}y_{i}^{k}}^{k})(I − S_{x_{i}^{k}y_{i}^{k}}^{k})^{T}, for k > 1. Therefore, by Lemma 4.2 and (5.1), A_{k} is left equivalent to

(5.2) diag_{p}(a′ + χ^{J_{1}} ⋯ + χ^{J_{k−1}})P_{σ_{k}}D_{[m_{k}]} = diag_{p}(a′ + χ^{J_{1}} ⋯ + χ^{J_{k−1}})D_{σ_{k}[m_{k}]}P_{σ_{k}}.

By Lemma 5.2 (b), we have σ_{k}[m_{k}] = J_{k}, and the result follows. □

5.2. Biwords again: a canonical biword. In the proof of Proposition 4.3 there are no restrictions on the shuffle decomposition that we have considered in Π. The sequence of matrices A_{0}, B_{1}, …, B_{t} given by the Main Algorithm satisfies always conditions I and II of Definition 4.1 for any biword Π as in (3.4) of T. To prove that B_{1}, …, B_{t} defines the rectification of T, we need restrictions on the biword Π, as we have seen in Example 4.4. We shall show that we may always choose a biword equivalent to Π obeying conditions that are convenient for our purpose.

In a biword Π some vertices play a special role in the proof of our Theorem 4.4. They are identified in the following definitions.

Definition 5.1. Given distinct lattice paths u, v of Π, a vertex (a, b) ∈ u is said to be a right critical vertex of the pair (u, v) if it is positively-linked to a vertex (a′, b′) such that (s(a′, b′), b) belongs to v. If b′ = b + 1 the right critical vertex is of type I, otherwise it is of type II.

Given pairwise distinct lattice paths v_{1}, …, v_{k}, k ≥ 2, of Π, a vertex (a_{1}, b_{1}) ∈ v_{1} is said to be a right critical vertex of type I (respectively of type II) of (v_{1}, …, v_{k}) with critical components v_{2}, …, v_{k−1}, if

• (a_{1}, b_{1}) ∈ v_{1} is a right critical vertex of type I (respectively of type II) of (v_{1}, v_{2}), positively-linked to (a_{2}, b_{2});

• for i = 2, …, k − 2, (s(a_{i}, b_{i}), b_{1}) is a right critical vertex of (v_{i}, v_{i+1}) positivelylinked to (a_{i+1}, b_{i+1}), and

• (s(a_{k−1}, b_{k−1}), b_{1}) is a right critical vertex of (v_{k−1}, v_{k}).

Since the lattice paths are distinct, a right critical vertex of type I is always an obstacle. In the case of a right critical vertex of type II, b′ − b > 1 and we may have a′ = a with an obstacle of another lattice path between (a, b) and (a, b′). The following diagrams are schematic representations of right critical vertices of types I and II, respectively, both with one critical component,

.

Definition 5.2. Given distinct lattice paths u, v of Π, a vertex (a, b) ∈ u is said to be a left critical vertex of (u, v) if it is not negatively-linked to a vertex in column b − 1 and there is an obstacle on its left in position (a, b − 1) belonging to v.

Given pairwise distinct lattice paths v_{1}, …, v_{k}, k ≥ 2, of Π, a vertex (a_{1}, b) ∈ v_{1} is a left critical vertex of (v_{1}, …, v_{k}) with critical components v_{2}, …, v_{k−1} if • (a_{1}, b) ∈ v_{1} is a left critical vertex of (v_{1}, v_{2});

• for i = 1, …, k − 2, the obstacle (a_{i}, b − 1) ∈ v_{i+1} is a right critical vertex of type I of (v_{i+1}, v_{i+2}) positively-linked to a vertex (a_{i+1}, b), and

• (a_{k−1}, b − 1) is an obstacle of (v_{k−1}, v_{k}).

Schematically, with k = 2, either (a_{1}, b) is the initial vertex of v_{1} or it is negatively linked to a vertex not in column b − 1.

.

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

In what follows, given a biword Π as in (3.4), we provide a procedure to adjust the links between their vertices, to form a new biword Π′ equivalent to Π, where the new lattice path decomposition satisfies some properties needed in the sequel.

Algorithm 5.1. Let Π be the biword (3.4) identified with its lattice path representation in [n] × [t]. For each vertex (a, b) of Π, we move along each column, from top to bottom, and left to right, to check whether (a, b) is a left or a right critical vertex of type I of a pair of lattice paths (u, v) such that both have vertices in columns b, b + 1, …, b + r, with r ≥ 1, u is below v in columns b, …, b + r − 1, and u is above v in column b + r. If so, we have two situations:

1- (a, b) is a left critical vertex of (u, v), and then (a, b−1) is an obstacle of v. The lattice paths u and v, restricted to the vertices in columns [b, b + r] and [b − 1, b + r], respectively, are the factors of the sub-biword

Π_{L} = uv

= (\begin{matrix}a_{r} & a_{r−1} & ⋯ & a_{1} & a \\ b + r & b + r − 1 & ⋯ & b + 1 & b \end{matrix}) (\begin{matrix}c_{r} & c_{r−1} & ⋯ & c_{1} & c & a \\ b + r & b + r − 1 & ⋯ & b + 1 & b & b − 1 \end{matrix})

of Π, respectively, where a > c, a_{i} > c_{i}, for i = 1, …, r −1, and a_{r} < c_{r}. Then, relink the vertices of u and v, between columns b and b + r, so that the sub-biword Π_{L} is replaced by

Π′_{L} = (\begin{matrix}a_{r} & c_{r−1} & ⋯ & c_{1} & c \\ b + r & b + r − 1 & ⋯ & b + 1 & b \end{matrix}) (\begin{matrix}c_{r} & a_{r−1} & ⋯ & a_{1} & a & a \\ b + r & b + r − 1 & ⋯ & b + 1 & b & b − 1 \end{matrix}) ,

.

2- (a, b) is a right critical vertex of type I of (u, v). The lattice paths u and v restricted to the vertices in columns [b, b + r] are factors of the sub-biword

Π_{R} = uv = (\begin{matrix}a_{r} & a_{r−1} & ⋯ & a_{1} & a \\ b + r & b + r − 1 & ⋯ & b + 1 & b \end{matrix}) (\begin{matrix}c_{r} & c_{r−1} & ⋯ & c_{1} & c \\ b + r & b + r − 1 & ⋯ & b + 1 & b \end{matrix})

of Π, where a > c = a_{1}, a_{i} > c_{i}, for i = 2, …, r − 1, and a_{r} < c_{r}. Then, relink the vertices of u and v, between columns b and b + r, so that the sub-biword Π_{R} is replaced by

Π′_{R} = (\begin{matrix}a_{r} & c_{r−1} & ⋯ & c_{1} & a \\ b + r & b + r − 1 & ⋯ & b + 1 & b \end{matrix}) (\begin{matrix}c_{r} & a_{r−1} & ⋯ & a_{1} & c \\ b + r & b + r − 1 & ⋯ & b + 1 & b \end{matrix}) ,

.

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

As there is only a finite number of vertices, this algorithm produces a new biword Π′, equivalent to Π, under the conditions of (3.4), satisfying the following proposition.

Proposition 5.4. The biword Π′ obtained by the application of Algorithm 5.1 to Π is such that, if u and v are two lattice paths each having vertices in all columns b, …, b + r, for some b, b + r ∈ [t], with r ≥ 1, and, if (a, b) is either a left critical vertex, or a right critical vertex of type I of (u, v), then the vertices of u are below the vertices of v in columns b, b + 1, …, b + r.

Remark 5.1. A biword Π satisfies trivially the conditions of the proposition above if either (1) two vertices in the same row belong to the same lattice path; or, (2) if (a, b′) and (a, b), b′ < b, are two vertices of Π in distinct lattice paths, then (a, b′) is single or only negatively linked, that is, s(a, b) = a.

When T rectifies to K(σα(m)), with σ the identity, or the reverse permutation in 𝔖_{t}, or σ ∈ 𝔖_{3}, the conditions in the proposition above are satisfied [4, 5, 7].

Example 5.1. (1) The biword Π as in (3.5) used in the matrix construction of Example 4.2 satisfies Proposition 5.4.

(2) In Example 4.4 the biword Π′ as in (3.5) was used in the matrix construction, but the sequence B_{1}, …, B_{4} generated in the Main Algorithm does not define K. Notice that both lattice paths u = \binom{14}{32} and v = \binom{1234}{4321} have vertices in columns 3 and 2; the vertex in position (4, 2) is a left critical vertex of (u, v), and u is above v in column 3. Therefore Π′ does not satisfy Proposition 5.4. Applying the algorithm above, we get Π^{†} as in (3.5), which already satisfies the conditions of Proposition 5.4,

(5.3)  .

Π^{†} was used in the matrix construction of Example 4.3 where the sequence B_{1}, …, B_{t} produces K.

(3) Consider now the lattice path representation of the biword

(\begin{matrix}11355777 444466 223345 \\ 87654321 865431 865431 \end{matrix}) .

This biword does not satisfy the conditions of Proposition 5.4, since, for example, the vertex (7, 3) is a right critical vertex of the lattice paths u = \binom{11355777}{87654321} and v = \binom{444466}{865431}. Both have vertices in columns 3, 4, …, 7, and u is above v in column 7. Below are the successive steps of the application of Algorithm 5.1 to this biword. Notice that the lattice path representation of the final biword satisfies the conditions of Proposition 5.4,

,

.

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

Lemma 5.5. Let (x, k) and (y, k + ε), ε ≥ 1, be two consecutive vertices of a lattice path of length q in Π with initial vertex (u, k′). Then the permutation ν and the matrix

S_{x,y}^{k+1} = S(x, s(y, k + ε), νσ_{k})

defined in Step 2 of the Main Algorithm satisfy:

(a) ν(x) = x.

(b) ν^{−1}(s(y, k + ε)) ∉ J′_{k} = {a ∈ J_{k} : (a, k) is a positively-linked vertex}.

(c) I + S_{x,y}^{k+1} = T_{ij}(1), with i = σ_{k}^{−1}(x) = σ_{1}^{−1}(s(u, k′)) ∈ I_{q} ⊆ [m_{k}], and j ∉ [|J′_{k}|].

Proof. (a) and (b) are obvious. To prove (c), recall that by the definition of the matrix I + S_{x,y}^{k+1} = (s_{ij}), we have s_{ij} ≠ 0 only if νσ_{k}(i) = x and νσ_{k}(j) = s(y, k + ε).

Using (a) and Corollary 5.3, we obtain

i = σ_{k}^{−1}(x) = σ_{1}^{−1}(s(u, k′)) ∈ I_{q} ⊆ [m_{k}].

Now, by (b), we find that σ_{k}(j) = ν^{−1}(s(y, k + ε)) ∉ J′_{k}. If σ_{k}(j) ∉ J_{k}, by Lemma 5.2 (b), we must have j ∉ [m_{k}]. Assume now that σ_{k}(j) ∈ J_{k} \ J′_{k}. Then, we must have σ_{k}(j) = a, where (a, k) is a not positively-linked vertex of a lattice path of length q′, with q > q′. Thus j = σ_{k}^{−1}(a) ∈ I_{q} ⊆ [m_{k}] \ [|J′_{k}|]. □

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

Example 5.2. Let Π = ( \begin{matrix}1112223 2233 1 \\ 7654321 7542 4 \end{matrix} ) and its lattice path representation

(5.4)  .

Applying the Main Algorithm, we must set σ_{1} = (13), since s_{1}^{0} = s(3, 1) = 3, s_{2}^{0} = s(3, 2) = 2 and s_{3}^{0} = s(1, 4) = 1, and thus σ_{i} = (3 2)σ_{1}, for i = 2, 3, 4 and σ_{5} = (3 2)(2 1)σ_{4}. Consider the matrices S_{3,2}^{2} = S(3, s(2, 2), σ_{2}), S_{2,1}^{5} = S(2, s(1, 5), σ_{4}), and S_{3,2}^{5} = S(2, s(2, 5), (2 1)σ_{4}), produced in Step 2 of the Main Algorithm. Since s(2, 2) = 2, s(1, 5) = 1 and s(2, 5) = 2, we get

(5.5)  I + S_{3,2}^{2} = T_{12}(1), I + S_{2,1}^{5} = T_{13}(1), and I + S_{3,2}^{5} = T_{23}(1).

Each matrix in (5.5) is upper triangular and satisfies Lemma 5.5. Notice that in the last two matrices the column index 3 ∈ [3] = [m_{4}]. This is consistent with the previous corollary, since the vertex (1, 4) is not positively-linked, and (2, 4) and (3, 4)

are right critical vertices of type I of ((\begin{matrix}1112223 \\ 7654321 \end{matrix}) , (\begin{matrix}1 \\ 4 \end{matrix})) and of ((\begin{matrix}2233 \\ 7542 \end{matrix}) , (\begin{matrix}1 \\ 4 \end{matrix})),

respectively.

In the next lemmas, we analyse the relationship between the critical vertices of our chosen biword Π and the matrices defined in Step 2 of the Main Algorithm. This analysis is important in order to prove that the invariant partition of B_{1}, …, B_{t} is the shape of K.

Lemma 5.7. For q = 1, r, let (x_{q}, k) and (y_{q}, k + ε_{q}) be a pair of linked vertices belonging to the lattice path u_{q}, with x_{1} < x_{r}, and consider the matrices I + S(x_{q}, s(y_{q}, k + ε_{q}), ν_{q}σ_{k}) = T_{i_{q}j_{q}}(1). Then j_{1} = j_{r} if and only if (x_{r}, k) is a right critical vertex of type I or II of (u_{r}, …, u_{2}, u_{1}), k ≥ 2, with critical components u_{r−1}, …, u_{2}.

Proof. The if part. Without loss of generality assume that (x_{2}, k) is a right critical vertex of type I or II of (u_{2}, u_{1}), without critical components. Then x_{1} = s(y_{2}, k+ε_{2}) and we may write ν_{2}σ_{k} = θ(x_{1} s(y_{1}, k + ε_{1}))ν_{1}σ_{k}, where θ ∈ 𝔖_{n} satisfy θ(x_{1}) = x_{1}. Since ν_{2}σ_{k}(j_{1}) = x_{1} we get ν_{2}σ_{k}(j_{1}) = θ(x_{1}) = x_{1}, and the result follows.

The only if part. Without loss of generality, assume that in the matrix B_{k}, defined in steps 2 and 3 of the Main Algorithm, there are no matrices T_{ij_{1}}(1) between T_{i_{1}j_{1}}(1) and T_{i_{2}j_{1}}(1). Then, we may write ν_{2}σ_{k} = θ(x_{1}s(y_{1}, k+ε_{1}))ν_{1}σ_{k}, for some permutation θ ∈ 𝔖_{n} satisfying θ(x_{1}) = x_{1}. By definition, we must have ν_{2}σ_{k}(j_{1}) = s(y_{2}, k + ε_{2}). On the other hand, ν_{2}σ_{k}(j_{1}) = θ(x_{1} s(y_{1}, k + ε_{1})) ν_{1}σ_{k}(j_{1}) = x_{1}. Therefore, we find that x_{1} = s(y_{2}, k + ε_{2}), and this equality means that (x_{2}, k) is a right critical vertex of type I or II of (u_{2}, u_{1}). □

Lemma 5.8. Suppose m_{k} < m_{k+1}, and let (x, k) and (y, k+1) be consecutive vertices of the lattice path v_{l}. Then I + S(x, y, νσ_{k}) = T_{ij}(1) with m_{k} < j ≤ m_{k+1} if and only if there is a vertex (a, k + 1) belonging to a lattice path v_{1} which is a left critical vertex of (v_{1}, …, v_{l}), with σ_{k+1}^{−1}(a) = j.

Proof. The if part. Without loss of generality, assume that (x, k + 1) is a left critical vertex of (u, v), with no critical components. Since σ_{k+1}([m_{k+1}]) = J_{k+1}, there is j ∈ [m_{k+1}] such that σ_{k+1}(j) = x. Consider the matrix S(x, y, νσ_{k}). Clearly, we may write σ_{k+1} = θ(x y)νσ_{k}, where θ ∈ 𝔖_{n} satisfy θ(x) = x. Therefore, νσ_{k}(j) = (x y)θ^{−1}σ_{k+1}(j) = y, and thus I + S(x, y, νσ_{k}) = T_{ij}(1), for some integer i ∈ [m_{k}]. Finally, note that since the lattice path v has no vertex in column k, all vertices in column k must be positively-linked. Thus, by Lemma 5.5, we find m_{k} < j.

The only if part. Assume now that I + S(x, y, νσ_{k}) = T_{ij}(1), for some integer m_{k} < j ≤ m_{k+1}. Again, it is clear that we must have

σ_{k+1} = ρ(x_{r} x_{r−1}) ⋯ (x_{2} x_{1})(x_{1} x)(x y)νσ_{k},

for some integers x_{r} > ⋯ > x_{1} > x > y and a permutation ρ ∈ 𝔖_{n} such that ρ(x_{r}) = x_{r}. Thus, σ_{k+1}(j) = x_{r} ∈ J_{k+1}, since j ∈ [m_{k+1}]. Denote by v the lattice path containing the vertex (x_{r}, k + 1), and note that since ρ(x_{r}) = x_{r}, v cannot have a vertex in column k. Thus, (x_{r}, k + 1) is a left critical vertex of (u, v). □

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

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

Proof of Theorem 4.4. It was shown in Proposition 4.3 that A_{0}, B_{1}, …, B_{t} satisfy conditions I and II of Definition 4.1. So it remains to show that B_{1} ⋯ B_{t} is equivalent to the diagonal matrix D_{[m_{1}]} ⋯ D_{[m_{t}]}, that is, B_{1}, …, B_{t} is a matrix construction of the key with weight (m_{1}, …, m_{t}). Using Corollary 5.3, Lemma 5.7, and the commutation rules in Lemma 4.1, we may write each matrix

B_{k} = ∏_{l=1}^{q_{k−1}}(T_{i_{l}j_{l}}(1)T_{j_{l}i_{l}}(−1))D_{[m_{k}]},

k = 2, …, t, as

B_{k} = (∏_{l=1}^{q_{k−1}} T_{i_{l}j_{l}}(1)) C_{k}D_{k} (∏_{l=1}^{q_{k−1}} T_{j_{l}i_{l}}(−1)) D_{[m_{k}]},

where each C_{k+1} [respectively D_{k+1}] is a product of upper [respectively lower] triangular elementary matrices T_{ij}(1), with i, j ∈{i_{1}, …, i_{q_{k}}}, i ≠ j. Moreover, note that T_{ij}(1) is a factor of C_{k+1}D_{k+1} only if there are lattice paths u_{l} with vertices (a_{l}, k) such that σ_{k}^{−1}(a_{l}) = l, for l = i, j, and where (a_{i}, k) is a right critical vertex of type I or II of (u_{i}, u_{j}). We will refer to T_{i_{l}j_{l}}(1) and T_{j_{l}i_{l}}(−1), l = 1, …, q_{k−1}, as original matrices of B_{k}, and we call the triangular matrices in C_{k}D_{k} secondary matrices.

Denote by u_{l} the lattice path for which σ_{0}^{−1}(u_{l}^{0}) = l, with u_{l}^{0} the column index of its initial vertex, for l ∈ [ℓ_{1} + ⋯ + ℓ_{t}]. Next, for k = 2, …, t, using Lemma 5.8 write

(5.6)  B_{k} = (∏_{l=1}^{q_{k−1}} T_{i_{l}j_{l}}(1)) C_{k}D_{k}D_{[m_{k}]} (∏_{l=1}^{q_{k−1}} T_{j_{l}i_{l}}(ϕ_{l})) ,

where ϕ_{l} = −1 if T_{j_{l}i_{l}}(−1) = S(x, y, νσ_{k}), if (x, k) and (y, k + 1) are linked vertices of u_{i_{l}} and there is a vertex (a, k + 1) ∈ u_{j_{l}}, which is a left critical vertex of (u_{j_{l}}, u_{i_{l}}); otherwise ϕ_{l} = −p.

The next step consists in using the commutation rules in Lemma 4.1 and Corollary 5.6 to eliminate, by left equivalence, the left most upper triangular matrix T_{ij}(x) in D_{[m_{1}]}B_{2} ⋯ B_{t}. Notice that this operation may generate new matrices T_{uv}(y). Repeat this operation, eliminating all upper triangular matrices.

By Lemma 4.1, there exists always a unimodular elementary matrix E such that

T_{ji}(τ)T_{ab}(τ′) = T_{ab}(ϱ′)T_{ji}(ϱ)E, with ϱ, τ and ϱ′, τ′ pairs of associated elements,

whenever τ, τ′ are not both unities, or (a, b) ≠ (i, j) if i ≠ j. Thus, the matrix operations described in the previous paragraph are feasible if they do not involve the passage of a matrix T_{ij}(τ), with i < j, to the left of a matrix T_{ji}(τ′), with τ = −τ′ = ±1.

We begin by noticing that D_{[m_{l}]}T_{ij}(1) = T_{ij}(p)D_{[m_{l}]}, whenever m_{l} < j. Thus, the situation described above only happens if the diagonal matrices, say D_{[m_{k+1}]}, …, D_{[m_{k+ε}]}, between T_{ji}(τ′) and T_{ij}(τ) satisfy j ≤ m_{k+1}, …, m_{k+ε}. If T_{ji}(τ′) = I − S(x, y, νσ_{k−1})^{T} is a original matrix of B_{k}, (5.6) implies the existence of a left critical vertex (a, k + 1) ∈ u_{j} of (u_{j}, u_{i}). If T_{ji}(τ′) is a secondary matrix of B_{k+1}, by Lemma 5.7, there is a right critical vertex of type I of u_{j}, in column k, of (u_{j}, u_{i}). By (5.6) and Lemma 4.1, any other case implies the existence of a sequence of matrices

(5.7)  T_{i_{0}i_{1}}(τ_{0}), T_{i_{1}i_{2}}(τ_{1}), …, T_{i_{s}i_{s+1}}(τ_{s}),

with i_{l} ≤ m_{k+1}, …, m_{k+ε}, for l = 0, 1, …, s + 1, s ≥ 1, which generates the matrix T_{ji}(τ′) by the process of elimination described above. By Corollary 5.6, and Lemmas 5.7 and 5.8, the matrices in (5.7) are the result of left or right critical vertices of type I. In particular, we find that u_{i_{0}} is below u_{i_{1}} in columns k + 1, …, k + ε, u_{i} is above u_{i_{1}} in columns k + ζ, …, k + ε and u_{j} is below u_{i_{0}} in columns k + ξ, …, k + ε, for some ε ≥ ζ, ξ ≥ 1. In any case, the existence of T_{ji}(τ′) means that u_{j} is below u_{i} in columns k + ε′, …, k + ε, for some ε ≥ ε′ ≥ 1.

The same reasoning shows that the existence of T_{ij}(τ) means that u_{i} is below u_{j} in column k + ε, contradicting Proposition 5.4. Therefore, whenever T_{ji}(τ), i < j, is on the left of D_{[m_{k+1}]} and satisfies j ≤ m_{k+1}, any elementary matrix T_{ij}(x) is transformed, during the process of its elimination by left equivalence, into T_{ij}(xp) when reaching the diagonal matrix D_{[m_{k+1}]}. We may thus eliminate all upper triangular matrices, and obtain

(5.8)  B_{1} ⋯ B_{t} ∼_{E} D_{[m_{1}]}T_{2}D_{[m_{2}]} ⋯ T_{t}D_{[m_{t}]},

where each T_{k} is a product of lower elementary triangular matrices, k = 2, …, t. Finally, using Lemma 4.1, together with Corollary 5.6, we may eliminate by right equivalence all these lower elementary triangular matrices, beginning with the right most triangular matrix in (5.8), and ending in the left most triangular matrix in T_{2}. Therefore, (5.8) is equivalent to D_{[m_{1}]} ⋯ D_{[m_{t}]}. □

6. Matrix tableau-pairs with key condition over a four-letter alphabet

6.1. An injection of the Knuth class of a key over the four-letter alphabet into a key over the six-letter alphabet. According to Theorem 2.1, in the case of a four-letter alphabet, the problem of a matrix construction of a tableau-pair (T, K), where T rectifies to the key-tableau K, is reduced to the key-tableau K(σ, (ℓ_{4}, …, ℓ_{1})) with σ ∈ S, ℓ_{2} > 0, and ℓ_{4} > 0, since its Knuth class is the union of the sets ⊔⊔(v̂_{5}^{n_{5}}, v_{4}^{ℓ_{4}−n_{5}}, v_{3}^{ℓ_{3}}, v_{2}^{ℓ_{2}−n_{5}}, v_{1}^{ℓ_{1}}) for 0 ≤ n_{5} ≤ min{ℓ_{2}, ℓ_{4}}. Recall, from Section 2, that v̂_{5} = 431421 and S = {1423, 1432, 4123, 4132}.

Consider w ∈⊔⊔(v̂_{5}^{n_{5}}, v_{4}^{n_{4}}, …, v_{1}^{n_{1}}), for some 0 ≤ n_{5} ≤ min{ℓ_{2}, ℓ_{4}}, n_{i} = ℓ_{i}, i = 1, 3, and n_{i} = ℓ_{i} − n_{5}, i = 2, 4. Let {X_{5}^{n_{5}}, …, X_{5}^{1}, …, X_{1}^{n_{1}}, …, X_{1}^{1}} be a set partition of [ ∑_{i=1}^{4} in_{i} + 6n_{5}], with w|X_{j}^{i} = v_{j}, i ∈ [n_{j}], j ∈ {1, 2, 3, 4}, and w|X_{5}^{i} = v̂_{5}, i ∈ [n_{5}]. Let I^{j,i} be a row of length j, for i ∈ [n_{j}], j = 1, …, 4, and I^{5,i} = a^{i}b^{i}c^{i}d^{i}e^{i}f^{i}, with a^{i} ≤ b^{i} ≤ c^{i} < d^{i} ≤ e^{i} ≤ f^{i}, for i ∈ [n_{5}]. We consider the biword

(6.1)  Π^{+} = (\begin{matrix}I^{5,n_{5}} & ⋯ & I^{5,1} \\ v̂_{5} & ⋯ & v̂_{5} \end{matrix}| \begin{matrix}I^{4,n_{4}} & ⋯ & I^{4,1} & ⋯ & I^{1,n_{1}} & ⋯ & I^{1,1} \\ v_{4} & ⋯ & v_{4} & ⋯ & v_{1} & ⋯ & v_{1} \end{matrix})

with bottom row v̂_{5}^{n_{5}}v_{4}^{n_{4}} ⋯ v_{1}^{n_{1}}. The lattice path representation Π^{+} as in (6.1) consists

of n_{5} +⋯+n_{1} nonintersecting lattice paths: the n_{j} lattice paths ( \begin{matrix}I^{j,i} \\ v_{j} \end{matrix} ) of length j

have nonnegative slope, for i ∈ [n_{j}], j ∈ {1, 2, 3, 4}, and the n_{5} lattice paths ( I^{5,i} ; v̂_{5} ),

i ∈ [n_{5}], of length 6, are such that the line linking the vertices ( \begin{matrix}c^{i} \\ 1 \end{matrix} ) and ( \begin{matrix}d^{i} \\ 4 \end{matrix} )

has negative slope.

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

Lemma 6.1. There is a biword Π̂^{+} equivalent to Π^{+} as in (6.1) satisfying the following conditions:

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

(b) If ( \begin{matrix}abcdef \\ 431421 \end{matrix} ) is a lattice path of Π̂^{+} then:

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

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

(iii) if d ≠ e, in row e, to the right of (e, 2), there are no vertices.

Proof. We prove only condition (b)(iii). All other conditions are proven in a similar way. Recall that we must have a ≤ b ≤ c < d ≤ e ≤ f. If (e, 3) is also a vertex of Π^{+}, then it must belong to one of the words 431421, 4321 or 431. In these cases, Π^{+} must have a sub-biword either of the form

Γ = ( \begin{matrix}abcdef & gehjkl \\ 431421 & 431421 \end{matrix} ) , or Δ = ( \begin{matrix}abcdef & gehi \\ 431421 & 4321 \end{matrix} ) , or Λ = ( \begin{matrix}abcdef & geh \\ 431421 & 431 \end{matrix} ) ,

with g ≤ e ≤ h ≤ i < j ≤ k ≤ l. We may re-link the vertices of the lattice paths of Γ, Δ, or Λ such that they are replaced in Π^{+} by

( \begin{matrix}abcjkl & geef & dh \\ 431421 & 4321 & 41 \end{matrix} ) , ( \begin{matrix}abcdhi & geef \\ 431421 & 4321 \end{matrix} ) , or ( \begin{matrix}geef & abc & dh \\ 4321 & 431 & 41 \end{matrix} ) ,

respectively. In either case, the vertex (e, 2) belongs now to the new lattice path

\binom{geef}{4321}, and it is linked to (e, 3). We have only changed the links in the two lattice

paths. Therefore, we may assume, without loss of generality, that, if (e, 2) is a vertex

of a lattice path ( I^{5,i} ; v̂_{5} ), there is no vertex in position (e, 3).

Assume now that (e, 4) is a vertex, but (e, 3) is not. An analysis similar to the

one done above shows that if (e, 4) is a vertex of ( I^{5,i} ; v̂_{5} ) or ( \begin{matrix}I^{j,i} \\ v_{j} \end{matrix} ), for some

j = 1, …, 4, then we may re-link the vertices of the corresponding lattice paths in such a way that the vertex (e, 2) is linked to (e, 4). Therefore, we may assume that (e, 4) is not a vertex of Π^{+}. □

Example 6.1. The biword Π^{+} = ( \begin{matrix}113566 & 2234 & 3 \\ 431421 & 4321 & 4 \end{matrix} ), whose lattice path repre-

sentation is given below, fails to satisfy condition (b)(i) of the lemma above, since

the vertex (3, 1) belongs to the lattice path of ( \begin{matrix}113566 \\ 431421 \end{matrix} ), and there is a vertex in row 3, column 2

(6.2)  .

Rearranging the links between the vertices, we obtain the biword

Π̂^{+} = ( \begin{matrix}114566 & 2233 & 3 \\ 431421 & 4321 & 4 \end{matrix} ) ,

which satisfy all the required conditions of Lemma 6.1

(6.3)  .

In what follows, we assume that our biword Π^{+} satisfies the conditions of Lemma 6.1.

Corollary 6.2. (a) If (a, i) is the initial vertex of a lattice path of length k, then s(a, i) ≠ a only if σ ∈ {4123, 4132}, i = 4, k = 1, and the nearest vertex in row a

is either in column 1, which is the rightmost vertex of the lattice path ( I^{5,i} ; v̂_{5} ) or of

( \begin{matrix}I^{j,i} \\ v_{j} \end{matrix} ), for some j = 1, …, 4, or in column 2, which is a vertex of ( \begin{matrix}I^{4,i} \\ v_{4} \end{matrix} ).

(b) If (b, j), (a, i) are consecutive vertices of a lattice path of length k, then s(a, i) ≠ a only if j = 1, i = 4, and the nearest vertex in row a is in column 2, and it is a vertex

of ( \begin{matrix}I^{4,i} \\ v_{4} \end{matrix} ).

Proof. This follows from Lemma 6.1 (a). □

For each σ = σ(1)σ(2)σ(3)σ(4) in 𝔖_{4}, consider the permutation

\overline{σ}(1)\overline{σ}(2)\overline{σ}(3)\overline{σ}(4)34 ∈ 𝔖_{6},

where

\overline{σ}(k) = \begin{cases}σ(k), & if σ(k) = 1, 2, \\ σ(k) + 2, & if σ(k) = 3, 4. \end{cases}

This correspondence is a bijection between 𝔖_{4} and the set \{\overline{σ} = α34 ∈ 𝔖_{6} : α ∈ 𝔖_{{1256}}} ⊆ 𝔖_{6}. In particular, S = {1423, 1432, 4123, 4132} is transformed into \{162534, 165234, 612534, 615234\} ⊆ 𝔖_{6}. Let ρ : \{v̂_{5}, v_{j} : j ∈ [4]\} → \{\overline{v}_{j} : j ∈ [6]\}, such that ρ(v̂_{5}) = \overline{v}_{6} and ρ(v_{j}) = \overline{v}_{j}, j = 1, 2, 3, 4, where \overline{v}_{6}, …, \overline{v}_{1} are the columns of the key encoded by the permutation \overline{σ} and the vector (1^{6}).

For each n_{5} = 0, …, min{ℓ_{2}, ℓ_{4}}, the map ρ can be extended, by shuffling, to a bijection between the sets ⊔⊔ (v̂_{5}^{n_{5}}, v_{4}^{n_{4}}, …, v_{1}^{n_{1}}) and ⊔⊔ (\overline{v}_{6}^{n_{5}}, \overline{v}_{4}^{n_{4}}, …, \overline{v}_{1}^{n_{1}}). This last set is a subset of the plactic class of the key encoded by the permutation \overline{σ} and the vector (n_{5}, 0, n_{4}, n_{3}, n_{2}, n_{1}). Thus every word in the plactic class of K(σα(m)), σ ∈ 𝔖_{4}, has a copy in the shuffle of the columns of some key over the alphabet [6]. Let w ∈⊔⊔(v̂_{5}^{n_{5}}, v_{4}^{n_{4}}, …, v_{1}^{n_{1}}). Fix an equivalent biword Π^{+} as in (6.1) satisfying the conditions of Lemma 6.1, and let

(6.4)  \overline{Π}^{+} = (\begin{matrix}I^{5,n_{5}} & ⋯ & I^{5,1} & I^{4,n_{4}} & ⋯ & I^{4,1} & ⋯ & I^{1,n_{1}} & ⋯ & I^{1,1} \\ \overline{v}_{6} & ⋯ & \overline{v}_{6} & \overline{v}_{4} & ⋯ & \overline{v}_{4} & ⋯ & \overline{v}_{1} & ⋯ & \overline{v}_{1} \end{matrix})

be the biword that we obtain when we transform each lattice path (\begin{matrix}I^{j,i} \\ v_{j} \end{matrix}) and

(\begin{matrix}a^{i}b^{i}c^{i}d^{i}e^{i}f^{i} \\ 4 3 1 4 2 1 \end{matrix}) of Π^{+} into (\begin{matrix}I^{j,i} \\ \overline{v} & j \end{matrix}) and ( \begin{matrix}a^{i}b^{i}c^{i}d^{i}e^{i}f^{i} \\ 6 5 4 3 2 1 \end{matrix} ), respectively, where a^{i} ≤ b^{i} ≤

c^{i} < d^{i} ≤ e^{i} ≤ f^{i}. Let \overline{Σ} be the biword obtained by sorting the biletters of \overline{Π}^{+} by weakly increasing rearrangement with respect to the anti-lexicographic order with priority in the first row. The second row of \overline{Σ}, denoted ρ(w), is a shuffle of columns

\overline{v}_{j}, j = 6, 4, 3, 2, 1. Under this injection the lattice path (\begin{matrix}a^{i}b^{i}c^{i}d^{i}e^{i}f^{i} \\ 4 3 1 4 2 1 \end{matrix}), which has

some negative slope steps, is stretched northeastward to ( \begin{matrix}a^{i}b^{i}c^{i}d^{i}e^{i}f^{i} \\ 6 5 4 3 2 1 \end{matrix} ), where now

every step has nonnegative slope.

Example 6.2. Let σ = 4123 and consider the biword Π̂^{+} = ( \begin{matrix}114566 & 2233 & 3 \\ 431421 & 4321 & 4 \end{matrix} )

in Example 6.1. We have \overline{σ} = 612534. Applying the map ρ, we obtain the biword

\overline{Π̂}^{+} = ( \begin{matrix}114566 & 2233 & 3 \\ 654321 & 6521 & 6 \end{matrix} ), whose lattice path representation is given below

(6.5)  .

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

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

Proposition 6.3. Let \overline{Π}^{+} be the biword defined above, and let ( \begin{matrix}abcdef \\ 654321 \end{matrix} ) be one

of its lattice paths. Then (a) \overline{Π}^{+} has no critical vertices.

(b) There are no vertices in row c to the left of (c, 4), nor are there in row d to the right of (d, 3), nor in row e to the right of (e, 2).

Proof. This is a consequence of the definition of \overline{Π}^{+} and Lemma 6.1. □

We are now in position to prove the following result.

Theorem 6.4. Let T be a Young tableau over a four-letter alphabet with rectification P, and let K be the key with the same weight as T. Then, (T, K) is a matrix tableaupair if and only if P = K.

Proof. The “only if” part was proved in [6]. Conversely, assume K = K(σα(m)), for some σ ∈ {1423, 1432, 4123, 4132} and ℓ_{4}, ℓ_{2} > 0. Recall that in any other case the plactic class of K(σα(m)) is the set of all shuffles of its columns and, thus, by Theorem 4.4, (T, K(σα(m))) is a matrix-tableau pair.

Without loss of generality let w be the word of T in the set ⊔⊔(v̂_{5}^{n_{5}}, v_{4}^{n_{4}}, …, v^{n_{1}}), for some 0 < n_{5} ≤ min{ℓ_{2}, ℓ_{4}}, where n_{i} = ℓ_{i}, i = 1, 3, and n_{i} = ℓ_{i} − n_{5}, i = 2, 4. Notice that either m_{1} = 2n_{5} + n_{4} + n_{3} + n_{2} + n_{1} and m_{4} = 2n_{5} + n_{4} + n_{3} + n_{2}, if σ ∈ {1423, 1432}, or m_{4} = 2n_{5} + n_{4} + n_{3} + n_{2} + n_{1} and m_{1} = 2n_{5} + n_{4} + n_{3} + n_{2} otherwise. Let Π^{+} be the biword (6.1) of T satisfying Lemma 6.1. Consider the injection ρ and the corresponding biword \overline{Π}^{+} as in (6.4), whose bottom word is the key K(\overline{σ}, (n_{5}, 0, n_{4}, n_{3}, n_{2}, n_{1}). Let \overline{T} be the Young tableau with the same skew-

shape as T and biword \overline{Π}^{+}. For each i = 1, …, n_{5}, let ( \begin{matrix}a^{i}b^{i}c^{i}d^{i}e^{i}f^{i} \\ 6 5 4 3 2 1 \end{matrix} ) be a lattice

path of \overline{Π}^{+}. Then, if J_{4}, J_{3}, J_{2}, J_{1} are the indexing sets of T, and if \overline{J}_{6}, ⋯, \overline{J}_{1} are the indexing sets of \overline{T}, we have \overline{J}_{1} = J_{1} \ \{c^{i} : i ∈ [n_{5}]\}, \overline{J}_{2} = J_{2}, \overline{J}_{5} = J_{3}, \overline{J_{3}} = \{d^{i} : i ∈ [n_{5}]\}, \overline{J}_{4} = \{c^{i} : i ∈ [n_{5}]\}, and \overline{J}_{6} = J_{4} \ \{d^{i} : i ∈ [n_{5}]\}. Note also that, by Proposition 6.3, there are no vertices in row c^{i} to the left of (c^{i}, 4), nor are there in row d^{i}, to the right of (d^{i}, 3). Then, we may apply the Main Algorithm to \overline{Π}^{+}, choosing a permutation σ_{1} ∈ 𝔖_{n} satisfying the conditions of Step 1, and satisfying in addition that σ_{1}(n_{1} + ⋯ + n_{5} + i) = c^{i}, for i = 1, …, n_{5}. Denote by A_{0}, B_{1}, …, B_{6} the sequence of matrices obtained by this procedure. Then A_{0} = diag_{p}(a′), B_{1} = P_{σ_{1}}D_{[m_{1}−n_{5}]}, B_{2} = S_{2}D_{[m_{2}]}, B_{k} = S_{k}D_{[n_{5}]}, for k = 3, 4, B_{5} = S_{5}D_{[m_{3}]}, and B_{6} = S_{6}D_{[m_{4}−n_{5}]}. By Theorem 4.4, this sequence is a matrix realization for the pair (\overline{T} , K(\overline{σ}, (n_{5}, 0, n_{4}, n_{3}, n_{2}, n_{1})). In particular, this means that

σ_{1}([m_{1} − n_{5}]) = J_{1} \ {c^{i} : i ∈ [n_{5}]}, σ_{2}([m_{2}]) = J_{2}, (6.6) σ_{3}([n_{5}]) = {d^{i} : i ∈ [n_{5}]}, σ_{4}([n_{5}]) = {c^{i} : i ∈ [n_{5}]}, (6.7) σ_{5}([m_{3}]) = J_{3}, and σ_{6}([m_{4} − n_{5}]) = J_{4} \ {d^{i} : i ∈ [n_{5}]}. (6.8)

Consider the sequence of matrices A′_{0}, B′_{1}, B′_{2}, B′_{3}, B′_{4}, defined by A′_{0} = diag_{p}(a′), B′_{1} := P_{σ_{1}}D_{Γ_{1}}, B′_{2} := B_{2}, B′_{3} := S_{3}S_{4}S_{5}D_{[m_{3}]}, and B′_{4} := S_{6}D_{Γ_{4}}, where Γ_{1} = [m_{1}], Γ_{4} = [m_{4} − n_{5}] ∪ {m_{4} + n_{1} + 1, …, m_{4} + n_{1} + n_{5}} if σ ∈ {1423, 1432}, and Γ_{1} = [m_{1} − n_{5}] ∪ {m_{1} + n_{1} + 1, …, m_{1} + n_{1} + n_{5}}, Γ_{4} = [m_{4}] otherwise.

By (6.6) and the definition of σ_{1}, it is clear that

A′_{0}B′_{1} = diag_{p}(a′)P_{σ_{1}}D_{Γ_{1}} = diag_{p}(a′ + χ^{J_{1}})P_{σ_{1}},

and

A′_{0}B′_{1}B′_{2} ∼_{L} diag_{p}(a′ + χ^{J_{1}})P_{σ_{2}}D_{[m_{2}]} = diag_{p}(a′ + χ^{J_{1}} + χ^{J_{2}})P_{σ_{2}}.

Next, by (6.7) and (6.8), we find that

A′_{0}B′_{1}B′_{2}B′_{3} ∼_{L} diag_{p}(a + χ^{J_{1}} + χ^{J_{2}})P_{σ_{5}}D_{[m_{3}]} = diag_{p}(a′ + χ^{J_{1}} + χ^{J_{2}} + χ^{J_{3}})P_{σ_{5}}.

Finally, consider the product

A′_{0}B′_{1}B′_{2}B′_{3}B′_{4} ∼ diag_{p}(a′ + χ^{J_{1}} + χ^{J_{2}} + χ^{J_{3}})P_{σ_{6}}D_{Γ_{4}},

and notice that, for each i = 1, …, n_{5}, we may write σ_{6} = α_{2}^{i}(c^{i}d^{i})α_{1}^{i}, with (c^{i}d^{i}) the transposition of c^{i} with d^{i}, for some α_{2}^{i}, α_{1}^{i} ∈ 𝔖_{n} satisfying α_{1}^{i}(c^{i}) = c^{i} and α_{2}^{i}(d^{i}) = d^{i}, since by Lemma 6.3 there are no vertices of \overline{Π}^{+} nor are there in row c^{i} to the left of (c^{i}, 4), nor in row d^{i} to the right of (d^{i}, 3). Therefore,

σ_{6}({m_{4} + n_{1} + 1, …, m_{4} + n_{1} + n_{5}}) = {d^{i} : i ∈ [n_{5}]},

and, by (6.8), we must have

A′_{0}B′_{1}B′_{2}B′_{3}B′_{4} ∼_{L} diag_{p}(a′ + χ^{J_{1}} + χ^{J_{2}} + χ^{J_{3}} + χ^{J_{4}}).

Thus, A′_{0}, B′_{1}, B′_{2}, B′_{3}, B′_{4} satisfy conditions I and II of Definition 4.1. It remains to show that B′_{1} ⋯ B′_{4} is equivalent to the diagonal matrix D_{[m_{1}]} ⋯ D_{[m_{4}]}. We start by using Lemma 4.1 to write, for k = 2, 3, 4,

B′_{k} = ∏_{l=1}^{q_{k−1}} T_{i_{l}j_{l}}(1)C_{k}D_{k} ∏_{l=1}^{q_{k−1}} T_{j_{l}i_{l}}(−1)D_{Γ_{k}},

where Γ_{l} = [m_{l}] for l = 2, 3, C_{k}D_{k} is the identity matrix for k = 2, 4, and C_{3} [respectively D_{3}] is a product of upper [respectively lower] elementary matrices T_{jj′}(τ), for some integers j, j′ ∈ [m_{2}], and τ = ±1. Next, use again Lemma 4.1 to write B′_{1} ⋯ B′_{4} as

(6.9) ∏_{l=1}^{q_{1}} T_{i_{l}j_{l}}(p^{ν_{l}})D_{[Γ_{1}]} ∏_{l=1}^{q_{1}} T_{j_{l}i_{l}}(−1) ∏_{l=1}^{q_{2}} T_{i_{l}j_{l}}(p)D_{[m_{2}]}C_{3}D_{3} ∏_{l=1}^{q_{2}} T_{j_{l}i_{l}}(−1)

· ∏_{l=1}^{q_{3}} T_{i_{l}j_{l}}(p)D_{[m_{3}]} ∏_{l=1}^{q_{3}} T_{j_{l}i_{l}}(−1)D_{[Γ_{4}]},

for some ν_{l} ≥ 0. Notice that we may eliminate any upper triangular matrix T_{ij}(p^{ν}), ν > 0, by left equivalence, using Lemma 4.1. This operation may create new elementary matrices T_{uv}(p^{ν′}), but, as we have mentioned, using Lemma 4.1, we may assume without loss of generality that this is not the case. Thus, we may write

(6.10) (6.9) ∼_{L} D_{[Γ_{1}]} ∏_{l=1}^{q_{1}} T_{j_{l}i_{l}}(−1)D_{[m_{2}]}C_{3}D_{3} ∏_{l=1}^{q_{2}} T_{j_{l}i_{l}}(−1)D_{[m_{3}]} ∏_{l=1}^{q_{3}} T_{j_{l}i_{l}}(−1)D_{[Γ_{4}]}.

Use again Lemma 4.1 to eliminate all upper triangular matrices in C_{3} by left equivalence. New elementary matrices may be created. Among these, eliminate all those by left equivalence which are upper triangular. Finally, starting from right and moving to the left, eliminate all lower triangular matrices left in the product by right equivalence. It is now clear that B_{1} ⋯ B_{4} is equivalent to the diagonal matrix D_{[Γ_{1}]}D_{[m_{2}]}D_{[m_{3}]}D_{[Γ_{4}]}. Since m_{k} ≤ n_{5} +n_{4} +n_{3} +n_{2}, k = 2, 3, and Γ_{1} ⊆ Γ_{4} or Γ_{4} ⊆ Γ_{1}, we find that this last diagonal matrix is equivalent to D_{[m_{1}]} ⋯ D_{[m_{4}]}. □

7. Concluding remarks and open questions

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

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

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

References

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

[2] G. Appleby and T. Whitehead, Matrix pairs over discrete valuation rings determine Littlewood– Richardson fillings, Linear Algebra and Its Applications 432 (2010), 1277–1298.

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

[4] O. Azenhas, Opposite Littlewood–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, Matrix realizations of pairs of Young tableaux, keys and shuffles, Séminaire Lotharingien de Combinatoire 53 (2006), Article B53h, 22 pp. (electronic).

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

[8] C. S. Barnes, Enumeration of the distinct shuffles of permutations, Discrete Mathematics and Theoretical Computer Science Proc. AK (2009), 155–166.

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

[10] W. Fulton, Young Tableaux, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, Cambridge, 1997.

[11] W. Fulton, Eigenvalues of sums of Hermitian matrices (after Klyachko), Séminaire Bourbaki vol. 1997/98, Astérisque 252 (1998), pp. 255–269.

[12] W. Fulton, Eigenvalues, invariant factors, highest weights, and Schubert calculus, Bulletin of the American Mathematical Society 7 (2000), 209–249.

[13] W. Fulton, Eigenvalues of majorized Hermitian matrices and Littlewood–Richardson coefficients, Linear Algebra and Its Applications 319 (2000), 23–36.

[14] J. A. Green, Symmetric Functions and p-Modules, Lecture notes, University of Manchester, Manchester, 1961.

[15] J. A. Green, 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.

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

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

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

[19] 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, Cambridge University Press, Cambridge, 2002, pp. 164–196.

[20] 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), 129–156.

[21] A. Lascoux and M. -P. Schützenberger, Keys and standard bases, Invariant theory and tableaux (Minneapolis, MN, 1988) IMA, Math. Appl., vol. 19, Springer, New York–Berlin, 1990, pp. 125– 144.

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

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

[24] V. Reiner and M. Shimozono Key polynomials and a flagged Littlewood–Richardson rule, Journal of Combinatorial Theory Series A 70 (1995), 107–143.

[25] C. Reutenauer, Free Lie Algebras, Oxford University Press, Oxford, 1993.

[26] B. E. Sagan, The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Functions, Springer Verlag, New York, 2001.

[27] R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, United Kingdom, 2001.

[28] R. C. Thompson, Smith invariants of a product of integral matrices, Linear algebra and its role in systems theory (Brunswick, Maine, 1984), Contemp. Math., 47, Amer. Math. Soc., Providence, RI, 1985, pp. 401–435.

CMUC, Department of Mathematics, University of Coimbra, 3001-454 Coimbra, Portugal