Chern and Yang through Ice

Alain Lascoux

CNRS, Institut Gaspard Monge, Université de Marne-la-Vallée

77454 Marne-la-Vallée Cedex, France

Center for Combinatorics, Nankai University

Tianjin 300071, P.R. China

Alain.Lascoux@univ-mlv.fr

Abstract

Characteristic classes for flags of vector bundles and Yang-Baxter coefficients are related to the flag variety for the linear group, and, ultimately, to the Ehresmann-Bruhat order on the symmetric group. This order can be interpreted in terms of an embedding of the symmetric group into the lattice of alternating-sign matrices (in bijection with square ice configurations). By decomposing the set of ice configurations into cells indexed by permutations, we are able to explicit characteristic classes, Grothendieck polynomials and Yang-Baxter coefficients from a simple weight on ice configurations.

Square-ice configurations are paved with 6 types of frozen water molecules, placed on a planar grid, shown on the following figure.

H − O − H  \begin{matrix}H \\ O \\ H \end{matrix}  \begin{aligned}H & – & O \\ & & H \end{aligned}  \begin{aligned}& & H \\ H & – & O \end{aligned}  \begin{matrix}O & – & H \\ H \end{matrix}  \begin{matrix}H \\ O & – & H \end{matrix}

Here is an example of such a configuration :

H – O H – O – H O – H O – H O – H
H  H  H  H  H
H – O – H O H – O H – O – H O – H
H  H  H  H  H
H – O H – O – H O – H O H – O – H
H  H  H  H  H
H – O H – O H – O H – O – H O – H
H  H  H  H  H
H – O H – O H – O – H O – H O – H

Ice configurations are in bijection with alternating-sign matrices (ASM in short), replacing horizontal molecules by 1, vertical molecules by -1, and the others by 0. Such matrices of 0, 1, −1 are characterized by the property that non zero entries alternate in each row and column, always starting and finishing with a 1.

Continuing with the same example, we get the following ASM :

[\begin{matrix}0 & 1 & 0 & 0 & 0 \\ 1 & −1 & 0 & 1 & 0 \\ 0 & 1 & 0 & −1 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{matrix}] .

One recovers an ice configuration from an ASM by adapting a two hundred year-old planar display, due to Rothe(1800), for permutations. His construction involves choosing a quadrant of the plane, and taking all quadrants, one gets four “Rothe diagrams” for a permutation [25]. Properly defining inversions, one gets more generally four diagrams (NW, SW, NE, SE diagrams) associated to a given ASM, as follows. Given a 0-entry in an ASM, ignore all the other zeroes. Then the current 0 is next to a 1 in its column and its row. Replace now this 0 by a box that will be attributed to one of the diagrams, depending on the orientation :

\begin{matrix}0 & → 1 & & NW & → 1 \\ ↓ & & gives & ↓ \\ 1 & & & 1 \end{matrix} , \begin{matrix}1 & & & 1 \\ ↑ & & gives & ↑ \\ 0 & → 1 & & SW & → 1 \end{matrix} ,

\begin{aligned}1 ← & 0 & & 1 ← & NE \\ & ↓ & gives & & ↓ \\ & 1 & & & 1 \end{aligned} , \begin{aligned}& 1 & & & 1 \\ & ↑ & gives & & ↑ \\ 1 ← & 0 & & 1 ← & SE \end{aligned} .

The preceding ASM gives the four diagrams :

[ \begin{matrix}□ & 1 & · & · & · \\ 1 & −1 & □ & 1 & · \\ · & 1 & · & −1 & 1 \\ · & · & □ & 1 & · \\ · & · & 1 & · & · \end{matrix} ] , [ \begin{matrix}· & 1 & · & · & · \\ 1 & −1 & · & 1 & · \\ □ & 1 & · & −1 & 1 \\ □ & □ & · & 1 & · \\ □ & □ & 1 & · & · \end{matrix} ] , [ \begin{matrix}· & 1 & □ & □ & □ \\ 1 & −1 & · & 1 & □ \\ · & 1 & □ & −1 & 1 \\ · & · & · & 1 & · \\ · & · & 1 & · & · \end{matrix} ] , [ \begin{matrix}· & 1 & · & · & · \\ 1 & −1 & · & 1 & · \\ · & 1 & · & −1 & 1 \\ · & · & · & 1 & □ \\ · & · & 1 & □ & □ \end{matrix}] .

Of course, the four types of boxes exactly correspond to the four types of hook frozen water molecules, but we shall only need the SE-type.

ASM are in turn in bijection with triangles, that is, staircase Young tableaux with weakly decreasing diagonals. One just has to read the successive rows of the matrix, from right to left, a 1 in column i meaning that the letter i appears in the tableau, a ^{−}1 meaning that it disappears, building in this way the successive columns of a tableau (from right to left), or a sequence of sets of order 1, 2, 3, . . ..

For the current ice-configuration, writing the letters directly in the ASM, a disappearance being designated with a ‘hat’, we read

[ \begin{matrix}. & 4 & . & . & . \\ 5 & ˆ4 & . & 2 & . \\ . & 4 & . & ˆ2 & 1 \\ . & . & . & 2 & . \\ . & . & 3 & . & . \end{matrix} ] ⟷ \{4\}, \{2, 5\}, \{1, 4, 5\}, \{1, 2, 4, 5\}, \{1, 2, 3, 4, 5\}

which are the columns of the following triangle (writing on its right the object that we shall really use, an ASM with SE-type zeroes indicated by a symbol o , the other zeroes being replaced by a dot) :

