An alternative evaluation of the Andrews–Burge determinant

C. Krattenthaler^{†}

Dedicated to Gian-Carlo Rota

Abstract. We give a short, self-contained evaluation of the Andrews–Burge determinant (Pacific J. Math. 158 (1994), 1–14).

1. Introduction

In [9, Theorem 1], Andrews and Burge proved a determinant evaluation equivalent to

(1.1) det_{0≤i,j≤n−1} (\binom{x + i + j}{2i − j} + \binom{y + i + j}{2i − j})
= (−1)^{χ(n≡3 mod 4)}2^{\binom{n}{2}+1}

× ∏_{j=1}^{n−1} \frac{(\frac{x+y}{2} + j + 1)_{⌊(j+1)/2⌋} (−\frac{x+y}{2} − 3n + j + \frac{3}{2})_{⌊j/2⌋}}{(j)_{j}} ,

where the shifted factorial (a)_{k} is given by (a)_{k} := a(a + 1) ⋯ (a + k − 1), k ≥ 1, (a)_{0} := 1, and where χ(A)=1 if A is true and χ(A)=0 otherwise. This determinant identity arose in connection with the enumeration of symmetry classes of plane partitions. The known proofs [9, 10] of (1.1) require that one knows (1.1) to hold for x = y. Indeed, the latter was first established by Mills, Robbins and Rumsey [15, p. 53], in turn using another determinant evaluation, due to Andrews [3], whose proof is rather complicated. In the meantime, simpler proofs of the x = y special case of (1.1) were found by Andrews [7], Andrews and Stanton [8], and Petkovšek and Wilf [16]. In this note we describe a new, concise, and self-contained proof of (1.1), see section 3.

Typeset by AMS-TEX

†Supported in part by EC’s Human Capital and Mobility Program, grant CHRX-CT93-0400 and the Austrian Science Foundation FWF, grant P10191-MAT

1991 Mathematics Subject Classification. Primary 15A15; Secondary 05A15, 05A17, 33C20.

Key words and phrases. determinant evaluations, hypergeometric series, enumeration of symmetry classes of plane partitions.

In fact, the main purpose of this note is to popularize the method that I use to prove (1.1) (see section 2 for a description). This method is simple but powerful. Aside from this note, evidence for this claim can be found e.g. in [11, 12, 13, 14]. Thus, the method enlarges the not at all abundant collection of methods for evaluating determinants. In fact, aside from elementary manipulations by row and column operations, we are just aware of one other method, namely Andrews’ “favourite” method of evaluating determinants (cf. [1, 2, 3, 4, 5, 6, 8]), which basically consists of guessing and then proving the LU-factorization of the matrix in question (i.e., the factorization of the matrix into a product of a lower triangular times an upper triangular matrix).

We should, however, also point out a limitation of our method. Namely, in order to be able to apply our method, we need a free parameter occuring in the determinant. (In (1.1) there are even two, x and y.) Andrews’ method, on the other hand, might still be applicable if there is no free parameter present. Still, it is safe to speculate that many more applications of our method are going to be found in the future.

2. The method

The method that I use to prove (1.1) is as follows. Suppose we have a matrix (f_{ij}(x))_{0≤i,j≤n−1} with entries f_{ij}(x) which are polynomials in x, and we want to prove the explicit factorization of det (f_{ij}(x)) as a polynomial in x,

(2.1)  det_{0≤i,j≤n−1} (f_{ij}(x)) = C(n) ∏_{l}(x − a_{l}(n))^{m_{l}(n)},

where C(n), a_{l}(n), m_{l}(n) are independent of x, and the a_{l}(n)’s are pairwise different for fixed n.

Then, in the first step, for each l we find m_{l}(n) linearly independent linear combinations of the columns, or of the rows, which vanish for x = a_{l}(n). In different, but equivalent terms, we find m_{l}(n) linearly independent vectors in the kernel of our matrix evaluated at x = a_{l}(n), i.e., in the kernel of (f_{ij}(a_{l}(n))), or of its transpose. That this really guarantees that (x − a_{l}(n))^{m_{l}(n)} is a factor of the determinant is a fact that might not be well-known enough. Therefore, for the sake of completeness, we state it as a lemma at the end of this section and provide a proof for it.

