Factorizations in Schubert cells

Christian Kassel^{1}, Alain Lascoux^{2} and Christophe Reutenauer^{3}

1 Institut de Recherche Mathématique Avancée, C.N.R.S. - Université Louis Pasteur, 7 rue René Descartes, 67084 Strasbourg Cedex, France 2 Institut Gaspard Monge, C.N.R.S., Université de Marne la Vallée, 5 Bd Descartes, Champs sur Marne, 77454 Marne La Vallée Cedex 2, France 3 Mathématiques, Université du Québec à Montréal, Montréal, CP 8888, succ. Centre Ville, Canada H3C 3P8

Abstract. For any reduced decomposition i = (i_{1}, i_{2}, …, i_{N}) of a permutation w and any ring R we construct a bijection

P_{i} : (x_{1}, x_{2}, …, x_{N}) ↦ P_{i_{1}}(x_{1}) P_{i_{2}}(x_{2}) ⋯ P_{i_{N}} (x_{N})

from R^{N} to the Schubert cell of w, where P_{i_{1}}(x_{1}), P_{i_{2}}(x_{2}), …, P_{i_{N}} (x_{N}) stand for certain elementary matrices satisfying Coxeter-type relations. We show how to factor explicitly any element of a Schubert cell into a product of such matrices. We apply this to give a one-to-one correspondence between the reduced decompositions of w and the injective balanced labellings of the diagram of w, and to characterize commutation classes of reduced decompositions.

Mathematics Subject Classification (1991): 20B30, 20G15, 05E15, 14M15, 15A23

Key Words: symmetric group, reduced decomposition, flag variety, Schubert cell, factorization of matrices, commutation class

Résumé. Etant donné un anneau R et une décomposition réduite i = (i_{1}, i_{2}, …, i_{N}) d’une permutation w, nous construisons une bijection

P_{i} : (x_{1}, x_{2}, …, x_{N}) ↦ P_{i_{1}}(x_{1}) P_{i_{2}}(x_{2}) ⋯ P_{i_{N}} (x_{N})

de R^{N} vers la cellule de Schubert de w, où P_{i_{1}}(x_{1}), P_{i_{2}}(x_{2}), …, P_{i_{N}} (x_{N}) sont des matrices élémentaires vérifiant des relations de type Coxeter. Nous montrons comment factoriser explicitement tout élément d’une cellule de Schubert comme un produit de matrices P_{i}(x). Nous utilisons ces factorisations pour établir une bijection entre les décompositions réduites de w et les remplissages injectifs équilibrés du diagramme de w et pour caractériser les classes de commutation de décompositions réduites.

Mots-Clés : groupe symétrique, décomposition réduite, variété de drapeaux, cellule de Schubert, factorisation de matrices, classe de commutation

1. Introduction and statement of main results

In this article we study matrix products obtained by multiplying certain elementary matrices, investigated in [KR], in the order given by a reduced decomposition of a permutation w. It turns out that such a matrix product differs from the matrix of the permutation w only by the entries lying in the diagram of w. In this way, we get a parametrization of the Schubert cell of w. Such parametrizations were previously known over the complex numbers. Here we extend them to any noncommutative ring together with precise formulas for the entries of the matrix products and determinantal formulas for the inverse mappings. These formulas use planar configurations naturally associated to reduced decompositions. We also show that the linear parts of these parametrizations give exactly all injective balanced labellings of the diagram of w, as defined in [FGRS], and that the quadratic parts characterize the commutation classes of reduced decompositions. Thus, these parametrizations provide a powerful algebraic representation of the diagram of a permutation, an object which comes up in many constructions related to permutations and Schubert varieties. One of the most interesting features of the objects we consider is their triple nature: algebraic, combinatorial, topological. In our proofs we rely in turn on each of these aspects.

Let us state our main results. Given a permutation w of the set {1, 2, …, n}, recall from [Mcd], Chapter I that the diagram D_{w}, first introduced by Rothe in 1800 (cf. [Mu], pp. 59–60), is the subset of {1, …, n} × {1, …, n} consisting of all couples (w(k), j) such that j < k and w(j) > w(k), or, equivalently, of all couples (i, j) such that

i < w(j) and j < w^{−1}(i).  (1.1)

It is clear that the cardinality of D_{w} is equal to the number of inversions of w or, equivalently, to the length ℓ(w) of w with respect to the standard generating set s_{1}, …, s_{n−1} of the symmetric group S_{n}, where s_{i} is the simple transposition (i, i + 1).

Let M_{w} be the matrix of the permutation w: this is the n × n-matrix defined by

(M_{w})_{ij} = δ_{i,w(j)}  (1.2)

for all 1 ≤ i, j ≤ n. Given a ring R and a permutation w ∈ S_{n}, we define the subset C_{w} of the group GL_{n}(R) of invertible n × n-matrices with entries in R as follows: a matrix is in C_{w} if it is of the form M_{w} + Q, where Q is any matrix with entries Q_{ij} in R such that Q_{ij} = 0 whenever (i, j) ∉ D_{w}. It is well-known that, when R is a field, the set C_{w} is in bijection with the Schubert cell BwB/B in the flag variety G/B, where G = GL_{n}(R) and B is the subgroup of upper triangular matrices (see [Mcd], Appendix, (A.4)). By extension, we call C_{w} the Schubert cell associated to w.

In [KR] the following invertible n × n-matrices P_{1}(x), P_{2}(x), …, P_{n−1}(x) depending on a variable x were defined: for 1 ≤ i ≤ n − 1 the matrix P_{i}(x) is obtained from the identity matrix by inserting the block

( \begin{matrix}x & 1 \\ 1 & 0 \end{matrix} )

on the diagonal such that x is the (i, i)-entry of P_{i}(x). In other words, P_{i}(x) is of the form

( \begin{matrix}1 & 0 & ⋯ & 0 & 0 & 0 & 0 & ⋯ & 0 \\ 0 & 1 & ⋯ & 0 & 0 & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ... & & & & & & ⋮ \\ 0 & 0 & ⋯ & 1 & 0 & 0 & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & 0 & x & 1 & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & 0 & 1 & 0 & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & 0 & 0 & 0 & 1 & ⋯ & 0 \\ ⋮ & ⋮ & & & & & & ... & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 & 0 & 0 & ⋯ & 1 \end{matrix} )  (1.3)

As observed in [KR], Lemma 1, the matrices P_{i}(x) (1 ≤ i ≤ n−1) satisfy the following Coxeter-type relations, where x, y, z are elements in a ring R:

P_{i}(x) P_{j}(y) = P_{j}(y) P_{i}(x)  (1.4a)

if |i − j| ≥ 2, and

P_{i}(x) P_{i+1}(y) P_{i}(z) = P_{i+1}(z) P_{i}(y + xz) P_{i+1}(x).  (1.4b)

Relation (1.4b) is similar to, but different from the famous Yang-Baxter equation with spectral parameters

P_{i}(x) P_{i+1}(x + z) P_{i}(z) = P_{i+1}(z) P_{i}(x + z) P_{i+1}(x),

which is another deformation of the usual Coxeter relation. It is interesting to note that the Yang-Baxter equation also leads to properties of Schubert varieties (see, e.g., [LLT]).

Before we state the first result of the paper, let us recall that a sequence (i_{1}, i_{2}, …, i_{N}) of indices belonging to {1, …, n − 1} is a reduced decomposition of w ∈ S_{n} if w = s_{i_{1}}s_{i_{2}} … s_{i_{N}} and if its length N is equal to the number of inversions of w.

1.1. Theorem.— For any ring R and any reduced decomposition i = (i_{1}, i_{2}, …, i_{N}) of the permutation w ∈ S_{n}, the map

P_{i} : (x_{1}, x_{2}, …, x_{N}) ↦ P_{i_{1}}(x_{1}) P_{i_{2}}(x_{2}) ⋯ P_{i_{N}} (x_{N})

is a bijection from R^{N} to the Schubert cell C_{w} ⊂ GL_{n}(R).

Theorem 1.1 is known when R is a field (cf. [Sp], Lemma 10.2.6; see also [FZ], Proposition 2.11). The proof we give for an arbitrary ring in Section 2.5 is based on Relations (1.4a–b) and on a matrix identity (given in Proposition 2.1), which is of independent interest.

Let us illustrate this theorem with the permutation

w = ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 3 & 2 & 1 \end{matrix} ) ∈ S_{5}.  (1.5)

It is of length 9 and the Schubert cell C_{w} consists of all 5 × 5-matrices of the form

( \begin{matrix}a_{11} & a_{12} & a_{13} & a_{14} & 1 \\ a_{21} & a_{22} & a_{23} & 1 & 0 \\ a_{31} & a_{32} & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{matrix} ) .  (1.6)

The sequence i = (1, 2, 3, 4, 1, 2, 3, 1, 2) is a reduced decomposition of w. The matrix P_{i}(x_{1}, x_{2}, …, x_{9}) is of the form (1.6). Computing its entries a_{ij} in terms of the variables x_{1}, x_{2}, …, x_{9}, we get

\begin{matrix}a_{11} = x_{3} + x_{2}x_{8} + x_{1}x_{6} + x_{1}x_{5}x_{8}, & & a_{12} = x_{4} + x_{2}x_{9} + x_{1}x_{7} + x_{1}x_{5}x_{9}, \\ a_{13} = x_{2} + x_{1}x_{5}, & & a_{14} = x_{1}, \\ a_{21} = x_{6} + x_{5}x_{8}, & & a_{22} = x_{7} + x_{5}x_{9}, \\ a_{23} = x_{5}, & a_{31} = x_{8}, & a_{32} = x_{9}. \end{matrix} (1.7)

We see that each entry of P_{i}(x_{1}, x_{2}, …, x_{9}) lying in the diagram of w is the sum of some variable x_{i} and possibly of distinct monomials in the remaining variables (thus, it is a substraction-free polynomial). Moreover, any monomial in the variables x_{i} appears at most once in the matrix.

These two features hold for P_{i}(x_{1}, x_{2}, …, x_{N}), where i is any reduced decomposition. They follow from Proposition 3.2, which exhibits a general formula for the entries of the matrix P_{i}(x_{1}, …, x_{N}) in terms of the variables x_{1}, …, x_{N}.

In Theorem 3.3 we shall give a formula for the inverse map P_{i}^{−1} : C_{w} → R^{N}. This formula yields a factorization of any element of the Schubert cell C_{w} as a product of matrices P_{i}(x). There is such a factorization for any reduced decomposition of w. As an application of Theorem 3.3, the matrix (1.6) is the product of the nine factors

P_{1}(a_{14}) P_{2}(| \begin{matrix}a_{13} & a_{14} \\ a_{23} & 1 \end{matrix} |) P_{3}(− | \begin{matrix}a_{11} & a_{13} & a_{14} \\ a_{21} & a_{23} & 1 \\ a_{31} & 1 & 0 \end{matrix} |) P_{4}(− | \begin{matrix}a_{12} & a_{13} & a_{14} \\ a_{22} & a_{23} & 1 \\ a_{32} & 1 & 0 \end{matrix} |) ×

