DETERMINANTS THROUGH THE LOOKING GLASS

Tewodros Amdeberhan^{1} and Doron Zeilberger^{2}

1DeVry Institute of Technology, North Brunswick NJ 08902, USA 2Department of Mathematics, Temple University, Philadelphia PA 19122, USA amdberha@nj.devry.edu, zeilberg@math.temple.edu

Submitted: December 23, 2000.

Dedicated to Dominique Foata on his 65^{th}-birthday

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, DODGSON, that automates the special case of Hankel and Toeplitz hypergeometric determinants.

AMS Subject Classification: Primary 05A, 15A

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šek [5]. For an excellent and detailed survey of existing methods of proofs of determinant identities, see [3].

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],

(Lewis)  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).

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 (Lewis) 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.

Typeset by AMS-TEX

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, (Lewis) should still be useful, by extending the ansatz 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.’ 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 DODGSON, that has on-line help.

Examples of Computer-assisted Explicit Evaluations:

(1)  det [\frac{1}{i!}\binom{x + ai + j}{y + ai − j}_{0≤i,j≤n}]

= a^{\binom{n+1}{2}} ∏_{i=0}^{n} \frac{(x + ai)!}{(y + ai)!(x − y + 2i)!} ∏_{j=1}^{i} [x + y + (i + j − 1)a + 1] .

(2)  det [\frac{1}{i!}\binom{x + ai + j}{y + ai − j}_{0≤i,j≤n}^{−1}]

= (−a)^{\binom{n+1}{2}} ∏_{i=0}^{n} \frac{(x − y + 2i)!(y + ai − n)!}{(x + ai + n)!} ∏_{j=1}^{i} [x + y + (i + j − 1)a + 1] .

(3)  det [\binom{2x + 2ai + 2j}{x + ai + j}_{0≤i,j≤n}]

= 2^{n}n!^{n+1}a^{\binom{n+1}{2}} ∏_{i=0}^{n} \binom{n + i}{i}\binom{2i}{i}^{−1}\binom{2x + 2ai}{x + ai} ∏_{j=1}^{n} \frac{1}{[x + ai + j]}.

(4)  det [i!\binom{x + ai + cj}{j}\binom{y + bi − j}{n − j}_{0≤i,j≤n}]

= ∏_{j=1}^{n} ∏_{i=1}^{j} [(y − j + 1)a − (x + cj − i + 1)b] ,

(5)  det [i!\binom{x + ai + j}{j}\binom{y + bi + cj}{n − j}_{0≤i,j≤n}]

= ∏_{i=1}^{n} ∏_{j=1}^{i} [(y + (n − j)c − i + 1)a − (x + n − i + 1)b] ,

(6)  det [\frac{1}{i!}\binom{x + ai + cj}{j}\binom{y + bi + j}{j}_{0≤i,j≤n}^{−1}]

= \frac{∏_{j=0}^{n}(y + bj)!}{∏_{j=0}^{n}(y + bj + n)!} ∏_{j=1}^{n} ∏_{i=1}^{j} [(y + j)a − (x + cj − i + 1)b] ,

(7)  det [\frac{x + ai + bj}{y + ai + bj} ]_{0≤i,j≤n}

= (ab)^{\binom{n+1}{2}}(x − y)^{n} [x + ny + \binom{n + 1}{2}(a + b)] \frac{∏_{i=0}^{n} i!^{2}}{∏_{i,j=0}^{n} [y + ai + bj]}.