The finding of a_{l}(n) linearly independent linear combinations of columns or rows which vanish for x = a_{l}(n) (equivalently, linearly independent vectors in the kernel of the matrix, or its transpose, evaluated at x = a_{l}(n)) can be done with some skill (and primarily patience) by setting x = a_{l}(n) in the matrix (f_{ij}(x)), computing tables for the coefficients of the linear combinations for n = 1, 2, … (by solving the respective systems of linear equations on the computer), and finally guessing what the general pattern of the coefficients could be. To prove that the guess is correct, in case of binomial determinants (such as the one in (1.1)) one has to verify certain binomial identities. But this is pure routine today, by means of Zeilberger’s algorithm [18, 19].

Next, in the second step, one checks the degrees of both sides of (2.1) as polynomials in x. If it should happen that the degree of det (f_{ij}(x)) is not larger than ∑_{l} m_{l}(n), the degree of the right-hand side, then it follows by what we did in the first step that the determinant det (f_{ij}(x)) has indeed the form of the right-hand side of (2.1), where C(n) is some unknown constant. This constant can then be determined in the third step by comparison of coefficients of a suitable power of x.

Finally, here is the promised lemma, and its proof.

Lemma. Let A = A(x) be a matrix whose entries are polynomials in x, and u a number. If dim Ker A(u) ≥ k, then u is a root of det A(x) of multiplicity at least k.

Proof. Let v_{1}, v_{2}, …, v_{k} be k linearly independent (column) vectors in the kernel of A(u). Without loss of generality, we may assume that v_{1}, v_{2}, …, v_{k} are such that the matrix [v_{1}, v_{2}, …, v_{k}], formed by gluing the columns v_{1}, v_{2}, …, v_{k} to a matrix, is in column-echelon form. In addition, again without loss of generality, we may assume that for any i = 1, 2, …, k the vector v_{i} is of the form v_{i} = (0, …, 0, 1, …)^{t}, i.e., the first i − 1 entries are 0, the i-th entry is 1, and the remaining entries could be anything. (To justify “without loss of generality” one would possibly have to permute the columns of A.)

Now we consider the matrix Ã = Ã(x), formed by replacing for i = 1, 2, …, k the i-th column of A by the column Av_{i}. It is an easy observation that Ã and A are related by elementary column operations. Therefore, their determinants are the same. On the other hand, the i-th column of Ã(u) is A(u)v_{i} = 0, for any i = 1, 2, …, k. Hence, each entry of Av_{i}, being a polynomial in x, must be divisible by (x − u). Therefore, in the determinant det Ã, we may take (x − u) out of the i-th column, i = 1, 2, …, k, with the entries in the remaining determinant still being polynomials in x. This proves that (x − u)^{k} divides det Ã = det A, and, thus, the lemma. ■

3. Proof of (1.1)

As announced in the previous section, the proof consists of three steps. For convenience, let us denote the determinant in (1.1) by AB(x, y; n), or sometimes just AB(n) for short.

Step 1. Identification of the factors. We show that the product on the right-hand side of (1.1),

∏_{j=1}^{n−1} (\frac{x+y}{2} + j + 1)_{⌊(j+1)/2⌋} (−\frac{x+y}{2} − 3n + j + \frac{3}{2})_{⌊j/2⌋},

is indeed a factor of AB(n), in the way that was described in section 2. Let us first consider just one part of this product,

∏_{j=1}^{n−1} ((x + y)/2 + j + 1)_{⌊(j+1)/2⌋} .

Let us concentrate on a typical factor (x + y + 2j + 2l), 1 ≤ j ≤ n − 1, 1 ≤ l ≤ (j + 1)/2. We claim that for each such factor there is a linear combination of the columns that vanishes if the factor vanishes. More precisely, we claim that for any j, l with 1 ≤ j ≤ n − 1, 1 ≤ l ≤ (j + 1)/2 there holds

