
\input amstex
\magnification=\magstep1
\documentstyle{amsppt}
\pagewidth{5.4in}
\topmatter
\title
Determinants through the looking Glass
\endtitle
\author
Tewodros Amdeberhan${}^1$ and Doron Zeilberger${}^2$
\endauthor
\affil 
${}^1$DeVry Institute of Technology, North Brunswick NJ 08902, USA \\
${}^2$Department of Mathematics, Temple University,
Philadelphia PA 19122, USA \\
amdberha\@nj.devry.edu, zeilberg\@math.temple.edu
\endaffil
\date Submitted: December 23, 2000. 
\enddate
\dedicatory
Dedicated to Dominique Foata on his $65^{th}$-birthday
\enddedicatory
\abstract
Using a recurrence derived from Dodgson's Condensation Method, we 
provide numerous explicit 
evaluations of determinants. They were all conjectured, and then 
rigorously proved, by
computer-assisted methods, that should be amenable to full automation. 
We also mention a 
first step towards that goal, our Maple package, {\tt DODGSON,} that
automates the special case of Hankel and Toeplitz hypergeometric 
determinants.
\endabstract
\endtopmatter
\def\({\left(}
\def\){\right)}
\def\R{\bold R}
\font\smcp=cmcsc8
\headline={\ifnum\pageno>1{\smcp Advances in Applied Mathematics 
\hfill\folio} \fi}
\document \noindent
{AMS Subject Classification:}
Primary 05A, 15A
\bigskip

\noindent
This article is motivated by the computation in [1] that was inspired 
by the short proof [6] of 
MacMahon's determinant evaluation [4], using a determinantal identity 
of Charles Dodgson [2]. 
Many special cases of the sampled determinants given below were 
independently discovered by 
M. Petkov\v sek [5]. For an excellent and detailed survey of existing 
methods of proofs of 
determinant identities, see [3]. \smallskip
\noindent
For any $n$ by $n$ matrix $A$, let $A_r(i,j)$ denote the $r$ by $r$ 
minor consisting 
of $r$ contiguous rows and 
columns of $A$, starting with row $i$ and column $j$. In particular, 
$A_n(1,1) = \det A$. Then, according to Dodgson [2],
$$
 A_n(1,1) A_{n-2}(2,2)  =
 A_{n-1}(1,1) A_{n-1}(2,2) -  A_{n-1}(2,1) A_{n-1}(1,2).\tag\text{\it 
Lewis\rm}
$$
\noindent
For many cases, $A_n(i,j)$ turn out, conjectured at first, to have an 
explicit expression,
involving single and double products. Whenever this is the case the 
proof of the conjectured
evaluation is completely routine, by induction on $n$, by checking that 
\it (Lewis) \rm is
satisfied by that conjectured expression, and by checking the trivial 
initial conditions for
$n=0$ and $n=1$. Finally, to get an explicit expression for the 
original determinant, all one
has to do is plug in $i=1$ and $j=1$. 

$$ $$
$$ $$

\pagebreak

\noindent
A more interesting case happens when $A_n(i,j)$ does not seem to have 
an explicit expression,
yet $A_n(1,1)$ does. We believe that in many cases, \it (Lewis) \rm 
should still be useful,
by extending the \it ansatz \rm to a larger class, that for us humans 
looks messy, but
that computers won't mind. Then plugging in $i=1$ and $j=1$ in that 
`messy expression' (which
may well be a recurrence satisfied by it) could still be simplified to 
something `nice.' 
\smallskip
\noindent
Be that as it may, in the former case things could be made completely 
automatic. But this
programming chore is too daunting. Hence so far we only accomplished a 
semi-automated 
implementation of the special case of Hankel and Toeplitz determinants 
of hypergeometric
type. The reader is invited to check out our Maple package {\tt 
DODGSON,} that has on-line
help. \bigskip

\noindent
\bf Examples of Computer-assisted Explicit Evaluations: \rm

$$\det\left[\frac{1}{i!} \binom{x+ai+j}{y+ai-j}_{0\leq i,j\leq n}\right]
\tag1$$
$$=a^{\binom{n+1}2} \prod_{i=0}^n  
\frac{(x+ai)!}{(y+ai)!(x-y+2i)!} 
\prod_{j=1}^i \left[x+y+(i+j-1)a+1 \right].$$

$$\det\left[\frac{1}{i!} \binom{x+ai+j}{y+ai-j}^{-1}_{0\leq i,j\leq 
n}\right]\tag2$$
$$=(-a)^{\binom{n+1}2} \prod_{i=0}^n \frac{(x-y+2i)! 
(y+ai-n)!}{(x+ai+n)!}
\prod_{j=1}^i \left[x+y+(i+j-1)a+1 \right].$$

$$\det\left[ \binom{2x+2ai+2j}{x+ai+j}_{0\leq i,j\leq n}\right]\tag3$$
$$=2^n n!^{n+1} a^{\binom{n+1}2} \prod_{i=0}^n \binom{n+i}i 
\binom{2i}i^{-1} \binom{2x+2ai}{x+ai}
\prod_{j=1}^n \frac1{\left[x+ai+j \right]}.$$