5 4 5 3 4 5 2 2 4 5 1 1 1 2 4 ⟷  [ \begin{matrix}· & 1 & · & · & · \\ 1 & ^{−}1 & · & 1 & · \\ · & 1 & · & −1 & 1 \\ · & · & · & 1 & o \\ · & · & 1 & o & o \end{matrix} ] .

Usual Young tableaux have weakly increasing rows, strictly decreasing columns, but the Young tableaux in bijection with ASM are characterized by the fact that they also have weakly decreasing diagonals.

Though it is straightforward to pass from one of these three types of combinatorial objects to the other two, nevertheless they show seemingly different properties. For example, one can define the supremum (resp. infimum) of a family of triangles of the same order, by just considering each of the boxes composing them, and taking the supremum (resp infimum) of the numbers contained in them.

Thus one has a lattice structure (in the sense of an ordered structure with sup and inf) on the set of triangles of a given order, but this lattice structure looks somehow mysterious on the set of ASM, or on the set of ice-configurations.

In particular, one can define the supremum of two permutation matrices, and this construction reveals some new properties of the Bruhat order on the symmetric group [23] (or more generally, on a Coxeter group, [13]).

Among triangles, there are special ones, called keys : they are those such that each of their columns is a subset of the preceding one. In other words keys are associated with a flag of subsets of {1, 2, …, n}. Reading the sequence of numbers in the order they appear, one gets a permutation.

Given a triangle t (or more generally, a Young tableau), one can associate to it a key K(t), which is minima among the keys bigger than it, and called its key. With M.P. Schützenberger, I used this notion to give combinatorial descriptions of Schubert polynomials and Demazure characters. I shall here use the corresponding construction for an ASM, i.e. canonically attach to each ASM a permutation matrix, still using the terminology key (in fact, the correspondence between ASM and triangles exchanges the two notions, but we shall not use it). At the level of ice-configurations, keys have not yet been used. It consists in getting rid, in a canonical way that we shall explain later, of all vertical molecules. Here, we need ice configurations or ASM rather than triangles, because we use the symmetry between rows and columns of an ASM, which is lost in the corresponding triangle.

Our main result (Theorem 8) shows that a simple statistic on ASM or ice configurations (easy to read also on triangles) gives the Chern classes associated to a pair of flags of vector bundles, as well as the coefficients in the expansion of Yang-Baxter elements in some deformations of the group algebra of the symmetric group. For each ASM, we shall need only its SEdiagram together with its ^{−}1 entries.

Chern classes

Chern classes are cohomology classes associated to a vector bundle V. Their first occurence (in the algebraic geometry of the end of the 19^{th} century, in special cases) can be formulated as classes representing the obstruction to extending sections of V. It is easy to see that one should in fact use two vector bundles V_{1}, V_{2}. Given a morphism between them

V_{1} ⟶^{φ} V_{2}

one uses the degeneraci loci of φ to define the Chern classes of the formal difference V_{2} − V_{1} (the usual case being when V_{1} is a trivial bundle). The generic situation is attained when V_{2} is the universal quotient bundle on a Grassmannian and when V_{1} is a trivial bundle. In that case, one has explicit varieties, the special Schubert varieties, which represent the Chern classes [6]. But as soon as one wants to describe products of Chern classes, one needs all the Schubert varieties, not only the special ones. Chern gave in [7] a description of the multiplication in the cohomology ring of a Grassmannian. The classes now correspond to a pair consisting of a (trivial) flag of vector bundles, together with the universal vector bundle on the Grassmannian.

More generally, one can take two flags of vector bundles

0 ↪ V_{1}^{1} ↪ ⋯ ↪ V_{1}^{n} ⟶^{φ} V_{2}^{n} → ⋯ → V_{2}^{1} → 0 ,

the universal situation being now realized on a flag manifold, the cohomology classes associated to the two flags still being represented by Schubert varieties in the generic case.

One can formulate this construction differently, having a variety X, and a matrix φ(x), x ∈ X, the Schubert varieties being now defined by a matrix of ranks (the ranks r[i, j] of the submatrices placed in the NW-corner; in fact, one should consider simultaneously, for any point [i, j], the four quadrants, and four rank-matrices).

It is easy to see that the rank-matrix of an invertible matrix is the matrix of ranks of a permutation matrix, and therefore the possible classes of matrices are in bijection with permutations, and with Schubert cycles in a flag manifold Flag(ℂ^{n}).

For example, the permutation σ = [2, 5, 1, 4, 3] (taking the convention that columns are numbered from right to left) gives rise to the following rank-matrix :

[ \begin{matrix}. & . & . & 1 & . \\ 1 & . & . & . & . \\ . & . & . & . & 1 \\ . & 1 & . & . & . \\ . & . & 1 & . & . \end{matrix} ] → [ \begin{matrix}0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 2 & 2 \\ 1 & 1 & 1 & 2 & 3 \\ 1 & 2 & 2 & 3 & 4 \\ 1 & 2 & 3 & 4 & 5 \end{matrix} ] .

The rank matrix, or the ranks of the different induced morphisms V_{1}^{i} → V_{2}^{j} are overdetermined, a minimal subset of rank conditions has been given by Fulton [12].