(3.1) ∑_{s=2l−1}^{⌊(j+2l−1)/2⌋} \frac{(j − 2l + 1)}{(j − s)} \frac{(j + 2l − 2s)_{s−2l+1}}{(s − 2l + 1)!}
· (column s of AB(−y − 2j − 2l, y; n))

+ (column j of AB(−y − 2j − 2l, y; n)) = 0.

To avoid confusion, for j = 2l − 1 it is understood by convention that the sum in the first line of (3.1) vanishes.

To establish the claim, we have to check

(3.2) ∑_{s=2l−1}^{⌊(j+2l−1)/2⌋} \frac{(j − 2l + 1)}{(j − s)} \frac{(j + 2l − 2s)_{s−2l+1}}{(s − 2l + 1)!}

· (\binom{−y − 2j − 2l + i + s}{2i − s} + \binom{y + i + s}{2i − s})

+ (\binom{−y − j − 2l + i}{2i − j} + \binom{y + i + j}{2i − j}) = 0.

The exceptional case j = 2l − 1 can be treated immediately. By assumption the sum in the first line of (3.2) vanishes for j = 2l −1, and, by inspection, also the last line in (3.2) vanishes for j = 2l − 1. So we are left with establishing (3.2) for l ≤ j/2. In terms of the usual hypergeometric notation

rF_{s}[ \begin{matrix}a_{1}, …, a_{r} \\ b_{1}, …, b_{s} \end{matrix}; z] = ∑_{k=0}^{∞} \frac{(a_{1})_{k} ⋯ (a_{r})_{k}}{k! (b_{1})_{k} ⋯ (b_{s})_{k}} z^{k} ,

this means to check

(3.3) \frac{(−1 − i − 2j + 2l − y)_{1+2i−2l}}{(1 + 2i − 2l)!}

×_{4}F_{3}[ \begin{matrix}−\frac{1}{2} − \frac{j}{2} + l, −\frac{j}{2} + l, −1 − 2i + 2l, i − 2j − y \\ −j + 2l, −\frac{1}{2} − \frac{i}{2} − j + l − \frac{y}{2} , −\frac{i}{2} − j + l − \frac{y}{2} \end{matrix} ; 1]

+ \frac{(−1 − i + 4l + y)_{1+2i−2l}}{(1 + 2i − 2l)!}_{4}F_{3}[ \begin{matrix}−\frac{1}{2} − \frac{j}{2} + l, −\frac{j}{2} + l, −1 − 2i + 2l, i + 2l + y \\ −j + 2l, −\frac{1}{2} − \frac{i}{2} + 2l + \frac{y}{2} , −\frac{i}{2} + 2l + \frac{y}{2} \end{matrix} ; 1]

+ (\binom{−y − j − 2l + i}{2i − j} + \binom{y + i + j}{2i − j}) = 0,

for 1 ≤ j ≤ n − 1, 1 ≤ l ≤ j/2. This identity can be proved routinely by means of Zeilberger’s algorithm [18, 19] and Salvy and Zimmermann’s Maple package GFUN [17]. However, it happens that a _{4}F_{3}-summation is already known that applies to both _{4}F_{3}-series in (3.3), namely Lemma 1 in [9]. (Here we need the assumption l ≤ j/2.) Little simplification then establishes (3.3) and hence the claim. Thus, ∏_{j=1}^{n−1} ((x + y)/2 + j + 1)_{⌊(j+1)/2⌋} is a factor of AB(n).

Now we prove that

∏_{j=2}^{n−1} (−(x + y)/2 − 3n + j + \frac{3}{2})_{⌊j/2⌋}