(8)  det [(x + ai + bj)^{k}]_{0≤i,j≤n} = \{ \begin{matrix}n!^{n+1}(−ab)^{\binom{n+1}{2}},  if k = n \\ 0,  if 0 ≤ k < n. \end{matrix}

(9)  det [(x + ai + bj)^{n}(y + ai − bj)^{n}]_{0≤i,j≤n}

= n!^{n+1}(ab)^{\binom{n+1}{2}} ∏_{j=1}^{n} ∏_{i=1}^{j} [x + y + (i + j − 1)a] [x − y + (i + j − 1)b] .

(10)  det [\frac{(x + ai + j)(y + bi + j)}{x + (a + b)i + j}]_{0≤i,j≤n}

= b^{n}(a + b)^{\binom{n}{2}} [y + nx + \binom{n + 1}{2}(a + b + 1)] ∏_{i=1}^{n} i!^{2}[y − x − ia] ∏_{j=0}^{n} \frac{1}{[x + (a + b)i + j]}.

(11)  det [\frac{1}{(x + bi + j)(y − bi + j)}]_{0≤i,j≤n}

= (−b)^{\binom{n+1}{2}} ∏_{i,j=0}^{n} \frac{1}{(x + bi + j)(y − bi + j)} ∏_{j=1}^{n} j!^{2} ∏_{i=1}^{j}[x − y + (j + i − 1)b][x + y + j + i − 1].

(12)  det [\frac{1}{(x + ai + j)(a + x + ai + j)}]_{0≤i,j≤n}

= \frac{a^{\binom{n+1}{2}}}{(n + 1)!} ∏_{i=0}^{n+1} i!^{2} ∏_{j=0}^{n} \frac{1}{(x + ai + j)}.

(13)  det [\frac{(x + ai + j − 1)!}{(x + r + ai + j)!}]_{0≤i,j≤n}

= a^{\binom{n+1}{2}} ∏_{i=0}^{n} i!^{2}\binom{r + i}{i}\frac{(x + ai − 1)!}{(x + r + ai + n)!}.

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

(14)  det [j!\binom{x + ai + cj}{j}\binom{y − ai + cj}{j}]_{0≤i,j≤n}

= (−a)^{\binom{n+1}{2}} ∏_{j=1}^{n} ∏_{i=1}^{j} [x − y + (i + j − 1)a] .

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

(15)  det [\frac{1}{(r + i + j)(1 + r + i + j)}]_{0≤i,j≤n} = \frac{1}{(n + 1)!} ∏_{i=0}^{n+1} i!^{2} ∏_{j=0}^{n} \frac{1}{(r + i + j)}.

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 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 (Lewis), 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.

Our Maple package DODGSON, combines some of these intermediate steps for the special cases of Hankel and Toeplitz determinants of hypergeometric type. DODGSON is available

at http://www.math.temple.edu/~ zeilberg/tokhniot/DODGSON.

Further Notes:

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

Fact 1: If deg(P (i, j, x) < n,

det[P (i, j, x)]_{0≤i,j≤n} = 0.

Proof: Follows from a rank argument on the first row of the matrix and the linearity assumption, above. □

Fact 2: If in addition, P is of degree n and P (i, j, x) = g(i + j + x), then

det[P (i, j, x)]_{0≤i,j≤n} ≡ constant.

Proof: By embedding the given matrix M_{n}(x) := [P (i, j, x)]_{0≤i,j≤n} into M_{n,0}(x) := [P (i, j, x)]_{0≤i,j≤n+1} and applying Dodgson’s rule, we gather that the determinant f_{n}(x) := det(M_{n}(x)) of the original matrix satisfies

(16)  f_{n}(x)f_{n}(x + 2) = f_{n}(x + 1)^{2},

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. □

Postscript: 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éraud and Gauthier for more efficient guessing. 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.

References

[1] T. Amdeberhan and S. B. Ekhad, A condensed condensation proof of a determianant evaluation conjectured by G. Kuperberg and G. Propp, Jour. Combin. Theory (A) 78 (1) (1997), 169-170.

[2] C. L. Dodgson, Condensation of Determinants, Proc. Royal Soc. London 15 (1866), 150-155.

[3] C. Krattenthaler, Advanced Determinant Calculus, Seminaire Lotharingien Combin 42 The Andrews

   Festschrifft (1999), B42q http://www.mat.univie.ac.at/~slc/wpapers/s42kratt.html.

[4] P. A. MacMahon, Combinatory Analysis, Cambridge University Press, vol. 2, 1916 (reprinted by Chelsea, 1960).

[5] M. Petkovšek, unpublished article.

[6] D. Zeilberger, Reverend Charles to the aid of Major Percy and Fields Medalist Enrico, Amer. Math. Monthly 103 (1996), 501-502.