There is a simpler way to introduce the symmetric group in the theory of Chern classes. It is called the splitting principle [14], which states that given a vector bundle V on a manifold M, then on the relative flag manifold F(V) → M, the pullback of V gives a sequence of line bundles L_{1}, …, L_{n}, such that the total Chern class c(V) is equal to (1 + c_{1}(L_{1})) ⋯ (1 + c_{1}(L_{n})). Chern classes now become elementary symmetric functions in the variables x_{1} = c_{1}(L_{1}), …, x_{n} = c_{1}(L_{n}).

To handle efficiently Chern classes through this method, one first has to describe the cohomology ring of the flag manifold. This has been done by Bernstein-Gelfand-Gelfand [1] and Demazure [8]. With Marcel-Paul Schützenberger, I gave in [20] polynomial representatives of the basis of Schubert cycles in the cohomology of the flag manifold Flag(ℂ^{n}), the Schubert polynomials. They can be defined by just taking all possible images under divided differences (acting on the x_{i}’s) of the extension of the Vandermonde :

∏_{i+j≤n}(x_{i} − y_{j}) .

Schubert polynomials can also be defined by simple vanishing conditions, and occur as universal coefficients in the extension of the Newton interpolation formula to several variables [18].

Notice that, for the usual Chern classes, one specializes the y_{j}’s to 0, and thus one loses the vanishing properties which characterize the polynomials in two sets of variables.

Instead of a cohomology ring, one can use the Grothendieck ring of classes of vector bundles and define in it Chern classes corresponding to a pair of flags of vector bundles. The universal situation is still encountered with a flag manifold.

The variables are now the classes x_{1} = [L_{1}], …, x_{n} = [L_{n}] of the tautological line bundles on Flag(ℂ^{n}). The geometrical basis is constituted of the classes of the structure sheaves of Schubert varieties, the Grothendieck polynomials being their distinguished representatives.

For each permutation σ ∈ 𝔖_{n}, there is a Grothendieck polynomial G_{σ} which can be obtained from

∏_{i+j≤n}(1 − y_{i}/x_{j})

by a product of isobaric divided differences acting on the x_{i}’s [16].

The case of only one flag or of one vector bundle is obtained by specializing all the y_{j}’s to 1, but, once more, one loses then vanishing properties. One recovers cohomology classes, and Schubert polynomials, by taking leading terms of Grothendieck polynomials.

Grothendieck polynomials can also be obtained through a generating function in the 0-Hecke algebra [11], or through a noncommutative Schubert calculus [24].

We shall use a third method to obtain Grothendieck polynomials, which decomposes them, without cancellations, into smaller polynomials.

Given a permutation σ ∈ 𝔖_{n}, which is not the identity, let r = max(i : σ_{i} > σ_{i+1}). Let now k = max(σ_{j}, j > r, σ_{j} < σ_{r}), and ν = (k, σ_{r}) σ, where (k, σ_{r}) is the transposition of the two values k, σ_{r}.

Let ν^{(1)}, …, ν^{(p)} be the all the permutations η such that ℓ(η)) = ℓ(ν) + 1, η ν^{−1} is equal to transposition (j, k), j < k (these are the permutations occuring in the transition for Schubert polynomial, [20, 25]).

Reformulating Proposition 3 of [17] (it adapts instantly to the case of two sets of variables that we need here), one has :

Proposition 1 Given a permutation σ ∈ 𝔖_{n}, let B(σ) be the (boolean) sublattice of 𝔖_{n} (considered as embedded into the lattice of ASM of order n, [23]), with generators the permutations ν^{(1)}, …, ν^{(p)}, and minimum element ν. Then

(G_{ν} − G_{σ}) \frac{y_{k}}{x_{j}} = ∑_{η∈B(σ)}(−1)^{ℓ(η)−ℓ(ν)}G_{η} .

For example, for σ = [6, 4, 8, 3, 1, 7, 2, 5], one has r = 6, k = 5, and the boolean lattice B(σ) is

[figure: [65843127]; [65841327]; [65834127]; [64853127]; [65831427]; [64851327]; [64835127]; [64831527]]

furnishing the following recursion between Grothendieck polynomials :

(G_{64831527} − G_{64831725}) \frac{y_{5}}{x_{6}} = G_{64831527} − G_{65831427} − G_{64851327} − G_{64835127}

+ G_{65841327} + G_{65834127} + G_{64853127} − G_{65843127} .

Yang-Baxter coefficients

The Bruhat order on the symmetric group is usually defined by taking subwords of reduced decompositions. This amounts developing, in the group algebra of the symmetric group, expressions of the type (1+s_{1})(1+s_{2})(1+s_{1}), with s_{i} = simple transposition (transposition of i, i ^{+}1). However, since (1 + s_{1})(1 + s_{2})(1 + s_{1}) ≠ (1 + s_{2})(1 + s_{1})(1 + s_{2}), this definition is not satisfactory, and one must put weights to make it canonical, e.g.

(1 + s_{1})(1 + 2s_{2})(1 + s_{1}) = (1 + s_{2})(1 + 2s_{1})(1 + s_{2}) .

The general rule to write weights is due to Yang. Yang’s original motivation for introducing the Yang-Baxter equation [28] was the n-body problem on a circle with Hamiltonian

H(y) = − ∑_{i=1}^{n} \frac{∂^{2}}{∂y_{i}^{2}} + 2c ∑_{i<j} δ(y_{i} − y_{j}) ,

where δ is the Dirac distribution. The problem was to solve the Schrödinger equation

H(y)ψ(y) = Eψ(y)

with periodic boundary conditions.

Yang looked for solutions of the form

ψ(y) = ∑_{τ∈𝔖_{n}} θ(y^{τ}) ∑_{σ∈𝔖_{n}} A_{σ}(τ)e^{ix^{σ}·y^{τ}}

