% Submitted February 21, 1994
%-----------begin Plain TeX file of submitted paper to Electronic J. %Comb.
%this file contains the paper by Dominique Foata and Doron
%Zeilberger, entitled ``Combinatorial Proofs of Capelli's and
%Turnbull's Identities from Classical Invariant Theory."
%The file is to be compiled with TeX and plain with no other
%format. There will be 10 printed pages to come.
\magnification=1200
\nopagenumbers
\font\smcp=cmcsc8
\headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 1 (1994), \#R1\hfill\folio} \fi}
\voffset=2\baselineskip
\hsize=11.25cm
\hoffset1.2cm
\font\smf=cmr8
\def\sgn{\mathop{\rm sgn}}
\def\qed{\quad\raise -2pt\hbox{\vrule
\vbox to 10pt{\hrule width 4pt \vfill\hrule}\vrule}}
\centerline{\bf COMBINATORIAL PROOFS OF CAPELLI'S}
\vskip 5pt
\centerline{\bf AND TURNBULL'S IDENTITIES FROM}
\vskip 5pt
\centerline{\bf CLASSICAL INVARIANT THEORY}
\vskip 2.8 mm
\centerline{\sevenrm BY}
\vskip 2.8mm
\centerline{Dominique
FOATA\footnote{$^*$}{D\'epartement de math\'ematique,
Universit\'e Louis-Pasteur, 7, rue Ren\'e Descartes,
F-67084 Strasbourg Cedex, France (foata@math.u-strasbg.fr).} and Doron
ZEILBERGER\footnote{$^{**}$}{Supported in part by NSF
grant DM8800663; \hfil\break
Department of Mathematics, Temple
University, Philadelphia, PA 19122, U.S.A.
(zeilberg@euclid.math.temple.edu).}}
\vskip 24 pt plus 6pt
{\bf 0. Introduction.
}
Capelli's [C] identity
plays a prominent role in Weyl's [W]
approach to Classical Invariant Theory. Capelli's identity
was recently considered by Howe~[H] and Howe and
Umeda~[H-U]. Howe~[H] gave an insightful
representation-theoretic proof of Capelli's identity, and
a similar approach was used in [H-U] to prove
Turnbull's~[T] symmetric analog, as well as a new
anti-symmetric analog, that was discovered
independently by Kostant and Sahi~[K-S]. The Capelli,
Turnbulll, and Howe-Umeda-Kostant-Sahi identities
immediately imply, and were inspired by, identities of
Cayley (see~[T1]), Garding~[G], and Shimura~[S],
respectively.
In this paper, we give short combinatorial proofs of
Capelli's and Turnbull's identities, and raise the hope
that someone else will use our approach to prove the
new Howe-Umeda-Kostant-Sahi identity.
\medskip
{\bf 1. The Capelli Identity.}
Throughout this paper
$x_{i,j}$ are mutually commuting indeterminates
(``positions''), as are $o_{i,j}$ (``momenta''), and they
interact with each other via the ``uncertainty principle"
$$
p_{ij}x_{ij}-x_{ij}p_{ij}=h,
$$
and otherwise $x_{i,j}$ commutes with all the $p_{k,l}$
if $(i,j)\not=(k,l)$. Of course, one can take
$p_{i,j}:=h(\partial/\partial x_{i,j})$. Set
$X=(x_{ij})$, $P=(p_{ij})$ $(1\le i,j\le n)$.
\proclaim Capelli's Identity. For each positive integer~$n$ and
for $1\le i,j\le n$ let
$$
\displaylines{
\rlap{$(1.1)$}\hfill
A_{ij}=\sum_{k=1}^n
x_{ki}p_{kj} + h(n-i) \delta _{ij}.\hfill\cr
\noalign{\hbox{Then}}
\rlap{\sevenrm (CAP)}\hfill
\sum_{\sigma \in {\cal S}_n}
\sgn(\sigma )\,A_{\sigma 1,1}\ldots A_{\sigma n,n}=\det
X.\det P.\hfill\cr}
$$
{\it Remark $1$}.
The Capelli identity can be viewed as a ``quantum analog"
ot the classical Cauchy-Binet identity
$\det XP=\det X.\det P$, when the entries of $X$ and $P$
commute, and indeed reduces to it when $h=0$. The
matrix $A$ is $X^t\,P$, with ``quantum correction"
$h(n-i)\delta _{i,j}$.
\medbreak
{\it Remark $2$}.
Note that since not all indeterminates
commute, it is necessary to define order in the
definition of the determinant of~$A$. It turns out that
the determinant is to be evaluated by ``column
expansion" rather than ``row expansion," which is
reflected in the left side of {\sevenrm (CAP)}.
\medbreak
{\bf Combinatorial Proof of Capelli's Identity}.
We will first figure out, step by step, what the combinatorial
objects that are being weight-enumerated by the left side of
{\sevenrm (CAP)}. Then we will decide who are the ``bad guys" and
will find an involution that preserves the absolute value of the
weight, but reverses the sign. The weight-enumerator of the
good guys will turn out to be counted by the right side of
{\sevenrm (CAP)}.
First we have to represent each $A_{ij}$ as a generating
polynomial over a particular set of combinatorial objects:
consider the 4-tuples $(i,j,k,l)$ where $i$, $j$,
$k=1,2,\ldots,n$ and $l=0,1$. For $i\not=j$ define
${\cal A}_{ij}$ as the set of all 4-tuples $(a,b,c,d)$ such that
$a=i$, $c=j$, $d=0$ and $b=1,2,\ldots,n$. Next define
${\cal A}_{ii}$ as the set of all 4-tuples $(a,b,c,d)$ such
that $a=c=i$, and either $d=0$ and $b=1,2,\ldots,n$, or
$d=1$ and $b=i+1,\ldots,n$. Finally, let
$$
w(a,b,c,d)=\cases{x_{ba}\,p_{bc},&if $d=0$;\cr
h,&if $d=1$ (and $a=c$).\cr}
$$
We can then rewrite: $A_{ij}=\sum w(a,b,c,d)$, where
$(a,b,c,d)$ runs over all~${\cal A}_{ij}$. Hence
$$
\displaylines{(1.2)
\quad \smash{\sum_{\sigma \in {\cal S}_n}}\sgn (\sigma)\,
A_{\sigma 1,1}\ldots A_{\sigma n,n}\hfill\cr
\hfill{}=
\sum\sgn (a)\,
w(a_1,b_1,c_1,d_1)\ldots w(a_n,b_n,c_n,d_n),\quad\cr
}
$$
where the sum is over all sequences
$(a_1,b_1,c_1,d_1,\ldots,a_n,b_n,c_n,d_n)$ satisfying
the properties:
\item {1)} $a=(a_1,\ldots,a_n)$ is a permutation;
\item {2)} $(c_1,\ldots,c_n)=(1,\ldots,n)$;
\item {3)} $d_i=0$ or 1 $(i=1,\ldots,n)$;
\item {4)} the $b_i$'s are arbitrary $(1\le b_i\le n)$ with the
sole condition that when $d_i=1$, then $a_i=i=c_i$ and
$i+1\le b_i\le n$.
It then suffices to consider the set $\cal A$ of all
$4\times n$-matrices
$$
G=\pmatrix{a_1&a_2&\ldots&a_n\cr
b_1&b_2&\ldots&b_n\cr
c_1&c_2&\ldots&c_n\cr
d_1&d_2&\ldots&d_n\cr}
$$
that satisfy the forementioned 1) to 4) properties
and define the {\it weight} of $G$ as
$$
w(G)=\sgn (a) \prod_{i=1}^n
(x_{b_i,a_i}\,p_{b_i,i}(1-d_i)+hd_i).\leqno(1.3)
$$
Then the (1.2) sum may be expressed as:
$$
\sum_{\sigma \in {\cal S}_n}\sgn (\sigma) \,
A_{\sigma 1,1}\ldots A_{\sigma n,n}
=\sum_{G\in {\cal A}} w(G).
$$
If there is no pair $(i,j)$ such that $1\le i