× P_{1}(a_{23}) P_{2}(| \begin{matrix}a_{21} & a_{23} \\ a_{31} & 1 \end{matrix} |) P_{3}(| \begin{matrix}a_{22} & a_{23} \\ a_{32} & 1 \end{matrix} |) P_{1}(a_{31}) P_{2}(a_{32}).  (1.8)

The expressions appearing in the factorization (1.8) are, up to sign, minors of the matrix (1.6). We shall give a sense to these minors over noncommutative rings as well.

The explicit formulas for the maps P_{i} and P_{i}^{−1} will be expressed with the help of the so-called pseudo-line arrangement of the reduced decomposition i. This is a configuration of lines in a horizontal strip of the plane whose precise definition is recalled in Section 3.1.

Out of the formulas for P_{i} and P_{i}^{−1} it is possible to relate the parametrizations corresponding to two different reduced decompositions (see also Remark 6.2).

Fomin, Greene, Reiner, and Shimozono [FGRS] constructed a one-to-one correspondence between the reduced decompositions of a permutation w and what they call “injective balanced labellings” of the diagram of w. Theorem 1.2 below states that such a bijection can be recovered from the linear part of our parametrization.

Let Q_{i}(x_{1}, …, x_{N}) be the linear part of the matrix P_{i}(x_{1}, …, x_{N}), i. e., the matrix obtained from P_{i}(x_{1}, …, x_{N}) by removing all monomials in x_{1}, …, x_{N} of degree ≠ 1. As P_{i}(x_{1}, …, x_{N}) − M_{w} is entirely supported by the diagram D_{w}, so is Q_{i}(x_{1}, …, x_{N}). The matrix Q_{i}(x_{1}, …, x_{N}) provides each element of the diagram (which we view as a matrix) with a label x_{i}. Let us denote this labelling by L_{i}. For simplicity, we replace each variable x_{i} in L_{i} by its index i. Such a labelling is injective in the terminology of [FGRS], i.e., each integer 1, …, N appears exactly once as a label in L_{i}.

For the reduced decomposition i = (1, 2, 3, 4, 1, 2, 3, 1, 2) considered above, (1.7) implies that

Q_{i}(x_{1}, …, x_{9}) = ( \begin{matrix}x_{3} & x_{4} & x_{2} & x_{1} & 0 \\ x_{6} & x_{7} & x_{5} & 0 & 0 \\ x_{8} & x_{9} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} ) ,  (1.9)

which leads to the injective labelling (we indicate the nonzero entries of M_{w} with crosses)

L_{i} = ( \begin{matrix}3 & 4 & 2 & 1 & × \\ 6 & 7 & 5 & × & . \\ 8 & 9 & × & . & . \\ × & . & . & . & . \\ . & × & . & . & . \end{matrix} ) .  (1.10)

The concept of balanced labelling of the diagram of a permutation we use (see Section 4 for the definition) is different from, but equivalent, up to transposition, to the one in [FGRS]. Under this equivalence, the bijection stated in the following theorem is the same as the bijection in [FGRS].

1.2. Theorem.— For any permutation w ∈ S_{n}, the map i ↦ L_{i} is a bijection between the set of reduced decompositions of w and the set of injective balanced labellings of the diagram of w.

Note that this implies that the matrix P_{i}(x_{1}, … x_{N}) is completely determined by its linear part (see (4.2) for an explicit formula).

We now use the quadratic part of P_{i}(x_{1}, … x_{N}) to get additional information on the set R(w) of reduced decompositions of w. More precisely, let R_{i} be the matrix (whose entries are nonnegative integers) which is the coefficient of X^{2} in the expansion of P_{i}(X, X, … X) as a polynomial in X. We have

P_{i}(X, X, … X) ≡ M_{w} + Q_{i}(1, 1, …, 1) X + R_{i} X^{2} modulo X^{3}.  (1.11)

An equivalent definition will be given in Lemma 4.9. The matrix R_{i} is a (noninjective) labelling of D_{w}. We use this matrix to characterize the commutation classes in R(w). Let us recall what these are.

By a well-known theorem of Iwahori-Tits (see [Bo]), any two reduced decompositions of w can be obtained from each other via a finite sequence of 2-moves and 3-moves. A 2-move on a reduced decomposition i consists in replacing two adjacent indices i, j in i by j, i under the condition |i − j| > 1. A 3-move on i consists in replacing three adjacent indices i, j, i in i by j, i, j under the condition |i − j| = 1. Two reduced decompositions i and j are said to belong to the same commutation class if they can be obtained from each other via a sequence of 2-moves. Commutation classes have recently come up in relation with dual canonical bases for quantum groups (see [BZ], [LZ]).

1.3. Theorem.— Two reduced decompositions i and j of a permutation w belong to the same commutation class if and only if R_{i} = R_{j}.

The paper is organized as follows. In Section 2 we establish a matrix identity from which we derive Theorem 1.1. In Section 3 we produce explicit formulas for the parametrization P_{i} (Proposition 3.2) and for the inverse map P_{i}^{−1} (Theorem 3.3). We deal with balanced labellings and prove Theorem 1.2 in Section 4. Section 5 is devoted to the proof of Theorem 1.3; we also give a characterization of the labellings R_{i}. In Section 6 we consider a partial order on the set C(w) of commutation classes of reduced decompositions of w, due to Manin and Schechtman; the poset C(w) has a unique minimal element and a unique maximal element, which we describe explicitly.

The paper [BFZ] by Berenstein, Fomin, and Zelevinsky was a source of inspiration to us, despite the fact that we deal with different questions and different parametrizations. We thank Robert Bédard for pointing out Lemma 10.2.6 of [Sp] and for showing us the experimental data he collected on the posets C(w_{0}) of Section 6.

2. A Matrix Identity

Let w be a permutation of the set {1, …, n} and M_{w} be its permutation matrix. We complete M_{w} with stars at all places (w(k), j) such that j < k and w(j) > w(k). As we saw in the introduction, the pattern formed by these stars is the diagram D_{w}.

Replace the stars by elements a_{1}, …, a_{N} of a ring R in the following order: start with the first column from bottom to top, then the second one again from bottom to top, and so on. We get a matrix M_{w}(a_{1}, …, a_{N}) whose entries are either 1, 0, or a_{1}, …, a_{N}. By definition, the Schubert cell C_{w} is the set of all matrices M_{w}(a_{1}, …, a_{N}) when a_{1}, …, a_{N} run over R. Observe that M_{w}(0, …, 0) = M_{w}.

We now create a sequence (j_{1}, …, j_{N}) of integers by labelling the entries in the diagram of w (considered as an n×n-matrix) in the following way: the upper entry of the j-th column gets the label j; the entry immediately below gets the label j + 1, and so on. Then (j_{1}, …, j_{N}) is the sequence obtained by reading the labels from bottom to top in each column, one column after the other, starting with the first column. We call (j_{1}, …, j_{N}) the canonical sequence of w.

We now express the matrix M_{w}(a_{1}, …, a_{N}) as a product of N matrices of type P_{i}(x), as defined in the Introduction.

2.1. Proposition.— Let w be a permutation and (j_{1}, …, j_{N}) be its canonical sequence. Then

M_{w}(a_{1}, …, a_{N}) = P_{j_{1}}(a_{1}) P_{j_{2}}(a_{2}) ⋯ P_{j_{N}} (a_{N}).

The proof is postponed to Section 2.6.

2.2. Example.— In order to get the canonical sequence for the permutation (1.5), we label its diagram as explained above. We get the labelling

( \begin{matrix}1 & 2 & 3 & 4 & . \\ 2 & 3 & 4 & . & . \\ 3 & 4 & . & . & . \\ . & . & . & . & . \\ . & . & . & . & . \end{matrix} ) ,

from which we see that the canonical sequence is (3, 2, 1, 4, 3, 2, 4, 3, 4). Applying Proposition 2.1, we have

( \begin{matrix}a_{3} & a_{6} & a_{8} & a_{9} & 1 \\ a_{2} & a_{5} & a_{7} & 1 & 0 \\ a_{1} & a_{4} & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{matrix} ) = P_{3}(a_{1}) P_{2}(a_{2}) P_{1}(a_{3}) P_{4}(a_{4}) P_{3}(a_{5}) P_{2}(a_{6}) P_{4}(a_{7}) P_{3}(a_{8}) P_{4}(a_{9}).

Let us derive a few consequences from Proposition 2.1. The following corollary has been observed in [La], p. 305 (see also [Pa]).

2.3. Corollary.— The canonical sequence (j_{1}, j_{2}, …, j_{N}) of the permutation w is a reduced decomposition of w.

Proof.— Set a_{1} = ⋯ = a_{N} = 0 in the matrix identity of Proposition 2.1. On the left-hand side, we get the permutation matrix M_{w}. As for the right-hand side, observe that P_{i}(0) is the matrix of the transposition s_{i}. The matrix identity thus implies that w = s_{i_{1}}s_{i_{2}} … s_{i_{N}}. The decomposition of w we get in this way is reduced because its length is equal to the number of inversions of w. □

2.4. Corollary.— Let K be a field and let a_{1}, …, a_{N} be variables. If M_{w}(a_{1}, …, a_{N}) = P_{i_{1}}(f_{1}) … P_{i_{k}}(f_{k}) where f_{1}, …, f_{k} belong to an extension of the field K(a_{1}, …, a_{N}), then k ≥ N. If, in addition, k = N, then (i_{1}, …, i_{N}) is a reduced decomposition of w.

Proof.— If k < N, then the degree of transcendence of a_{1}, …, a_{N} would be < N, which is not possible. Assume now that k = N. Then f_{1}, …, f_{k} are algebraically independent and a_{1}, …, a_{N} belong to the ring generated by f_{1}, …, f_{k}. Thus we may set f_{i} = 0 for all i = 1, …, N and we get M_{w}(ā_{1}, …, ā_{N}) = P_{i_{1}}(0) … P_{i_{k}}(0), where ā_{1}, … ā_{N} belong to the ground field K. The right-hand side of the previous identity is a permutation matrix M_{w′} with n nonzero entries, whereas the left-hand side is a matrix of the form M_{w} + Q, where all entries of Q not in the diagram of w vanish. In particular, M_{w} and Q have disjoint supports. Counting the number of nonzero entries in M_{w} + Q, we see that necessarily Q = 0 and M_{w} = M_{w′}. It follows that (i_{1}, …, i_{N}) is a reduced decomposition of w. □

2.5. Proof of Theorem 1.1.— By Proposition 2.1, the theorem holds for the canonical reduced decomposition (j_{1}, …, j_{N}). Now one passes from (j_{1}, …, j_{N}) to (i_{1}, …, i_{N}) by a sequence of 2-moves and 3-moves. Relations (1.4a–b) show how the matrices P_{i}(x) are affected under such moves. We conclude immediately that