where 𝔖_{n} is the symmetric group, x = (x_{1}, …, x_{n}) ∈ ℂ^{n} is the vector of spectral parameters, x^{σ} := (x_{σ_{1}}, …, x_{σ_{n}}), and θ is the characteristic function of the domain y_{1} < y_{2} < … < y_{n}. The unknown coefficients A_{σ}(τ) form an n! × n! matrix, and it is convenient to regard each A_{σ} as a function on the symmetric group, or equivalently as an element of its group algebra.

Yang’s construction can be interpreted as follows. Given any sequence of spectral parameters x_{1}, …, x_{n}, there exists a linear basis {𝕐_{σ}, σ ∈ 𝔖_{n}}, the Yang-Baxter basis, of ℂ[x_{1}, …, x_{n}][𝔖_{n}], which is defined through the following recursions :

𝕐_{σs_{i}} = 𝕐_{σ} (1 + (x_{σ_{i+1}} − x_{σ_{i}}) s_{i}) , ℓ(σs_{i}) > ℓ(σ).  (1)

The validity of such a definition is insured by the Yang-Baxter relations :

(1 + αs_{i}) (1 + (α + β)s_{i+1}) (1 + βs_{i}) = (1 + βs_{i+1}) (1 + (α + β)s_{i}) (1 + αs_{i+1}) . (2)

Now, Yang’s coefficients are the coefficients of the expansion of Yang-Baxter elements in the basis of permutations.

It is interesting to note that Young’s construction of irreducible representations of the symmetric group can be interpreted as giving a solution to the Yang-Baxter equation, the spectral parameters being the distance of entries, in a Young tableau, to the main diagonal (these distances are called contents). Jucys [15], then Cherednik [5], have shown moreover that Young’s natural idempotents are limits of some Yang-Baxter elements when spectral parameters are specialized to the contents of a Young tableau.

The same construction is valid for the different deformations of ℂ[𝔖_{n}], that is, for the algebras generated by T_{1}, …, T_{n−1} satisfying the braid relations, together with a Hecke relation (with fixed q_{1}, q_{2}) :

(T_{i} − q_{1}) (T_{i} − q_{2}) = 0 .  (3)

The two cases relevant to geometry (for the cohomology ring, and the Grothendieck ring respectively) are

(T_{i}^{N il})^{2} = 0 Nil-Hecke algebra
(T_{i}^{0H})^{2} = −T_{i}^{0H}  0-Hecke algebra

Expanding the corresponding Yang-Baxter elements 𝕐_{σ}^{N il} and 𝕐_{σ}^{0H} one gets coefficients :

𝕐_{σ}^{N il} = ∑_{τ∈𝔖_{n}} c_{σ}^{τ} T_{τ}^{N il}  (4)
𝕐_{σ}^{0H} = ∑_{τ∈𝔖_{n}} g_{σ}^{τ} T_{τ}^{0H}  (5)

The link with the preceding section is provided by the following property [19] :

Proposition 2 The Yang-Baxter coefficients c_{σ}^{τ} and g_{σ}^{τ} are specializations of Schubert and Grothendieck polynomials :

c_{σ}^{τ} = 𝕏(x^{τ}, x) & g_{σ}^{τ} = 𝔾(x^{τ}, x) ,  (6)

denoting by x^{τ} the reordering x_{τ_{1}}, …,_{,} x_{τ_{n}} of the spectral parameters.

Notice that recursions by divided differences, for Schubert and Grothendieck polynomials, are hidden when one specializes one set of parameters to a permutation of the other; Schubert and Grothendieck polynomials are easier to compute than expansions of Yang-Baxter elements.

Keys and weights of ASM

Ehresmann [10] gave a cellular decomposition of the flag manifold Flag(ℂ^{n}), from which he deduced the homology ring of it. His construction amounts to say that the set of complete flags of a vector space with a basis {e_{1}, …, e_{n}} can be partitionned into cells, each of which contains a coordinate flag, that is a complete flag of subsets of {e_{1}, …, e_{n}} (Ehresmann was not using permutations to index cells, but flags of sets, and gave in this set-up the first definition of the Bruhat order on the symmetric group).

We chose matrices as basic objects, having already indicated that each ASM can be considered as a sequence of sets of respective orders 1, 2, 3, . . .. The case of a permutation σ is when one takes as a sequence the complete flag of sets

{e_{σ_{1}}} ⊂ {e_{σ_{1}}, e_{σ_{2}}} ⊂ ⋯ ⊂ {e_{σ_{1}}, …, e_{σ_{n}}} .

For the order 3, there is only one ASM which is not a permutation matrix :

[ \begin{matrix}0 & 1 & 0 \\ 1 & −1 & 1 \\ 0 & 1 & 0 \end{matrix} ] ↔ sequence of sets \{e_{2}\}, \{e_{1}, e_{3}\}, \{e_{1}, e_{2}, e_{3}\} .

Given a point ■ in ℤ × ℤ, it determines a SE-quadrant (all the points South and East of it, including horizontal and vertical, minus ■ itself). Let us call neighbours of ■ in an ASM the entries 1 in its SE-quadrant such that the submatrix (on consecutive rows and columns) \begin{matrix}■ & ··· & · \\ · & ··· & 1 \end{matrix} has only 0 entries, outside the two pointed vertices.

The domain covered by all the submatrices associated to the neighbours of ■ is a Ferrers’ diagram [26], with 1’s at its corners, 0’s elsewhere (apart from ■).