$$\det\left[i!\binom{x+ai+cj}j \binom{y+bi-j}{n-j}_{0\leq i,j\leq 
n}\right]\tag4$$
$$=\prod_{j=1}^n \prod_{i=1}^j \left[(y-j+1)a -(x+cj-i+1)b 
\right],$$

$$ $$
$$ $$

\pagebreak


$$\det\left[i!\binom{x+ai+j}j \binom{y+bi+cj}{n-j}_{0\leq i,j\leq 
n}\right]\tag5$$
$$=\prod_{i=1}^n \prod_{j=1}^i \left[(y+(n-j)c-i+1)a -(x+n-i+1)b 
\right],$$

$$\det\left[\frac1{i!}\binom{x+ai+cj}j 
\binom{y+bi+j}{j}^{-1}_{0\leq i,j\leq n}\right]\tag6$$
$$=\frac{\prod_{j=0}^n (y+bj)!} {\prod_{j=0}^n(y+bj+n)!}
\prod_{j=1}^n \prod_{i=1}^j \left[(y+j)a 
-(x+cj-i+1)b\right],$$

$$\det\left[\frac{x+ai+bj}{y+ai+bj}\right]_{0\leq i,j\leq n}\tag7$$
$$=(ab)^{\binom{n+1}2}(x-y)^n \left[x+ny+\binom{n+1}2 (a+b)\right]
 \frac{\prod_{i=0}^n i!^2}{\prod_{i,j=0}^n \left[y+ai+bj 
\right]}.$$