M_{w}(a_{1}, …, a_{N}) = P_{j_{1}}(a_{1}) P_{j_{2}}(a_{2}) ⋯ P_{j_{N}} (a_{N}) = P_{i_{1}}(a′_{1}) P_{i_{2}}(a′_{2}) ⋯ P_{i_{N}} (a′_{N}),

where a_{k} ↦ a′_{k} is an endomorphism of the free ring generated by a_{1}, …, a_{N}. This endomorphism is a product of Jonquières automorphisms, hence it is an automorphism. Recall that a Jonquières automorphism is an automorphism that sends some variable to the sum of itself and of a polynomial in the other variables, and fixes the remaining variables (see [Co], p. 342). We may then conclude that the matrices P_{i_{1}}(a_{1}) P_{i_{2}}(a_{2}) ⋯ P_{i_{N}} (a_{N}) parametrize the Schubert cell C_{w} as well. □

2.6. Proof of Proposition 2.1.— We proceed by induction on the length N of w. Suppose that N = 1. Then w is a transposition s_{j}. The only element of D_{s_{j}} being (j, j), the canonical sequence of w is (j) and the identity M_{w}(a_{1}) = P_{j}(a_{1}) holds trivially.

Suppose now that N > 1 and that we have proved the proposition for all permutations w′ ∈ S_{n} of length < N. Let (i, j) be the position of the entry a_{N} in the matrix M_{w}(a_{1}, …, a_{N}).

Claim 1: j < n and w(j + 1) = i. This follows from the definitions of D_{w} and of the canonical sequence. See Figure 2.1.a.

Claim 2: If w′ = ws_{j}, then D_{w′} is obtained from D_{w} as follows: first remove the element (i, j) ∈ D_{w}, then exchange the jth and the j + 1st columns. This claim is easy to prove (see Figures 2.1.a–c). As a consequence, D_{w′} has one element less than D_{w}, and the length of w′ is N − 1.

Claim 3: By definition of the canonical sequence (j_{1}, …, j_{N}) of w, we have j_{N} = j, j_{N−1} = j + 1, j_{N−2} = j + 2, and so forth, as long as we are in the jth column of D_{w}. Let w′ = ws_{j} as in Claim 2 and let (j′_{1}, …, j′_{N−1}) be its canonical sequence. Then j′_{r} = j_{r} for all r = 1, …, N − 1. The proof of this claim uses Claim 2 and the fact that the columns lying left to the jth column are the same in D_{w} and in D_{w′} (see Figures 2.1.b and 2.1.c).

Claim 4: Let w′ = ws_{j} be as in Claim 2. The matrix M_{w′}(a_{1}, …, a_{N−1}) is obtained from M_{w}(a_{1}, …, a_{N}) by first replacing a_{N} by 0, then by exchanging the jth and the j +1st columns. This follows from Claim 2.

Claim 5: Given any matrix M, the j + 1st column of the matrix product MP_{j}(a_{N}) is equal to the jth column of M, and the jth column of MP_{j}(a_{N}) is the sum of the j + 1st column of M and of the jth column of M multiplied by a_{N}; all other columns of MP_{j}(a_{N}) and M are the same.

Claims 3–5 and the induction hypothesis imply that

\begin{aligned}M_{w}(a_{1}, …, a_{N}) & = M_{w′}(a_{1}, …, a_{N−1})P_{j}(a_{N}) = P_{j′_{1}}(a_{1}) ⋯ P_{j′_{N−1}}(a_{N−1})P_{j}(a_{N}) \\ & = P_{j_{1}}(a_{1}) ⋯ P_{j_{N−1}}(a_{N−1})P_{j_{N}} (a_{N}). \end{aligned}

□

3. Factorizations in a Schubert cell

The aim of this section is to give explicit formulas for the parametrizations P_{i} and for the inverse maps P_{i}^{−1}.

3.1. Pseudo-Line Arrangements. Following [BFZ], Section 2.3, we define a pseudoline arrangement as the union of a finite number of intervals, called pseudo-lines, smoothly immersed in a bounded horizontal strip of the plane such that

(i) each vertical line in the strip intersects each pseudo-line in exactly one point, (ii) each pair of distinct pseudo-lines intersect at one point at most, such a intersection

being transversal (we call the intersection of two pseudo-lines a crossing point),

(iii) no three pseudo-lines meet at a point and no two crossing points lie on the same vertical line. (See Figures 3.2 and 3.3 for two examples of pseudo-line arrangements.)

We consider pseudo-line arrangements up to isotopy in the space of pseudo-line arrangements.

A path on a pseudo-line arrangement is a subset that projects bijectively onto the horizontal projection of the pseudo-line arrangement. Thus a path is composed of parts of one or more pseudo-lines. A path is admissible if the only allowed changes of pseudo-lines are at crossing points where the left tangent of the path has a bigger slope than the right tangent (see Figure 3.1 for an allowed change of pseudo-lines).

Figure 3.1. Allowed change of pseudo-lines in an admissible path

Let us label the left and right ends of the pseudo-lines in a pseudo-line arrangement by the integers 1 to n from bottom to top, where n is the number of pseudo-lines. Any reduced decomposition (i_{1}, …, i_{N}) of a permutation w ∈ S_{n} gives rise to a pseudo-line arrangement with n pseudo-lines, according to the following rules:

(a) to the transposition s_{i} we assign the pseudo-line arrangement with a unique crossing point, which sits on the pseudo-lines whose left (and right) labels are i and i + 1 (see Figure 3.2);

(b) if D′ is the pseudo-line arrangement of (i_{1}, …, i_{N−1}) and D′′ is the pseudo-line arrangement of (i_{N}), then the pseudo-line arrangement we assign to (i_{1}, …, i_{N}) is obtained by placing D′′ to the right of D′ in the horizontal strip and gluing together the i-th left end of D′′ and the i-th right end of D′ for all i = 1, …, n.

The pseudo-line arrangement of a reduced decomposition has the following properties:

(i) If the right label of a pseudo-line is k, then its left label is w(k).

(ii) The number N of crossing points is equal to the length of the reduced decomposition.

Figure 3.2. Pseudo-line arrangement of the transposition s_{i}

Given a reduced decomposition i of length N and its pseudo-line arrangement Γ, we label the N crossing points of Γ from left to right by labels x_{1}, …, x_{N} considered in this order. We define the weight of a path in Γ as the product from left to right of the labels of the crossing points where the path switches from a pseudo-line to another. If a path consists of one pseudo-line (without any pseudo-line change), we agree that its weight is 1.

We use these definitions to describe the entries of the matrix P_{i}(x_{1}, …, x_{N}).

3.2. Proposition.— For all 1 ≤ i, j ≤ n, the (i, j)-entry of the matrix P_{i}(x_{1}, x_{2}, …, x_{N}) = P_{i_{1}}(x_{1}) ⋯ P_{i_{N}} (x_{N}) is equal to the sum of the weights of all admissible paths with left label i and right label j in the pseudo-line arrangement of i.

Proof.— If i = (i) is of length one, then we immediately see from Figure 3.2 that Proposition 3.2 holds for the entries of P_{i}(x_{1}) = P_{i}(x_{1}). The case of a reduced decomposition i of length > 1 follows by induction on the length of i from the previous case and from the formula giving the entries of a product of matrices. □

Apply Proposition 3.2 to Figure 3.3 in order to recover Formulas (1.7).

Figure 3.3. Pseudo-line arrangement of the reduced decomposition (1, 2, 3, 4, 1, 2, 3, 1, 2)

Our next task is to give a formula for the inverse map P_{i}^{−1} : C_{w} → R^{N}, where i is a reduced decomposition of w. To the k-th crossing point (counted from left to right) in the pseudo-line arrangement of i we associate subsets I_{k}, J_{k} of {1, …, n} and a sign ε_{k} as follows. Considering the two pseudo-lines intersecting at this point, we define by T_{k} the union of their parts lying below the crossing point. We call T_{k} the k-th roof of the pseudo-line arrangement. A roof has a left and a right slope. A pseudo-line will be called efficient for T_{k} if it intersects transversally both the left and the right slopes of T_{k}.

We set ε_{k} = + (resp. ε_{k} = −) if the total number of pairwise intersections of the efficient pseudo-lines for T_{k} is even (resp. is odd). In other words, ε_{k} is the sign of the permutation represented by the pseudo-line arrangement consisting only of the pseudolines that are efficient for T_{k}. The set I_{k} (resp. J_{k}) is defined as the set of left labels (resp. right labels) of the efficient pseudo-lines for T_{k} to which we add the left label (resp. right label) of the left slope (resp. right slope) of T_{k}. (See Remark 3.10 for an alternative definition of I_{k} and J_{k}.)

In order to state Theorem 3.3, we need the following two conventions. Given a n × nmatrix M and subsets I, J of {1, …, n}, we denote by M_{I,J} the submatrix of M consisting of the entries M_{ij} of M such that i ∈ I and j ∈ J. For a p × p-matrix A = (A_{ij})_{1≤i,j≤p}, we set

|A| = ∑_{σ∈S_{p}} (−1)^{σ} A_{1,σ(1)}A_{2,σ(2)} … A_{p,σ(p)}.  (3.1)

This coincides with the determinant of A when the ring R is commutative.

We now give a formula for the inverse bijection P_{i}^{−1} : C_{w} → R^{N}.

3.3. Theorem.— Let i = (i_{1}, i_{2}, …, i_{N}) be a reduced decomposition of a permutation w ∈ S_{n} and let M be an element of the Schubert cell C_{w}. Then for any k such that 1 ≤ k ≤ N, the k-th component of P_{i}^{−1}(M) = (x_{1}, …, x_{N}) ∈ R^{N} is given by

x_{k} = ε_{k} |M_{I_{k},J_{k}}|.  (3.2)

For example, consider the roof T_{4} (labelled x_{4}) in Figure 3.3. The left label of its left slope is 1 and the right label of its right slope is 2. The roof T_{4} has two efficient pseudo-lines: one connects 2 to 4, the other connects 3 to 3, from left to right. It follows that the index sets are I_{4} = {1, 2, 3} and J_{4} = {2, 3, 4}. We have ε_{4} = − because the two efficient pseudo-lines intersect exactly once. Proceeding in the same way for the other roofs, we recover the factorization (1.8).

3.4. Proof of Theorem 3.3: Preliminaries. We shall prove Theorem 3.3 in two steps: first, in the case when the ring R is commutative (see Section 3.6); then in the case of a general ring R (see Section 3.9).

In view of Theorem 1.1, it is enough to check (3.2) when M = P_{i}(x_{1}, …, x_{N}). We start with the following construction.