Inflating a Ferrers’ diagram consists in replacing it by a bigger diagram, with inner corners where the original corners were :

\begin{matrix}■ & ♡ & ♡ & ♡ & ♡ & ♡ & · & · \\ ♡ & ♡ & ♡ & · & · & · & · & · \\ ♡ & ♡ & ♡ & · & · & · & · & · \\ ♡ & · & · & · & · & · & · & · \\ ♡ & · & · & · & · & · & · & · \end{matrix} ⟶^{inflation}  \begin{matrix}■ & ♡ & ♡ & ♡ & ♡ & ♡ & · & · \\ ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & · & · \\ ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & · & · \\ ♡ & ♡ & ♡ & · & · & · & · & · \\ ♡ & ♡ & ♡ & · & · & · & · & · \end{matrix} .

The original Ferrers’ diagram, as well as its image under inflation, covers the places where ♡ is written (apart from ■).

An entry ^{−}1 in an ASM is removable if its SE-quadrant contains no other −1 entry. Removing this ^{−}1 consists in inflating the Ferrers’diagram it determines, filling it with 0’s, except at its corners when one puts 1’s.

\begin{matrix}^{−}1 & ♡ & ♡ & ♡ & ♡ & 1 & · & · \\ ♡ & ♡ & ♡ & 0 & 0 & 0 & · & · \\ ♡ & ♡ & 1 & 0 & 0 & 0 & · & · \\ ♡ & 0 & 0 & · & · & · & · & · \\ 1 & 0 & 0 & · & · & · & · & · \end{matrix} ⟶^{Removing−1}  \begin{matrix}♡ & ♡ & ♡ & ♡ & ♡ & ♡ & · & · \\ ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & · & · \\ ♡ & ♡ & ♡ & ♡ & ♡ & 1 & · & · \\ ♡ & ♡ & ♡ & · & · & · & · & · \\ ♡ & ♡ & 1 & · & · & · & · & · \end{matrix} .

The original Ferrers’ diagram, as well as its image under inflation, covers the places where ±1 or ♡ (which is a zero entry) are written. It is clear that this operation gives a new ASM.

One checks :

Lemma 3 Given an ASM, and two removable ^{−}1, then the ASM obtained by removing the two ^{−}1 is independent of the order in which one removes them.

Corollary 4 Removing successively all ^{−}1’s in an ASM 𝔞𝔰𝔪 produces a unique permutation matrix 𝔎𝔢𝔶(𝔞𝔰𝔪) called its key.

Here is an example of a sequence producing a key (0 entries are written with a dot).

[ \begin{matrix}· & · & · & · & · & 1 & · & · \\ · & 1 & · & · & · & · & · & · \\ · & · & · & 1 & · & −1 & · & 1 \\ 1 & −1 & · & · & 1 & · & · & · \\ · & · & 1 & −1 & · & · & 1 & · \\ · & 1 & · & · & · & · & · & · \\ · & · & · & · & · & 1 & · & · \\ · & · & · & 1 & · & · & · & · \end{matrix} ] , [ \begin{matrix}· & · & · & · & · & 1 & · & · \\ · & 1 & · & · & · & · & · & · \\ · & · & · & 1 & · & · & · & · \\ 1 & −1 & · & · & 1 & · & · & · \\ · & · & 1 & −1 & · & · & · & 1 \\ · & 1 & · & · & · & · & · & · \\ · & · & · & · & · & · & 1 & · \\ · & · & · & 1 & · & · & · & · \end{matrix} ] , [ \begin{matrix}· & · & · & · & · & 1 & · & · \\ · & 1 & · & · & · & · & · & · \\ · & · & · & 1 & · & · & · & · \\ 1 & −1 & · & · & 1 & · & · & · \\ · & · & 1 & · & · & · & · & · \\ · & 1 & · & · & · & · & · & · \\ · & · & · & · & · & · & · & 1 \\ · & · & · & · & · & · & 1 & · \end{matrix} ] , [ \begin{matrix}· & · & · & · & · & 1 & · & · \\ · & 1 & · & · & · & · & · & · \\ · & · & · & 1 & · & · & · & · \\ 1 & · & · & · & · & · & · & · \\ · & · & 1 & · & · & · & · & · \\ · & · & · & · & 1 & · & · & · \\ · & · & · & · & · & · & · & 1 \\ · & · & · & · & · & · & 1 & · \end{matrix} ] .

Given a permutation matrix, let us call pivot the position occupied by the top box of the leftmost column of its SE-diagram. The pivot of an ASM is the pivot of its key. Let us call top of an ASM the 2×2 submatrix containing the pivot, and the two entries 1 in the same column, above, and in the same row, on the left.

Lemma 5 In an ASM there is no ^{−}1 entry in a column left of the pivot, nor in the same column above it.

Proof. If 𝔞𝔰𝔪 is not a permutation matrix, remove all ^{−}1 from right to left, from bottom to top, except the last one. The two entries 1 in the top of −1 : \begin{matrix}0 & 1 \\ 1 & −1 \end{matrix} will remain 1’s in 𝔎𝔢𝔶(𝔞𝔰𝔪). Therefore, the place occupied by this −1 is a box of the SE-diagram of 𝔎𝔢𝔶(𝔞𝔰𝔪), and satisfies the geographical constraints fixed by the lemma with respect to the pivot. QED

This remark allows us to define transition on ASM.

