A CONDENSED CONDENSATION PROOF OF A DETERMINANT EVALUATION CONJECTURED BY Greg KUPERBERG AND Jim PROPP

Tewodros AMDEBERHAN^{1} and Shalosh B. EKHAD^{1}

Greg Kuperberg and Jim Propp [P] have conjectured the following determinant identity:

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

where a!! := 0! · 1! · 2! ⋯ a!, and a! := 1 · 2 ⋯ a.

This is the special case (m = n, a = b = 0) of

det [\binom{i + j + a + b}{i + a}\binom{2n − i − j − a − b}{n − i − a}_{0≤i,j≤m}] =

\frac{(a + b)!(2n + 1)!^{m+1}(2n − m)!!m!!(m + a + b)!!(2n − m − a − b)!!a!!b!!(n − m − a − 1)!!(n − m − b − 1)!!}{a!b!(2n + 1)!!(n − a)!!(n − b)!!(m + a)!!(m + b)!!(a + b)!!(2n − 2m − a − b − 1)!!} ,

(Rabbit)

which follows immediately from Dodgson’s[D] rule for evaluating determinants: (For any n × n matrix A, let A_{r}(k, l) be the r × r connected submatrix whose upper leftmost corner is the entry a_{k,l},)

det A = \frac{det A_{n−1}(1, 1) det A_{n−1}(2, 2) − det A_{n−1}(1, 2) det A_{n−1}(2, 1)}{det A_{n−2}(2, 2)} .  (Lewis)

Indeed, let the left and right sides of (Rabbit) be L_{m}(a, b) and R_{m}(a, b) respectively. Dodgson’s rule immediately implies that the recurrence:

X_{m}(a, b) = \frac{X_{m−1}(a, b)X_{m−1}(a + 1, b + 1) − X_{m−1}(a + 1, b)X_{m−1}(a, b + 1)}{X_{m−2}(a + 1, b + 1)} ,

holds with X = L. Since L_{m}(a, b) = R_{m}(a, b) for m = 0, 1 (check!), and the recurrence also holds with X = R (check!^{2} ), it follows by induction that L_{m}(a, b) = R_{m}(a, b) for all m. .

The present proof is in the spirit of [Z1]. Another proof can be found in [A1]. The same method yields a q-analog of (Rabbit), that can be found in [A2]. A beautiful combinatorial proof of (Lewis) can be found in [Z2]. An alternative proof of (Rabbit) is given in [K].

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. E-mail:[tewodros,ekhad]@math.temple.edu;

WWW: http://www.math.temple.edu/~[tewodros,ekhad] .

2 Divide both sides by the left, then use r!!/(r-1)!!=r! whenever possible, and then r!/(r-1)!=r whenever possible,

reducing it to a completely routine polynomial identity. The small Maple package rabbit obtainable from our Home Pages, performs these steps mechanically.

References

[A1] T. Amdeberhan, A WZ proof of a determinant evaluation conjectured by Kuperberg and Propp, exclusively published in Amdeberhan’s Home Page http://www.math.temple.edu/~tewodros.

[A2] T. Amdeberhan, A q-generalization of a determinant evaluation conjectured by Kuperberg and Propp, exclusively published in Amdeberhan’s Home Page http://www.math.temple.edu/~tewodros.

[D] C.L. Dodgson, Condensation of Determinants, Proceedings of the Royal Society of London 15(1866), 150-155.

[K] C. Krattenthaler, E-mail message to T. Amdeberhan, dated 9 Aug. 1996, 19 : 22 : 27 + 0100 (MET). By kind permission of Krattenthaler, it can be gleaned at the first author’s Home Page

http://www.math.temple.edu/~tewodros.

[P] J. Propp, E-mail message to D. Zeilberger, dated 1 July 1996, 15:47:56 (EDT). By kind permission of Propp, it can be gleaned at the first author’s Home Page http://www.math.temple.edu/~tewodros.

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

[Z2] D. Zeilberger, Dodgson’s determinant-evaluation rule proved by Two-Timing Men and Women, to appear in the Elec. J. of Combinatorics [Wilf Festschrifft volume]. It can be downloaded from

Zeilberger’s Home Page: http://www.math.temple.edu/~zeilberg.

Version of Sept. 4, 1996. First version: Aug. 2, 1996.