Let us concentrate on the kth crossing point (counted from left to right) in the pseudoline arrangement Γ of i. This crossing point is labelled by x_{k}. Out of Γ we form a new pseudo-line arrangement Γ′ by keeping only the two pseudo-lines intersecting at the kth crossing point of Γ and the pseudo-lines that are efficient for the kth roof T_{k}. The pseudoline arrangement Γ′ has m pseudo-lines with m ≤ n. The labels of the crossing points of Γ′ form a subset {y_{1}, …, y_{M}} of {x_{1}, …, x_{N}} (we assume that the labels y_{1}, …, y_{M} appear in this order when we sweep Γ′ from left to right). Observe that the label x_{k} belongs to this subset: we denote by p the integer such that x_{k} = y_{p}. The configuration Γ′ is the pseudo-line arrangement of a reduced decomposition j. The corresponding permutation in S_{m} will be denoted by w′.

From the reduced decomposition j = (j_{1}, …, j_{M}) and the labels y_{1}, … y_{M} of the crossing points of Γ′, we can form the matrix product P_{j_{1}}(y_{1}) ⋯ P_{j_{M}} (y_{M}) ∈ GL_{m}(R). Removing the last row and the last column in each matrix P_{j_{ℓ}}(y_{ℓ}) appearing in the previous product, we get (m−1)×(m−1)-matrices \overline{P}_{j_{ℓ}}(y_{ℓ}). Let us form the (m−1)×(m−1)-matrix

M_{k} = \overline{P}_{j_{1}}(y_{1}) … \overline{P}_{j_{M}} (y_{M}).  (3.3)

We claim the following, which relates the matrix M_{k} to the submatrix M_{I_{k},J_{k}} of M = P_{i}(x_{1}, …, x_{N}), as defined above.

3.5. Lemma.— For all k = 1, …, N, we have M_{k} = M_{I_{k},J_{k}}.

Proof.— As a consequence of the definitions of I_{k}, J_{k}, and of Proposition 3.2, the submatrix M_{I_{k},J_{k}} is the (m − 1) × (m − 1)-matrix obtained from the m × m-matrix P_{j_{1}}(y_{1}) ⋯ P_{j_{M}} (y_{M}) by removing its last row and its last column, in view of the following observation: if ℓ is a pseudo-line that is efficient for the roof T_{h} formed by two pseudo-lines ℓ_{1}, ℓ_{2} that are efficient for the roof T_{k}, then ℓ is efficient for T_{k}. Figure 3.4 gives graphical evidence for this observation.

Figure 3.4

It therefore suffices to check that the operation of simultaneously removing the last row and the last column of a matrix commutes with the product of matrices. This is of course not true in general. Nevertheless, it works for the product P_{j_{1}}(y_{1}) ⋯ P_{j_{M}} (y_{M}).

Indeed, there is exactly one integer p such that y_{p} = x_{k}. It is clear from the definition of Γ′ that we have j_{p} = m − 1 for the corresponding index j_{p}. Hence P_{j_{p}}(y_{p}) = P_{m−1}(x_{k}) is of the form

( \begin{matrix}& & & & 0 \\ & \overline{P}_{j_{p}}(y_{p}) & & & ⋮ \\ & & & & 0 \\ & & & & 1 \\ 0 & ⋯ & 0 & 1 & 0 \end{matrix} ) ,

where the entries of the last row and of the last column are all 0, except the (m, m − 1)- and the (m − 1, m)-entries, which are equal to 1.

By contrast, if ℓ ≠ p, then j_{ℓ} < m − 1, which implies that P_{j_{ℓ}}(y_{ℓ}) is of the form

( \begin{matrix}& & & & 0 \\ & \overline{P}_{j_{ℓ}}(y_{ℓ}) & & & ⋮ \\ & & & & 0 \\ & & & & 0 \\ 0 & ⋯ & 0 & 0 & 1 \end{matrix} ) ,

where now the only nonzero entry in the last row and in the last column is the (m, m)-entry.

In view of these facts, the equality M_{k} = M_{I_{k},J_{k}} will then be a consequence of the following matrix identity holding for any triple (A, B, C) of (m − 1) × (m − 1)-matrices:

( \begin{matrix}& & & & 0 \\ & A & & & ⋮ \\ & & & & 0 \\ & & & & 0 \\ 0 & ⋯ & 0 & 0 & 1 \end{matrix} ) ( \begin{matrix}& & & & 0 \\ & B & & & ⋮ \\ & & & & 0 \\ & & & & 1 \\ 0 & ⋯ & 0 & 1 & 0 \end{matrix} ) ( \begin{matrix}& & & & 0 \\ & C & & & ⋮ \\ & & & & 0 \\ & & & & 0 \\ 0 & ⋯ & 0 & 0 & 1 \end{matrix} ) = ( \begin{matrix}& & & & ∗ \\ & ABC & & & ⋮ \\ & & & & ∗ \\ & & & & ∗ \\ ∗ & ⋯ & ∗ & ∗ & 0 \end{matrix} ) ,

where ABC is the product of the matrices A, B, C. □

3.6. Proof of Theorem 3.3: The Commutative Case. Assume that the ring R is commutative. Then we may take the determinants of both sides of (3.3) and we get

|M_{k}| = |\overline{P}_{j_{1}}(y_{1})| … |\overline{P}_{j_{M}} (y_{M})|.  (3.4)

We saw in the proof of Lemma 3.5 that P_{j_{p}}(y_{p}) = P_{m−1}(x_{k}) ∈ GL_{m}(R). Consequently, \overline{P}_{j_{p}}(y_{p}) is a diagonal matrix whose diagonal entries are 1, except for the last one which is y_{p} = x_{k}. It follows that |\overline{P}_{j_{p}}(y_{p})| = x_{k}. If ℓ ≠ p, then |\overline{P}_{j_{ℓ}}(y_{ℓ})| = |P_{j_{ℓ}}(y_{ℓ})| = −1. The computation of these determinants, together with (3.4) and Lemma 3.5, implies that |M_{I_{k},J_{k}}| = ε x_{k} for some ε = ±.

In order to complete the proof of (3.2), it remains to check that ε = ε_{k}. Each factor |\overline{P}_{j_{ℓ}}(y_{ℓ})| = |P_{j_{ℓ}}(y_{ℓ})| with p ≠ ℓ corresponds to a crossing point of Γ′ that is not the top of the roof T_{k} in Γ. Therefore, ε is the parity of the number of such crossing points. The latter can be divided into two sets: the crossing points that lie on the slopes of the roof T_{k} and the crossing points that do not. By the very definition of efficient pseudo-lines, the crossing points that lie on T_{k} come in pairs. It follows that ε is the parity of the number of the crossing points of Γ′ that do not lie on T_{k}; now, the latter are exactly the intersection points of pairs of efficient pseudo-lines. This proves that ε = ε_{k}. □

For the noncommutative case, we shall need the following lemma, which is of independent combinatorial interest. In order to state it, we shall need the concept of a traverse of a matrix A: this is any nonzero monomial A_{1,σ(1)}A_{2,σ(2)} … A_{p,σ(p)} occurring in the right-hand side of (3.1).

3.7. Lemma.— Let σ ∈ S_{m} such that σ(1) = m and σ(m) = 1, and Q be any m × mmatrix whose support lies in the diagram of σ. Let A be the matrix obtained from M_{σ} + Q by deleting its last row and its last column. Then any traverse of A is of the form

A_{1,j_{1}}A_{σ(j_{1}),j_{2}}A_{σ(j_{2}),j_{3}} … A_{σ(j_{p−1}),j_{p}}

with j_{1} > j_{2} > … > j_{p−1} > j_{p} = 1.

Lemma 3.7 is illustrated in Figure 3.5 below: overlining and underlining certain entries, we show two examples of traverses of the matrix obtained by removing the last row and the last column.

Proof.— The lemma clearly holds if m = 1. Assume m > 1 and the lemma holds for any m′ < m and any σ′ ∈ S_{m′} such that σ(1) = m′ and σ(m′) = 1.

Consider σ ∈ S_{m}, matrices Q and A as in the statement of the lemma. Let j be such that σ(j) = m − 1 (we have 1 < j < m).

(a) Take any traverse of A. Assume that it contains the (m − 1, j)-entry (this is the case of the traverse depicted in Figure 3.5 with underlined entries). Suppressing the m−1st row and the jth column of A (and of M_{w} + Q), we are reduced to a similar case in S_{m−1}, which allows us to use induction.

(b) If the traverse does not contain the (m−1, j)-entry (this is the case of the traverse depicted in Figure 3.5 with overlined entries), it necessarily contains the (m − 1, 1)-entry which is an entry of Q, hence of A. We claim that it also contains all the entries in position (σ(2), 2), (σ(3), 3), …, (σ(j −1), j −1). Indeed, the only nonzero entries of A in the σ(2)th row are in the first and second columns. Since the traverse already contains the (m − 1, 1)- entry, it has to contain the (σ(2), 2)-entry. Similarly, the only nonzero entries of A in the σ(3)th row are in the first, second, and third columns. Since the traverse already contains entries in position (m − 1, 1) and (σ(2), 2), it has to contain the (σ(3), 3)-entry. This argument works up to the σ(j − 1)th row; it shows that the traverse contains the entries indicated in the claim.

Suppress Columns 1, 2 …, j − 1 and Rows σ(1), σ(2), …, σ(j − 1) in the matrices M_{w} + Q and A. What is left is a similar matrix of smaller size (Figure 3.6 shows the matrix obtained by suppressing these rows and columns in the example of Figure 3.5 with overlined entries), which allows us to apply the induction hypothesis. □

( \begin{matrix}∗ & ∗ & ∗ & ∗ & ∗ & ∗ & ∗ & \underline{∗} & \overline{∗} & 1 \\ ∗ & ∗ & ∗ & \underline{\overline{1}} & 0 & 0 & 0 & 0 & 0 & 0 \\ ∗ & ∗ & ∗ & 0 & ∗ & \underline{∗} & ∗ & \overline{1} & 0 & 0 \\ ∗ & ∗ & ∗ & 0 & ∗ & ∗ & \overline{∗} & ∗ & \underline{1} & 0 \\ ∗ & ∗ & \underline{\overline{1}} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ ∗ & ∗ & 0 & 0 & \underline{∗} & \overline{1} & 0 & 0 & 0 & 0 \\ \underline{∗} & ∗ & 0 & 0 & \overline{1} & 0 & 0 & 0 & 0 & 0 \\ ∗ & \underline{\overline{1}} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \overline{∗} & 0 & 0 & 0 & 0 & 0 & \underline{1} & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} )

Figure 3.5

( \begin{matrix}∗ & ∗ & \overline{∗} & 1 \\ ∗ & \overline{1} & 0 & 0 \\ \overline{∗} & ∗ & 1 & 0 \\ 1 & 0 & 0 & 0 \end{matrix} )

Figure 3.6