Definition 6 For each ASM 𝔞𝔰𝔪, let ■ be its pivot. Let 𝔗𝔯𝔞𝔫𝔰(𝔞𝔰𝔪) be the matrix obtained from 𝔞𝔰𝔪 by transforming its top as follows. If the pivot contains a 0, change its top

[ ⋮ ⋮_{1 ··· ■}^{0 ··· 1}]  into  [ ⋮ ⋮_{0 ··· 1}^{1 ··· 0} ] .

If it contains a ^{−}1, then change

[ ⋮ ⋮_{1 ··· ■}^{0 ··· 1}]  into  [ ⋮ ⋮_{0 ··· 0}^{1 ··· 0} ]

(the pivot cannot contain a 1).

Proposition 7 Given a permutation σ, the image under 𝔗𝔯𝔞𝔫𝔰 of ASM(σ) is the union of all ASM(η) : η ∈ B(σ).

Proof. Let 𝔞𝔰𝔪 ∈ ASM(σ). The neighbours of its pivot are not neighbours of any ^{−}1 not located in the pivot. Therefore, one can remove all ^{−}1 located outside the pivot and restrict to ASM having at most one ^{−}1, located in the pivot.

If there is a 0 in the pivot, then 𝔞𝔰𝔪 is a permutation matrix (= σ), and its image under a transition is K(ν), where ν is the minimum element of B(σ). If there is a ^{−}1, removing it gives K(σ), and this means that inflating the Ferrrers’diagram of ■ in 𝔞𝔰𝔪 gives the Ferrrers’ diagram of ■ in K(σ). Each pair of consecutive neighbours of ■ in 𝔞𝔰𝔪 gives a neighbour of ■ in K(σ), and conversely, the neighbours of ■ in 𝔞𝔰𝔪 are in bijection with a subset of neighbours of ■ in K(σ), and the inflated Ferrers’ diagram is a subset of the Ferrers’ diagram of ■ in K(σ) (we have framed the 1’s giving back 𝔞𝔰𝔪 from K(σ), and restricted matrices to their relevant part) :

𝔞𝔰𝔪 = \begin{matrix}■ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & 1 \\ ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & 0 & 0 & 0 \\ ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & 1 & 0 & 0 & 0 \\ ♡ & ♡ & 0 & 0 & 0 & 0 & 0 \\ ♡ & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & · & · \\ 0 & 0 & · & · \\ 0 & 0 & · & 1 \\ 0 & 0 \\ 1 & 0 \end{matrix} , K(σ) = \begin{matrix}■ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ \\ ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ \\ ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & 1 \\ ♡ & ♡ & ♡ & ♡ & ♡ & ♡ & ♡ \\ ♡ & ♡ & ♡ & ♡ & ♡ & 1 \\ ♡ & ♡ & · & · \\ ♡ & ♡ & · & · \\ ♡ & ♡ & · & 1 \\ ♡ & ♡ \\ ♡ & 1 \end{matrix}

On the other hand, the generators of the boolean lattice B(σ) can be described on K(σ), rather than using the formulation of Proposition 1. Reading from left to right the position of the 1’s, one has to find the first column where there is an increase (noting c the entry 1 of this column), take in its SW-quadrant the upper 1 (noted b), and look at all 1’s in the SE-quadrant of c such that the rectangle with corner a, and edges on the vertical of c and the horizontal of b only contains 0’s, apart from a. In other words, the NW corner of the rectangle is the pivot, and a is a neighbour of it. Then exchanging b, c, a into c, a, b produces a new permutation which is a generator of B(σ), and conversely every generator is obtained in this manner [22].

\begin{aligned}0 & · & · & c \\ · & & & · \\ · & & & · \\ b & · & · & ■ & 0 & 0 & 0 & 0 \\ & & & 0 & 0 & 0 & 0 & 0 \\ & & & 0 & 0 & 0 & 0 & a \end{aligned}  ⟶  \begin{aligned}c & · & · & 0 \\ · & & & · \\ · & & & · \\ 0 & · & · & ■ & 0 & 0 & 0 & b \\ & & & 0 & 0 & 0 & 0 & 0 \\ & & & a & 0 & 0 & 0 & 0 \end{aligned} .

The minimum element of B(σ) is obtained by passing from c, b to b, c :

⋮ ⋮_{b ··· ■}^{0 ··· c} ↦ ⋮ ⋮_{0 ··· b}^{c ··· 0} . QED

Main property

Let us now introduce parameters x_{1}, …, x_{n}, y_{1}, …, y_{n}. Given an ASM, attribute to each entry 0 belonging to the SE-diagram the weight \frac{y_{i}}{x_{j}} − 1, to each entry ^{−}1 the weight \frac{y_{i}}{x_{j}}, where i, j are the coordinates (and the weight 1 to all other entries). The weight ϕ(𝔞𝔰𝔪) of an ASM is the product of all the weights of its entries.

I can now explain how to obtain Yang-Baxter coefficients, Grothendieck and Schubert polynomials from enumeration of square ice-configurations. Since Schubert polynomials and Yang-Baxter coefficients are instantly deduced from Grothendieck polynomials, it is sufficient to state the property in terms of Grothendieck polynomials only.

Theorem 8 Given an integer n, and a permutation σ ∈ 𝔖_{n}, let ω = [n, …, 1] ∈ 𝔖_{n}. Then the Grothendieck polynomial G_{σ} satisfies

(−1)^{ℓ(ωσ)}G_{σ} = ∑ ϕ(𝔞𝔰𝔪)

with the sum over all ASM with key equal to σ^{−1}ω.