is a factor of AB(n). Also here, let us concentrate on a typical factor (x + y + 6n − 2j − 2l − 1), 2 ≤ j ≤ n − 1, 1 ≤ l ≤ j/2. This time we claim that for each such factor there is a linear combination of the columns that vanishes if the factor vanishes. More precisely, we claim that for any j, l with 2 ≤ j ≤ n − 1, 1 ≤ l ≤ j/2 there holds

∑_{s=1}^{n−l} \frac{(2n − j − s)_{j−2l}}{(n + l − j)_{j−2l}} \frac{(s)_{n−l−s} (3n + l − 2j − 2)_{n−l−s}}{4^{n−l−s} (n − l − s)! (2n − j − \frac{1}{2})_{n−l−s}}

· (column s of AB(−y − 6n + 2j + 2l + 1, y; n)) = 0.

This means to check

∑_{s=1}^{n−l} \frac{(2n − j − s)_{j−2l}}{(n + l − j)_{j−2l}} \frac{(s)_{n−l−s} (3n + l − 2j − 2)_{n−l−s}}{4^{n−l−s} (n − l − s)! (2n − j − \frac{1}{2})_{n−l−s}}

· (\binom{−y − 6n + 2j + 2l + 1 + i + s}{2i − s} + \binom{y + i + s}{2i − s}) = 0

Converting this into hypergeometric notation and cancelling some factors, we see that we have to check

(3.4) (4 − i + 2j + 2l − 6n − y)_{2i−1}

×_{5}F_{4}[ \begin{matrix}1 − 2i, \frac{5}{2} + j + l − 3n, 2 + j − 2n, \\ 4 + 2j − 4n, 2 + 2l − 2n, 2 − \frac{i}{2} + j + l − 3n − \frac{y}{2} , \end{matrix}

\begin{matrix}1 + l − n, 3 + i + 2j + 2l − 6n − y \\ \frac{5}{2} − \frac{i}{2} + j + l − 3n − \frac{y}{2} \end{matrix} ; 1]

= −(3 − i + y)_{2i−1}

×_{5}F_{4}[ \begin{matrix}1 − 2i, \frac{5}{2} + j + l − 3n, 2 + j − 2n, 1 + l − n, 2 + i + y \\ 4 + 2j − 4n, 2 + 2l − 2n, \frac{3}{2} − \frac{i}{2} + \frac{y}{2} , 2 − \frac{i}{2} + \frac{y}{2} \end{matrix} ; 1]

Again, in view of Zeilberger’s algorithm, this is pure routine. However, also this identity happens to be already in the literature. It is exactly identity (5.7) in [8], with a = \frac{3}{2} − i + j + l − 3n − y, x = \frac{3}{2} + j + l − 3n, z = 1 + j − 2n, p = 2i − 1. Thus, ∏_{j=2}^{n−1} (−(x + y)/2 − 3n + j + \frac{3}{2})_{⌊j/2⌋} is a factor of AB(n).

Step 2. Bounding the polynomial degrees. The degree of AB(n) as a polynomial in x is obviously at most \binom{n}{2}. But the degree of the product on the right-hand side of (1.1) is exactly \binom{n}{2}. Therefore it follows that

(3.5) det_{0≤i,j≤n−1} (\binom{x + i + j}{2i − j} + \binom{y + i + j}{2i − j})

= C(n) ∏_{j=1}^{n−1} (\frac{x+y}{2} + j + 1)_{⌊(j+1)/2⌋} (−\frac{x+y}{2} − 3n + j + \frac{3}{2})_{⌊j/2⌋},

with some C(n) independent of x, and, by symmetry, also independent of y.

Step 3. Determining the constant. To compute C(n), on both sides of (3.5) set y = x and then compare coefficients of x^{\binom{n}{2}}. On the right-hand side the coefficient is (−1)^{χ(n≡3 mod 4)}C(n), whereas on the left-hand side the coefficient is

det_{0≤i,j≤n−1} (2\frac{1}{(2i − j)!}) = 2^{n} ∏_{i=0}^{n−1} \frac{1}{(2i)!} det_{0≤i,j≤n−1} ((2i − j + 1)_{j})