3.8. The Matrices Π_{i}. In order to prove (3.2) when the ring R is not commutative, it will be useful to label the crossing points of the pseudo-line arrangement Γ of the reduced decomposition i = (i_{1}, …, i_{N}) with double-indexed variables x_{rs} where 1 ≤ r < s ≤ n. More precisely, we label the kth crossing point of Γ with the variable x_{r_{k}s_{k}}, where r_{k} < s_{k} are the left labels of the two pseudo-lines intersecting at the k-th crossing point. Since two pseudo-lines intersect in at most one point, the variables x_{r_{k}s_{k}} labelling the crossing points are distinct. Observe also that the only variables x_{ij} coming up as labels for the crossing points of Γ are the ones with indices i, j such that i < j and w^{−1}(i) > w^{−1}(j).

We set

Π_{i} = P_{i_{1}}(x_{r_{1}s_{1}}) ⋯ P_{i_{N}} (x_{r_{N} s_{N}}).  (3.5)

Alternatively, Π_{i} can be defined by induction on the length of i according to the following rules:

(a) if i = (i) is of length one, then Π_{i} = P_{i}(x_{i,i+1});

(b) if i = (i_{1}, …, i_{N−1}, i_{N}) is of length N > 1, define i′ = (i_{1}, …, i_{N−1}); if we set w′ = s_{i_{1}} … s_{i_{N−1}}, then

Π_{i} = Π_{i′} P_{i_{N}} (x_{w′(i_{N}),w′(i_{N} +1)}).

It follows from the definition of Π_{i} and of Proposition 3.2 that each entry of Π_{i} differing from 0 or from 1 (equivalently, in the diagram of w) is a sum of monomials of the form

x_{a_{1}a_{2}}x_{a_{2}a_{3}} … x_{a_{q−1}a_{q}},  (3.6)

where a_{1} < a_{2} < … a_{q−1} < a_{q}. Moreover, if it is the (i, j)-entry of Π_{i}, we have

a_{1} = i and a_{q} = w(j).  (3.7)

3.9. Proof of Theorem 3.3: The General Case. It is enough to prove (3.2) when the matrix M ∈ C_{w} is of the form M = Π_{i}. Then (3.2) is equivalent to

x_{r_{k}s_{k}} = ε_{k} |M_{I_{k},J_{k}}|.  (3.8)

(1 ≤ k ≤ N). Start as in Section 3.4. Lemma 3.5 implies that the matrix M_{I_{k},J_{k}} is of the form M_{σ} + Q considered in Lemma 3.7 for some σ ∈ S_{m}. We use this to prove the following claim.

Claim: Any monomial in any traverse of M_{I_{k},J_{k}} is of the form x_{c_{1}c_{2}}x_{c_{2}c_{3}} … x_{c_{t−1}c_{t}}, where c_{1} < c_{2} < … < c_{t−1} < c_{t}. Indeed, by Lemma 3.7, we know that any traverse of M_{I_{k},J_{k}} is of the form M_{1,j_{1}}M_{σ(j_{1}),j_{2}}M_{σ(j_{2}),j_{3}} … M_{σ(j_{p−1}),j_{p}} where M_{u,v} stand for the entries of M_{I_{k},J_{k}}. The latter is a submatrix of Π_{i}. Therefore, by (3.6) and (3.7), we have

M_{σ(j_{u}),j_{u+1}} = ∑ x_{a_{1}a_{2}}x_{a_{2}a_{3}} … x_{a_{q−1}a_{q}}

where the summation is over some a_{1} < a_{2} < … a_{q−1} < a_{q} such that a_{1} = σ(j_{u}) and a_{q} = σ(j_{u+1}). Similarly, for M_{σ(j_{u+1}),j_{u+2}} we have

M_{σ(j_{u+1}),j_{u+2}} = ∑ x_{b_{1}b_{2}}x_{b_{2}b_{3}} … x_{b_{r−1}b_{r}}

with b_{1} = σ(j_{u+1}) and b_{r} = σ(j_{u+2}). Therefore, b_{1} = a_{q}, which shows that the product M_{σ(j_{u}),j_{u+1}}M_{σ(j_{u+1}),j_{u+2}} is of the form (3.6). This argument extends to the whole product M_{1,j_{1}}M_{σ(j_{1}),j_{2}}M_{σ(j_{2}),j_{3}} … M_{σ(j_{p−1}),j_{p}}, which proves the claim.

The above claim implies that the determinant |M_{I_{k},J_{k}}| is of the form

|M_{I_{k},J_{k}}| = ∑ ± x_{c_{1}c_{2}}x_{c_{2}c_{3}} … x_{c_{t−1}c_{t}},

where the indices are increasing: c_{1} < c_{2} < … < c_{t−1} < c_{t}. By the proof in the commutative case (see Section 3.6), we know that |M_{I_{k},J_{k}}| ≡ ε_{k}x_{r_{k}s_{k}} modulo the ideal I generated by the commutators of the variables x_{ij}. Now, it is clear that

∑_{c_{1}<c_{2}<...<c_{t−1}<c_{t}} ± x_{c_{1}c_{2}}x_{c_{2}c_{3}} … x_{c_{t−1}c_{t}} ≡ ε_{k}x_{r_{k}s_{k}} mod I

implies

∑_{c_{1}<c_{2}<...<c_{t−1}<c_{t}} ± x_{c_{1}c_{2}}x_{c_{2}c_{3}} … x_{c_{t−1}c_{t}} = ε_{k}x_{r_{k}s_{k}}.

This proves (3.8), hence Theorem 3.3, in the general case. □

3.10. Remark.— The sets of indices I_{k} and J_{k} entering the statement of Theorem 3.3 can be recovered from the matrix P_{i}(x_{1}, …, x_{N}) as follows. Take the entry of P_{i}(x_{1}, …, x_{N}) whose linear term is x_{k}. We denote by Φ_{k} the homogeneous polynomial of highest degree in this entry. Let V_{k} be the set of those variables x_{1}, …, x_{N} that occur in Φ_{k}. Then I_{k} (resp. J_{k}) is the set of indices of the rows (resp. of the columns) of Q_{i}(x_{1}, …, x_{N}) where the variables in V_{k} appear.

4. Balanced labellings

The purpose of this section is to prove Theorem 1.2. To this end, we need the definition of a balanced labelling of the diagram D_{w} of a permutation w ∈ S_{n}.

Given an element (i, j) of D_{w}, we call arm (resp. leg) of (i, j) the subset of D_{w} consisting of all elements (i, k) with k > j (resp. of all elements (h, j) with h > i). The hook of (i, j) is the union of {(i, j)}, of its arm and of its leg. An injective labelling L of D_{w} by the integers 1, 2, …, N is said to be balanced if for any element of D_{w}, whose label we denote by a, the number of labels > a in the leg is equal to the number of labels < a in the arm.

This definition of a balanced labelling of a diagram extends the concept of balanced tableau introduced by Edelman and Greene [EG] for the Ferrers diagram of an integer partition. An injective balanced labelling in our sense is equivalent, up to transposition, to the definition given by Fomin et al. in [FGRS], Section 2.

In the introduction, we associated a labelling L_{i} of the Rothe diagram D_{w} to any reduced decomposition i of w.

4.1. Proposition.— The labelling L_{i} is injective and balanced.

Proof.— (a) From Proposition 3.2 it is clear that each variable x_{1}, …, x_{N}, where N is the length of w, appears in the linear part Q_{i}(x_{1}, …, x_{N}) of the matrix P_{i}(x_{1}, …, x_{N}) and that distinct variables appear in distinct entries of Q_{i}(x_{1}, …, x_{N}). Since D_{w} has N elements, it follows that the labelling L_{i} is injective.

(b) We shall show that L_{i} is balanced by constructing for each element (i, j) of D_{w} a one-to one correspondence between the labels in the leg of (i, j) that are greater than the label of (i, j) and the labels in the arm of (i, j) that are smaller than the label of (i, j).

Let a be the label of (i, j) in L_{i}. Let (i′, j) be an element of the leg of (i, j) with label b with b > a. By definition of the leg, we have i′ > i. Let us consider the pseudo-line arrangement Γ of i with its crossings points labelled from left to right by x_{1} up to x_{N}. By Proposition 3.2 and the definition of L_{i}, the variable x_{a} labels the intersection of the pseudo-line with left label i and of the pseudo-line with right label j. Similarly, the variable x_{b} labels the intersection of the pseudo-line with left label i′ and of the pseudo-line with right label j. Since b > a, the crossing point labelled x_{b} lies to the right of the crossing point labelled x_{a} on the pseudo-line with right label j. Since the left labels i and i′ verify i′ > i and since pseudo-lines intersect in at most one point, the pseudo-line with left label i′ must intersect the pseudo-line with left label i in a point, labelled, say, by x_{c}, lying left of the crossing point labelled x_{a} on the pseudo-line with left label i (see Figure 4.1, which shows the only possible configuration). It follows that c < a and w^{−1}(i′) = j′ > j. Therefore, to any label b > a of an element (i′, j) in the leg of (i, j) we assigned an element (i, j′) = (i, w^{−1}(i′)) in the arm of (i, j) with label c < a.

Proceeding in a similar way, to any label c < a of an element (i, j′) in the arm of (i, j) one assigns an element (w(j′), j) in the leg of (i, j) with label b > a. These two maps are inverse of each other. □

Figure 4.1

So far we have a map i ↦ L_{i} from the set R(w) of reduced decompositions of w to the set of injective balanced labellings of D_{w}. The fact thas this map is bijective may be deduced from [FGRS], Theorem 2.4. For the sake of completeness, we shall give a self-contained proof of this fact after a few preliminaries.

Fix a permutation w ∈ S_{n} of length N ≥ 1 and an injective labelling L of the Rothe diagram D_{w} of w. Let (i, j) ∈ D_{w} be the element with label N. We assume that L is balanced. This assumption implies the following lemma.

4.2. Lemma.— (a) We have w(j + 1) = i.

(b) If (k, j) ∈ D_{w} for some k < i, then (k, j + 1) ∈ D_{w}.

(c) If a_{k} is the label of (k, j) ∈ D_{w} with k < i and b_{k} is the label of (k, j + 1), then a_{k} > b_{k}.

Proof.— (a) Since N is the greatest label, there is no greater label in the leg of (i, j). The labelling L being balanced, there is no smaller label in the arm of (i, j). This means that D_{w} does not contain any element (i, j′) with j′ > j. If we had w(j +1) > i, then, since (i, j) ∈ D_{w}, we would have w^{−1}(i) > j; as w^{−1}(i) ≠ j + 1, we would have w^{−1}(i) > j + 1, which would imply (i, j + 1) ∈ D_{w} and contradict our hypothesis on (i, j).

We now show that w(j +1) < i is impossible as well. Indeed, by (1.1), the assumption (i, j) ∈ D_{w} implies that (w(j + 1), j) ∈ D_{w}. The arm of (w(j + 1), j) is empty by (1.1). By the assumption on L, there is no label in the leg of (w(j + 1), j) that is greater than the label of (w(j + 1), j). But w(j + 1) < i implies that (i, j), which has the greatest label, is in the leg of (w(j + 1), j). This is a contradiction.