Proof. The generators of the lattice B(σ) are obtained by taking the pivot, one of its neighbour, and transforming the submatrix of order 3 of the key

[ \begin{matrix}0 & ··· & 1 & ··· & 0 \\ ⋮ & & ⋮ & & ⋮ \\ 1 & ··· & ■ & ··· & 0 \\ ⋮ & & ⋮ & & ⋮ \\ 0 & ··· & 0 & ··· & 1 \end{matrix} ]  into  [ \begin{matrix}1 & ··· & 0 & ··· & 0 \\ ⋮ & & ⋮ & & ⋮ \\ 0 & ··· & ■ & ··· & 1 \\ ⋮ & & ⋮ & & ⋮ \\ 0 & ··· & 1 & ··· & 0 \end{matrix} ] .

Let the pivot of σ have coordinates r, k.

The effect of a transition on the weight of an 𝔞𝔰𝔪 with key σ, is just to suppress the factor y_{k}/x_{r}, if there is a^{−}1 at the pivot, or to suppress the factor y_{k}/x_{r} − 1, if there is a 0 at the pivot. Therefore, thanks to Proposition 7, the sum ∑_{𝔞𝔰𝔪:𝔎𝔢𝔶(𝔞𝔰𝔪)=σ} ϕ(𝔞𝔰𝔪) satisfies the same recursion, under transition, as (−1)^{ℓ(ωσ)}G_{σ}. QED

For example, the Grothendieck polynomial of index [4, 2, 1, 5, 3] is given by the four ASM, with key equal to [4, 1, 5, 2, 3], having the following weights (remember that columns are numbered from right to left; only SE-type 0’s are indicated):

5 4 5 3 4 5 2 2 2 4 1 1 1 1 4 [\begin{matrix}. & 1 & . & . & . \\ . & . & . & . & 1 \\ 1 & ^{−}1 & . & 1 & o \\ . & 1 & . & o & o \\ . & . & 1 & o & o \end{matrix} ] \frac{y_{3}}{x_{4}} (\frac{y_{1}}{x_{2}} ^{−}1)(\frac{y_{2}}{x_{2}} ^{−}1)(\frac{y_{1}}{x_{1}} ^{−}1)(\frac{y_{2}}{x_{1}} ^{−}1)(\frac{y_{3}}{x_{1}} ^{−}1)

5 4 5 3 3 5 2 2 2 4 1 1 1 1 4 [\begin{matrix}. & 1 & . & . & . \\ . & . & . & . & 1 \\ 1 & ^{−}1 & . & 1 & o \\ . & . & 1 & o & o \\ . & 1 & o & o & o \end{matrix} ] \frac{y_{3}}{x_{4}} (\frac{y_{1}}{x_{3}} ^{−}1)(\frac{y_{1}}{x_{2}} ^{−}1)(\frac{y_{2}}{x_{2}} ^{−}1)(\frac{y_{1}}{x_{1}} ^{−}1)(\frac{y_{2}}{x_{1}} ^{−}1)(\frac{y_{3}}{x_{1}} ^{−}1)

5 4 5 3 4 5 2 2 4 4 1 1 1 1 4 (𝔎𝔢𝔶) [\begin{matrix}. & 1 & . & . & . \\ . & . & . & . & 1 \\ 1 & o & . & . & o \\ . & . & . & 1 & o \\ . & . & 1 & o & o \end{matrix} ] (\frac{y_{1}}{x_{2}} ^{−}1)(\frac{y_{3}}{x_{4}} ^{−}1)(\frac{y_{1}}{x_{1}} ^{−}1)(\frac{y_{2}}{x_{1}} ^{−}1)(\frac{y_{3}}{x_{1}} ^{−}1)

5 4 5 3 3 5 2 2 3 4 1 1 1 1 4 [\begin{matrix}. & 1 & . & . & . \\ . & . & . & . & 1 \\ 1 & ^{−}1 & 1 & . & o \\ . & . & . & 1 & o \\ . & 1 & o & o & o \end{matrix} ] \frac{y_{3}}{x_{4}} (\frac{y_{1}}{x_{3}} ^{−}1)(\frac{y_{1}}{x_{2}} ^{−}1)(\frac{y_{1}}{x_{1}} ^{−}1)(\frac{y_{2}}{x_{1}} ^{−}1)(\frac{y_{3}}{x_{1}} ^{−}1)

Therefore, the Grothendieck polynomial G_{42153} is equal to

G_{42153} = (1^{−} \frac{y_{1}}{x_{2}} )(1^{−} \frac{y_{1}}{x_{1}} )(1^{−} \frac{y_{2}}{x_{1}} )(1^{−} \frac{y_{3}}{x_{1}} )(1^{−} \frac{y_{1}y_{2}y_{3}}{x_{2}x_{3}x_{4}} ) .

Since the ^{−}1’s are located at the pivot, the image under transition of the four matrices are permutation matrices, and one has

(G_{42135} − G_{42153})\frac{y_{3}}{x_{4}} = G_{42135} − G_{43125} − G_{42315} + G_{43215} .

There exists a Cauchy kernel for Grothendieck polynomials, which generalizes the Cauchy kernel for Schur functions. Rewriting Theorem 2.8 and Lemma 2.9 of [16], the existence of such kernel amounts to the following identity involving three sets of variables {x_{1}, …, x_{n}}, {y_{1}, …, y_{n}}, {z_{1}, …, z_{n}} (writing σω for [σ_{n}, …, σ_{1}], σ ∈ 𝔖_{n}) :

