% ChernYang.tex  version janvier 02  Corr. 27Fev02; figure,biblio 12Juin02
%                                    COR 26 nov 02
\documentclass[a4paper,12pt]{article}
\usepackage{amsmath,amsfonts,amssymb,amscd}

\long\def\bee#1\ee{\begin{equation}#1\end{equation}}
\def\be{\begin{equation}}

\def\s{\scriptstyle }
\def\a{\alpha}
\def\b{\beta}
\def\ss{\sigma}
\def\d{\partial}
\def\x{\mathbf x}
\def\y{\mathbf y}
\def\Sym{{\mathfrak Sym}}
\def\C{{\mathbb C}}
\def\Y{{\mathbb Y}}
\def\X{{\mathbb X}}
\def\Z{{\mathbb Z}}
\def\G{{\mathbb G}}
\def\cB{\mathcal B}
\def\hh{\heartsuit}

\def\moins{\raise 1pt\hbox{$\s -$}}
\def\plus{\raise 1pt \hbox{ $\s +$}}
\def\Trans{\mathfrak{Trans}}
\def\asm{\mathfrak{asm}}
\def\ASM{\mathcal A\!\mathcal S\!\mathcal M}
\def\S{{\mathfrak S}}
\def\key{{\mathfrak{Key}}}