(b) In order to show that (k, j + 1) ∈ D_{w}, we have to check that k < w(j + 1) and j + 1 < w^{−1}(k). The first inequality follows from k < i and Part (a). Let us prove the second inequality: (k, j) ∈ D_{w} implies that j < w^{−1}(k). So it is enough to check that w^{−1}(k) ≠ j + 1. This follows from k ≠ i and j + 1 = w^{−1}(i) (Part (a)).

(c) Suppose Statement (c) is not true. Then there is a maximal k < i such that a_{k} < b_{k}. Assume that there are exactly p labels > a_{k} in the leg of (k, j). Since N > a_{k}, we have p ≥ 1. By the assumption on the labelling L, there are p labels u_{1}, …, u_{p}, all < a_{k}, in the arm of (k, j). Since u_{i} < a_{k} < b_{k} for all i = 1, …, p, then u_{1}, …, u_{p} are the labels < b_{k} in the arm of (k, j + 1), hence there are p labels > b_{k} in the leg of (k, j + 1). Assume that these labels are b_{h_{1}}, …, b_{h_{p}}. By Part(a), they label elements (i′, j + 1) of D_{w} such that k < i′ < i. Then for any i = 1, …, p, we have a_{h_{i}} > b_{h_{i}} > b_{k} > a_{k} by the maximality of k. The label N together with a_{h_{1}}, …, a_{h_{p}} form p + 1 labels > a_{k} in the leg of (k, j), which is in contradiction with the definition of p.

□

Let w′ = ws_{j}, where again (i, j) is the element of D_{w} with label N.

4.3. Lemma.— The permutation w′ is of length N − 1. Moreover, the Rothe diagram D_{w′} is obtained from D_{w} by first removing the element (i, j), then by exchanging the jth and the j + 1st columns.

Proof.— Lemma 4.2 (a) shows that we are in the situation of Figure 2.1.a. Lemma 4.3 follows. □

In view of Lemmas 4.2 and 4.3, out of the labelling L we get an injective labelling L′ of D_{w′} by removing the label N and by exchanging the jth and the j + 1st columns. As a consequence of Lemma 4.2 (c), we get the following result, which is crucial for the proof of Theorem 1.2.

4.4. Corollary.— The labelling L′ of D_{w′} is balanced.

4.5. Proof of Theorem 1.2. It it clear when w is of length 1, i.e., when w is a simple transposition s_{j} for some 1 ≤ j ≤ n − 1.

To a permutation w ∈ S_{n} of length N ≥ 1 and an injective balanced labelling L of D_{w}, we assign a reduced decomposition i of w as follows.

Let (i, j) ∈ D_{w} be the element with label N. As above, we introduce the permutation w′ = ws_{j}, which is of length N − 1 (Lemma 4.3), and the labelling L′ of D_{w′} obtained from L by removing the label N and by exchanging the jth and the j + 1st columns. The labelling L′ is balanced by Corollary 4.4.

Starting the same procedure with the couple (w′, L′), we get a new couple (w′′, L′′), where w′′ = w′s_{j′} is a permutation of length N − 2, the integer j′ is the number of the column in which the highest label N − 1 of L′ appears, and L′′ is the balanced labelling of D_{w′′} obtained from L′ by removing the label N − 1 and by exchanging the j′th and the j′ + 1st columns.

Iterating this procedure, we get a sequence of permutations w_{N}, w_{N−1}, w_{N−2}, …, w_{0}, where w_{i} is of length i for all i = 0, …, N, and a sequence of integers j_{N}, j_{N−1}, j_{N−2}, …, j_{1} with w_{N} = w, w_{N−1} = w′, w_{N−2} = w′′ and j_{N} = j, j_{N−1} = j′, j_{N−2} = j′′, such that w_{i} = w_{i−1}s_{j_{i}}, hence w_{i} = s_{j_{1}}s_{j_{2}} … s_{j_{i}} for all i = 1, …, N. In particular,

w = w_{N} = s_{j_{1}}s_{j_{2}} … s_{j_{N}} ,

which implies that (j_{1}, j_{2}, …, j_{N}) is a reduced decomposition of w. We denote this reduced decomposition by r(L).

This defines a map r from the set of injective balanced labellings of D_{w} to the set R(w) of reduced decompositions of w. It is easy to check that r is a two-sided inverse to the map i ↦ L_{i} of Theorem 1.2. □

Figure 4.2 shows how r(L) is obtained using the above procedure when we start from the following injective balanced labelling of w = 2 4 6 5 3 1 (the crosses indicate the entries of the permutation matrix M_{w}):

L = ( \begin{matrix}1 & 3 & 7 & 5 & 2 & × \\ × & . & . & . & . & . \\ . & 4 & 8 & 6 & × & . \\ . & × & . & . & . & . \\ . & . & 9 & × & . & . \\ . & . & × & . & . & . \end{matrix} ) .  (4.1)

In each labelling of Figure 4.2 we underlined the greatest label. The integer j that appears when we pass from one labelling to one with one label less is written over the corresponding arrow. The last labelling is empty because it is the labelling of the identity permutation. For this example, we get r(L) = (1, 2, 3, 2, 4, 3, 5, 4, 3).

( \begin{matrix}1 & 3 & 7 & 5 & 2 & . \\ . & . & . & . & . & . \\ . & 4 & 8 & 6 & . & . \\ . & . & . & . & . & . \\ . & . & \underline{9} & . & . & . \\ . & . & . & . & . & . \end{matrix} ) ⟶^{3} ( \begin{matrix}1 & 3 & 5 & 7 & 2 & . \\ . & . & . & . & . & . \\ . & 4 & 6 & \underline{8} & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \end{matrix} ) ⟶^{4} ( \begin{matrix}1 & 3 & 5 & 2 & \underline{7} & . \\ . & . & . & . & . & . \\ . & 4 & 6 & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \end{matrix} ) ⟶^{5}

( \begin{matrix}1 & 3 & 5 & 2 & . & . \\ . & . & . & . & . & . \\ . & 4 & \underline{6} & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \end{matrix} ) ⟶^{3} ( \begin{matrix}1 & 3 & 2 & \underline{5} & . & . \\ . & . & . & . & . & . \\ . & 4 & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \end{matrix} ) ⟶^{4} ( \begin{matrix}1 & 3 & 2 & . & . & . \\ . & . & . & . & . & . \\ . & \underline{4} & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \end{matrix} ) ⟶^{2}

( \begin{matrix}1 & 2 & \underline{3} & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \end{matrix} ) ⟶^{3} ( \begin{matrix}1 & \underline{2} & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \end{matrix} ) ⟶^{2} ( \begin{matrix}\underline{1} & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \end{matrix} ) ⟶^{1} ∅.

Figure 4.2

4.6. Remark.— The bijection of Theorem 1.2 is the same as the one described for the longest permutation w_{0} ∈ S_{n} in [EG] and, up to transposition, for general w in [FGRS].

4.7. Remark.— The matrix P_{i}(x_{1}, …, x_{N}) can be recovered from the labelling L_{i} as follows. If we denote the (k, ℓ)-entry of L_{i} by ν(k, ℓ), then the (i, j)-entry of P_{i}(x_{1}, …, x_{N}) for (i, j) ∈ D_{w} is given by

∑ x_{ν(w(j_{k}),j_{k−1})} … x_{ν(w(j_{2}),j_{1})} x_{ν(w(j_{1}),j_{0})},  (4.2)

where the sum runs over all indices such that k ≥ 1, j = j_{0} < j_{1} < … < j_{k} = w^{−1}(i), w(j) = w(j_{0}) > w(j_{1}) > … > w(j_{k}) = i, and ν(w(j_{k}), j_{k−1}) < … < ν(w(j_{2}), j_{1}) < ν(w(j_{1}), j_{0}). See Figure 4.3 for a graphical interpretation of the conditions on the indices j_{p}.

Figure 4.3

4.8. An Extension of Theorem 1.2.— Transposing from [FGRS], we say that a labelling of D_{w}, with not necessarily distinct labels, is balanced if each hook is balanced in the following sense: we say that a hook is balanced if the corner label remains unchanged after we have rearranged the labels in the hook so that they weakly increase upwards and from left to right. When the labels are distinct, this definition coincides with the one we gave at the beginning of this section. We also say that a labelling is row-strict if the labels in each row are distinct. Then the following extension of Theorem 1.2 holds: the set of row-strict balanced labellings of D_{w} coincides with the set of linear parts of the matrix products P_{i}(x_{1}, x_{2}, …, x_{N}) for all reduced decompositions i = (i_{1}, i_{2}, …, i_{N}) of w and all totally ordered variables x_{1} ≤ x_{2} ≤ … ≤ x_{N}, the equality x_{k} = x_{k+1} being permitted only if i_{k} > i_{k+1}.

Let us end this section by showing how to recover the labelling R_{i}, defined by (1.11), from the labelling L_{i}.

4.9. Lemma.— The (i, j)-entry of R_{i} is the number of labels in the arm of (i, j) in L_{i}, smaller than the label ν(i, j) of (i, j); equivalently, it is the number of labels in the leg of (i, j) in L_{i}, greater than the label ν(i, j).

Proof.— The labelling R_{i} counts the quadratic monomials in P_{i}(x_{1}, …, x_{N}), hence, by Proposition 3.2, the efficient pseudo-lines in the pseudo-line arrangement of i. One then argues as in Part (b) of the proof of Proposition 4.1 so as to conclude that each efficient pseudo-line produces a label in the arm that is smaller than the label in the (i, j)-position, and a label in the leg that is greater than it; conversely, such labels come from efficient pseudo-lines. □

Applying Lemma 4.9 to the labelling L_{i} given by (4.1), we get

R_{i} = ( \begin{matrix}0 & 1 & 2 & 1 & 0 & . \\ . & . & . & . & . & . \\ . & 0 & 1 & 0 & . & . \\ . & . & . & . & . & . \\ . & . & 0 & . & . & . \\ . & . & . & . & . & . \end{matrix} ) .  (4.3)

4.10. Remark.— Recall that the code (also called the Lehmer code) of a permutation σ ∈ S_{p} is the vector (c_{1}, …, c_{p}) ∈ N^{p} such that c_{i} = card{j | j > i and σ(j) < σ(i)}. The integer c_{i} is also the number of elements in the ith column of the diagram D_{σ}. The code function is a bijection between S_{p} and the set of vectors (c_{1}, …, c_{p}) ∈ N^{p} such that c_{1} ≤ p − 1, c_{2} ≤ p − 2, …, c_{p} ≤ 0.

Lemma Ê4.9 states that each row of R_{i} is the code of the permutation induced by the natural order on the labels in the corresponding row in L_{i}. Similarly, one interprets the columns as codes of permutations, the inversions being now counted with respect to the reverse order on labels: e.g., c = (1, 2, 0, 0) codes the permutation 3 1 4 2.