y_{1}^{n−1} ⋯ y_{n}^{0} ∏_{i+j≤n} (\frac{1}{z_{i}} − \frac{1}{x_{j}} ) = ∑_{σ∈𝔖_{n}}(−1)^{ℓ(σ)}G_{σ}(x, y) G_{σω}(z, y) . (7)

The same kernel also expands in terms of Schubert polynomials. Using Theorem 8, one can write the kernel as a statistics on pairs of ASM.

Bousquet-Mélou and Habsieger [2] give a sum over ASM, which in our terms, states that

∑_{σ∈𝔖_{n}}(−1)^{ℓ(σ)}G_{σ}(x, 1) = x_{1}^{n−1}x_{2}^{n−2} ⋯ x_{n}^{0} ,

and is obtained by specializing Eq.7.

Their summation involves counting the number of SE-zeroes in each column of an ASM, as well as the ^{−}1. Robbins and Rumsey [27] express the q-Vandermonde ∏_{1≤i<j≤n}(x_{i} + qx_{j}) through a summation on the ASM of order n, this time recording the SW-zeroes as well. Chapman [4], refines their construction and gives a combinatorial description of ∏_{1≤i<j≤n}(x_{i} + y_{j}).

References

[1] I.N. Bernstein, I.M. Gelfand and S.I. Gelfand, Schubert cells and the cohomology of the spaces G/P, Russian Math. Surveys 28 (1973), 1-26.

[2] M. Bousquet-Mélou, L. Habsieger, Sur les matrices à signes alternants, Discrete Math. 139 (1995) 55-72.

[3] D. Bressoud, Proofs and Confirmations: the Story of Alternating Sign Matrix Conjecture, Cambridge University Press (1999).

[4] R. Chapman, Alternating sign matrices and tournaments, xxx0008029 (2000).

[5] I.V. Cherednik, A new interpretation of Gelfand-Tzetlin bases, Duke. Math. J. 54 (1987), 563-577.

[6] S.S. Chern, Classes of Hermitian manifolds, Annals of Math. 47 (1946) 85-121.

[7] S.S. Chern, On the multiplication in the characteristic ring of a sphere, Annals of Math. 49 (1948) 362-372.

[8] M. Demazure, Invariants symétriques entiers des groupes de Weyl et torsion, Invent. Math 21 (1973), 287-301.

[9] G. Duchamp, D. Krob, A. Lascoux, B. Leclerc, T. Scharf and J.-Y. Thibon, Euler-Poincaré characteristic and polynomial representations of Iwahori-Hecke algebras, Publ. RIMS Kyoto 31 (1995), 179-201.

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

[11] S. Fomin and A.N. Kirillov, Grothendieck polynomials and the Yang-Baxter equation, Proceedings of FPSAC’94, DIMACS, Rutgers University, 183–189.

[12] W. Fulton, Flags, Schubert polynomials, degeneracy loci, and determinantal formulas, Duke Math. J. 65 (1991), 381-420.

[13] R. Geck, S. Kim, Bases for the Bruhat-Chevalley order on all finite Coxeter groups, J. of Algebra 197 (1997) 278–310.

[14] F. Hirzebruch, Topological methods in algebraic geometry, 3rd ed., Springer, 1978.

[15] A. Jucys, Symmetric polynomials and the center of the symmetric group rings, Rep. Math. Phys. 5 (1974) 107–112.

[16] A. Lascoux, Anneau de Grothendieck de la variété de drapeaux, in “The Grothendieck Festchrift”, vol III, Birkhäuser (1990) 1–34.

[17] A. Lascoux, Transition on Grothendieck polynomials, Proc. Nagoya Workshop on Physics and Combinatorics (2000), ed. A Kirillov, N. Liskova, World Scientific (2001) 164–179.

[18] A. Lascoux, The Newton interpolation formula, with more variables, Newton Institute preprint (2001).

[19] A. Lascoux, B. Leclerc and J.Y. Thibon, Flag Varieties and the Yang-Baxter Equation , Letters in Math. Phys., 40 (1997) 75–90.

[20] A. Lascoux and M.P. Schützenberger, Polynômes de Schubert, C.R. Acad. Sci. Paris 294 (1982), 447-450.

[21] A. Lascoux and M.P. Schützenberger, Structure de Hopf de l’anneau de cohomologie et de l’anneau de Grothendieck d’une variété de drapeaux, C.R. Acad. Sci. Paris 295 (1982) 629–633.

[22] A. Lascoux and M.P. Schützenberger, Schubert polynomials and the Littlewood-Richardson rule, Letters in Math.Phys. 10(1985) 111– 124.

[23] A. Lascoux and M.P. Schützenberger, Treillis et bases des groupes de Coxeter, Electronic J. of Comb. 3 # R27 (1996).

[24] C. Lenart, Noncommutative Schubert calculus and Grothendieck polynomials, Adv. in Math.143 (1999) 159–183.

[25] I. G. Macdonald, Notes on Schubert polynomials LACIM, Publi. Université Montréal, (1991).

[26] I. G. Macdonald, Symmetric functions and Hall polynomials. Oxford University Press, Oxford, 2nd edition (1995).

[27] D.P. Robbins, H. Rumsey, Determinants and Alternating sign matrices, Adv. in Maths (1986) 169–184.

[28] C.N. Yang, Some exact results for the many-body problem in one dimension with repulsive delta-function interaction, Phys. Rev. Lett. 19 (1967), 1312– 1315.