$$\det\left[(x+ai+bj)^k \right]_{0\leq i,j\leq n}=\left\{ 
\aligned n!^{n+1} (-ab)^{\binom{n+1}2}, \qquad\text{if $k=n$} \\
  0, \qquad\text{if $0\leq k < n.$}  \endaligned \right. \tag8$$

$$\det\left[ (x+ai+bj)^n (y+ai-bj)^n  \right]_{0\leq i,j\leq n}\tag9$$
$$=n!^{n+1} (ab)^{\binom{n+1}2}\prod_{j=1}^n  \prod_{i=1}^j
 \left[x+y+(i+j-1)a \right] \left[x-y+(i+j-1)b \right].$$
 
$$ $$
$$ $$

\pagebreak

$$\det\left[ \frac{(x+ai+j) (y+bi+j)}{x+(a+b)i+j}  \right]_{0\leq 
i,j\leq n}\tag10$$
$$=b^n(a+b)^{\binom{n}2} \left[y+nx+\binom{n+1}2 (a+b+1)\right]
\prod_{i=1}^n i!^2[y-x-ia]  \prod_{j=0}^n
 \frac1{[x+(a+b)i+j]}.$$
 
 $$\det\left[ \frac1{(x+bi+j) (y-bi+j)}  \right]_{0\leq i,j\leq 
n}\tag11$$
$$=(-b)^{\binom{n+1}2} \prod_{i,j=0}^n \frac1{(x+bi+j)(y-bi+j)}
\prod_{j=1}^n j!^2 \prod_{i=1}^j [x-y+(j+i-1)b][x+y+j+i-1].$$

$$\det\left[ \frac1{(x+ai+j) (a+x+ai+j)}  \right]_{0\leq i,j\leq 
n}\tag12$$
$$=\frac{a^{\binom{n+1}2}}{(n+1)!} \prod_{i=0}^{n+1} i!^2 
\prod_{j=0}^n 
\frac{1}{(x+ai+j)}.$$

$$\det\left[ \frac{(x+ai+j-1)!}{(x+r+ai+j)!}  \right]_{0\leq 
i,j\leq n}\tag13$$
$$=a^{\binom{n+1}2} \prod_{i=0}^n i!^2 \binom{r+i}i 
\frac{(x+ai-1)!}{(x+r+ai+n)!}.$$

\noindent
\bf Remark: \rm Notice in particular that Eqn. (13) reveals the 
Hilbert matrix when $r=0$ and $a=1$.

$$\det\left[j!\binom{x+ai+cj}j \binom{y-ai+cj}{j}\right]
_{0\leq i,j\leq n}\tag14$$
$$=(-a)^{\binom{n+1}2}
\prod_{j=1}^n \prod_{i=1}^j \left[x-y+(i+j-1)a\right].$$

$$ $$

\pagebreak

\noindent
We now demonstrate how such identities could be discovered. Let us 
take the following example:

$$\det\left[ \frac1{(r+i+j) (1+r+i+j)}  \right]_{0\leq i,j\leq n}=
\frac1{(n+1)!} \prod_{i=0}^{n+1} i!^2 \prod_{j=0}^n 
\frac{1}{(r+i+j)}.\tag15$$
\noindent
Denoting the left-hand side of (15) by $f_n(r)$, we form the ratio
$h_n(r):=\frac{f_n(r+1)}{f_n(r)}$ and input empirical data ($n$ 
fixed, $r$
varying) in the MAPLE package {\tt gfun}, which in turn suggests 
the recurrence 
$$-(r+n+1)(r+n+2)h_n(r)+ r(r+2n+3)h_n(r+1)=0$$
for $h_n(r)$. This, combined with the definition of 
$h_n(r)$ 
implies that 
$$f_n(r)=a_n \frac{(r+n)!!(r+n-1)!!}{(r-2)!! (r+2n+1)!!}$$
for some constant $a_n$, depending (possibly) on $n$. 
At this stage, we invoke the recurrence relation (\it Lewis\rm ), 
resulting from
Dodgson's rule, on $f_n(r)$. Consequently, we obtain 
$$\frac{a_n a_{n-2}}{a_{n-1}^2} = n(n+1).$$ 
We then conclude that $a_n = n!! (n+1)!!$ and the construction of
the identity (15) is completed. 
\smallskip
\noindent
Our Maple package {\tt DODGSON,} combines some of these intermediate 
steps for the
special cases of Hankel and Toeplitz determinants of hypergeometric 
type. 
{\tt DODGSON} is available at {\tt http://www.math.temple.edu/\~{}
zeilberg/tokhniot/DODGSON.}

\bigskip
\noindent
\bf Further Notes: \rm \bigskip \noindent
Let $P(i,j,x)$ be polynomials in $x$, and assume also
$P(i+1,j,x) = P(i,j,x+c)$ for some constant $c$. Then, we have 
\bigskip
\noindent
\bf Fact 1: \rm If $deg(P(i,j,x) < n$,
$$\det[ P(i,j,x) ]_{0\leq i,j\leq n} = 0.$$
\noindent
\bf Proof: \rm Follows from a rank argument on the first row of 
the matrix
and the linearity assumption, above. $\square$

$$ $$
$$ $$

\pagebreak

\noindent
\bf Fact 2: \rm If in addition, $P$ is of degree $n$ and 
$P(i,j,x) = g(i+j+x)$, 
then
$$\det[ P(i,j,x) ]_{0\leq i,j\leq n} \equiv \text{\it constant\rm}.$$
\noindent
\bf Proof: \rm By embedding the given matrix $M_n(x):=[P(i,j,x)]_{0\leq 
i,j\leq n}$ into 
$M_{n,0}(x):=[ P(i,j,x) ]_{0\leq i,j\leq n+1}$ 
and applying Dodgson's rule, we gather that the determinant 
$f_n(x):=\det(M_n(x))$ of the
original matrix satisfies
$$f_n(x) f_n(x+2) = f_n(x+1)^2,\tag16$$
since the determinant of the new matrix $M_{n,0}(x)$ vanishes by Fact 
1, 
above. But $f_n(x)$ is a polynomial, thus for Eqn. (16) to hold $f_n(x)
$ must 
be a constant. $\square$
\bigskip

\noindent
\bf Postscript: \rm \par \noindent
Christian Krattenthaler pointed out that most of our determinants
are special cases of known determinants mentioned in [3].
More interestingly, with the exception of our identities
(8)-(10), they can be derived from his amazingly general and
versatile lemma [3, Lemma 5.] He also recommended the Maple package
``Guess'' by B\'eraud and Gauthier for more efficient guessing.

\noindent
Nevertheless, the identities we presented above are all
beautiful, and once our complete automation will be achieved,
it would be much easier to prove them from scratch than
to find how they can be derived from Krattenthaler's Lemma.
Also, in defense of Dodgson, we are almost sure,
(and will be glad to try it for a fee of $\$5000$), that
Krattenthaler's Lemma is Dodgeable, and the humanly-daunting
task of manipulating double products should also be 
capable of automation.


\midspace{.1in}

\Refs
\widestnumber\key{1}

\ref\key 1 \by T. Amdeberhan and S. B. Ekhad \paper \it A condensed 
condensation
proof of a determianant evaluation conjectured by G. Kuperberg and G. 
Propp \rm
\jour Jour. Combin. Theory (A) \vol 78 (1)\yr1997 \pages169-170
\endref
\smallskip
 
\ref\key 2 \by C. L. Dodgson\paper \it Condensation of Determinants \rm 
\jour 
Proc. Royal Soc. London \vol 15 \yr1866 \pages150-155
\endref
\smallskip

\ref\key 3 \by C. Krattenthaler\paper \it Advanced Determinant 
Calculus\rm \jour 
Seminaire Lotharingien Combin \vol 42 The Andrews Festschrifft \yr1999 
\pages B42q 
{\tt http://www.mat.univie.ac.at/\~{}slc/wpapers/s42kratt.html}
\endref
\smallskip

\ref\key 4 \by P. A. MacMahon, \it Combinatory Analysis \rm
\jour Cambridge University Press, vol. 2, 1916 \yr reprinted by 
Chelsea, 1960
\endref
\smallskip

\ref\key 5 \by M. Petkov\v sek \paper \it unpublished article \rm
\endref
\smallskip
 
\ref\key 6 \by D. Zeilberger\paper \it Reverend Charles to the aid of 
Major 
Percy and Fields Medalist Enrico \rm \jour Amer. Math. Monthly \vol 103 
\yr1996
\pages501-502
\endref

\endRefs


\enddocument