= 2^{n} ∏_{i=0}^{n−1} \frac{1}{(2i)!} det_{0≤i,j≤n−1} ((2i)^{j})

= 2^{n} ∏_{i=0}^{n−1} \frac{1}{(2i)!} ∏_{0≤i<j≤n−1}(2j − 2i)

= 2^{n+\binom{n}{2}} ∏_{i=0}^{n−1} \frac{i!}{(2i)!}

= 2^{1+\binom{n}{2}} ∏_{i=1}^{n−1} \frac{1}{(i)_{i}} ,

where in the step from the first to the second line we used elementary column operations, and the subsequent step is just the Vandermonde determinant evaluation.

This completes the proof of (1.1). ■

References

[1] G. E. Andrews, Plane partitions (II): The equivalence of the Bender–Knuth and the MacMahon conjectures, Pacific J. Math. 72 (1977), 283–291.

[2] G. E. Andrews, Plane partitions (I): The MacMahon conjecture, in: Studies in Foundations and Combinatorics, G.-C. Rota (ed.), Adv. in Math. Suppl. Studies, Vol. 1, 1978, 131–150.

[3] G. E. Andrews, Plane partitions (III): The weak Macdonald conjecture, Inventiones Math. 53 (1979), 193–225.

[4] G. E. Andrews, Macdonald’s conjecture and descending plane partitions, in: Combinatorics, representation theory and statistical methods in groups, Young Day Proceedings, T. V. Narayana, R. M. Mathsen, J. G. Williams (eds.), Lecture Notes in Pure Math., vol. 57, Marcel Dekker, New York, Basel, 1980, 91–106.

[5] G. E. Andrews, Plane partitions (IV): A conjecture of Mills–Robbins– Rumsey, Aequationes Math. 33 (1987), 230–250.

[6] G. E. Andrews, Plane partitions V: The t.s.s.c.p.p. conjecture, J. Combin. Theory Ser. A 66 (1994), 28–39.

[7] G. E. Andrews, Pfaff’s method (I): The Mills–Robbins–Rumsey determinant, preprint.

[8] G. E. Andrews and D. W. Stanton, Determinants in plane partition enumeration, preprint.

[9] G. E. Andrews and W. H. Burge, Determinant identities, Pacific J. Math. 158 (1993), 1–14.

[10] I. P. Goulden and D. M. Jackson, Further determinants with the averaging property of Andrews–Burge, J. Combin. Theory Ser. A 73 (1996), 368–375.

[11] C. Krattenthaler, Determinant identities and a generalization of the number of totally symmetric self-complementary plane partitions, Elect. J. Combin. (to appear).

[12] C. Krattenthaler, Some q-analogues of determinant identities which arose in plane partition enumeration, Séminaire Lotharingien Combin. (to appear).

[13] C. Krattenthaler, A new proof of the MRR-conjecture — including a generalization, preprint.

[14] G. Kuperberg, Another proof of the alternating sign matrix conjecture, Math. Research Letters (1996), 139–150.

[15] W. H. Mills, D. H. Robbins and H. Rumsey, Enumeration of a symmetry class of plane partitions, Discrete Math. 67 (1987), 43–55.

[16] M. Petkovšek and H. Wilf, A high-tech proof of the Mills-Robbins-Rumsey determinant formula, Elect. J. Combin. 3 (no. 2, “The Foata Festschrift”) (1996), #R19, 3 pp.

[17] B. Salvy and P. Zimmermann, GFUN — A MAPLE package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math. Software 20 (1994), 163–177.

[18] D. Zeilberger, A fast algorithm for proving terminating hypergeometric identities, Discrete Math. 80 (1990), 207–211.

[19] D. Zeilberger, The method of creative telescoping, J. Symbolic Comput. 11 (1991), 195–204.

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria. e-mail: KRATT@Pap.Univie.Ac.At 8 C. Krattenthaler

WWW: http://radon.mat.univie.ac.at/People/kratt