\magnification=1200
\input a4new
\overfullrule = 0pt
\font\twelvebf = cmbx12
\font\petcap = cmcsc10
\font\sevenit = cmti7
\def\boxit#1#2{\setbox1=\hbox{\kern#1{#2}\kern#1}%
\dimen1=\ht1 \advance\dimen1 by #1 \dimen2=\dp1 \advance\dimen2 by #1
\setbox1=\hbox{\vrule height\dimen1 depth\dimen2\box1\vrule}%
\setbox1=\vbox{\hrule\box1\hrule}%
\advance\dimen1 by .4pt \ht1=\dimen1
\advance\dimen2 by .4pt \dp1=\dimen2 \box1\relax}
\def\tab#1{\boxit{1pt}{$\matrix{#1}$}}
\def\bitab#1{\boxit{1pt}{\boxit{1pt}{$\matrix{#1}$}}}
\def\bo#1{\boxit{1pt}{$#1$}}
\def\he{\hskip 1mm}
\def\th{\noalign{\smallskip}\noalign{\hrule}\noalign{\smallskip}}

\centerline{\twelvebf TURBO-STRAIGHTENING}
\smallskip
\centerline{\twelvebf FOR DECOMPOSITION INTO STANDARD BASES.}
\bigskip
\bigskip
\centerline{Christophe CARRE, Alain LASCOUX, and Bernard LECLERC.}
\bigskip
\centerline{\it Laboratoire d'Informatique Th\'eorique et Programmation}
\centerline{\it Institut Blaise Pascal -- Universit\'e Paris 7}
\centerline{\it 2 place Jussieu,  Paris Cedex 05}
\bigskip\bigskip\bigskip
{\sevenbf Abstract. }{\sevenrm Specht and Hodge have shown that the space 
generated by products of minors
of a matrix admits a linear basis in bijection with Young tableaux. The decomposition of any 
element into this basis is called {\sevenit straightening} and corresponds to the 
iterative use of
Pl\"ucker relations. Thanks to a well known isomorphism between the space of harmonic polynomials
and the space of polynomials modulo the ideal generated by symmetric polynomials, we can now use
as a main technical tool the canonical scalar product on this later space. This leads to a 
different, and possibly better, algorithm for straightening.} 
\bigskip
\bf1. Introduction.
\rm\medskip
Young introduced his celebrated tableaux to denote particular elements of the 
group algebra of the symmetric group ${\goth{S}}_n$ \bf[Yo]\rm. His purpose was to solve 
certain equations in this algebra, which arose in his study of the theory of 
Invariants. Moreover, his constructions allowed him to give explicit bases of irreducible
representations of the symmetric group. 
\smallskip
Using a different approach to describe these representations, Specht considered tableaux 
as special polynomials {\bf [Sp]}. More explicitely, given any filling $t$  of the shape of a 
partition with consecutive numbers (that we shall call a \it tablo\"id\rm), Specht defines
the polynomial $\bo{t}$ to be the product of Vandermonde determinants corresponding
separately to the columns of $t$. Thus, if  
\setbox3 = \hbox{$t =\ $}
\setbox4 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th&\cr
\+ \tv\cc{7}&\tv\cr
\+&\th& \th& \cr
\+ \tv\cc{4}&\tv\cc{3}&\tv\cc{8}&\tv\cr
\+ &&&\th &\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{6}&\tv\cc{5}&\tv\cr
\+ \th&\th&\th&\th& \cr
}$}
$$\line{\hfill\box3\box4,\hfill}$$
$\bo{t}$ is the polynomial
$$\bo{t}\ =\Delta(a_1,a_4,a_7).\Delta(a_2,a_3).\Delta(a_6,a_8).\Delta(a_5).$$
Specht has shown that the space generated by all tablo\"ids of a given shape is an 
irreducible representation of ${\goth{S}}_n$, a basis being given by 
{\it tableaux}  (i.e. tablo\"ids with increasing columns and
 rows). 
\smallskip
In fact, Specht polynomials are products of minors of a Vandermonde matrix, and
the construction remains valid for any matrix, as was shown by Hodge \bf [Ho]\rm. 
Given a matrix $(a_{ij})$ and a tablo\"id $t$, the symbol $\bo{t}$ now means the 
product of 
minors corresponding to its successive columns. For instance, the preceeding tableau  
corresponds to the product of minors:  
$$
\left|\matrix{
a_{11} &a_{14} &a_{17} \cr
a_{21} &a_{24} &a_{27} \cr
a_{31} &a_{34} &a_{37} \cr
}\right|
\left|\matrix{
a_{12} &a_{13} \cr
a_{22} &a_{23} \cr
}\right|
\left|\matrix{
a_{16} &a_{18} \cr
a_{26} &a_{28} \cr
}\right|
a_{15}.$$
Hodge obtained that Young tableaux still provide a linear basis of products 
of minors, and moreover gave an algorithm to decompose any tablo\"id 
into the basis of Young tableaux \bf [Ho]\rm. This algorithm is usually named 
{\it straightening}  and is a direct consequence of a repetitive use 
of Pl\"ucker relations. Various implementations of it have
 been experimented by White \bf [Wh]\rm.
\smallskip
A more general point of view of the underlying algebraic structures can 
be found in the work of De Concini and Procesi, who introduced the 
Hodge algebra structure \bf [CP]\rm. A different approach is given by 
Gr\"obner bases, as was shown by Sturmfels and White \bf [SW] \rm.
\smallskip
Let us go back to minors. In fact Specht case is generic for what 
concerns the straightening, and we shall restrict to this case. 
This was also the point of view of Garnir, who has, 
independently of Hodge but later, described the explicit relations 
to straighten tablo\"ids by means of quadratic syzigies \bf [Ga]\rm.
 His aim 
was to give explicit matrices for Specht representation.  
\smallskip
In the mean time, Rutherford had shown in his exposition of Young's work 
\bf[Ru]\rm, that Young's natural representation was intimately associated with a 
triangular matrix $\Xi$ whose entries are $0,\pm1$. This matrix $\Xi$ was 
generalized by D\'esarm\'enien \bf[Des]\rm, who established its link with the 
straightening formula for bitableaux, and proposed a new algorithm. 
\smallskip
In this paper, we shall interpret differently the links between these 
different constructions. Tablo\"ids still code Specht polynomials. But
 now, one uses the fact that Specht polynomials are special harmonic 
polynomials. The space of harmonic polynomials is isomorphic (as a 
representation of the symmetric group) to the space of polynomials 
modulo the ideal generated by symmetric polynomials. Tablo\"ids are 
sent to special monomials, and Rutherford matrix is now a matrix of 
scalar products. To straighten an element, one must evaluate its scalar 
products (but this reduces to mere additions) with the elements of a basis, 
and locally invert the matrix $\Xi$. This gives a tree, each level consisting 
of tableaux, the edges being given by the operation ``scalar product \& local 
inversion''.
\smallskip
One can combine such an algorithm with other tools more specific to polynomials. 
As an example, we give the explicit straightening of some tableaux having 
much symmetries.
\bigskip

\bf2. Harmonic polynomials. The ring \rm${\bb{Q}}[{\bb{A}}]/{\cal{S}}$ \bf and its scalar product.
\rm\medskip
{\petcap Definition 2.1. } A harmonic polynomial in ${\bb{Q}}[{\bb{A}}]$ is a polynomial 
which 
is annihilated by any symmetric differential operator, \it i.e. \rm by any symmetric 
polynomial $P$ without constant term in the partial derivatives $\delta_a,\ a\in{\bb{A}}$. 
Such a differential operator will be denoted by $P^\delta$, or by $\delta^H$ when $P$ 
reduces to a single monomial $a_1^{h_1}\ldots a_n^{h_n}$.
\medskip
{\petcap Example 2.2. } Let $\Delta$ be the Vandermonde determinant on the 
alphabet 
${\bb{A}}$. For any symmetrical polynomial $P$ without constant term, $P^\delta(\Delta)$ is an 
antisymmetric polynomial of degree smaller than $\Delta$, hence is null. Therefore 
$\Delta$ is harmonic. Since partial derivatives commute, $\delta^H(\Delta)$ is also harmonic 
for all $H\in{\bb{N}}^n$.
\medskip
{\petcap Proposition 2.3. } {\it The linear space ${\cal{H}}({\bb{A}})$ of harmonic 
polynomials is generated by the derivatives $\delta^H(\Delta)$ of the Vandermonde.}
\smallskip
Specht polynomials are particular cases of polynomials $\delta^H(\Delta)$. To be 
more explicit, we shall need some definitions.
\medskip
{\petcap Definition 2.4. } Let $t$ be a tablo\"id of shape $I$ and weight 
$n$, and let $J=j_1\geq j_2\geq\ldots \geq j_k$ denote the conjugate partition of $I$. 
Define $H\in{\bb{N}}^n$ by
$$H=(\underbrace{0,\ldots,0}_{j_1},\underbrace{j_1,\ldots,\ j_1}_{j_2},
\underbrace{j_1+j_2,\ldots,\ j_1+j_2}_{j_3},\ldots ,\ 
\underbrace{j_1+\ldots +j_{k-1}, 
\ldots,\ j_1+\ldots +j_{k-1}}_{j_k}) $$
Now, let $\sigma$ be the permutation of $1,\ 2,\ldots,\ n$ obtained by reading the 
columns of $t$ from bottom to top and from left to right. We set
$$Col(t)=\sigma^{-1}(H):=(h_{\sigma^{-1}(1)},\ldots ,h_{\sigma^{-1}(n)}),
\quad sgn(t)=sgn(\sigma)\ .$$
In other words the column-indicator $Col(t)$ is obtained by attaching to each column of the 
diagram of the partition $I$, the weight of the columns situated to its left, 
and by reading the sequence of columns corresponding to the tablo\"id 
$t$.
\medskip
{\petcap Example 2.5. }
Let $n=8$ and $t$ be the tablo\"id
\setbox3 = \hbox{$t =\ $}
\setbox4 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th&\cr
\+ \tv\cc{7}&\tv\cr
\+&\th& \th& \cr
\+ \tv\cc{4}&\tv\cc{3}&\tv\cc{8}&\tv\cr
\+ &&&\th &\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{6}&\tv\cc{5}&\tv\cr
\+ \th&\th&\th&\th& \cr
\+\tvi &&&&\cr
}$}
\setbox5 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th&\cr
\+ \tv\cc{ }&\tv\cr
\+&\th& \th& \cr
\+ \tv\cc{ }&\tv\cc{ }&\tv\cc{ }&\tv\cr
\+ &&&\th &\cr
\+ \tv\cc{ }&\tv\cc{ }&\tv\cc{ }&\tv\cc{ }&\tv\cr
\+ \th&\th&\th&\th& \cr
\+ \tvi\cc{0}&\cc{3}&\cc{5}&\cc{7}&\cr
}$}
$$\line{\hfill\box3\box4\qquad\qquad\box5\hfill}$$
Then $I=134,\ J=3221,\ H=00033557,\ \sigma=14723685,\ \sigma^{-1}=14528637,$ so that 
$sgn(t)=+1$ and $Col(t)=03307505$. 
\smallskip
Now for any tablo\"id $t$, the determinant $\delta^{Col(t)}(\Delta)$ is easily seen to 
be equal, up to a constant factor, to the Specht polynomial $\bo{t}$. Thus, 
for the tableau $t$ considered above, one has$$\bo{t}\ =\ \delta^{03307505}(\Delta)/7!\ 
6!\ 5!\ 4!\ 3!.$$
\medskip
We shall now describe the canonical isomorphism which will enable us to 
replace computations on tablo\"ids by computations on monomials.
\smallskip
Let ${\cal{S}}$ be the ideal generated in ${\bb{Q}}[{\bb{A}}]$ by symmetric polynomials without 
constant term. Denote by $a^H$ the monomial $a_1^{h_1}\ldots a_n^{h_n}$. We 
have the following result (cf. for example \bf[La]\rm).
\medskip
{\petcap Proposition 2.6. } {\it The morphism defined by $\phi(a^H)=\delta^H(\Delta)$ induces 
an isomorphism $\Phi$ between ${\bb{Q}}[{\bb{A}}]/{\cal{S}}$ and the space ${\cal{H}}({\bb{A}})$ of harmonic 
polynomials. }
\smallskip
Thus, any identity between Specht polynomials (that is, any identity between 
tablo\"ids considered as products of minors) may be transformed by means of 
$\Phi^{-1}$ into an identity between monomials modulo ${\cal{S}}$.
\medskip
{\petcap Example 2.7. } Let $n=4$. The simplest case of Pl\"ucker's 
relations reads:
\setbox4 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th      &\th      &\cr
\+ \tv\cc{2}&\tv\cc{4}&\tv\cr
\+ \tv\cc{1}&\tv\cc{3}&\tv\cr
\+ \th&\th&\cr
}$}
\setbox5 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th      &\th      &\cr
\+ \tv\cc{3}&\tv\cc{4}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cr
\+ \th&\th&\cr
}$}
\setbox6 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th      &\th      &\cr
\+ \tv\cc{4}&\tv\cc{3}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cr
\+ \th&\th&\cr
}$}
$$\line{$\hfill\box4\ -\ \box5\ +\ \box6\ =\ 0\hfill$}$$
In ${\bb{Q}}[a_1,a_2,a_3,a_4]/{\cal{S}}$ this identity becomes:
$$ a^{0022}+a^{0202}+a^{0220}=0. $$
\smallskip
Let us consider now the straightening of a tablo\"id $t$ of shape $I$. Let 
$H$ be the vector of ${\bb{N}}^n$ associated with $I$ as shown in 2.4. The 
image in ${\bb{Q}}[{\bb{A}}]/{\cal{S}}$ of the straightening of $t$ is now an identity 
between monomials of degree $\sigma(H),\ \sigma\in{\goth{S}}_n$. We shall denote by ${\cal{W}}(H)$ the 
subspace generated in ${\bb{Q}}[{\bb{A}}]/{\cal{S}}$ by all monomials whose degree is a permutation 
of $H$. Such a subspace is called a \it weight space\rm. Let us describe the monomials which 
are images of tableaux under the isomorphism $\Phi^{-1}$. We shall 
need a definition.
\medskip
{\petcap Definition 2.8. } Given a totally ordered alphabet ${\bb{X}}=\{x,y,z\ldots \}$, a 
word on ${\bb{X}}$ is a {\it Yamanouchi word}, iff any of its left factors contains more 
$x$'s than $y$'s, more $y$'s than $z$'s, etc.
\smallskip
Thus $xxyzyxyz$ is a Yamanouchi word, but $xyyxz,\ xyxzzxyy$ are not since 
$xyy$ has 2 $y$'s and only one $x$, and $xyxzz$ has 2 $z$'s and only one $y$.
\smallskip
Now we may state the following easy proposition.
\medskip
{\petcap Proposition 2.9. } {\it A tablo\"id $t$ whose columns are increasing 
from bottom to top is a tableau iff its columns--indicator $Col(t)$ is 
a Yamanouchi word.}
\medskip
{\petcap Example 2.10. } Let us consider the Specht module ${\cal{M}}(I)$ generated 
by all polynomials $\bo{t}$ associated to tablo\"ids $t$ of shape $I=1122$. 
This module is sent by $\Phi^{-1}$ on the weight space ${\cal{W}}(000044)$. There are 
$9$ tableaux of shape $I$ corresponding to the $9$ following 
Yamanouchi words:
$$ 000044,\ 000404,\ 004004,\ 040004,\ 000440,\ 004040,\ 040040,\ 004400,\ 
040400.$$
\smallskip
The straightening formula shows that tableaux of shape $I$ 
constitute a basis of ${\cal{M}}(I)$, from which it is deduced that ${\cal{M}}(I)$ is the 
irreducible representation of ${\goth{S}}_n$ corresponding to the partition $I$. This 
theorem lifted to ${\bb{Q}}[{\bb{A}}]/{\cal{S}}$ by means of $\Phi^{-1}$ becomes:
\medskip
{\petcap Theorem 2.11. } {\it Let ${\cal{W}}(H)$ be the image of the Specht module 
${\cal{M}}(I)$. The monomials $a^K$, where $K$ runs through all permutations of $H$ 
satisfying the Yamanouchi condition, form a basis of ${\cal{W}}(H)$ that we shall 
denote by ${\cal{Y}}(H)$. ${\cal{W}}(H)$ is the irreducible representation of ${\goth{S}}_n$ 
corresponding to the partition $I$, for the action by permutation of 
variables and multiplication by the signature.}
\smallskip
Note however that only a few weight spaces ${\cal{W}}(H)$ are images of Specht 
modules. For instance, in ${\bb{Q}}[a_1,a_2,a_3,a_4]/{\cal{S}}$ these weight spaces are 
${\cal{W}}(0000),\ {\cal{W}}(0003),\ {\cal{W}}(0022),\ {\cal{W}}(0023),\ {\cal{W}}(0123),$ and correspond 
respectively to the irreducible representations indexed by partitions $1111,\ 112,\ 
22,\ 13,\ 4.$
\smallskip
The imbedding of Specht modules into ${\bb{Q}}[{\bb{A}}]/{\cal{S}}$ will make it possible to 
straighten tableaux using the natural scalar product in this space.
\medskip
{\petcap Definition 2.12. } Let $P,\ Q$ be polynomials in ${\bb{Q}}[{\bb{A}}]$ and let 
$\overline{P},\ \overline{Q}$ denote their class modulo ${\cal{S}}$. The scalar 
product $<\overline{P}\ |\ \overline{Q}>$ is defined as the constant term of 
the symmetric polynomial
$$\sum_{\sigma\in{\goth{S}}_n}(P.Q/ \Delta)^\sigma\ .$$
Thus, denoting in the same way monomials and their classes modulo ${\cal{S}}$, we 
have the following easy rule:
$$<a^H\ |\ a^K>\ =\ \left\{\matrix{
 sgn(\sigma)& {\rm if}\ H+K=\sigma(\rho),\cr
 0& {\rm else,\hfill}\cr
}\right.$$
where $\rho$ denotes the staircase partition $\rho = 0,\ 1,\ 2,\ldots ,\ n-1$. 
\smallskip
From this definition results immediately the following proposition:
\medskip
{\petcap Proposition 2.13. } {\it Let ${\cal{W}}(H)$ be the image of a Specht module. 
The only monomials which are not orthogonal to ${\cal{W}}(H)$ belong to the weight 
space ${\cal{W}}(\rho-H)$.}
\smallskip
We now proceed to describe the fundamental correspondance between the 
Yamanouchi monomials of ${\cal{W}}(H)$ and ${\cal{W}}(\rho-H)$. For that purpose, it will be 
convenient to define, by analogy with 2.4., the row--indicator of a tablo\"id.
\medskip
{\petcap Definition 2.14.} 
Let $t$ be a tablo\"id of shape $I$. Number the rows of the diagram of $I$ 
from bottom to top (the bottom row has number 0). $Row(t)$ is the sequence of levels 
of the successive boxes of I, enumerating them in the order indicated by $t$. 
\medskip
{\petcap Example 2.15. } Take again the tablo\"id $t$ considered in 2.5:
\setbox3 = \hbox{$t =\ $}
\setbox4 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th&\cr
\+ \tv\cc{7}&\tv\cr
\+&\th& \th& \cr
\+ \tv\cc{4}&\tv\cc{3}&\tv\cc{8}&\tv\cr
\+ &&&\th &\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{6}&\tv\cc{5}&\tv\cr
\+ \th&\th&\th&\th& \cr
\+ \tvi &&&& \cr
}$}
\setbox5 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+\cc{ } \quad&\th&\cr
\+            &\tv\cc{2}&\tv\cr
\+            &\tv\cc{1}&\tv\cr
\+            &\tv\cc{0}&\tv\cr
\+            &\th& \cr
\+\tvi{\sevenit Row}&\cc{ }{\sevenit level}\cr
}$}
$$\line{\hfill\box3\box4\qquad\qquad\box5\hfill}$$
Its row--indicator is $Row(t)=00110021$.
\smallskip
If $t$ is a tablo\"id whose columns are increasing, $Row(t)$ is evidently a 
Yamanouchi word, and the correspondance between $Col(t)$ and $Row(t)$ is 
worth noting. We first set the following definition:
\medskip
{\petcap Definition 2.16. } Let $H\in{\bb{N}}^n$. Given a permutation $K$ of $H$, read 
the word $K$ from left to right and replace the first occurences of any 
letter by $0$'s, the second occurences by $1$'s, etc.. We denote by ${\bf p}(K)$ 
the word obtained thus.
\smallskip
For example, $\bf p\rm(30050300)=00102134$. We have now the following results:
\medskip
{\petcap Proposition 2.17. } {\it Let $I$ be a partition of $n$ and define 
$H$ as in {\rm 2.4.} A permutation of H is called a word of evaluation H.
\smallskip 
{\rm (i)} The map $\bf p\rm$ is a surjection from the set of words of evaluation $H$ 
onto the set of Yamanouchi words of evaluation $\rho-H$.\par
{\rm (ii)} The restriction of $\bf p\rm$ to the set of Yamanouchi words of 
evaluation $H$ is a bijection $\bf b\rm$ decreasing for the lexicographic order.\par
{\rm (iii)} For any tablo\"id $t$ whose columns are increasing from bottom to 
top, one has $Row(t)=\bf p\it(Col(t))$ and $Col(t)+Row(t)=\sigma^{-1}(\rho)$, where $\sigma$ 
is the permutation obtained by reading the columns of $t$ from bottom to 
top and from left to right.\par
{\rm (iv)} If $t$ and $u$ are two tabloids whose columns are increasing from 
bottom to top, and such that $Col(t)+Row(u)$ is a permutation of $\rho$, then 
$t$ and $u$ have the same shape and $Col(t)$ is before $Col(u)$ in the 
lexicographic order.}\medskip\eject
This combinatorial lemma may now be translated in terms of monomials 
modulo ${\cal{S}}$.
\medskip
{\petcap Proposition 2.18. } {\it Let ${\cal{W}}(H)$ be the image of a Specht module in ${\bb{Q}}[{\bb{A}}]/{\cal{S}}$.
\smallskip
{\rm (i)} The map $a^K\longrightarrow a^{{\bf p}(K)}$ is a canonical surjection  
from the set of monomials in ${\cal{W}}(H)$ onto the set ${\cal{Y}}(\rho-H)$ of Yamanouchi 
monomials in $W(\rho-H)$.\par
{\rm (ii)} The restriction of this map to ${\cal{Y}}(H)$ is a bijection.\par
{\rm (iii)} The matrix $\Xi$ of scalar products $<a^K\ |\ a^L>$, where $a^K,\ 
a^L$ run through the sets ${\cal{Y}}(H)$, lexically ordered, and ${\cal{Y}}(\rho-H)$, 
anti-lexically ordered, is triangular with entries $0, +1, -1$.}
\medskip
{\petcap Example. } Take $I=1122$, so that ${\cal{W}}(H)={\cal{W}}(000044)$ and 
${\cal{W}}(\rho-H)={\cal{W}}(001123)$. Writing the word $K$ in place of the monomial $a^K$, one 
has for example:
$$\bf p\rm(440000)=\bf p\rm(404000)=001123,\ \ \bf p\rm(400040)=001213,\ \ \bf b\rm(000440)=012013.$$
The image under $\bf b\rm$ of the basis ${\cal{Y}}(000044)$ given above is
$${\cal{Y}}(001123)=(012301,\ 012031,\ 012013,\ 010231,\ 010213,\ 010123,\ 001231,\ 
001213,\ 001123).$$
Finally the matrix $\Xi$ is
$$\Xi=\pmatrix{
1& .& .& .& .& .& .& .& .\cr
.& -1& .& .& .& .& .& .& .\cr
.& .& 1& .& .& .& .& .& .\cr
.& .& .& 1& .& .& .& .& .\cr
.& .& .& .& -1& .& .& .& .\cr
.& .& .& .& .& 1& .& .& .\cr
.& .& .& .& .& .& -1& .& .\cr
-1& .& .& .& .& .& .& 1& .\cr
.& 1& -1& .& .& .& .& .& -1\cr
}\ .$$
\smallskip
Now, we can easily describe an algorithm for the decomposition on the basis 
${\cal{Y}}(H)$ of any polynomial belonging to ${\cal{W}}(H)$, or, what is equivalent as we 
have just shown, for the straightening of any linear combination of tableaux 
of shape $I$. Indeed, let $P$ be the polynomial to be decomposed, and let
$$ P=\sum_i \lambda_K a^K $$
denote its decomposition. The coefficients $\lambda_K$ are the solutions of the 
linear system obtained by computing the scalar products $\mu_L=<P\ |\ a^L>,\ 
a^L\in{\cal{Y}}(\rho-H)$. The matrix of this system is $\Xi$, and it remains only to compute 
its inverse $\Xi^{-1}$, which is made possible, despite of its hugeness, by its 
being unitriangular with lots of entries equal to 0.
\smallskip
We conclude this section by emphasizing that the matrix $\Xi$ is already 
well-known in representation theory of ${\goth{S}}_n$. Up to sign factors this matrix 
is exactly the matrix $\Xi$ used by Rutherford to obtain the so-called \it natural 
representation \rm\bf[Ru]\rm. The fact that it may also be used to compute the 
coefficients of the straightening formula was shown by D\'esarm\'enien, by 
means of Capelli operators \bf[Des]\rm.
\bigskip
\bf3. The turbo-straightening algorithm.
\rm\medskip
The basic routine of this algorithm generates the rows of the matrix $\Xi$, 
that is, computes the monomials in ${\cal{Y}}(\rho-H)$ whose scalar product with a given 
monomial in ${\cal{W}}(H)$ is non-zero. It is based on the following proposition:
\medskip
{\petcap Proposition 3.1. } {\it Let $a^K$ be a monomial in ${\cal{W}}(H)$ and let 
$a^L=a^{{\bf p}(K)}$ denote its image in ${\cal{Y}}(\rho-H)$ under the surjection $\bf p\rm$.  
From the two words $K=(k_1,\ldots k_n)$ and $L=(l_1\ldots l_n)$, form the biword 
${K\choose L}={k_1\choose l_1}\ldots {k_n\choose l_n}.$ Let $a^M$ belong to 
${\cal{Y}}(\rho-H)$. Then $<a^M\ |\ a^K>\neq0$ iff the biword ${K\choose M}$ is a 
reordering of ${K\choose L}$.}
\medskip
{\petcap Example 3.2. } Take $K=047040740$, so that $L=000112123$, and 
$${K\choose L} = {0\choose 0}{4\choose 0}{7\choose 0}{0\choose 1}{4\choose 
1}{0\choose 2}{7\choose 1}{4\choose 2}{0\choose 3}.$$
The routine enumerates all Yamanouchi biwords ${K\choose L^{'}}$, which are 
obtained by permuting between themselves biletters having the same upper 
letter. In this case, the list of all words $L^{'}$ such that ${K\choose 
L^{'}}$ is Yamanouchi is the following, where the permutations operated are 
indicated by the symbols $\sharp,\ \flat,\ \natural$.
$$\matrix{
0& 0& 0& 1& 1& 2& 1& 2& 3\cr
0& 0& 0& 1& 2^\flat & 3^\natural & 1& 1^\flat & 2^\natural\cr
0& 0& 1^\sharp & 1& 2^\flat & 2& 0^\sharp & 1^\flat & 3\cr
0& 0& 1^\sharp & 1& 2^\flat & 3^\natural & 0^\sharp & 1^\flat & 2^\natural\cr
0& 0& 1^\sharp & 2^\natural & 1& 3^\natural & 0^\sharp & 2& 1^\natural\cr
0& 1^\flat & 0& 1& 0^\flat & 2& 1& 2& 3\cr
0& 1^\flat & 0& 2^\natural & 0^\flat & 1^\natural & 1& 2& 3\cr
0& 1^\flat & 0& 2^\natural & 0^\flat & 3^\natural & 1& 2& 1^\natural\cr
}$$
\smallskip
Now the straightening of a monomial $a^K$ of ${\cal{W}}(H)$ is performed by 
sequential application of the routine described above. Indeed, we saw in 
section 1 that this straightening is equivalent to the resolution of a 
unitriangular linear system. It is easily seen that the computations to be 
done may be conveniently represented by the construction of a tree of 
biwords, whose root is the word ${K\choose {\bf p}(K)}$. The sons of a given word 
${S\choose T}$ in this tree are all words ${U\choose V}$ different from 
${S\choose T}$ satisfying the conditions:
\smallskip
($i$) $<a^S\ |\ a^V>\neq0,$\par
($ii$) $a^V$ belongs to ${\cal{Y}}(\rho-H)$, and $U={\bf b}^{-1}(V)$.\par
\smallskip
Each edge ${S\choose T}\longrightarrow {U\choose V}$ bears the sign $\varepsilon=<a^S\ 
|\ a^V><a^U\ |a^V>.$
The result of the straightening is the sum of the signed monomials $\varepsilon(S)a^S$ 
corresponding to all words ${S\choose T}$ of the tree (except the root), the 
sign $\varepsilon(S)$ being the product of the two following signs:
\smallskip
($a$) the product of the signs beared by the edges going from ${S\choose T}$ 
to the root of the tree;\par
($b$) $(-)^{k-1}$ where $k$ is the level of the tree to which the word 
${S\choose T}$ belongs (the root is at level $0$).
\medskip\vfill\eject
{\petcap Example 3.3.}
The straightening tree of the monomial $a^{030663306}$ is
$$
\setbox10=\vbox{\hsize=2cm 000336366\par 012010212}
\setbox11=\vbox{\hsize=2cm 000333666\par 012012012}
\setbox12=\hbox{$\vcenter{\hsize=2cm 030603366\par 001021212}$}
\setbox13=\hbox{$\vcenter{\copy10\medskip\copy11}$}
\setbox14=\hbox{\box12\hskip 1cm\box13}
\setbox17=\hbox{$\vcenter{\hsize=2cm 000333666\par 012012012}$}
\setbox18=\hbox{$\vcenter{\hsize=2cm 000336366\par 012010212}$}
\setbox19=\hbox{$\vcenter{\hsize=2cm 000363636\par 012001122}$}
\setbox20=\hbox{$\vcenter{\hsize=2cm 030306366\par 001120212}$}
\setbox21=\hbox{\box19\hskip 1cm\copy17}
\setbox22=\hbox{\box20\hskip 1cm\box18}
\setbox23=\hbox{$\vcenter{\box14\bigskip\copy21\bigskip\copy22}$}
\setbox24=\hbox{$\vcenter{\hsize=2cm 030636036\par 001011222}$}
\setbox25=\hbox{$\vcenter{\hsize=2cm 030630636\par 001012122}$}
\setbox26=\hbox{\box24\hskip 1cm\box23}
\setbox30=\hbox{$\vcenter{\hsize=2cm 030303666\par 001122012}$}
\setbox31=\hbox{\box30\hskip 1cm\copy17}
\setbox27=\hbox{$\vcenter{\box31\bigskip\copy21}$}
\setbox28=\hbox{\box25\hskip 1cm\box27}
\setbox32=\vbox{\hsize=2cm 000336636\par 012010122}
\setbox33=\vbox{\hsize=2cm 030063366\par 001201212}
\setbox34=\vbox{\hsize=2cm 030036366\par 001210212}
\setbox35=\hbox{$\vcenter{\box32\bigskip\box33\bigskip\copy21\bigskip\box34}$}
\setbox36=\hbox{$\vcenter{\hsize=2cm 030366036\par 001101222}$}
\setbox37=\hbox{\box36\hskip 1cm\box35}
\setbox38=\vbox{\hsize=2cm 030033666\par 001212012}
\setbox39=\hbox{$\vcenter{\hsize=2cm 030360636\par 001102122}$}
\setbox40=\hbox{$\vcenter{\box38\bigskip\copy21}$}
\setbox41=\hbox{\box39\hskip 1cm\box40}
\setbox29=\hbox{$\vcenter{\box26\bigskip\box28\bigskip\box37\bigskip\box41 
\bigskip\box10\bigskip\box11}$}
\setbox42=\hbox{$\vcenter{\hsize=2cm 030663306\par 001011222}$}
\setbox43=\hbox{\box42\hskip 1cm\box29}
\box43
$$\eject
The result is, writing $K$ in place of $a^K$:
$$
030663306=\underbrace{030636036+030630636+030366036+030360636-000336366-000
333666}_{first\ level}$$
$$\underbrace{-030603366-030306366-030303666-000336636-030063366- 
030036366-030033666}_{second\ level}
$$
Note that in this case four words of the second level and all words of the 
third level are annihilated in the summation. We shall see in Prop.3.5, 3.6 
that some of these cancellations could be foreseen, and therefore the 
corresponding computations avoided.
\smallskip
It will perhaps be helpful to restate this example using the classical 
tableau notation. The monomial $a^{030663306}$ corresponds to the tableau
\setbox4 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{8}&\tv\cc{7}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{6}&\tv\cc{5}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{4}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox5=\hbox{$t = $}
$$\line{\hfill\box5\box4\hfill}$$
The straightening tree of $t$ is:
\vfill \eject
$$
\def\cc#1{\hfill{\sevenrm#1}\hfill}
\def\th{\vrule height 0.4pt width 1.1em}
\def\tvi{\vrule height 6pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\setbox10=\vbox{\hsize=2cm \offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{3}&\tv\cc{7}&\tv\cc{9}&\tv\cr
\+ \tv\cc{2}&\tv\cc{5}&\tv\cc{8}&\tv\cr
\+ \tv\cc{1}&\tv\cc{4}&\tv\cc{6}&\tv\cr
\+ \th&\th&\th& \cr
}
\setbox11=\vbox{\hsize=2cm \offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{3}&\tv\cc{6}&\tv\cc{9}&\tv\cr
\+ \tv\cc{2}&\tv\cc{5}&\tv\cc{8}&\tv\cr
\+ \tv\cc{1}&\tv\cc{4}&\tv\cc{7}&\tv\cr
\+ \th&\th&\th& \cr
}
\setbox12=\hbox{$\vcenter{\hsize=2cm \offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{5}&\tv\cc{7}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{6}&\tv\cc{8}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{4}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox13=\hbox{$\vcenter{\copy10\medskip\copy11}$}
\setbox54=\hbox{\box12\hskip 1cm\box13}
\setbox17=\hbox{$\vcenter{\hsize=2cm \offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{3}&\tv\cc{6}&\tv\cc{9}&\tv\cr
\+ \tv\cc{2}&\tv\cc{5}&\tv\cc{8}&\tv\cr
\+ \tv\cc{1}&\tv\cc{4}&\tv\cc{7}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox18=\hbox{$\vcenter{\hsize=2cm\offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{3}&\tv\cc{7}&\tv\cc{9}&\tv\cr
\+ \tv\cc{2}&\tv\cc{5}&\tv\cc{8}&\tv\cr
\+ \tv\cc{1}&\tv\cc{4}&\tv\cc{6}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox19=\hbox{$\vcenter{\hsize=2cm\offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{3}&\tv\cc{8}&\tv\cc{9}&\tv\cr
\+ \tv\cc{2}&\tv\cc{6}&\tv\cc{7}&\tv\cr
\+ \tv\cc{1}&\tv\cc{4}&\tv\cc{5}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox20=\hbox{$\vcenter{\hsize=2cm\offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{5}&\tv\cc{7}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{4}&\tv\cc{8}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{6}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox21=\hbox{\box19\hskip 1cm\copy17}
\setbox22=\hbox{\box20\hskip 1cm\box18}
\setbox23=\hbox{$\vcenter{\box54\bigskip\copy21\bigskip\box22}$}
\setbox24=\hbox{$\vcenter{\hsize=2cm \offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{7}&\tv\cc{8}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{5}&\tv\cc{6}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{4}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox25=\hbox{$\vcenter{\hsize=2cm\offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{6}&\tv\cc{8}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{5}&\tv\cc{7}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{4}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox26=\hbox{\box24\hskip 1cm\box23}
\setbox30=\hbox{$\vcenter{\hsize=2cm\offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{5}&\tv\cc{6}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{4}&\tv\cc{8}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{7}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox31=\hbox{\box30\hskip 1cm\box17}
\setbox27=\hbox{$\vcenter{\box31\bigskip\copy21}$}
\setbox28=\hbox{\box25\hskip 1cm\box27}
\setbox50=\vbox{\box26\bigskip\box28}
\setbox32=\vbox{\hsize=2cm\offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{3}&\tv\cc{8}&\tv\cc{9}&\tv\cr
\+ \tv\cc{2}&\tv\cc{5}&\tv\cc{7}&\tv\cr
\+ \tv\cc{1}&\tv\cc{4}&\tv\cc{6}&\tv\cr
\+ \th&\th&\th& \cr
}
\setbox33=\vbox{\hsize=2cm\offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{4}&\tv\cc{7}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{6}&\tv\cc{8}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{5}&\tv\cr
\+ \th&\th&\th& \cr
}
\setbox34=\vbox{\hsize=2cm \offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{4}&\tv\cc{7}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{5}&\tv\cc{8}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{6}&\tv\cr
\+ \th&\th&\th& \cr
}
\setbox35=\hbox{$\vcenter{\box32\bigskip\box33\bigskip\copy21\bigskip\box34}$}
\setbox36=\hbox{$\vcenter{\hsize=2cm\offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{7}&\tv\cc{8}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{4}&\tv\cc{6}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{5}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox37=\hbox{\box36\hskip 1cm\box35}
\setbox51=\vbox{\box50\bigskip\box37}
\setbox38=\vbox{\hsize=2cm \offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{4}&\tv\cc{6}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{5}&\tv\cc{8}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{7}&\tv\cr
\+ \th&\th&\th& \cr
}
\setbox39=\hbox{$\vcenter{\hsize=2cm \offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{6}&\tv\cc{8}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{4}&\tv\cc{7}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{5}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox40=\hbox{$\vcenter{\box38\bigskip\box21}$}
\setbox41=\hbox{\box39\hskip 1cm\box40}
\setbox52=\vbox{\box51\bigskip\box41}
\setbox29=\hbox{$\vcenter{\box52\bigskip\box10\bigskip\box11}$}
\setbox42=\hbox{$\vcenter{\hsize=2cm
\offinterlineskip\cleartabs
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{8}&\tv\cc{7}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{6}&\tv\cc{5}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{4}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox43=\hbox{\box42\hskip 1cm\box29}
\box43 
$$

\bigskip
The construction of this tree may be easily described in terms of tableaux 
only. The root is the tableau to be straightened. The sons of a given tableau 
$u$ are all standard tableaux $s$ different from $u$ which are obtained by 
permuting the columns of $u$ and reordering the lines. Thus, the 
transposition of $4$ and $5$ in the last column of the tableau $t$ 
straightened above, leads to a son in the first level of the tree:
\setbox4 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{8}&\tv\cc{7}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{6}&\tv\cc{5}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{4}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox5 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{8}&\tv\cc{7}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{6}&\tv\cc{4}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{5}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox6 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{7}&\tv\cc{8}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{4}&\tv\cc{6}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{5}&\tv\cr
\+ \th&\th&\th& \cr
}$}
$$\line{$\hfill\box4\longrightarrow\box5\longrightarrow\box6\hfill$}$$
But the transposition of $2$ and $6$ in the second column of $t$ leads to a 
tableau whose columns are not increasing from bottom to top, and therefore 
must be rejected:
\setbox4 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{8}&\tv\cc{7}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{6}&\tv\cc{5}&\tv\cr
\+ \tv\cc{1}&\tv\cc{2}&\tv\cc{4}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox5 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{8}&\tv\cc{7}&\tv\cc{9}&\tv\cr
\+ \tv\cc{3}&\tv\cc{2}&\tv\cc{5}&\tv\cr
\+ \tv\cc{1}&\tv\cc{6}&\tv\cc{4}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox6 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th      &\th      &\th      &\cr
\+ \tv\cc{7}&\tv\cc{8}&\tv\cc{9}&\tv\cr
\+ \tv\cc{2}&\tv\cc{3}&\tv\cc{5}&\tv\cr
\+ \tv\cc{1}&\tv\cc{4}&\tv\cc{6}&\tv\cr
\+ \th&\th&\th& \cr
}$}
$$\line{$\hfill\box4\longrightarrow\box5\longrightarrow\box6\hfill$}$$
The sign beared by an edge $u\longrightarrow s$ of the tree, is now the 
signature of the permutation of the columns of $u$ which is operated to get 
$s$. The sign of $s$ in the straightening of $t$ is, as above, the product of 
the signs of the edges going from $s$ to the root of the tree, multiplied by 
$(-)^{k-1}$, where $k$ denotes the level of the tree to which $s$ belongs, 
the root being at level $0$.
\bigskip
We proceed to describe some symmetries of the straightening tree of a 
monomial (or of a tablo\"id). These symmetries are not surprising, since the 
ordinary action of the symmetric group (by permutation of the variables and 
multiplication by the signature) is compatible with the scalar product in 
${\bb{Q}}[{\bb{A}}]$. But it must be noted that the set of Yamanouchi monomials is not 
stable for this action. We have only the following property:
\medskip
{\petcap Proposition 3.4. } {\it Let $a^S$ be a monomial in ${\cal{Y}}(H)$ and let 
$a^T=a^{{\bf b}(S)}$ be its image in ${\cal{Y}}(\rho-H)$ under the bijection $\bf b\rm$. Suppose that 
two adjacent biletters ${s_i\choose t_i},\ {s_{i+1}\choose t_{i+1}}$ of the 
word ${S\choose T}$ satisfy $s_i\ \neq\ s_{i+1}$ and $t_i\ \neq\ t_{i+1}$. Then the 
words obtained by permuting these letters in $S$ and $T$ are still Yamanouchi 
words.}
\medskip
In terms of tableaux this is the classical lemma which states that when two 
consecutive numbers of a tableau lie in different columns and rows, 
the tablo\"id obtained by permuting these numbers is still a tableau.
\smallskip
From this we deduce at once the following proposition.
\medskip
{\petcap Proposition 3.5. } {\it A polynomial symmetrical in two consecutive 
letters $a_i,\ a_{i+1}$ will have a decomposition in the basis ${\cal{Y}}(H)$ 
presenting the same symmetry.}
\medskip
More precisely, the following proposition shows that the algorithm respects 
step by step such a symmetry.
\medskip
{\petcap Proposition 3.6. } {\it Let ${S\choose T}$ be a vertex of the 
straightening tree of $a^K$.
\smallskip
(i) If the $i^{th}$ and $(i+1)^{th}$ letters of $S$ are equal, the sum of all 
signed monomials $\pm a^U$ coming from the subtree of root ${S\choose T}$ is a 
polynomial symmetric in the two letters $a_i$ and $a_{i+1}$.
\smallskip
(ii) If the word ${S'\choose T'}$ obtained by permuting the $i^{th}$ and 
$(i+1)^{th}$ letters of ${S\choose T}$ is another vertex in the tree, the sum 
of all signed monomials $\pm a^U$ coming from the subtrees of root ${S\choose 
T}$ and ${S'\choose T'}$ is a polynomial symmetric in the two letters $a_i$ 
and $a_{i+1}$.}
\medskip
{\petcap Proof. } The proof is by induction on the number of levels of the 
subtrees. Suppose that the sum of monomials coming from level $k$ is the 
polynomial $P=\sum_U c_Ua^U$, symmetrical in $a_i,\ a_{i+1}$. The sum 
coming 
from level $k+1$ will be $$Q=\sum_{U,V} c_U <a^U|a^{{\bf b}(V)}><a^V|a^{{\bf b}(V)}>a^V 
=: 
\sum_{U,V} d_{U,V}a^V,$$ where $a^V$ runs through the basis ${\cal{Y}}(H)$, and $\bf b\rm$ 
is the bijection described in 2.17. Let $\sigma$ denote the transposition of $i$ 
and $i+1$. If $<a^U|a^{{\bf b}(V)}>\neq0$ and $a^V$ is not symmetric in $a_i,\ 
a_{i+1}$, there are two cases:
\smallskip
(1) $a^{\sigma(V)} \in {\cal{Y}}(H)$, in which case the compatibility of the scalar product 
with the action of $\sigma$ and the equality $c_U=c_{\sigma(U)}$ show that 
$d_{U,V}=d_{\sigma(U),\sigma(V)}$
\smallskip
(2) $a^{\sigma(V)} \notin {\cal{Y}}(H)$, which implies that $a^{{\bf b}(V)}$ is symmetric in $a_i,\ 
a_{i+1}$ (Prop.3.4.), so that $d_{U,V}=-d_{\sigma(U),V}$ and the total coefficient 
of $a^V$ in $Q$ is zero.
\smallskip
Hence $Q$ is symmetric in $a_i,\ a_{i+1}$, and the proof follows by induction. 
$\qed$
\medskip
{\petcap Example 3.7. } In the staightening tree of example 3.3 there are 
several 
subtrees which may illustrate the proposition. For example, the subtree of 
root 
\setbox36=\hbox{$\vcenter{\hsize=2cm 030366036\par 001101222}$}
$$\box36$$
and the whole tree for case (i); and the couples of subtrees of roots
\setbox24=\hbox{$\vcenter{\hsize=2cm 030636036\par 001011222}$}
\setbox25=\hbox{$\vcenter{\hsize=2cm 030366036\par 001101222}$}
\setbox26=\hbox{$\vcenter{\hsize=2cm 030630636\par 001012122}$}
\setbox27=\hbox{$\vcenter{\hsize=2cm 030360636\par 001102122}$}
\setbox28=\hbox{\box24\hskip 5mm\box25\hskip 2mm;\hskip 1.5cm \box26\hskip 
5mm\box27}$$\box28$$
for case (ii).
\medskip
This proposition has an important consequence concerning the straightening of 
tableaux with repeated letters. Indeed, these tableaux may always be treated 
as tableaux without repetition, by merely polarizing the equal letters 
$a=a=a<b=b<\ldots $, that is replacing them by $a<a'<a"<b<b'\ldots $, 
straightening the tableaux obtained, and specializing $a=a'=a"<b=b'<\ldots$ 
in the result. But this method is not very effective, since a lot of useless 
computations are made. Proposition 3.6. shows that specializations 
corresponding to equal letters may be used at every level of the construction 
of the straightening tree.
\bigskip
\bf4. Final comments.
\rm\medskip
Much of what has been given here is not new, but we hope it clarifies the 
subject to see, for example, that the matrix introduced by Rutherford is a 
matrix of scalar products. Moreover in the classical presentation, one has 
to test if, given a pair of tableaux, 
there exists a horizontal permutation of the entries of the first one and a 
vertical permutation of the entries of the second one which generate the same 
tablo\"id. This looks much heavier than to test if the sum of two vectors is a 
permutation of $0,\ 1,\ 2,\ldots,\ n-1$ or not, though it is strictly 
equivalent. By transfering to the ring of polynomials, we can use much more 
tools than that is available for tableaux or minors of matrices (change of 
variables, partial symmetries, divided differences, etc.).
\smallskip
Let us give an example, also known to White, which shows how to use symmetric 
functions to straighten a particular monomial. We first give a definition.
\medskip
{\petcap Definition 4.1. } Let $J=j_1,\ j_2,\ \ldots ,\ j_k$ be a partition of  
$n$, and $L=(l_1,l_2,\ldots ,l_n)$ be a vector of integers.
Set $A_1=\{a_1,\ldots ,a_{j_1}\},\ \ldots ,\ A_k=\{a_{n-j_k+1},\ldots ,a_n\}$,
and $L_1=(l_1,\ldots ,l_{j_1}),\ \ldots ,\ L_k=(l_{n-j_k+1},\ldots ,l_n)$.
We define the multi--monomial function
$\Psi_L(A_1|A_2|\ldots |A_k)$ by setting
$$\Psi_L(A_1|A_2|\ldots |A_k)=\Psi_{L_1}(A_1)\ldots 
\Psi_{L_k}(A_k),$$ 
where $\Psi_T(X)$ denotes the ordinary monomial symmetric function of 
degree $T$ on the set of variables $X$ (cf. \bf[LS] \rm or \bf[Mcd]\rm).
\medskip
{\petcap Proposition 4.2. } {\it Let ${\cal{W}}(h_n\ldots h_1)$, with $h_1\geq\ldots 
\geq h_n$, be the weight space image of the Specht module ${\cal{M}}(I)$, and let 
$J=j_1\leq j_2\leq\ldots \leq j_k$ denote the conjugate partition of $I$. The 
straightening of the monomial $a^{H}$ is given by an explicit formula: 
$$a^H=\pm\Psi_L(A_1|A_2|\ldots |A_k),$$
where $L=\bf b\rm^{-1}\circ \bf p\it(H)$.}
\medskip
{\petcap Example. } Let $I=11233$ so that $J=235$ and $H=8855500000$. Then, 
${\bf p}(H)=0101201234,\ L={\bf b}^{-1}({\bf p}(H))=00\ 550\ 88500,\ L_1=00,\ L_2=550,\ L_3=88500.$ 
The straightening of $a^H$ reads
$$a^{8855500000}=-\Psi_{0055088500}(A_1|A_2|A_3):=-\Psi_{00}(a_1,a_2)\Psi_{550}(a_3,a_4,a_5)\Psi_{885
00}(a_6,\ldots a_{10}).$$
\medskip
{\petcap Proof.}  By proposition 3.5, we know that the straightening 
decomposition of $a^H$ is symmetric in each subset $\{a_1,\ldots 
,\ a_{j_1}\}\ldots \{a_{n-j_k+1},\ldots ,a_n\}$. Thus, its decomposition 
on ${\cal{Y}}(H)$ will be of the form
$$a^H=\sum_M c_M \Psi_M(A_1|A_2|\ldots |A_k),$$
where the summation is over a certain set of words $M$ of evaluation $H$. 
Now, all monomials obtained by expanding the product $\Psi_M(A_1|A_2|\ldots |A_k)$ 
must belong to ${\cal{Y}}(H)$, from which we deduce that, if the letters of each 
subword $M_1,\ldots ,\ M_k$ are rearranged in decreasing order, the word 
obtained (that we may continue to denote by $M=M_1\ldots M_k)$ will be a 
Yamanouchi word. It turns out that this condition is satisfied by a single 
word of evaluation $H$, which is $S=\bf b\rm^{-1}(\bf p\it(H))$. Indeed, the condition on 
$M$ is equivalent to the condition, that every subword $N_1,\ldots ,\ N_k$ of 
$N:=\bf b\it(M)$ be strictly increasing. In view of the evaluation $\rho-H$ of the word 
$N$, we see that the only possibility is 
$$N=01\ldots j_1\ 01\ldots j_2\ \ldots \ 01\ldots j_k=\bf p\it(H).$$
We conclude by identifying the coefficient $c_L=<a^H|a^{{\bf b}(L)}> 
<a^L|a^{{\bf b}(L)}>=\pm1$, since by proposition 2.18 $<a^K|a^{{\bf b}(L)}>=0$ for all 
monomials $a^K \neq a^L$ appearing in $\Psi_L(A_1|A_2|\ldots |A_k)$. $\qed$
\medskip
The result of Proposition 4.2. may be translated in terms of tableaux. For 
instance the example given above is equivalent to the following identity:
\setbox4 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th&\cr
\+ \tv\cc{10}&\tv\cr
\+ \tv\cc{9}&\tv\cr
\+&\th&\cr
\+ \tv\cc{8}&\tv\cc{5}&\tv\cr
\+&&\th      &\cr
\+ \tv\cc{7}&\tv\cc{4}&\tv\cc{2}&\tv\cr
\+ \tv\cc{6}&\tv\cc{3}&\tv\cc{1}&\tv\cr
\+ \th&\th&\th& \cr
}$}
\setbox5 = \hbox{$\vcenter{
\offinterlineskip\cleartabs
\def\cc#1{\hfill#1\hfill}
\def\th{\vrule height 0.4pt width 1.5em}
\def\tvi{\vrule height 9pt depth 2pt width 0pt}
\def\tv{\tvi\vrule}
\+ \th&\cr
\+ \tv\cc{$10^\sharp$}&\tv\cr
\+ \tv\cc{$9^\sharp$}&\tv\cr
\+&\th&\cr
\+ \tv\cc{$5^\flat$}&\tv\cc{$8^\sharp$}&\tv\cr
\+&&\th      &\cr
\+ \tv\cc{2}&\tv\cc{$4^\flat$}&\tv\cc{$7^\sharp$}&\tv\cr
\+ \tv\cc{1}&\tv\cc{$3^\flat$}&\tv\cc{$6^\sharp$}&\tv\cr
\+ \th&\th&\th& \cr
}$}
$$\line{$\hfill\box4\ =\ \sum\pm\ \box5\ ,\hfill$}$$
where the sum on the right side is the alternated sum of all ${3\choose 
2,1}{5\choose 2,1,2}=90$ tableaux obtained by permutation of the 
letters of type $\flat$ between themselves, and of the letters of type 
$\sharp$ between themselves. 
\smallskip
In this article we have only used minors of a very special matrix, namely the 
Vandermonde matrix of powers of indeterminates. However, this case is 
sufficiently generic for what concerns the straightening through Pl\"ucker 
relations. The relations used to describe Specht modules or Hodge algebras 
are the same, though in the second case, one uses minors of generic matrices. 
What we did in this paper was to translate these relations into simpler 
computations in the quotient ring ${\bb{Q}}[{\bb{A}}]/{\cal{S}}$. More general computations on 
minors could also be interpreted in this ring. This is the case for example 
of Turnbull formula which is, to our knowledge, the most general identity 
between minors of a generic matrix (cf. \bf[Le]\rm).
\bigskip
\bf Acknowledgement.
\rm\medskip
The authors are very grateful to Neil White for fruitful mathematic 
exchanges, and communications of many explicit computations.
\bigskip
\centerline{\petcap References.}
\bigskip
\bf[CP] \rm\hskip 5mm {\petcap C. De Concini and C. Procesi,} \it Hodge algebras, a 
survey\rm, in Tableaux de Young et foncteurs de Schur, Ast\'erisque 87--88 (1981)
79--83.
\smallskip
\bf[Des] \rm\hskip 5mm {\petcap J. D\'esarm\'enien,} \it An algorithm for the Rota 
straightening formula\rm, Discrete Mathematics 30 (1980) 51--68.
\smallskip
\bf[Ga] \rm\hskip 5mm {\petcap H. Garnir,} \it Th\'eorie de la repr\'esentation 
lin\'eaire des groupes sym\'etriques\rm, Li\`ege, 1950.
\smallskip
\bf[Ho] \rm\hskip 5mm {\petcap W. Hodge and D. Pedoe,} Methods of algebraic 
geometry, vol.II, 1952.
\smallskip
\bf[La] \rm\hskip 5mm {\petcap A. Lascoux,} \it Cyclic permutations on words, tableaux 
and harmonic polynomials, \rm Proc. of the Hyderabad conference on Algebraic 
Groups, Manoj Prakashan, Madras, 1991, 323--347.
\smallskip
\bf[Le] \rm\hskip 5mm {\petcap B. Leclerc,} \it On identities satisfied by minors of a 
matrix, \rm to appear in Advances in Mathematics.
\smallskip
\bf[LS] \rm\hskip 5mm {\petcap A. Lascoux and M.P. Schutzenberger,} Formulaire 
raisonn\'e de fonctions sym\'etriques, Publ. Math. Univ. Paris 7, 1985.
\smallskip
\bf[Mcd] \rm\hskip 5mm {\petcap I.G. Macdonald,} Symmetric functions and Hall 
polynomials, Oxford Math. Monographs, 1979.
\smallskip
\bf[Ru] \rm\hskip 5mm {\petcap D.E. Rutherford,} Substitutionnal Analysis, 
Edimburgh, 1948.
\smallskip
\bf[Sp] \rm\hskip 5mm {\petcap W. Specht,} \it Die irreduziblen Darstellungen der 
symmetrischen Gruppe, \rm Math. Zeit 39, 1935, 696--711.
\smallskip
\bf[SW] \rm \hskip 5mm {\petcap B. Strurmfels and N. White,} \it Gr\"obner bases 
and invariant theory, \rm Advances in Mathematics 76, 245--259 (1989).
\smallskip
\bf[Wh] \rm\hskip 5mm {\petcap N. White,} \it Implementation of the 
straightening algorithm of classical invariant theory, \rm in Invariant theory 
and tableaux, Springer, 1989.
\smallskip
\bf[Yo] \rm\hskip 5mm {\petcap A. Young,} \it On quantitative substitutional analysis, 
\rm Proc. London Math. Soc., 1900--1933.
\bye