5. Characterizing commutation classes of reduced decompositions

The purpose of this section is to prove Theorem 1.3. Recall the matrices Π_{i} of Section 3.8.

5.1. Theorem.— Two reduced decompositions i and j of a permutation w belong to the same commutation class if and only if Π_{i} = Π_{j}.

Proof.— (a) If i and j differ by a 2-move, then Relation (1.4a) and the definition of Π_{i} and Π_{j} imply that Π_{i} = Π_{j}. This can also be seen using the pseudo-line arrangements of i and j (which are isotopic as configurations in the plane) and Proposition 3.2. It follows that, if i and j belong to the same commutation class, then Π_{i} = Π_{j}.

(b) Let i and j be reduced decompositions of w such that Π_{i} = Π_{j}. We wish to show that i and j belong to the same commutation class. We shall proceed by induction on the length of w.

If w is of length 1, then it has exactly one reduced decomposition, hence exactly one commutation class and there is nothing to show.

Suppose that i and j are of length N > 1. Consider their pseudo-line arrangements denoted by Γ_{i} and Γ_{j} respectively. Let us concentrate on the leftmost crossing point of Γ_{i} and the two pseudo-lines intersecting at this point. Their left labels are necessarily of the form i_{1} and i_{1} + 1, where i_{1} is the first index in i. By definition of Π_{i}, the double-indexed variable x_{i_{1},i_{1}+1} appears in the matrix Π_{i}, hence in the matrix Π_{j}. This means that in Γ_{j} the pseudo-line L with left label i_{1} and the pseudo-line L′ with left label i_{1} + 1 intersect each other. Let C be the union of the connected components of the plane deprived of Γ_{j} situated above L and under L′, to the left of their joint intersection. See Figure 5.1.

Figure 5.1

We claim that there is no pseudo-line of Γ_{j} crossing C. It follows from the claim that Γ_{j} can be isotoped to a pseudo-line arrangement whose leftmost crossing point is labelled by x_{i_{1},i_{1}+1}. Equivalently, one can pass through a sequence of 2-moves from j to a reduced decomposition k with first index k_{1} = i_{1}. By Part (a), we have Π_{k} = Π_{j} = Π_{i}.

Let i′ and k′ be the reduced decompositions obtained respectively from i and k by removing the first index i_{1} = k_{1}. The equality Π_{i} = Π_{k} implies Π_{i′} = Π_{k′}. Since i′ and k′ are of length N − 1, we may appeal to the induction hypothesis and conclude that i′ and k′ belong to the same commutation class. So do i and k, hence i and j.

We now prove the claim. Suppose that some pseudo-line L′′ of Γ_{j} with left label r (necessarily ≠ i_{1}, i_{1} + 1) crosses the region C. Then it must necessarily intersect L and L′ to the left of the intersection of L and L′. There are two cases: either r < i_{1} or r > i_{1} + 1.

Suppose that r < i_{1}. The intersection of L′′ with L produces a crossing point with label x_{r,i_{1}} whereas the intersection of L′′ with L′ produces a crossing point with label x_{r,i_{1}+1} (see Figure 5.2). By Proposition 3.2 the matrix Π_{j} contains simultaneously the monomials x_{r,i_{1}+1} and x_{r,i_{1}}x_{i_{1},i_{1}+1}. Therefore, the matrix Π_{i} must contains the same monomials. Since the pseudo-lines L, L′, L′′ intersect pairwise in Γ_{j}, they must intersect pairwise in Γ_{i}. Because the crossing point labelled x_{i_{1},i_{1}+1} is the leftmost in Γ_{i}, the crossing point labelled x_{r,i_{1}+1} comes before the crossing point labelled x_{r,i_{1}} (see Figure 5.3). By Proposition 3.2 this implies that the quadratic monomial x_{r,i_{1}}x_{i_{1},i_{1}+1} cannot appear in the matrix Π_{i}, which leads to a contradiction.

The case r > i_{1} + 1 is treated in a similar way (see Figures 5.4 and 5.5). □

Figure 5.2. The area C in Γ_{j} when r < i_{1} Figure 5.3. The leftmost part of Γ_{i} when r < i_{1} Figure 5.4. The area C in Γ_{j} when r > i_{1} + 1 Figure 5.5. The leftmost part of Γ_{i} when r > i_{1} + 1

The previous proof also shows that the following holds. 5.2. Corollary.— For two reduced decompositions i and j of w, the following conditions are equivalent:

(i) i and j belong to the same commutation class.

(ii) their pseudo-line arrangements are isotopic as configurations in the plane. (iii) their pseudo-line arrangements have the same efficient pseudo-lines. (iv) the matrices Π_{i} and Π_{j} have the same quadratic part.

As a consequence, the matrix Π_{i} is completely determined by its quadradic part.

5.3. Proof of Theorem 1.3. If i and j belong to the same commutation class, then Π_{i} = Π_{j} by Theorem 5.1. It follows that these matrices have the same number of quadratic terms in each entry; hence, so have the matrices P_{i}(X, …, X) and P_{j}(X, …, X). In view of (1.11), we get R_{i} = R_{j}.

Conversely, if we know R_{i}, then, since quadratic terms of P_{i} correspond to efficient pseudo-lines, and since efficient pseudo-lines give smaller labels in the arm in the matrix L_{i}, we know how many labels in the arm of any hook are smaller than the corner label. Since a permutation is determined by its code, this in turn implies that we know the relative order of the labels in each row of the diagram. Hence we can determine the labels that are smaller than a given corner label, hence the efficient pseudo-lines. Therefore, if R_{i} = R_{j}, then i and j have the same efficient pseudo-lines, which by Corollary 5.2 implies that i and j belong to the same commutation class. □

5.4. Corollary.— A reduced decomposition i of w is in the same commutation class as the canonical sequence of w if and only if the labelling R_{i} consists of zeroes only.

Proof.— By Proposition 2.1, if j is the canonical sequence of the permutation w, then the matrix P_{j}(x_{1}, …, x_{n}) has no quadratic monomials. Therefore, R_{j} = 0. We conclude with Theorem 1.3. □

5.5. Characterization of the Matrices R_{i}.— If k_{1}, …, k_{ℓ} are the labels in a row of R_{i}, then (k_{1}, …, k_{ℓ}) is by Lemma 4.9 the code of a permutation in S_{ℓ}, which we call the row permutation of this row. Similarly, we have a column permutation (the code being interpreted with respect to the decreasing order on integers). Thus, to each matrix R_{i}, we associate a bipermutation matrix with support in the diagram of w, whose (i, j)-entry consists of the couple (α, β), where α (resp. β) is the corresponding digit of the ith row (resp. jth column) permutation of R_{i}. From this, we define a graph whose vertices are the entries of the bipermutation matrix, with edges u → v if either u, v are in the same row and u = (α, β) and v = (α + 1, β′), or u, v are in the same column and u = (α, β) and v = (α′, β + 1). An example of a labelling R_{i}, corresponding to (1.10), is given in Figure 5.6 together with its bipermutation matrix and its graph.

Figure 5.6 5.6. Theorem.— The mapping i ↦ R_{i} defines a bijection from the set of commutation classes of reduced decompositions of w onto the set of labellings of D_{w} by natural numbers such that

(i) the kth element in each row (resp. each column) is ≤ ℓ − k, where ℓ is the length of the row (resp. the column), and

(ii) the previously described graph has no cycles.

Proof.— Let us show that R_{i} satisfies the two conditions: for the first one, it is an immediate consequence of the reminder at the beginning of Section 5.5; for the second one, note that the labels in L_{i} define a total order which is compatible with the graph. Therefore, the latter has no cycle.

Conversely, let R be a labelling of D_{w} satisfying (i) and (ii). The graph having no cycle, we can find a compatible labelling of D_{w} by the numbers 1, 2, …, N = ℓ(w). This labelling is balanced by construction. Therefore, it comes from a reduced decomposition of w, and so does R. □

5.7. Remark.— In analogy with (4.2), we can express the matrix Π_{i} in terms of the bipermutation matrix described previously or, equivalently, of the associated graph. Indeed, denote by ≻ the partial order on the entries of D_{w} induced by this graph. Then, for (i, j) in D_{w}, the (i, j)-entry of Π_{i} is given by

∑ x_{w(j_{k}),w(j_{k−1})} … x_{w(j_{2}),w(j_{1})} x_{w(j_{1}),w(j_{0})},

where the sum runs over all indices such that k ≥ 1,

j = j_{0} < j_{1} < … < j_{k} = w^{−1}(i), w(j) = w(j_{0}) > w(j_{1}) > … > w(j_{k}) = i,

and (w(j_{1}), j_{0}) ≻ (w(j_{2}), j_{1}) ≻ … ≻ (w(j_{k}), j_{k−1}).

6. The poset structure of the set of commutation classes

Let w ∈ S_{n} be a permutation of length N and R(w) be the set of reduced decompositions of w. Recall that i, j ∈ R(w) belong to the same commutation class if they can be obtained from each other by a sequence of 2-moves. We denote by C(w) the set of commutation classes in R(w). Manin and Schechtman [MS] put a partial order on C(w): it is the reflexive and transitive binary relation ≤_{c} generated by

(…, i + 1, i, i + 1, …) <_{c} (…, i, i + 1, i, …)

for all 1 ≤ i ≤ N − 1. (That this order is well defined may be proved by considering the sum of the indices in the reduced decompositions.)

By [MS], [BZ], [LZ], the poset C(w) has a unique minimal element. We show that it is the commutation class α_{w} of the canonical sequence (j_{1}, …, j_{N}) of w, as defined in Section 2.

6.1. Proposition.— We have α_{w} ≤_{c} β for any element β of C(w).

Proof.— Let i = (…, i, i + 1, i, …) and j = (…, i + 1, i, i + 1, …) be reduced decompositions of w differing by a 3-move. This means that the respective pseudo-line arrangements Γ_{i} and Γ_{j} differ only locally as shown in Figure 6.1. Let k < ℓ < m be the left labels of the three pseudo-lines appearing in the parts of Γ_{i} and Γ_{j} shown in Figure 6.1. From Proposition 3.2 it is clear that all entries of the matrices Π_{i} and Π_{j} of Section 3.8 are the same, except the (k, w^{−1}(m))-entries. The pseudo-line with left label ℓ is efficient for the roof of Γ_{i} whose top is labelled by x_{km}; but the same pseudo-line is not efficient for the corresponding roof in Γ_{j}. Therefore, Π_{j} has one quadratic monomial less than Π_{i}, namely x_{kℓ} x_{ℓm}, and the only change when passing from the labelling R_{i} to the labelling R_{j} is that one label of R_{i} diminishes by 1.