\def\qed{\hfill QED}
\def\proof{\noindent{\it Proof.}\ }
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{Def}[theorem]{Definition}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begingroup
\catcode`\@=11
\gdef\petitematrice#1{\null\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\thinspace  \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}}
\endgroup

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newdimen\Squaresize \Squaresize=14pt
\newdimen\Thickness \Thickness=0.7pt

\def\Square#1{\hbox{\vrule width \Thickness
   \vbox to \Squaresize{\hrule height \Thickness\vss
      \hbox to \Squaresize{\hss#1\hss}
   \vss\hrule height\Thickness}
\unskip\vrule width \Thickness}
\kern-\Thickness}

\def\Vsquare#1{\vbox{\Square{$#1$}}\kern-\Thickness}
\def\blk{\omit\hskip\Squaresize}

\def\young#1{
\vbox{\smallskip\offinterlineskip
\halign{&\Vsquare{##}\cr #1}}}

\def\trait{\vrule height 6pt depth 0pt width .4pt}
\def\tir{$--$}

\newsavebox{\OO}
\sbox{\OO}{\vrule height 3.2pt depth -2.4pt width 5pt o \kern -7.6pt%
 {\hbox{\vrule height 11pt depth -5.8pt width 0.8pt}}\kern 7pt }


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\bf Chern and Yang through Ice}
\author{\small Alain Lascoux\\
\small CNRS, Institut Gaspard Monge, Universit\'e de Marne-la-Vall\'ee\\
\small 77454 Marne-la-Vall\'ee Cedex, France\\
\small Center for Combinatorics, Nankai University\\
\small Tianjin 300071, P.R. China\\
\small  Alain.Lascoux@univ-mlv.fr }
\date{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle

\begin{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.
\end{abstract}

\emph{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\qquad
\petitematrice{H\cr
\trait\cr
O\cr
\trait\cr
H\cr}\qquad
\petitematrice{H&$--$&O\cr
&&\trait\cr
&&H\cr}\qquad
\petitematrice{&&H\cr
&&\trait\cr
H&$--$&O\cr
}\qquad
\petitematrice{O&$--$&H\cr
\trait\cr
H\cr}\qquad
\petitematrice{H\cr
\trait\cr
O&$--$&H\cr}
$$

Here is an example of such a configuration~:
$$   % figure orginale avec \petitematrice
\begin{smallmatrix}H&\tir&O&&H&\tir&O&\tir&H&&O&\tir
&H&&O&\tir&H&&O&\tir&H\cr
&&\trait&&&&&&&&\trait&&&&\trait&&&&\trait&&\cr
&&H&&&&H&&&&H&&&&H&&&&H&&\cr
&&&&&&\trait&&&&&&&&&&&\cr
H&\tir&O&\tir&H&&O&&H&\tir&O&&H&\tir&O&\tir&H&&O&\tir&H\cr
&&&&&&\trait&&&&\trait&&&&&&&&\trait&&\cr
&&H&&&&H&&&&H&&&&H&&&&H&&\cr
&&\trait&&&&&&&&&&&&\trait&&&&&&\cr
H&\tir&O&&H&\tir&O&\tir&H&&O&\tir&H&&O&&H&\tir&O&\tir&H\cr
&&&&&&&&&&\trait&&&&\trait&&&&&&\cr
&&H&&&&H&&&&H&&&&H&&&&H&&\cr
&&\trait&&&&\trait&&&&&&&&&&&&\trait&&\cr
H&\tir&O&&H&\tir&O&&H&\tir&O&&H&\tir&O&\tir&H&&O&\tir&H\cr
&&&&&&&&&&\trait&&&&&&&&&&\cr
&&H&&&&H&&&&H&&&&H&&&&H&&\cr
&&\trait&&&&\trait&&&&&&&&\trait&&&&\trait&&\cr
H&\tir&O&&H&\tir&O&&H&\tir&O&\tir
&H&&O&\tir&H&&O&\tir&H\cr\end{smallmatrix}
$$
Ice configurations  are in bijection with 
\emph{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{bmatrix}
 0&1&0&0&0\cr 1&-1&0&1&0\cr 0&1&0&-1&1\cr 0&0&0&1&0\cr 0&0&1&0&0 
\end{bmatrix} \ .$$

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
\cite{MacSchub}.
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{multline*}
 \begin{array}{rlccl} 0 &\to 1& & \framebox{\small NW} &\to 1 \\
                        \downarrow & &\ \text{gives}\  &\downarrow\\
                          1        &&             &  1
 \end{array}\quad ,\quad 
\begin{array}{rlccl}  1&&& 1\\ \uparrow  & &\ \text{gives}\ &\uparrow \\ 
 0 &\to 1& & \framebox{\small SW} &\to 1 
 \end{array}\quad ,  \\[3pt]
\begin{array}{rlcrc} 1\leftarrow &0& &1\leftarrow & \framebox{\small NE} \\
                        &\downarrow  &\ \text{gives}\ &&\downarrow\\
                          &1     &&  &  1
 \end{array}\quad ,\quad 
\begin{array}{rlcrc} &1     &&  &  1\\
  &\uparrow  &\  \text{gives}\ &&\uparrow\\
   1\leftarrow &0& &1\leftarrow & \framebox{\small SE}
 \end{array}\ .
\end{multline*}
The preceding ASM gives the four diagrams~:
$$\left[ \begin{smallmatrix} 
   \square&1&\cdot&\cdot&\cdot\cr 1& \moins 1&\square&1&\cdot\cr
     \cdot &1&\cdot &\moins1&1\cr \cdot &\cdot&\square&1&\cdot\cr 
 \cdot&\cdot&1&\cdot&\cdot \end{smallmatrix} \right]\ ,\ 
\left[ \begin{smallmatrix}
 \cdot&1&\cdot&\cdot&\cdot\cr 1&\moins1&\cdot&1&\cdot\cr 
  \square&1&\cdot &\moins 1&1\cr \square&\square&\cdot&1&\cdot\cr 
  \square&\square&1&\cdot&\cdot
\end{smallmatrix} \right]\ ,\
\left[ \begin{smallmatrix}
 \cdot&1&\square&\square&\square\cr 1&\moins1&\cdot&1&\square\cr 
  \cdot&1&\square&\moins1&1\cr 
  \cdot&\cdot&\cdot&1&\cdot\cr \cdot&\cdot&1&\cdot&\cdot
\end{smallmatrix} \right]\ ,\
\left[ \begin{smallmatrix}
 \cdot&1&\cdot&\cdot&\cdot\cr 1&\moins1&\cdot&1&\cdot\cr 
  \cdot&1&\cdot&-1&1\cr \cdot&\cdot&\cdot&1&\square\cr 
   \cdot&\cdot&1&\square&\square 
\end{smallmatrix} \right]\ .
$$  
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 \emph{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 $\moins1$ 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,\ldots$.

For the current  ice-configuration, writing the 
letters directly in the ASM, a disappearance being designated with  
a `hat', we read
$$ \left[ \begin{smallmatrix}
  .&4&.&.&.\\[2pt] 5&\widehat 4&.&2&.\\[2pt]
  .&4&.&\widehat 2&1\\[1pt]  .&.&.&2&.\\[1pt]  .&.&3&.&.
\end{smallmatrix}\right] \longleftrightarrow 
\{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 $\usebox{\OO}\ $, the other zeroes 
being replaced by a dot)~: 
$$ \raise -27pt \young{ 5\cr 4 &5\cr 3 & 4 &5\cr 2&2&4&5\cr 1&1&1&2&4\cr} \quad 
 \longleftrightarrow \qquad \left[
 \begin{array}{ccccc}  \cdot&1&\cdot&\cdot&\cdot\cr 1&\moins1&\cdot&1&\cdot\cr
  \cdot&1&\cdot&-1&1\cr \cdot&\cdot&\cdot&1&\usebox{\OO}\cr
   \cdot&\cdot&1& \usebox{\OO} &\usebox{\OO}
 \end{array}   \right] \ .$$

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 \emph{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 \emph{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 \cite{LS:Treillis}
(or more generally, on a Coxeter group, \cite{GeckKim}).

Among triangles, there are special ones, called \emph{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,\, \ldots,\, 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 \emph{key}.
With M.P. Sch\"utzenberger, 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 {\it 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 \ref{th:GrothASM}) 
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 SE-diagram together 
 with its $\moins 1$ entries. 

\bigskip
\centerline{\bf Chern classes}

\medskip
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
$$ \begin{CD}
                     V_1 @>{\varphi}>>  V_2
   \end{CD}
$$
one uses  the degeneraci loci of $\varphi$  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 \emph{universal quotient bundle on a Grassmannian}
and when $V_1$ is a trivial bundle. In that case, one has explicit varieties,
the \emph{special Schubert varieties},  which represent the Chern classes
\cite{Chern1}. 
But as soon as one wants to describe products of Chern classes, one 
needs all the \emph{Schubert varieties}, not only the special ones.
Chern gave in \cite{Chern2} 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
$$ \begin{CD}
 0 \hookrightarrow V_1^1 \hookrightarrow \cdots \hookrightarrow
                     V_1^n @>{\varphi}>>  V_2^n \rightarrow \cdots
     \rightarrow V_2^1 \rightarrow 0  \ ,
   \end{CD}
$$
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 
${\mathcal X}$, and a matrix $\varphi(x)$, $x\in {\mathcal 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 
${\mathcal Flag}(\C^n)$.

For example, the permutation $\sigma=[2,5,1,4,3]$ (taking the convention that
columns are numbered from right to left)  gives rise to the
following rank-matrix~: 
$$ \left[ \begin{smallmatrix}
 .& .& .& 1& .\cr\cr 1& .& .& .& .\cr\cr .& .& .& .& 
1\cr\cr .& 1& .& .& .\cr\cr .& .& 1& .& . \end{smallmatrix} \right]
\to\left[ \begin{smallmatrix}0& 0& 0& 1& 1\cr\cr 1& 1& 1& 2& 2\cr\cr 1& 1& 1& 2& 
3\cr\cr 1& 2& 2& 3& 4\cr\cr 1& 2& 3& 4& 5
\end{smallmatrix}\right]   \ .  $$ 
The rank matrix, or the ranks of the different induced 
morphisms $V_1^i \to V_2^j$ are overdetermined, a minimal subset of
rank conditions has been given by Fulton \cite{Fulton}. 

There is a simpler way to introduce the symmetric group in the theory of
Chern classes. It is called the \emph{splitting principle}
\cite{Hirzebruch}, which states
that given a vector bundle $V$ on a manifold $\mathcal M$, then
 on the relative flag manifold $\mathcal F(V) \rightarrow \mathcal M$, 
the pullback of $V$ gives a sequence of line bundles 
$L_1,\, \ldots,\, L_n$, such that the total Chern class $c(V)$ is equal
to $(1+c_1(L_1))\cdots (1+c_1(L_n))$.  Chern classes now become
elementary symmetric functions in the variables 
$x_1= c_1(L_1),\ldots,\, 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 \cite{BGG} and Demazure \cite{Demazure}.
With Marcel-Paul Sch\"utzen\-ber\-ger, I gave in \cite{LS1}
 polynomial representatives of the basis of Schubert cycles in
the cohomology of the flag manifold ${\mathcal F}lag(\C^n)$,
the \emph{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~:
$$  \prod\nolimits_{ i+j \leq 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 
\emph{Newton interpolation formula} to several variables \cite{LaNewton}.

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 \emph{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],\ldots,\, x_n=[L_n]$ 
of the tautological line bundles on $\mathcal Flag(\C^n)$.
The geometrical basis is constituted of the classes of the structure sheaves
of Schubert varieties, the \emph{Grothendieck polynomials} 
being their distinguished  representatives.

For each permutation $\ss\in \S_n$, there is a Grothendieck
polynomial $G_\ss$ which can be obtained from
$$ \prod\nolimits_{ i+j \leq n} (1 - y_i/x_j)  $$
by a product of isobaric divided differences acting on the $x_i$'s 
\cite{LaGroth}.  

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 \cite{FK}, or through a noncommutative Schubert calculus
\cite{Lenart}.

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

Given a permutation $\ss\in \S_n$, which is not the identity, let 
$r= \max(i: \ss_i >\ss_{i+1})$. 
Let now $k= \max(\ss_j,\, j>r,\, \ss_j<\ss_r)$, and
$\nu = (k,\ss_r)\,  \ss$, where $(k,\ss_r)$ is the transposition of
the two values $k,\, \ss_r$. 

Let $\nu^{(1)},\ldots, \nu^{(p)}$ be the all the permutations $\eta$ such 
that $\ell(\eta))=\ell(\nu)+1$, $\eta\, \nu^{-1}$ is equal to 
transposition $(j,k)$, $j<k$ (these are the permutations occuring 
in the transition for Schubert polynomial, \cite{LS1, MacSchub}).    

Reformulating Proposition 3 of \cite{LaTrans} 
(it adapts instantly to the case
 of two sets of variables that we need here), one has~:
\begin{proposition}  \label{th:Transition}
  Given a permutation $\ss \in \S_n$, 
let $\cB(\ss)$ be the (boolean) sub-lattice 
of $\S_n$ (considered as embedded into the lattice of ASM of order $n$,
\cite{LS:Treillis}),  
with generators the permutations $\nu^{(1)},\ldots, \nu^{(p)}$,
and minimum element $\nu$.
Then
$$ \Bigl( G_\nu -G_\ss\Bigr)\, \frac{x_j}{y_k} =
  \sum_{\eta\in \cB(\ss)}  (-1)^{\ell(\eta)-\ell(\nu)} G_\eta  \ .$$
\end{proposition}

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

\begin{center}
\setlength{\unitlength}{1mm}
\begin{picture}(70,45)
\put(35,40){\makebox{[65843127]}}
\put(10,30){\makebox{[65841327]}}
\put(35,30){\makebox{[65834127]}}
\put(60,30){\makebox{[64853127]}}
\put(10,20){\makebox{[65831427]}}
\put(35,20){\makebox{[64851327]}}
\put(60,20){\makebox{[64835127]}}
\put(35,10){\makebox{[64831527]}}
\put(44,39){\line(0,-1){5}}
\put(39,39){\line(-4,-1){20}}
\put(49,39){\line(4,-1){20}}
\put(39,29){\line(-4,-1){20}}
\put(19,29){\line(4,-1){20}}
\put(69,29){\line(-4,-1){20}}
\put(49,29){\line(4,-1){20}}
\put(44,14){\line(0,1){5}}
\put(39,14){\line(-4,1){20}}
\put(49,14){\line(4,1){20}}
\end{picture}
\end{center}
furnishing the following recursion between Grothendieck polynomials~: 
\begin{multline*}
  \Bigl( G_{64831527}-G_{64831725}\Bigr)\, \frac{x_6}{y_5} =
  G_{64831527} -G_{65831427} -G_{64851327} -G_{64835127} \\
  + G_{65841327} +G_{65834127} +G_{64853127}  - G_{65843127} \ .
\end{multline*}  



\bigskip
\centerline{\bf Yang-Baxter coefficients}

\medskip

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\plus 1$). 
However, since $ (1+s_1)(1+s_2)(1+s_1)\neq (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 \cite{Y}
was the $n$-body problem on a circle with Hamiltonian
$$
H(\y)= -\sum_{i=1}^n{\partial^2\over \partial y_i^2} +
2c\sum_{i<j}\delta(y_i-y_j) \ ,
$$
where $\delta$ is the Dirac distribution.
The problem was to solve the Schr\"odinger equation
$$
H(\y)\psi(\y)=E \psi(\y)
$$
with periodic boundary conditions.

Yang looked for solutions of the form
$$\psi(\y) = \sum_{\tau\in\S_n}  \theta(\y^\tau) \sum_{\ss\in\S_n} A_\ss(\tau)
e^{{\rm i}\x^\ss \cdot \y^\tau}$$
where $\S_n$ is the symmetric group,
$\x =(x_1,\ldots,x_n)\in\C^n$ is the vector of spectral parameters,
$\x^\ss :=(x_{\ss_1},\ldots,x_{\ss_n})$,
and $\theta$ is the characteristic function of the domain
$y_1<y_2<\ldots <y_n$.
The unknown coefficients $A_\ss(\tau)$ form an $n!\times n!$ matrix, and
it is convenient to regard each $A_\ss$ 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,\ldots, x_n$, 
there exists a linear basis $\{\Y_\ss,\, \ss\in \S_n \}$, 
the  \emph{Yang-Baxter basis}, of $\C[x_1,\ldots, x_n][\S_n]$,
which is defined through the following recursions~:
\bee
 \Y_{\ss s_i} = \Y_{\ss}\, \bigl(1 + (x_{\ss_{i+1}} - 
        x_{\ss_{i}})\, s_i\bigr) \ ,\ \ell(\ss s_i) >\ell(\ss) .
\ee
The validity of such a definition is insured by the 
\emph{Yang-Baxter relations}~:
\begin{multline}
  (1+ \a s_i)\, (1+ (\a+\b)s_{i+1})\, (1+\b s_i) = \\
  (1+ \b s_{i+1})\, (1+ (\a+\b)s_i)\, (1+\a s_{i+1})   \ .
\end{multline}

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 \emph{contents}).  
Jucys \cite{Jucys}, then Cherednik
\cite{Cherednik}, 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 $\C[\S_n]$, that is, for the algebras generated by
$T_1,\ldots,\, T_{n-1}$ satisfying the \emph{braid relations}, together
with a \emph{Hecke relation} (with fixed $q_1,\, q_2$)~:
\bee
   (T_i-q_1)\, (T_i-q_2) =0   \ .
\ee

The two cases relevant to geometry (for the cohomology ring, and
the Grothendieck ring respectively) are 
\begin{eqnarray*}
  \left(T_i^{\mathcal Nil} \right)^2  &=& 0 \qquad \text{Nil-Hecke algebra} \\
  \left(T_i^{0\mathcal H} \right)^2  &=& -T_i^{0\mathcal H}  
\qquad \text{0-Hecke algebra} \\
\end{eqnarray*} 

Expanding the corresponding Yang-Baxter elements 
$\Y_\ss^{\mathcal Nil}$  and 
$\Y_\ss^{0\mathcal H}$ one gets coefficients~:
\begin{eqnarray}
  \Y_\ss^{\mathcal Nil} &=& \sum\nolimits_{\tau\in \S_n} c_\ss^\tau\, 
     T_\tau^{\mathcal Nil}  \\
  \Y_\ss^{0\mathcal H} &=& \sum\nolimits_{\tau\in \S_n} g_\ss^\tau\, 
     T_\tau^{0\mathcal H}
\end{eqnarray} 

The link with the preceding section is provided by the following property
\cite{LLT}~:
\begin{proposition}
The Yang-Baxter coefficients $c_\ss^\tau$ and $g_\ss^\tau$
are specializations of Schubert and Grothendieck polynomials~:
\bee
  c_\ss^\tau = \X_\ss ( \x^\tau,\, \x) \quad \& \quad 
  g_\ss^\tau = \G_\ss ( \x^\tau,\, \x)  \ ,
\ee
denoting by $\x^\tau$ the reordering $x_{\tau_1},\ldots,_, x_{\tau_n}$
of the spectral parameters. 
\end{proposition}

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.

\bigskip
\centerline{\bf  Keys and weights of ASM}

\medskip
Ehresmann \cite{Ehresmann} gave a cellular decomposition of the flag manifold 
${\mathcal F}lag(\C^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,\ldots,\, e_n\}$
can be partitionned into cells, each of which contains a \emph{coordinate
flag}, that is a complete flag 
of subsets of $\{ e_1,\ldots,\, 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,\ldots$. The case of a permutation $\ss$ is when one takes
as a sequence the complete flag of sets 
$$ \{e_{\ss_1}\} \subset \{e_{\ss_1},e_{\ss_2}\}\subset
\cdots \subset \{e_{\ss_1},\ldots,\, e_{\ss_n}\} \ .$$

For the order 3, there is only one ASM which is not a 
permutation matrix~:
$$ \left[\begin{smallmatrix} 0 &1&0\\ 1&-1&1 \\0 &1&0 \end{smallmatrix} 
\right] \leftrightarrow \ \text{sequence of sets}\quad 
 \{e_2\},\, \{e_1,e_3 \}, \,  \{e_1,e_2,e_3 \} \ .$$ 

\bigskip 
Given a point $\blacksquare$
in $\Z\times \Z$, it determines a \emph{SE-quadrant} 
(all the points South and East of it, including horizontal and vertical, minus
$\blacksquare$ itself). Let us call \emph{neighbours} of $\blacksquare$
in an ASM the entries 1 in its SE-quadrant 
such that the submatrix (on consecutive rows and
columns) 
\fbox{$\begin{smallmatrix}
   \blacksquare & \cdots & \cdot\\[3pt] \cdot  &\cdots & 1\end{smallmatrix} $}
% $\begin{array}{lcr}  \hline \blacksquare & \ & \\[3pt] & & & 1 \\ \hline
% \end{array}$
has only 0 entries, outside the two pointed vertices.

The domain covered by all the submatrices associated to the neighbours of 
$\blacksquare$ is a Ferrers' diagram \cite{Macdonald},
with $1$'s at its corners, $0$'s elsewhere (apart from $\blacksquare$).

\emph{Inflating} a Ferrers' diagram consists in replacing it by a bigger
diagram, with inner  corners where the original corners were~:

$$ \begin{CD}
 \begin{matrix} \blacksquare & \hh &\hh &\hh   &\hh    &\hh &\cdot &\cdot \cr
           \hh & \hh &\hh & \cdot & \cdot  &\cdot &\cdot  &\cdot \cr
           \hh & \hh &\hh &\cdot &\cdot  &\cdot &\cdot&\cdot \cr
           \hh &\cdot&\cdot &\cdot   &\cdot &\cdot &\cdot &\cdot \cr
            \hh  & \cdot&\cdot &\cdot   &\cdot &\cdot &\cdot &\cdot
\end{matrix}
\ @>{\s inflation}>> \quad
\begin{matrix} \blacksquare& \hh  &\hh  &\hh    &\hh   &\hh  &\cdot &\cdot \cr
          \hh & \hh  &\hh  &\hh    &\hh   &\hh    &\cdot &\cdot   \cr
          \hh & \hh  &\hh  &\hh    &\hh   & \hh    &\cdot&\cdot  \cr
          \hh & \hh  &\hh  &\cdot  &\cdot &\cdot &\cdot &\cdot \cr
          \hh & \hh  &\hh    &\cdot  &\cdot &\cdot &\cdot &\cdot 
\end{matrix} \ .
\end{CD}
$$
The original Ferrers' diagram, as well as its image under inflation,
covers the places where $\hh$ 
 is written (apart from $\blacksquare$).  

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

$$ \begin{CD}
\begin{matrix} \moins 1 & \hh &\hh &\hh   &\hh    &1 &\cdot &\cdot \cr
           \hh & \hh &\hh & 0 & 0  &0 &\cdot  &\cdot \cr
           \hh & \hh &1 &0 &0  &0 &\cdot&\cdot \cr
           \hh & 0&0 &\cdot   &\cdot &\cdot &\cdot &\cdot \cr
            1  & 0&0 &\cdot   &\cdot &\cdot &\cdot &\cdot
\end{matrix}
\ @>{\s Removing -\! 1}>> \quad
\begin{matrix} \hh& \hh  &\hh  &\hh    &\hh   &\hh  &\cdot &\cdot \cr
          \hh & \hh  &\hh  &\hh    &\hh   &\hh    &\cdot &\cdot   \cr
          \hh & \hh  &\hh  &\hh    &\hh   & 1    &\cdot&\cdot  \cr
          \hh & \hh  &\hh  &\cdot  &\cdot &\cdot &\cdot &\cdot \cr
          \hh & \hh  &1    &\cdot  &\cdot &\cdot &\cdot &\cdot
\end{matrix} \ .
\end{CD}  $$
The original Ferrers' diagram, as well as its image under inflation,
covers the places where $\pm 1$ or $\hh$ (which is a zero entry)
are written.
It is clear that this operation gives a new ASM. 

One checks~:
\begin{lemma}  Given an ASM, and two removable $\moins 1$, then the ASM
obtained by removing the two $\moins 1$ is independent of the order
in which one removes them.
\end{lemma}

\begin{corollary} Removing successively all $\moins 1$'s in an ASM $\asm$ 
produces a unique permutation matrix   $\key(\asm)$
called its \emph{key}.
\end{corollary}
Here is an example of a sequence producing a key (0 entries are written with a
dot).
$$
\left[\begin{smallmatrix} \cdot& \cdot& \cdot& \cdot& \cdot& 1& \cdot& \cdot
\cr \cdot& 1& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot
\cr \cdot& \cdot& \cdot& 1& \cdot& -1& \cdot& 1
\cr 1& -1& \cdot& \cdot& 1& \cdot& \cdot& \cdot
\cr \cdot& \cdot& 1& -1& \cdot& \cdot& 1& \cdot
\cr \cdot& 1& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot
\cr \cdot& \cdot& \cdot& \cdot& \cdot& 1& \cdot& \cdot
\cr \cdot& \cdot& \cdot& 1& \cdot& \cdot& \cdot& \cdot
\end{smallmatrix}\right],\,
\left[\begin{smallmatrix}\cdot& \cdot& \cdot& \cdot& \cdot& 1& \cdot& \cdot
\cr \cdot& 1& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot
\cr \cdot& \cdot& \cdot& 1& \cdot& \cdot& \cdot& \cdot
\cr 1& -1& \cdot& \cdot& 1& \cdot& \cdot& \cdot
\cr \cdot& \cdot& 1& -1& \cdot& \cdot& \cdot& 1
\cr \cdot& 1& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot
\cr \cdot & \cdot& \cdot& \cdot& \cdot& \cdot& 1& \cdot
\cr \cdot& \cdot& \cdot& 1& \cdot& \cdot& \cdot& \cdot
\end{smallmatrix}\right],\,
\left[\begin{smallmatrix}\cdot& \cdot& \cdot& \cdot& \cdot& 1& \cdot& \cdot
\cr \cdot& 1& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot
\cr \cdot& \cdot& \cdot& 1& \cdot& \cdot& \cdot& \cdot
\cr 1& - 1& \cdot& \cdot& 1& \cdot& \cdot& \cdot
\cr \cdot& \cdot& 1& \cdot& \cdot& \cdot& \cdot& \cdot
\cr \cdot& 1& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot
\cr \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& 1
\cr \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& 1& \cdot
\end{smallmatrix}\right],\,
\left[\begin{smallmatrix}\cdot& \cdot& \cdot& \cdot& \cdot& 1& \cdot& \cdot
\cr \cdot& 1& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot
\cr \cdot& \cdot& \cdot& 1& \cdot& \cdot& \cdot& \cdot
\cr 1& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot
\cr \cdot& \cdot& 1& \cdot& \cdot& \cdot& \cdot& \cdot
\cr \cdot& \cdot& \cdot& \cdot& 1& \cdot& \cdot& \cdot
\cr \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& 1
\cr \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& 1& \cdot
\end{smallmatrix}\right]\, .
$$

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

\begin{lemma} In an ASM there is no $\moins 1$ entry in a column left of 
the pivot, nor in the same column above it. 
\end{lemma}
 \proof If $\asm$ is not a permutation matrix, remove all $\moins 1$ from
right to left, from bottom to top, except the last one. 
The two entries 1 in the top of $\moins 1$~:
             $\begin{smallmatrix} 0& 1\\ 1 &-1\end{smallmatrix}$ 
will remain 1's in $\key(\asm)$.
Therefore, the place occupied by this $\moins 1$ is a box of the SE-diagram of 
$\key(\asm)$, and satisfies the geographical constraints fixed 
by the lemma with respect to the pivot.   \qed

This remark allows us to define \emph{transition} on $\ASM$.

\begin{Def}  For each ASM $\asm$, let $\blacksquare$ be its pivot.
Let $\Trans(\asm)$ be the matrix obtained from $\asm$
by transforming its top as follows.
If the pivot   contains a 0, change its top 
$$ \left[\begin{smallmatrix}   0 &\cdots & 1 \\  \vdots & &\vdots\\
 1&\cdots &\blacksquare \end{smallmatrix} \right]
\qquad \text{into}\qquad
\left[\begin{smallmatrix}   1 &\cdots & 0 \\  \vdots & &\vdots\\
 0&\cdots &1 \end{smallmatrix} \right] \ .
$$
If it contains a $\moins 1$, then change
$$ \left[\begin{smallmatrix}   0 &\cdots & 1 \\  \vdots & &\vdots\\
 1&\cdots &\blacksquare \end{smallmatrix} \right]
\qquad \text{into}\qquad
\left[\begin{smallmatrix}   1 &\cdots & 0 \\  \vdots & &\vdots\\
 0&\cdots &0 \end{smallmatrix} \right]
$$                        (the pivot cannot contain a 1).
\end{Def}

\begin{proposition}  \label{th:TransAMS} 
 Given a permutation $\ss$, the image under $\Trans$ of 
$\ASM(\ss)$ is the union of all $\ASM(\eta) :\ \eta\in \cB(\ss)$.  
\end{proposition}

\proof Let $\asm\in \ASM(\ss)$. The neighbours of its pivot are not neighbours
of any $\moins 1$ not located in the pivot. Therefore, one can 
remove all $\moins 1$ located outside the pivot and restrict to ASM
having at most one $\moins 1$, located in the pivot. 

If there is a 0 in the pivot, then $\asm$ is a permutation matrix ($=\ss$),
and its image under a transition is $K(\nu)$, where
$\nu$ is the minimum element of $\cB(\ss)$. If there is a $\moins 1$,
removing it gives $K(\ss)$, and this means that
 inflating the Ferrrers'diagram 
of $\blacksquare$ in $\asm$ gives the Ferrrers' diagram 
of $\blacksquare$ in $K(\ss)$. Each pair of consecutive neighbours 
of $\blacksquare$ in $\asm$ gives a
neighbour of $\blacksquare$ in $K(\ss)$, and conversely, the neighbours
of $\blacksquare$ in $\asm$ are in bijection with a subset of
neighbours of $\blacksquare$ in $K(\ss)$, and the inflated Ferrers' diagram 
is a subset of the Ferrers' diagram of $\blacksquare$ in $K(\ss)$
(we have framed the $1$'s giving back $\asm$ from $K(\ss)$, 
and restricted matrices to their relevant part)~:
$$ \asm =  \begin{smallmatrix}  
   \blacksquare &\hh &\hh &\hh &\hh &\hh &\hh &\hh &\hh &1 \\[2pt]
    \hh &\hh &\hh &\hh &\hh &\hh &\hh & 0&0&0 \\[3pt]
    \hh &\hh &\hh &\hh &\hh &\hh & 1  & 0&0&0 \\[3pt]
    \hh &\hh & 0&0&0 &0&0 \\[3pt]
     \hh & 1 & 0&0&0 &0&0 \\[3pt]
    0&0& \cdot &\cdot \\[2pt]
    0&0& \cdot &\cdot \\[2pt]
    0&0& \cdot &1 \\[2pt]
    0&0 \\[3pt]
    1&0
\end{smallmatrix}   \quad ,\quad
 K(\ss) =
\begin{smallmatrix}
   \blacksquare &\hh &\hh &\hh &\hh &\hh &\hh &\hh &\hh &\hh \\
    \hh &\hh &\hh &\hh &\hh &\hh &\hh & \hh &\hh &\hh \\
    \hh &\hh &\hh &\hh &\hh &\hh & \hh  & \hh&\hh& \fbox{$\s 1$} \\
    \hh &\hh & \hh &\hh &\hh &\hh &\hh \\
     \hh & \hh &\hh &\hh &\hh &\fbox{$\s 1$} \\
     \hh &\hh & \cdot &\cdot \\
     \hh &\hh& \cdot &\cdot \\
     \hh&\hh& \cdot &1 \\
     \hh&\hh \\
      \hh& \fbox{$\s 1$} 
\end{smallmatrix}
$$
On the other hand, 
the generators of the boolean lattice $\cB(\ss)$ can be described on
$K(\ss)$, rather than using the formulation 
of Proposition \ref{th:Transition}.  
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 $\cB(\ss)$, and conversely every generator is obtained in this
manner \cite{LSFlato}. 
$$\begin{matrix}  0&\cdot&\cdot&c\\  \cdot&&&\cdot\\  \cdot&&&\cdot\\ 
                  b &\cdot &\cdot & \blacksquare &0&0&0&0\\  
                  &&& 0&0&0&0&0\\ &&& 0&0&0&0&a
\end{matrix} \qquad  \longrightarrow \qquad
\begin{matrix}    c&\cdot&\cdot&0 \\  \cdot&&&\cdot\\ \cdot&&&\cdot\\
                  0 &\cdot &\cdot & \blacksquare &0&0&0&b\\
                  &&& 0&0&0&0&0\\ &&& a&0&0&0&0
\end{matrix} \ . 
$$
The minimum element of $\cB(\ss)$ is obtained by passing from
 $c,b$ to $b,c$~:
$\begin{smallmatrix}   0 &\cdots & c \\  \vdots & &\vdots\\
 b&\cdots &\blacksquare \end{smallmatrix} 
\ \mapsto \ 
\begin{smallmatrix}   c &\cdots & 0 \\  \vdots & &\vdots\\
 0&\cdots &b \end{smallmatrix} $ . \qed

\bigskip 
\centerline{\bf  Main property}
\bigskip

Let us now introduce parameters $x_1,\ldots,\, x_n$,
$y_1,\ldots,\, 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 $\moins 1$ the weight $\frac{y_i}{x_j}$, where $i,j$ are
the coordinates (and the weight 1 to all other entries).
 The \emph{weight} $\phi(\asm)$ 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.

\begin{theorem}   \label{th:GrothASM}  \qquad 
Given an integer $n$, and a permutation $\ss\in \S_n$,
let\\   $\omega=[n,\ldots,1]\in \S_n$.   Then the 
Grothendieck polynomial 
 $G_{\ss}$ satisfies
$$ (-1)^{\ell(\omega\ss)} G_{\ss} =  \sum \phi(\asm) $$
with the sum over all ASM with key equal to $\ss^{-1}\omega$.  
\end{theorem}

\proof  
The generators of the lattice $\cB(\ss)$ are obtained by taking the pivot,
 one of its neighbour, and transforming the submatrix of order 3 of the key 
$$ \left[
   \begin{smallmatrix}    0 &\cdots &1      &\cdots & 0\\
                          \vdots & &\vdots  &      &\vdots\\
                     1 &\cdots&\blacksquare  &\cdots &0 \\
                     \vdots & &\vdots  &      &\vdots\\ 
                     0 &\cdots &0      &\cdots & 1
\end{smallmatrix} \right]  \qquad \text{into}\qquad
\left[
   \begin{smallmatrix}    1 &\cdots &0      &\cdots & 0\\
                          \vdots & &\vdots  &      &\vdots\\
                     0 &\cdots&\blacksquare  &\cdots &1 \\
                     \vdots & &\vdots  &      &\vdots\\
                     0 &\cdots &1      &\cdots & 0
\end{smallmatrix} \right] \ .
$$

 Let the pivot of $\ss$ have coordinates $r,k$.

The effect of a transition on the weight of an $\asm$ with key $\ss$,
is just to suppress the factor
$y_k/x_r$, if there is a  $\moins 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 \ref{th:TransAMS},
the sum $\sum_{\asm: \key(\asm)=\ss} \phi(\asm)$ 
satisfies the same recursion, under transition, as 
$(-1)^{\ell(\omega\ss)} G_{\ss}$.   \qed

\medskip
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):~

\medskip 
$
\young{ 5\cr 4&5\cr
 3& 4 & 5 \cr2& 2 & 2 & 4 \cr 1&1 & 1 & 1 & 4 \cr }
\quad {\raise 27pt \hbox{  
$\left[ \petitematrice{.& 1& .& .& .\cr .& .& .& .& 1\cr 1& \moins 1& .& 1
& \usebox{\OO}\cr .& 1& .& \usebox{\OO}&\usebox{\OO}\cr .& .& 1&
\usebox{\OO}&\usebox{\OO}} \, \right]$ }} $
{\raise 24pt \hbox{$ \frac{y_3}{x_4}(\frac{y_1}{x_2}\moins 1)
(\frac{y_2}{x_2}\moins 1)
(\frac{y_1}{x_1}\moins 1)(\frac{y_2}{x_1}\moins 1)(
\frac{y_3}{x_1}\moins 1)$}}

$
\young{  5 \cr
  4& 5 \cr 3&3 & 5 \cr2& 2 & 2 & 4 \cr 1& 1 & 1 & 1 & 4 \cr }\ 
{\raise 27pt \hbox{$\left[ 
\petitematrice{.& 1& .& .& .\cr .& .& .& .& 1\cr 1& \moins 1& .& 1
& \usebox{\OO}\cr .& .& 1& \usebox{\OO}& \usebox{\OO}\cr .& 1& 
 \usebox{\OO}& \usebox{\OO}& \usebox{\OO}}\, \right]$}} $
{\raise 24pt \hbox{$ 
\frac{y_3}{x_4}(\frac{y_1}{x_3}\moins 1)
(\frac{y_1}{x_2}\moins 1)(\frac{y_2}{x_2}\moins 1)
(\frac{y_1}{x_1}\moins 1)(\frac{y_2}{x_1}\moins 1)(
\frac{y_3}{x_1}\moins 1) $}} 

$
\young{  5\cr
  4& 5 \cr 3&4 & 5 \cr 2&2 & 4 & 4 \cr 1& 1 & 1 & 1 & 4 \cr }\ 
 {\raise 24pt \hbox{$(\key)$}} 
\  {\raise 27pt \hbox{$ \left[
\petitematrice{.& 1& .& .& .\cr .& .& .& .& 1\cr 
1&\usebox{\OO}& .& .&\usebox{\OO}\cr
 .& .& .& 1& \usebox{\OO}\cr .& .& 1& \usebox{\OO}& \usebox{\OO}}\, \right]$}} $
{\raise 24pt \hbox{$ (\frac{y_1}{x_2}\moins 1)(\frac{y_3}{x_4}\moins 1)
(\frac{y_1}{x_1}\moins 1)(\frac{y_2}{x_1}\moins 1)(\frac{y_3}{x_1}\moins 1)$}}

$
\young{5\cr 4&5 \cr 3&3 & 5 \cr 2&2 & 3 & 4 \cr 1& 1 & 1 & 1 & 4 \cr }
\quad {\raise 27pt \hbox{ $\left[
\petitematrice{.& 1& .& .& .\cr .& .& .& .& 1\cr 1& \moins 1& 1& .
& \usebox{\OO}\cr .& .& .& 1& \usebox{\OO}\cr .& 1& \usebox{\OO}&
\usebox{\OO}& \usebox{\OO}}\, \right]$}} $
{\raise 24pt \hbox{
$ \frac{y_3}{x_4}(\frac{y_1}{x_3}\moins 1)(\frac{y_1}{x_2}\moins 1)
(\frac{y_1}{x_1}\moins 1)(\frac{y_2}{x_1}\moins 1)(\frac{y_3}{x_1}\moins 1)$ }}

\medskip
Therefore, the Grothendieck polynomial $G_{4 2 1 5 3}$ is equal to
$$ G_{4 2 1 5 3} = (1\moins\frac{y_1}{x_2}) (1\moins \frac{y_1}{x_1}
)(1\moins \frac{y_2}{x_1})(1\moins \frac{y_3}{x_1})
(1\moins \frac{y_1y_2y_3}{x_2x_3x_4}) \ .$$

Since the $\moins 1$'s are located at the pivot, the image under transition
of the four matrices are permutation matrices, and one has 
$$ \bigl(G_{42135}-G_{42153}  \bigr) \frac{y_3}{x_4}= 
 G_{42135} -G_{43125} -G_{42315} +G_{43215} \ .$$

\medskip
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 \cite{LaGroth}, the existence of such kernel 
 amounts to the following identity involving
three sets of variables $\{x_1,\ldots,x_n\}$, $\{y_1,\ldots,y_n\}$,
$\{z_1,\ldots,z_n\}$ (writing $\ss\omega$ for $[\ss_n,\ldots,\ss_1]$,
$\ss\in\S_n$)~:
\bee \label{eq:Kernel}
   y_1^{n-1}\cdots y_n^0 \prod_{i+j\leq n} \left( 
     \frac{1}{z_i} -\frac{1}{x_j} \right)=   
       \sum_{\ss\in\S_n} (-1)^{\ell(\ss)} G_\ss({\mathbf x},{\mathbf y})\,
          G_{\ss\omega}({\mathbf z},{\mathbf y}) \ .
\ee
The same kernel also expands in terms of Schubert polynomials. 
Using Theorem \ref{th:GrothASM}, one can write the kernel as a statistics
on pairs of ASM. 

Bousquet-M\'elou and Habsieger \cite{Mireille}
give a sum over  $\ASM$, which in our terms,
states that 
$$\sum_{\ss\in\S_n} (-1)^{\ell(\ss)} G_\ss(\mathbf x, \mathbf 1) =
   x_1^{n-1} x_2^{n-2}\cdots x_n^0 \ ,$$
and is obtained by specializing Eq.\ref{eq:Kernel}. 

Their summation involves  counting the number of SE-zeroes in each column
of an ASM, as well as the $\moins 1$. 
Robbins and Rumsey \cite{RR} express the $q$-Vandermonde
$\prod_{1\leq i<j\leq n}(x_i+qx_j)$ through a summation on the ASM
of order $n$, this time recording the  SW-zeroes as well.  
Chapman \cite{Chapman}, refines their
 construction and gives a combinatorial
description of $\prod_{1\leq i<j\leq n}(x_i+y_j)$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{11}

\bibitem{BGG} {\sc I.N. Bernstein, I.M. Gelfand {\rm and} S.I. Gelfand},
{\it Schubert cells and the cohomology of the spaces $G/P$}, Russian Math.
Surveys {\bf 28} (1973), 1-26.

\bibitem{Mireille} {\sc M. Bousquet-M\'elou, L. Habsieger},
{\it Sur les matrices \`a signes alternants},
Discrete Math. {\bf 139} (1995) 55-72.

\bibitem{Bressoud}  {\sc D. Bressoud}, 
\emph{Proofs and Confirmations: the Story of Alternating Sign Matrix
Conjecture}, Cambridge University Press  (1999). 

\bibitem{Chapman}{\sc R. Chapman}, \emph{Alternating sign matrices
and tournaments}, xxx0008029 (2000). 


\bibitem{Cherednik}{\sc I.V. Cherednik}, {\it A new interpretation of
Gelfand-Tzetlin bases}, Duke. Math. J. {\bf 54} (1987), 563-577.

\bibitem{Chern1} {\sc S.S. Chern}, \emph{Classes of Hermitian manifolds},
 Annals of Math. {\bf 47} (1946) 85-121.

\bibitem{Chern2} {\sc S.S. Chern}, \emph{ On the multiplication in the
characteristic ring of a sphere}, 
Annals of Math. {\bf49} (1948) 362-372. 

\bibitem{Demazure} {\sc M. Demazure}, {\it Invariants sym\'etriques entiers
des groupes de Weyl et torsion}, Invent. Math {\bf 21} (1973), 287-301.

\bibitem{DKLLST} {\sc G. Duchamp, D. Krob, A. Lascoux, B. Leclerc, T. Scharf}
and {\sc J.-Y. Thibon}, {\it Euler-Poincar\'e characteristic and polynomial
representations of Iwahori-Hecke algebras},  Publ. RIMS Kyoto {\bf 31} (1995),
179-201.

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


\bibitem{FK} {\sc S. Fomin} and {\sc A.N. Kirillov}, {\it
Grothendieck polynomials and the Yang-Baxter equation}, Proceedings
of FPSAC'94, DIMACS, Rutgers University, 183--189.

\bibitem{Fulton}{\sc W. Fulton}, {\it Flags, Schubert polynomials,
degeneracy loci, and determinantal formulas},
Duke Math. J. {\bf 65 } (1991), 381-420.

\bibitem{GeckKim} {\sc R. Geck, S. Kim}, 
{\it Bases for the Bruhat-Chevalley order on
all finite Coxeter groups}, J. of Algebra {\bf 197} (1997) 278--310.

\bibitem{Hirzebruch}{\sc F. Hirzebruch}, {\it Topological methods in algebraic
geometry}, 3rd ed., Springer, 1978.

\bibitem{Jucys}{\sc A. Jucys},  
{\it Symmetric polynomials and the center of the
symmetric group rings}, Rep. Math. Phys. {\bf 5} (1974) 107--112.

\bibitem{LaGroth}      {\sc A. Lascoux},
 {\it  Anneau de Grothendieck de la vari\'et\'e de
  drapeaux}, in {``The Grothendieck Festchrift''}, vol III,
 Birkh\"auser (1990) 1--34.

\bibitem{LaTrans}      {\sc A. Lascoux},
\emph{Transition on Grothendieck polynomials},
 Proc. Nagoya Workshop on Physics and Combinatorics (2000),
ed. A Kirillov, N. Liskova, World Scientific (2001) 164--179. 

\bibitem{LaNewton} {\sc A. Lascoux},
 \emph{The Newton interpolation formula, with more variables},
Newton Institute preprint (2001).  

\bibitem{LLT}
{\sc A. Lascoux, B. Leclerc and J.Y. Thibon},
\emph{ Flag Varieties and the Yang-Baxter Equation },
{ Letters in Math. Phys.}, {\bf 40} (1997) 75--90.

\bibitem{LS1} {\sc A. Lascoux {\rm and} M.P. Sch\"utzenberger},
\it Polyn\^omes de Schubert\rm, C.R. Acad. Sci. Paris {\bf 294} (1982),
447-450.

\bibitem{LS2}  {\sc A. Lascoux {\rm and} M.P. Sch\"utzenberger}, 
\emph{Structure de Hopf de l'anneau de cohomologie et de l'anneau de
Grothendieck d'une vari\'et\'e de drapeaux}, C.R. Acad. Sci. Paris
{\bf 295} (1982) 629--633.

\bibitem{LSFlato}  {\sc A. Lascoux {\rm and} M.P. Sch\"utzenberger},
\emph{Schubert polynomials and the
Littlewood-Richardson rule}, Letters in Math.Phys. {\bf 10}(1985) 111--124.

\bibitem{LS:Treillis}   {\sc A. Lascoux {\rm and} M.P. Sch\"utzenberger},
{\it Treillis et bases des groupes de Coxeter},
Electronic J. of Comb. {\bf 3} \# R27 (1996).

\bibitem{Lenart} {\sc  C.~Lenart}, 
{\it Noncommutative Schubert calculus and Grothendieck
  polynomials},
{Adv. in Math.}{\bf 143} (1999) {159--183}.

\bibitem{MacSchub}{\sc I.~G. Macdonald},
\newblock {\em Notes on Schubert polynomials}
\newblock LACIM, Publi. Universit\'e Montr\'eal, (1991).

\bibitem{Macdonald} {\sc I.~G. Macdonald},
\newblock {\em Symmetric functions and {Hall} polynomials}.
\newblock Oxford University Press, Oxford, 2nd edition (1995).

\bibitem{RR} {\sc D.P. Robbins, H. Rumsey}, 
{\it Determinants and Alternating sign
matrices}, Adv. in Maths (1986) 169--184.


\bibitem{Y} {\sc C.N. Yang}, {\it Some exact results for the many-body
problem in one dimension with repulsive delta-function interaction},
Phys. Rev. Lett. {\bf 19} (1967), 1312-- 1315.
\end{thebibliography}

 

\end{document}


\begin{multline*}
\Bigl(
(1\moins\frac{y_1}{x_2}) (1\moins \frac{y_1}{x_1}
)(1\moins \frac{y_2}{x_1})(1\moins \frac{y_3}{x_1})
(1\moins \frac{y_1y_2y_3}{x_2x_3x_4})
\Bigr)\frac{y_3}{x_4}  =\\
(1-{y_{1}\over x_{2}})(1-{y_{1}\over x_{1}})(1-{y_{2}\over
x_{1}})(1-{y_{3}\over x_{1}}) %
-(1-{y_{1}\over x_{2}})(1-{y_{2}\over x_{2}})(1-{y_{1}\over
x_{1}})(1-{y_{2}\over x_{1}})(1-{y_{3}\over x_{1}})   \\
-(1-{y_{1}\over x_{3}})(1-{y_{1}\over x_{2}})(1-{y_{1}\over
x_{1}})(1-{y_{2}\over x_{1}})(1-{y_{3}\over x_{1}})  %
+(1-{y_{1}\over x_{3}})(1-{y_{1}\over x_{2}})(1-{y_{2}\over 
x_{2}})(1-{y_{1}\over x_{1}})(1-{y_{2}\over x_{1}})(1-{y_{3}\over x_{1}})
\end{multline*}