Fix an element β ∈ C(w) represented by a reduced decomposition i of w. Suppose it is not in the commutation class of α_{w}. Then R_{i} ≠ 0 by Corollary 5.4. This means that the pseudo-line arrangement Γ_{i} of i has a pseudo-line L that is efficient for some roof of Γ_{i}, as in the left part of Figure 6.1. We take L such that the triangle formed by L and the slopes of the roof is not crossed by any other pseudo-line (we may call this a region of minimal area; such regions always exist when there is an efficient pseudo-line). Let us move L in order to get the configuration shown in the right part of Figure 6.1. For i, this amounts to make a 3-move (…, i, i + 1, i, …) → (…, i + 1, i, i + 1, …) as well as some 2-moves. It follows from the definition of the partial order in C(w) that the commutation class of the new reduced decomposition j we have obtained by performing these moves is smaller than the commutation class of i for <_{c}. By the above discussion, the total sum of the labels in R_{j} is less than the total sum of the labels in R_{i}. We iterate this procedure until we get a labelling R = 0 for which we apply Corollary 5.4. In this way, we have found a sequence of classes β_{0}, β_{1}, …, β_{p} such that β = β_{0} >_{c} β_{1} >_{c} … >_{c} β_{p} = α_{w}.

□

Figure 6.1. Effect of a 3-move on a pseudo-line arrangement

6.2. Remark.— As observed in the previous proof, a 3-move as in Figure 6.1 (from left to right) suppresses the monomial x_{kℓ} x_{ℓm} and all its multiples from the matrix Π_{i}. A 2-move does not change the matrix Π_{i}. Note that one can also easily describe the effect of 2and 3-moves on the matrix P_{i}(x_{1}, …, x_{N}), thereby describing the polynomial change of parametrizations of the Schubert cell C_{w}. A 2-move in position k, k + 1 of i interchanges the variables x_{k} and x_{k+1} in P_{i}(x_{1}, …, x_{N}). A 3-move s, s+1, s ↦ s+1, s, s+1 in position k − 1, k, k + 1 interchanges the variables x_{k−1} and x_{k+1} in P_{i}(x_{1}, …, x_{N}) (hence also in the balanced labelling L_{i}), and suppresses the monomial x_{k−1} x_{k+1} and its multiples.

The poset C(w) has a unique maximal element (see [BZ], [LZ], [MS]). Let us describe it.

Let w_{0} be the longest element of S_{n}, defined by w_{0}(i) = n + 1 − i for all i = 1, …, n. If i = (i_{1}, …, i_{N}) is a reduced decomposition of w, then i^{∗} = (n−i_{1}, …, n−i_{N}) is a reduced decomposition of w_{0}ww_{0}. It is clear that the map i ↦ i^{∗} from R(w) to R(w_{0}ww_{0}) is a bijection and preserves the commutation classes. It therefore induces a bijection β ↦ β^{∗} from C(w) to C(w_{0}ww_{0}). Let ω_{w} be the element of C(w) such that ω_{w}^{∗} = α_{w_{0}ww_{0}} is the minimal element of C(w_{0}ww_{0}).

6.3. Proposition.— We have β ≤_{c} ω_{w} for any element β of C(w).

Proof.— The definitions of ≤_{c} and of the involution ∗ imply β ≤_{c} γ ⇒ γ^{∗} ≤_{c} β^{∗}. Hence β ≤_{c} ω_{w} is equivalent to ω_{w}^{∗} = α_{w_{0}ww_{0}} ≤_{c} β^{∗}, which follows from Proposition 6.1. □

As an application, we characterize the fully commutative permutations, i.e., the permutations w such that the set C(w) consists of a single element (see, e.g., [BJS], [Fa], [St]). By Propositions 6.1 and 6.3, w is fully commutative if and only if α_{w} = ω_{w}.

By Theorem 1.3 the labelling R_{i} defined for any reduced decomposition i depends only on the commutation class β of i. We denote it by R_{β}.

6.4. Theorem.— For any w ∈ S_{n}, the following statements are equivalent.

(i) The permutation w is fully commutative.

(ii) The labelling R_{β} for any commutation class β ∈ C(w) consists of zeroes only. (iii) The labelling R_{ω_{w}} for the maximal element ω_{w} consists of zeroes only. (iv) There is no efficient pseudo-line in any pseudo-line arrangement of w.

Proof.— (i) ⇒ (ii): Since card C(w) = 1, we have β = α_{w}, hence R_{β} = R_{α_{w}} = 0 by Corollary 5.4.

(ii) ⇒ (iii): Clear.

(iii) ⇒ (i): In view of Theorem 1.3, R_{ω_{w}} = 0 = R_{α_{w}} implies ω_{w} = α_{w}; hence w is fully commutative.

(ii) ⇔ (iv): By Proposition 3.2, given a reduced decomposition i and its pseudo-line arrangement Γ, the quadratic terms in P_{j}(x_{1}, …, x_{n}) are in one-to-one correspondence with the efficient pseudo-lines in Γ. □

Figure 6.2 shows the poset C(w_{0}) for w_{0} = 4 3 2 1 ∈ S_{4}. Each commutation class is represented by its smallest reduced decomposition for the lexicographic order. Each 3-move is represented by an arrow going from the smaller class to the bigger class for the partial order <_{c}. The extremal classes α_{w_{0}} and ω_{w_{0}} consist of two reduced decompositions. The classes in the middle row have four reduced decompositions each. The four remaining classes are of cardinality 1 (see Figure 1 in [BZ], §9).

When w_{0} = 5 4 3 2 1 ∈ S_{5}, the set R(w_{0}) has 768 elements and C(w_{0}) has 62 elements (see [Kn] p. 35, where A_{n} denotes the number of reduced decompositions of w_{0} ∈ S_{n}, and B_{n} the number of commutation classes). Robert Bédard showed us (private communication) that the poset C(w_{0}) can be drawn on the surface of a 2-dimensional sphere S^{2}. In other words, its geometric realization is homeomorphic to S^{2}.

It would be interesting to determine the topology of the poset C(w_{0}) when w_{0} is the longest element of S_{n} for n ≥ 6.

(1, 2, 1, 3, 2, 1)

↗  ↖
(1, 2, 3, 2, 1, 2)  (2, 1, 2, 3, 2, 1)
↑  ↑
(1, 3, 2, 1, 3, 2)  (2, 1, 3, 2, 1, 3)
↑  ↑
(3, 2, 1, 2, 3, 2)  (2, 3, 2, 1, 2, 3)
↖  ↗

(3, 2, 1, 3, 2, 3)

Figure 6.2. The poset C(w_{0}) for w_{0} = 4 3 2 1 ∈ S_{4}

References

[BFZ] A. Berenstein, S. Fomin, and A. Zelevinsky, Parametrizations of canonical bases and totally positive matrices, Advances in Math. 122 (1996), 49–149.

[BZ] A. Berenstein, A. Zelevinsky, String bases for quantum groups of type A_{r}, I. M. Gelfand Seminar, 51–89, Adv. Soviet Math., 16, Part 1, Amer. Math. Soc., Providence, RI, 1993.

[BJS] S. Billey, W. Jockusch, and R. Stanley, Some combinatorial properties of Schubert polynomials, J. Alg. Combin. 2 (1993), 345–394.

[Bo] N. Bourbaki, Groupes et algèbres de Lie, Chapitre 4, Hermann, Paris, 1968.

[Co] P. M. Cohn, Free rings and their relations, London Math. Society Monographs (second edition), Academic Press, London, 1985.

[EG] P. Edelman, C. Greene, Balanced tableaux, Adv. in Math. 63 (1987), 42–99.

[Fa] S. C. K. Fan, A Hecke algebra quotient and some combinatorial applications, J. Alg. Combin. 5 (1993), 175–189.

[FGRS] S. Fomin, C. Greene, V. Reiner, and M. Shimozono, Balanced labellings and Schubert polynomials, Europ. J. Combinatorics 18 (1997), 373–389.

[FZ] S. Fomin, A. Zelevinsky, Double Bruhat cells and total positivity, preprint IRMA Strasbourg 1998/08 (http://www-irma.u-strasbg.fr/irma/publications/1998/98008.ps.gz).

[KR] C. Kassel and C. Reutenauer, Une variante à la Coxeter du groupe de Steinberg, (http://www-irma.u-strasbg.fr/irma/publications/1996/96013.dvi.gz), K-Theory (1998).

[Kn] D. E. Knuth, Axioms and hulls, Lecture Notes in Computer Science, 606, Springer-Verlag, Berlin, 1992.

[La] A. Lascoux, Polynômes de Schubert : une approche historique, Formal power series and algebraic combinatorics (Montréal, 1992), Discrete Math. 139 (1995), 303–317.

[LLT] A. Lascoux, B. Leclerc, J.-Y. Thibon, Flag varieties and the Yang-Baxter equation, Lett. Math. Phys. 40 (1997), 75–90.

[LZ] B. Leclerc, A. Zelevinsky, Quasicommuting families of quantum Plücker coordinates, Kirillov’s seminar on representation theory (ed. G. I. Olshanski), Amer. Math. Soc. Transl. Ser. 2, 181, 1997.

[Mcd] I. Macdonald, Notes on Schubert polynomials, Publications du Laboratoire de Combinatoire et d’Informatique Mathématique, vol. 6, Université du Québec à Montréal, Montréal, Canada, 1991.

[MS] Yu. I. Manin, V. V. Schechtman, Higher Bruhat orders related to the symmetric group, Funktsional. Anal. i Prilozhen. 20:2 (1986), 74–75 (English transl.: Funct. Anal. Appl. 20 (1986), 148–150).

[Mu] T. Muir, The theory of determinants in the historical order of development, vol. 1 (second edition), Macmillan and Co., London, 1906.

[Pa] P. Papi, Convex orderings and symmetric group, Comm. Algebra 22 (1994), 4089– 4094.

[Sp] T. A. Springer, Linear algebraic groups, Progr. In Math., vol. 9, Birkhäuser, Boston, 1981.

[St] J. R. Stembridge, On the fully commutative elements of Coxeter groups, J. Alg. Combin. 5 (1996), 353–385.

C.K.: Institut de Recherche Mathématique Avancée C.N.R.S. - Université Louis Pasteur 7 rue René Descartes 67084 Strasbourg Cedex, France

E-mail: kassel@math.u-strasbg.fr

Fax: +33 (0)3 88 61 90 69

A.L.: Institut Gaspard Monge C.N.R.S., Université de Marne la Vallée 5 Bd Descartes, Champs sur Marne, 77454 Marne La Vallée Cedex 2, France

E-mail: Alain.Lascoux@univ-mlv.fr — URL: http://phalanstere.univ-mlv.fr/~al

Fax: +33 (0)1 49 32 91 38

C.R.: Mathématiques Université du Québec à Montréal Montréal, CP 8888, succ. Centre Ville, Canada H3C 3P8

E-mail: reutenauer.christophe@uqam.ca

Fax: +514 987 8935

(27 mai 1998)