YAY FOR DETERMINANTS!

TEWODROS AMDEBERHAN, CHRISTOPH KOUTSCHAN, AND DORON ZEILBERGER

Abstract. In this case study, we hope to show why Sheldon Axler was not just wrong, but wrong, when he urged, in 1995: “Down with Determinants!”. We first recall how determinants are useful in enumerative combinatorics, and then illustrate three versatile tools (Dodgson’s condensation, the holonomic ansatz and constant term evaluations) to operate in tandem to prove a certain intriguing determinantal formula conjectured by the first author. We conclude with a postscript describing yet another, much more efficient, method for evaluating determinants: ‘ask determinant-guru, Christian Krattenthaler’, but advise people only to use it as a last resort, since if we would have used this last method right away, we would not have had the fun of doing it all by ourselves.

Dedicated to Maestro^{1} Christian Krattenthaler (b. 8 Oct., 1958) on his millionth-and-one birthday.

“Philosophers and psychiatrists should explain why it is that we mathematicians are in the habit of systematically erasing our footsteps. Scientists have always looked askance at this strange habit of mathematicians, which has changed little from Pythagoras to our day”. –Gian-Carlo Rota.^{2}

1. The Joy of Determinants

In 1995, Sheldon Axler published an article [2] with a very catchy title (that being determinantal lovers, we love to hate): ‘Down with Determinants!’ This admittedly well-written paper was well received and even won the prestigious Lester Ford award for that year. Let’s quote the first paragraph.

“Ask anyone why a square matrix of complex numbers has an eigenvalue, and you’ll probably get the wrong answer, which goes something like this: The characteristic polynomial of the matrix—which is defined via determinants—has a root (by the fundamental theorem of algebra); this root is an eigenvalue of the matrix. What’s wrong with that answer? It depends upon determinants, that’s what. Determinants are difficult, non-intuitive, and often defined without motivation. As we’ll see, there is a better proof—one that is simpler, clearer, provides more insight, and avoids determinants.”

Axler then goes on to describe a determinant-less approach to linear algebra, that while very elegant, is not to our liking. It is way too abstract for our taste. We believe that one of the ills of undergraduate mathematics instruction is excess abstraction. We love determinants because they are so concrete.

1in piano, determinants, and hypergeometrics, inter alia.

2Two Turning Points in Invariant Theory, Math. Intell. 21(1) (Winter 1999), p. 26.

In our humble opinion, determinants are easy, intuitive, and can be easily defined with great motivation. In fact, it is a straightforward extension of the good-old factorial function n!. Recall that n! counts the number of permutations of the set {1, …, n}. In other words

n! = ∑_{π∈S_{n}} 1 .

Now for any permutation π = (π_{1}, …, π_{n}) define a weight

Weight(π) : = sign(π) a_{1,π_{1}} ⋯ a_{n,π_{n}} ,

and then the determinant is simply the weight-enumerator of the symmetric group:

det(a_{ij}) = ∑_{π∈S_{n}} Weight(π) .

Note that our definition is combinatorial, and indeed they come up so often in tough enumeration problems, where it is already a challenge to express the quantity of interest as an explicit (symbolic) determinant, and then an often bigger challenge is to evaluate it in closed form. In this case study we will discuss various ways to tackle such determinants, by focusing on one ‘hard nut’ that came up in MathOverflow.

2. An Intriguing Determinant

The discussion in this article is motivated by a question on MathOverflow [4] posed by Johann Cigler wherein he asked for a simple direct proof of

det A_{n,m} := det [\binom{2m}{j − i + m} − \binom{2m}{m − i − j − 1}]_{i,j=0}^{n−1} = ∏_{i≤j}^{1,m−1} \frac{2n + i + j}{i + j} .

The expression on the right-hand side of the identity is connected to a host of interesting combinatorial interpretations (see references [9], [10], [8], [19] and [20]). Our journey began with a generalization (true to Pólya’s dictum: generalize to trivialize). Introduce a new parameter x and a matrix given by

T_{n,m}(x) : = [\binom{x + m}{j − i + m} − \binom{x + m}{m − i − j − 1}]_{i,j=0}^{n−1} .

After enough experimentation, we managed to guess a closed-form evaluation for its determinant.

Conjecture 1. We have

det T_{n,m}(x) = ∏_{i=1}^{n} ∏_{j=1}^{m} \frac{(x + i − j)(x + 2i + j − 2)}{(x + 2i − j)(i + j − 1)}.

None of our initial attempts at proving this claim worked.

Remark 1. In the meantime, we made the following curious observation. If

φ_{n}(y) := \frac{(1 + y^{n} − y^{n+1} + y^{2n})(1 − y^{n})^{2}}{y^{n−1}(1 + y)(1 − y)^{2}} ∈ ℤ[y, y^{−1}]

then

det T_{n,n}(x) = n!^{−n} ∏_{i=0}^{n−1} \binom{n + i}{i}^{−1} · ∏_{s=1−n}^{3n−2}(x + s)^{CT_{y}(y^{−s}φ_{n}(y))};

where CT_{y} F (y) denotes the constant term of a Laurent polynomial F (y).

3. Enter Dodgson

A relatively simple choice for conjecturing and proving explicit determinant evaluations is a method inspired by Dodgson’s condensation [22], that goes back to Jacobi and Desanot, and popularized by the Reverend Charles L. Dodgson (aka Lewis Caroll). However, det T_{n,m}(x) did not yield to this at all. It was necessary to change the approach. Our first breakthrough was realized in the form of discovering a new matrix

D_{n}(a, b) : = [\binom{2i + 2a}{i − j + a − b} − \binom{2i + 2a}{i − j + a − b − 1}]_{i,j=0}^{n−1}

which, happily, is amenable to the present technique.

Theorem 3.1. We have the determinantal evaluation

det D_{n}(a, b) = ∏_{i=1}^{n} ∏_{j=1}^{a−b} \frac{(a + b + i − j)(a + b + 2i + j − 2)}{(a + b + 2i − j)(i + j − 1)}.

Proof. Denoting the determinant by M_{n}(a, b), Dodgson’s condensation states that

M_{n}(a, b) = \frac{M_{n−1}(a, b)M_{n−1}(a + 1, b + 1) − M_{n−1}(a + 1, b)M_{n−1}(a, b + 1)}{M_{n−2}(a + 1, b + 1)}.

Therefore, we only need to verify (routinely) that the right-hand side does the same. To conclude, simply check both sides agree, say, when n = 1 and n = 2. □

For reasons that will become clearer soon, let’s reformulate the above result.

Corollary 3.2. We have

det B_{n,m}(x) : = det [\binom{x + m + 2i}{i − j + m} − \binom{x + m + 2i}{i − j + m − 1}]_{i,j=0}^{n−1}

= ∏_{i=1}^{n} ∏_{j=1}^{m} \frac{(x + i − j)(x + 2i + j − 2)}{(x + 2i − j)(i + j − 1)}.

Proof. This follows from Theorem 3.1 with a = \frac{x+m}{2} and b = \frac{x−m}{2} in D_{n}(a, b). □

Note that the right hand sides of the (already proved!) Corollary 3.2 and the (still unproved) Conjecture 1 are the same, but why is it useful? We will see in the next section that the left hand sides are the same, and, hence Conjecture 1 would follow from the transitivity of the = relation: A = B and B = C ⇒ A = C. This method was famously used by one of us (DZ) to prove the Mills-Robbins-Rumsey alternating sign matrix conjecture [26] (see also [3]). In that article the author first found a (complicated) constant term expression for the desired quantity (the number of alternating sign matrices) and another (almost as complicated) constant term expression for another quantity (totally symmetric self-complementary plane partitions), already proved by guru George Andrews to be equal to the desired expression. He then worked very hard to prove that these two constant term expressions are the same, and finally, by taking afree ride from Andrews’ previously proved enumeration, and using the above ‘transitivity of =’, gave the first proof of this notorious conjecture. In the next section we will use this methodology, but things will be much simpler, since we will prove that the left sides of Conjecture 1 and Corollary 3.2 are given by the same constant-term expression, so unlike [26], we will not have to work hard to prove that A = B, since A is exactly B.

4. Enter Constant Term Evaluations

As promised at the end of the last section, in this section, we describe the connection between the two matrices B_{n,m}(x) and T_{n,m}(x) from the preceding sections.

Theorem 4.1. It holds true that det T_{n,m}(x) = det B_{n,m}(x), and hence so does Conjecture 1.

Proof. Denote the constant term of the Laurent series expansion of F (t) by CT_{t}F. In view of this, the entries of T_{n,m}(x) can be expressed as a constant term:

\binom{x + m}{j − i + m} − \binom{x + m}{m − i − j − 1} = CT_{t} (1 + \frac{1}{t})^{x+m} t^{m}(t^{j−i} − t^{−i−j−1}).

The entries in the i^{th} row of the matrix T_{n,m}(x) are (we need a different variable for each row, let’s call it t_{i} - this does not change the values)

CT_{t_{i}} (1 + \frac{1}{t_{i}} )^{x+m} t_{i}^{m}(t_{i}^{j−i} − t_{i}^{−i−j−1}).

Let t⃗ = (t_{0}, t_{1}, …, t_{n−1}). We apply multi-linearity of determinants to obtain

det T_{n,m}(x) = det [CT_{t_{i}} (1 + \frac{1}{t_{i}} )^{x+m} t_{i}^{m−i} (t_{i}^{j} − t_{i}^{−j−1})]

= CTt⃗ [∏_{i=0}^{n−1} (1 + t_{i})^{x+m} · t_{i}^{−x−i− \frac{1}{2}} · det (t_{i}^{j+ \frac{1}{2}} − t_{i}^{−j− \frac{1}{2}} )]

= CTt⃗ [∏_{i=0}^{n−1} \frac{(1 + t_{i})^{x+m}(t_{i} − 1)}{t_{i}^{x+n+i}} · ∏_{i<j}^{0,n−1}(t_{i} − t_{j})(1 − t_{i}t_{j})];

where we have utilized [14, Lemma 2]. Let us symmetrize the right-hand side (by averaging over the images of the symmetric group 𝔖_{n}, using the fact that the functional CT is unaffected by permuting the variables, since a constant is always a constant, this was called the Stanton-Stembridge trick in [26]). Note that only the product of two factors ∏_{i=0}^{n−1} t_{i}^{−i} · ∏_{i<j}(t_{i} − t_{j}) will be impacted to introduce a new Vandermonde:

det T_{n,m}(x)

= \frac{1}{n!} CTt⃗ \{∏_{i=0}^{n−1} [\frac{(1 + t_{i})^{x+m}(t_{i} − 1)}{t_{i}^{x+n}}] · ∏_{i<j}^{0,n−1}(t_{i} − t_{j})(t_{j}^{−1} − t_{i}^{−1})(1 − t_{i}t_{j})\}

= \frac{1}{n!} CTt⃗ \{∏_{i=0}^{n−1} [\frac{(1 + t_{i})^{x+m}(t_{i} − 1)}{t_{i}^{x+2n−1}}] · ∏_{i<j}^{0,n−1}(t_{i} − t_{j})^{2}(1 − t_{i}t_{j})\} .

Now, repeat the constant term extraction on the determinant from the previous section. The outcome of this procedure is:

det B_{n,m}(x)

= det [CT_{t_{i}} (1 + \frac{1}{t_{i}} )^{x+m+2i} t_{i}^{m}(t_{i}^{i−j} − t_{i}^{i−j−1})]

= CTt⃗ \{∏_{i=0}^{n−1} [(1 + \frac{1}{t_{i}} )^{x+m+2i} t_{i}^{m+i−1}(t_{i} − 1)] ∏_{i<j}^{0,n−1}(t_{j}^{−1} − t_{i}^{−1})\}

= CTt⃗ \{∏_{i=0}^{n−1} [\frac{(1 + t_{i})^{x+m}(t_{i} − 1)}{t_{i}^{x+n}}] (2 + t_{i} + t_{i}^{−1})^{i} ∏_{i<j}^{0,n−1}(t_{i} − t_{j})\}

= \frac{1}{n!} CTt⃗ \{∏_{i=0}^{n−1} [\frac{(1 + t_{i})^{x+m}(t_{i} − 1)}{t_{i}^{x+n}}] ∏_{i<j}^{0,n−1}(t_{i} − t_{j}) (t_{j} + t_{j}^{−1} − t_{i} − t_{i}^{−1})\}

= \frac{1}{n!} CTt⃗ \{∏_{i=0}^{n−1} [\frac{(1 + t_{i})^{x+m}(t_{i} − 1)}{t_{i}^{x+2n−1}}] ∏_{i<j}^{0,n−1}(t_{i} − t_{j})^{2}(1 − t_{i}t_{j})\} .

Based on our analysis shown above, both determinants det T_{n,m}(x) and det B_{n,m}(x) are equal to the same constant term

\frac{1}{n!} CTt⃗ \{∏_{i=0}^{n−1} [(1 + t_{i})^{x+m}(t_{i} − 1)t_{i}^{−x−2n+1}] ∏_{i<j}^{0,n−1}(t_{i} − t_{j})^{2}(1 − t_{i}t_{j})\} .

Hence det T_{n,m}(x) and det B_{n,m}(x) must be equal to each other, as claimed. □

In particular, we thus recover the determinant of Cigler as stated in Section 1:

Corollary 4.2. (The case x = m) We have

det [\binom{2m}{j − i + m} − \binom{2m}{m − i − j − 1}]_{i,j=0}^{n−1} = ∏_{1≤i≤j≤m−1} \frac{2n + i + j}{i + j} .

Proof. The specialization x = m in the formula for det T_{n,m}(x) results in

det T_{n,m}(m) = ∏_{1≤i≤j≤m−1} \frac{2n + i + j}{i + j}

after some simplification, which is det A_{n,m}. □

In addition, we believe to have uncovered a new constant term evaluation which appears not to fit any of the existing formulas in the literature.

Corollary 4.3. We have

CTt⃗ \{∏_{i=0}^{n−1} [\frac{(1 + t_{i})^{x+m}(t_{i} − 1)}{t_{i}^{x+2n−1}}] ∏_{i<j}^{0,n−1}(t_{i} − t_{j})^{2}(1 − t_{i}t_{j})\}

= n! · ∏_{i=1}^{n} ∏_{j=1}^{m} \frac{(x + i − j)(x + 2i + j − 2)}{(x + 2i − j)(i + j − 1)}.

Proof. This is a consequence of Corollary 3.2 and the proof of Theorem 4.1. □

5. Enter the Holonomic Ansatz

In this section, we use an automated method called the holonomic ansatz due to the third author [24], and extended by the second author and collaborators [5, 11, 13] to discover and prove many new deep determinant identities, which will provide yet another proof of Conjecture 1. Note: we also reindex 1 ≤ i, j ≤ n instead of 0 ≤ i, j ≤ n − 1. Let us recall the matrix A_{n} := A_{n}(m, x) := (a_{i,j})_{1≤i,j≤n} whose entries a_{i,j} are given as follows:

a_{i,j} := a_{i,j}(m, x) := \binom{m + x}{m − i + j} − \binom{m + x}{m − i − j + 1}.

Denote by A_{n}^{(i,j)} the matrix A_{n} with the i^{th}-row and the j^{th}-column being removed. Then we define

(1)  c_{n,j} := c_{n,j}(m, x) := (−1)^{n+j} \frac{det A_{n}^{(n,j)}}{det A_{n−1}} .

Employing an ansatz with undetermined coefficients (“guessing”), we find plausible recurrence relations that are conjecturally satisfied by the sequence c_{n,j}, which suggest that it is holonomic with rank 2:

j(j − n − 1)(m + n)(2n + x − 1)(2n + x)c_{n+1,j}+
(2j − 1)n(j − m)(2n + x)(j − n − x + 1)c_{n,j+1}+
n(j + n + x − 1)(4j^{2}n − (m^{2} + 4n^{2} − m)j
− 2mn + (2j^{2} − 4jn − m)x − jx^{2})c_{n,j} = 0, and
j(j − m + 1)(j + n + 1)(j − n − x + 2)c_{n,j+2}
+ (2j^{4} + 4j^{3} − j^{2}m^{2} − 2j^{2}n^{2} − 2j^{2}nx + 2j^{2}n − j^{2}x^{2} + 2j^{2}x + 2j^{2} − jm^{2}
− 2jn^{2} − 2jnx + 2jn − jx^{2} + 2jx − mn^{2} − mnx + mn)c_{n,j+1}
+ (j + 1)(j + m)(j − n)(j + n + x − 1)c_{n,j} = 0.

For the purpose of guessing, one has to evaluate c_{n,j} for concrete values of n and j; in this particular example it suffices to consider 1 ≤ j ≤ n ≤ 15. For a concrete integer n, the vector (c_{n,j})_{1≤j≤n} can be determined by computing the kernel of the matrix (a_{i,j})_{1≤i<n,1≤j≤n}. Note that this kernel computation appears to be challenging, because the matrix entries are not rational functions in the parameters m and x. To overcome this problem, and also for efficiency reasons, we employ the evaluation-interpolation technique: when m and x are substituted by concrete integers, then the matrix entries turn into integers, and the recurrences for c_{n,j} can be easily guessed. Performing the same computation for different choices of m and x allows one to reconstruct recurrences with symbolic m and x, as given above. The shape of the above recurrences, i.e., their support and their leading coefficients, implies that the following three initial conditions are sufficient to define a unique bivariate sequence: c_{1,1} = 1, c_{1,2} = 0, c_{2,2} = 1. From now on, let c_{n,j} denote this unique bivariate sequence that is defined by unrolling the recurrences, starting from the given initial conditions. We want to prove that this conjectured definition of c_{n,j} agrees with its original definition (1). For this purpose it suffices to establish the two identities:

(2)  c_{n,n} = 1  (n ≥ 1),
(3)  ∑_{j=1}^{n} a_{i,j}c_{n,j} = 0  (1 ≤ i < n),

which can be achieved by holonomic closure properties and creative telescoping, respectively. We use the Mathematica package HolonomicFunctions [12]. Observe that the closure property “integer-linear substitution” implies that c_{n,n} satisfies a univariate recurrence of order at most 2. We compute this recurrence and show that it admits a constant solution. Then the two initial values c_{1,1} = c_{2,2} = 1 imply that c_{n,n} = 1 for all n ≥ 1. In order to prove (3), we split the sum into two parts:

s_{i,n} := ∑_{j=1}^{n} a_{i,j}c_{n,j} = ∑_{j=1}^{n} \binom{m + x}{m − i + j}c_{n,j} − ∑_{j=1}^{n} \binom{m + x}{m − i − j + 1}c_{n,j}.

Now creative telescoping can be employed to derive a set of recurrences for each of the sums on the right-hand side, which can be combined to a set of recurrences that is satisfied by the whole expression s_{i,n}. These computations are far from trivial (it took about two hours of CPU time) and the recurrences are too big to be displayed here. It can easily be checked that s_{i,n} = 0 for a few concrete small integers i and n, and the computed recurrences then imply that s_{i,n} = 0 for all 1 ≤ i < n. Finally, we investigate the sum

t_{n} := t_{n}(m, x) := ∑_{j=1}^{n} a_{n,j}c_{n,j} = ∑_{j=1}^{n} \binom{m + x}{m − n + j}c_{n,j} − ∑_{j=1}^{n} \binom{m + x}{m − n − j + 1}c_{n,j}.

Another two applications of creative telescoping exhibit that both sums on the right-hand side satisfy the same recurrence, which therefore is also valid for their difference t_{n}:

(m + n)(2n + x − 1)(2n + x + 1)(2n + x)^{2}(m − n − x)t_{n+1}

+ n(n + x)(m − 2n − x − 1)(m − 2n − x)(m + 2n + x − 1)(m + 2n + x)t_{n} = 0.

Since this is a first-order recurrence, a closed form for t_{n} is immediately obtained in terms of Euler’s gamma function:

t_{n} = \frac{Γ(n) Γ(n + x) Γ(2n + x − m) Γ(2n + x + m − 1)}{Γ(n + m) Γ(n + x − m) Γ(2n + x) Γ(2n + x − 1)}.

From the definition (1) of c_{n,j} it follows that

t_{n} = \frac{det A_{n}}{det A_{n−1}} ,

which yields the desired closed form of our determinant:

det A_{n} = ∏_{i=1}^{n} t_{i} = ∏_{i=1}^{n} ∏_{j=1}^{m} \frac{t_{i}(j, x)}{t_{i}(j − 1, x)} = ∏_{i=1}^{n} ∏_{j=1}^{m} \frac{(x + i − j)(x + 2i + j − 2)}{(x + 2i − j)(i + j − 1)}. □

The special case x = m: we point out something very pleasant happening here. The entries a_{i,j} of the matrix T_{n,m}(m) are given by

a_{i,j} = \binom{2m}{m − i + j} − \binom{2m}{m − i − j + 1},

and the corresponding determinant by

b_{n} := det T_{n,m}(m) = ∏_{1≤i≤j≤m−1} \frac{2n + i + j}{i + j} .

The key difference: this time, we are able to construct an explicit double-indexed sequence c according to c_{n,n} = 1 and for 1 ≤ j < n,

c_{n,j} = \frac{(−1)^{n−j}\binom{2n−1}{n−j}\binom{n+m−j−1}{n−j}}{\binom{2n+m−2}{n−j}}.

Then, Zeilberger’s holonomic ansatz rules supreme once the following system of equations are proven to hold true:

\begin{cases}c_{n,n} = 1  n ≥ 1 \\ ∑_{j=1}^{n} a_{i,j} c_{n,j} = 0  1 ≤ i ≤ n − 1 \\ ∑_{j=1}^{n} a_{n,j} c_{n,j} = \frac{b_{n}}{b_{n−1}}  n ≥ 1. \end{cases}

But, these are directly justified with the help of Zeilberger’s algorithm [25]. We will not pursue this matter because we have already proven Conjecture 1 (see above), in its full generality.

6. T_{n,m}(x) Finds its Twin

Suppressing the parameters a and b, and defining u_{k} := \binom{a+b}{a−k}, the matrix T_{c,a}(b) is nothing but the difference of a Toeplitz and a Hankel matrix:

T_{c,a}(b) = [u_{i−j} − u_{i+j+1}].

By analogy, we may introduce its natural companion as a sum of a Toeplitz and a Hankel matrix:

T̃_{c,a}(b) = [u_{i−j} + u_{i+j+1}].

A truly parallel argument (as in the previous sections) produces a very similar determinantal evaluation:

Theorem 6.1. We have

det T̃_{c,a}(b) = ∏_{i=1}^{c} ∏_{j=1}^{a} \frac{(b + i − j)(b + 2i + j − 1)}{(b + 2i − j − 1)(i + j − 1)}.

To give some context, let f(z) be a complex L_{1}(C) function on the unit circle having Fourier coefficients

u_{k} = \frac{1}{2π} ∫_{0}^{2π} f(e^{iθ})e^{−ikθ}dθ, i = \sqrt{−1}.

Then, in the terminology of Widom [21], the determinant of a Toeplitz matrix with symbol f is given by

E_{n}(f) = det[u_{j−i}].

Toeplitz determinants find homes in many topics, such as statistical physics and random matrix theory. Different types of matrix ensembles lend themselves to classes of Toeplitz plus Hankel matrices of the form

det[u_{j−i} ± u_{j+i}],  det[u_{j−i} ± u_{j+i+1}],  etc.

From a more mathematical vantage point, such determinants arise in the decomposition of the determinants E_{n}(f). Namely, if the symbol f is an even function (in the sense f(z) = f(\frac{1}{z}) on the unit circle), then

E_{2n+1}(f) = \frac{1}{2} det[u_{j−i} − u_{j+i+2}]_{0}^{n−1} × det[u_{j−i} + u_{j+i}]_{0}^{n},
E_{2n}(f) = det[u_{j−i} − u_{j+i+1}]_{0}^{n−1} × det[u_{j−i} + u_{j+i}]_{0}^{n−1}.

Andrews and Stanton ([1], see p. 274) involved a somewhat analogous splitting up of a certain determinant that arose in plane partitions although they did not view them as such.

7. BONUS: CT Identities and Plane Partitions

Borrowing notations from Section 6, the Toeplitz matrix [u_{i−j}] that appeared as a component in our matrix T_{c,a}(b) is in fact recognizable due to its relevance in the theory of plane partitions. Indeed, MacMahon [17] gave an elegant explicit formula for the number of plane partitions inside an a × b × c box:

∏_{i=0}^{a−1} ∏_{j=0}^{b−1} ∏_{k=0}^{c−1} \frac{i + j + k + 2}{i + j + k + 1}.

One may readily associate a determinantal formulation [16] to this enumeration

det[u_{i−j}] = det [\binom{a + b}{a − i + j}]_{i,j=0}^{c−1} = ∏_{i=0}^{a−1} ∏_{j=0}^{b−1} ∏_{k=0}^{c−1} \frac{i + j + k + 2}{i + j + k + 1}.

We have found what appears to be new (for us, at least) matrix whose determinant matches the above product formula and enjoys the expected symmetry.

Lemma 7.1. It holds true that

det [\binom{i + j + a + b}{i + a}]_{i,j=0}^{c−1} = ∏_{i=0}^{a−1} ∏_{j=0}^{b−1} ∏_{k=0}^{c−1} \frac{i + j + k + 2}{i + j + k + 1}.

Proof. This is an immediate application of Dodgson’s condensation [22]. □

Remark 2. The third author has previously employed the same approach towards furnishing a simple proof [23] of a determinant by MacMahon [17].

Proof. Here is a combinatorial proof for Lemma 7.1 given by C. Krattenthaler [15]. We thank him for allowing us to reproduce it. Plane partitions in an a × b × c box are in bijection with families (P_{0}, P_{1}, …, P_{c−1}) of non-intersecting lattice paths, where P_{i} runs from (−i − a, i) to (−i, i + b), i = 0, 1, …, c − 1. This is explained in Section 3.3 of Bressoud’s book [3]. An example for such a family of paths for a = 6 and b = c = 3 is displayed in the figure below.

•  _{•}  _{•}  _{•}  _{•}  _{•}  _{•}  _{•}  _{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•} • • •  • • •

By the Lindström–Gessel–Viennot theorem [6], this leads to the determinant

det_{0≤i,j≤c−1} (\binom{a + b}{a − i + j})

for the enumeration of both objects being counted here. We may prepend and append “forced” path pieces, see the thick path portions in the figure below.

•  _{•}  _{•}  _{•}  _{•}  _{•}  _{•}  _{•}  _{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•}  ^{•} • • •  • • •

In this manner, we obtain families (Q_{0}, Q_{1}, …, Q_{c−1}) of non-intersecting lattice paths, where Q_{i} runs from (−i − a, 0) to (0, i + b), i = 0, 1, …, c − 1. The corresponding Lindström–Gessel–Viennot determinant [6] is

det_{0≤i,j≤c−1} (\binom{i + j + a + b}{i + a}) .

The proof is complete. □

In the context of Selberg’s integrals, there are equivalently-stated constant term identities, and we prove (a special case of) one due to Morris [18] associated with the root system A_{n}.

Proposition 1. We have

CTt⃗ ∏_{i=0}^{c−1}(1 + t_{i})^{a} (1 + t_{i}^{−1})^{b} ∏_{i≠j}^{0,c−1} (1 − t_{j}t_{i}^{−1})^{m} = ∏_{ℓ=0}^{c−1} \frac{(a + b + ℓm)! ((ℓ + 1)m)!}{(a + ℓm)! (b + ℓm)! m!}.

Proof. We are only proving the special case m = 1. Start with the determinant from Lemma 7.1 where the method of constant term extraction is brought to bear:

det [\binom{i + j + a + b}{i + a}] = det [CT_{t_{i}} (t_{i}^{i+a} (1 + \frac{1}{t_{i}} )^{i+j+a+b})]

= det [CT_{t_{i}} ((1 + t_{i})^{i+a} (1 + \frac{1}{t_{i}} )^{b} (1 + \frac{1}{t_{i}} )^{j})]

= CTt⃗ ∏_{i=0}^{c−1}(1 + t_{i})^{i+a} (1 + \frac{1}{t_{i}} )^{b} · det [(1 + \frac{1}{t_{i}} )^{j}]

= CTt⃗ ∏_{i=0}^{c−1}(1 + t_{i})^{i+a} (1 + \frac{1}{t_{i}} )^{b} · ∏_{i<j}^{0,c−1}(t_{j}^{−1} − t_{i}^{−1})

= \frac{1}{c!} CTt⃗ ∏_{i=0}^{c−1}(1 + t_{i})^{a} (1 + \frac{1}{t_{i}} )^{b} · ∏_{i<j}^{0,c−1}(t_{j} − t_{i})(t_{j}^{−1} − t_{i}^{−1})

= \frac{1}{c!} CTt⃗ ∏_{i=0}^{c−1}(1 + t_{i})^{a} (1 + \frac{1}{t_{i}} )^{b} · ∏_{0≤i≠j≤c−1} (1 − \frac{t_{j}}{t_{i}} ) .

From Lemma 7.1, again, we gather that

CTt⃗ ∏_{i=0}^{c−1}(1 + t_{i})^{a} (1 + \frac{1}{t_{i}} )^{b} · ∏_{i≠j}^{0,c−1} (1 − \frac{t_{j}}{t_{i}} ) = c! · ∏_{i=0}^{a−1} ∏_{j=0}^{b−1} ∏_{k=0}^{c−1} \frac{i + j + k + 2}{i + j + k + 1}.

Further algebraic manipulation confirms the desired conclusion. □

We will strengthen the discussion by providing yet another new proof for a special case of a constant term identity due to Macdonald for the BC_{n} root system [18]. We need some preliminary work first. To this end, recall the super Catalan numbers [7] defined by

S_{i,j} := \frac{(2i)! (2j)!}{2 i! j! (i + j)!}.

Lemma 7.2. We have

det[S_{i+a,j+b}]_{i,j=1}^{n} = \frac{(−1)^{\binom{n}{2}}}{2^{n} n!} ∏_{i=1}^{n} \frac{(2a + 2i)! (2b + 2i)! i!}{(a + i)! (b + i)! (a + b + n + i)!}.

Proof. A direct application of Dodgson’s condensation settles the argument. □

Corollary 7.3. Let t⃗ = (t_{1}, …, t_{n}). The following identity holds true

CTt⃗ ∏_{i=1}^{n}(1 − t_{i})^{α} (1 − \frac{1}{t_{i}} )^{α} (1 − t_{i}^{2})^{β} (1 − \frac{1}{t_{i}^{2}} )^{β} ×

∏_{i<j} (1 − \frac{t_{j}}{t_{i}} ) (1 − \frac{t_{i}}{t_{j}} ) (1 − t_{i}t_{j}) (1 − \frac{1}{t_{i}t_{j}} )

= ∏_{i=1}^{n} \frac{(2β + 2i − 2)! (2α + 2β + 2i − 2)! i!}{(β + i − 1)! (α + β + i − 1)! (α + 2β + n + i − 2)!}.

Proof. Start with the observation that

S_{i+a,j+b} = (−1)^{i+a} CT_{t} \frac{(1 − t)^{2i+2a}(1 + t)^{2j+2b}}{2 t^{i+a+j+b}}

and proceed as usual

det[S_{i+a,j+b}]_{1}^{n} = det [(−1)^{i+a} CT_{t_{i}} \frac{(1 − t_{i})^{2i+2a}(1 + t_{i})^{2j+2b}}{2 t_{i}^{i+a+j+b}} ]_{1}^{n}

= γ_{n} det [CT_{t_{i}} \frac{(1 − t_{i})^{2i+2a}(1 + t_{i})^{2b+2}}{t_{i}^{i+a+b+1}} (2 + t_{i} + \frac{1}{t_{i}} )^{j−1}]

= γ_{n} CTt⃗ ∏_{i=1}^{n} \frac{(1 − t_{i})^{2i+2a}(1 + t_{i})^{2b+2}}{t_{i}^{i+a+b+1}} ∏_{i<j} (t_{j} + \frac{1}{t_{j}} − t_{i} − \frac{1}{t_{i}} )

= γ_{n} CTt⃗ ∏_{i=1}^{n} \frac{(1 − t_{i})^{2a+2}(1 + t_{i})^{2b+2}(−2 + t_{i} + \frac{1}{t_{i}})^{i−1}}{t_{i}^{a+b+2}} ∏_{i<j}(t_{j} − t_{i}) (1 − \frac{1}{t_{i}t_{j}} )

= \frac{γ_{n}}{n!} CTt⃗ ∏_{i=1}^{n} \frac{(1 − t_{i})^{2a+2}(1 + t_{i})^{2b+2}}{t_{i}^{a+b+2}} ∏_{i<j}(t_{j} − t_{i})^{2} (1 − \frac{1}{t_{i}t_{j}} )^{2}

= \frac{(−1)^{n(a+1)}γ_{n}}{n!} CTt⃗ ∏_{i=1}^{n}(1 − t_{i})^{a+1} (1 − \frac{1}{t_{i}} )^{a+1} (1 + t_{i})^{b+1} (1 + \frac{1}{t_{i}} )^{b+1}

× ∏_{i<j} (1 − \frac{t_{j}}{t_{i}} ) (1 − \frac{t_{i}}{t_{j}} ) (1 − t_{i}t_{j}) (1 − \frac{1}{t_{i}t_{j}} );

where γ_{n} := (−1)^{\binom{n+1}{2}}(−1)^{na}2^{−n}. The rest follows from applying Lemma 7.2, from above, with a = α + β − 1 and b = β − 1 and some algebraic simplifications. □

8. Postscript: The Fourth Method - Ask Determinant guru Christian Krattenthaler

After the first version of this paper was written, we sent it out to a few experts, and to our initial horror, we got the following email from Christian Krattenthaler, that he kindly allowed us to quote.

“Obviously, I agree that determinants are (*not* non-intuitive) = intuitive, extremely useful, and that linear algebra without determinants is an aberration. (We had in fact a colleague at our determinant (sic!) - working in harmonic analysis - who also believed in - and taught - a determinant-free linear algebra; his poor students had to learn determinants afterwards ...) Concerning the determinant that you look at: it is the special case of (3.18) in my “Advanced Determinant Calculus” [14] where q = 1, A = x + m, L_{i} = i − m. This identity has a simple direct proof. As explained above Theorem 30 in [14], after having taken out appropriate factors, the determinant turns out to be a special case of Lemma 5 in [14]. That lemma is so general so that it can be proved in various ways, one of which is explained in Ref. [88] of [14].”

Indeed this is an extreme case of Polya’s dictum already alluded to above. The general lemma, in hindsight, is almost trivial to prove, once known, but coming up with it, is anything but.

At first, we kicked ourselves for not asking guru Christian right away, and saving us the trouble of doing it ourselves - this is the cowardly way. But this ‘trouble’ was lots of fun, and it brings us to yet another take-home message. Don’t rush to ask the expert!, it is like ‘peeking at the answer at the back of the textbook’. You will learn much more by trying to do it all by yourself! Of course, if you finally give up, after an honest effort, then you can contact Professor Krattenthaler. Also if you succeed, and want to make sure that you were not scooped, do likewise, but not right away!.

Remark 3. The determinant (3.18) in [14], generalizing our Conjecture 1, was used in the proof of refinements of the MacMahon ex-Conjecture and the Bender–Knuth ex-Conjecture.

9. The Revenge of Rev. Charles

At times life rides like a domino-effect. The last section exhibited a notion of thinking retroactively - by way of consulting experts. This prompted us to have another look at the original problem which would really make our paper even more self-contained. In this section, we revisit our running example - the matrix

T_{n,m}(x) := [\binom{x + m}{j − i + m} − \binom{x + m}{m − i − j + 1}]_{1≤i,j≤n} ,

for which we had the formula

det T_{n,m}(x) = ∏_{i=1}^{n} ∏_{j=1}^{m} \frac{(x + i − j)(x + 2i + j − 2)}{(x + 2i − j)(i + j − 1)}.

We have had a ton of adventures in proving and applying it. As noted above, Krattenthaler claimed priority by providing a generalized determinant evaluation. Fair enough. We, too, have another idea in trivializing the proof. Follow us. Step 1. Change variables: x = a + b, m = b − a. Rename T_{n,m}(x) to write

U_{n}(a, b) = [\binom{2b}{j − i + b − a} − \binom{2b}{b − a − i − j + 1}]_{1≤i,j≤n} .

Step 2. This is the key: use the symmetry \binom{A}{B} = \binom{A}{A−B} on the second binomial coefficient so that

U_{n}(a, b) = [\binom{2b}{j − i + b − a} − \binom{2b}{a + b + i + j − 1}]_{1≤i,j≤n} ,

while maintaining the lingering assertion

det U_{n}(a, b) = ∏_{i=1}^{n} ∏_{j=1}^{b−a} \frac{(a + b + i − j)(a + b + 2i + j − 2)}{(a + b + 2i − j)(i + j − 1)}.

Step 3. Call Dodgson’s condensation on U_{n}(a, b) because this matrix is in a natural form for such an application.

Proof. Denoting the determinant by M_{n}(a, b), Dodgson’s condensation states that

M_{n}(a, b) = \frac{M_{n−1}(a, b)M_{n−1}(a + 1, b + 1) − M_{n−1}(a + 1, b)M_{n−1}(a, b + 1)}{M_{n−2}(a + 1, b + 1)}.

Therefore, we only need to verify (routinely) that the right-hand side does the same. To conclude, simply check both sides agree, say, when n = 1 and n = 2. □

References

[1] G. E. Andrews, D. W. Stanton. Determinants in plane partition enumeration, European Journal of Combinatorics 19 (1998), 273–282.

[2] Sheldon Axler, Down with determinants!, The American Mathematical Monthly 102 (2) (Feb. 1995), 139–154.

[3] D. M. Bressoud. Proofs and confirmations - The story of the alternating sign matrix conjecture, Cambridge University Press, Cambridge, 1999.

[4] J. Cigler. Determinants of band matrices which are related to Hankel matrices of Catalan

numbers, https://mathoverflow.net/users/5585/johann-cigler , 2023.

[5] H. Du, C. Koutschan, T. Thanatipanonda, E. Wong. Binomial determinants for tiling problems yield to the holonomic ansatz, European Journal of Combinatorics, 99 (2022). Paper No. 103437, 40 pp.

[6] I. M. Gessel, X. Viennot. Determinants, paths, and plane partitions, preprint, 1989.

[7] I. M. Gessel. Super ballot numbers, Journal of Symbolic Computation 14 (2–3) (1992), 179– 194.

[8] S. R. Ghorpade, C. Krattenthaler, The Hilbert series of Pfaffian rings. – Appendix: Geometry of degeneracy loci and a plethora of multiplicity formula, ArXiv 2001 (see p. 12, Theorem 2).

[9] Z. Hamaker, N. Williams. Subwords and plane partitions, Daejeon, South Korea DMTCS proc. FPSAC’15 (see p. 244, Theorem 6).

[10] J. Jonsson. Generalized triangulations and diagonal-free subsets of stack polyominoes, Journal of Combinatorial Theory, Series A 112 (2005) 117-142 (see p. 130, Corollary 17).

[11] C. Koutschan, M. Kauers, D. Zeilberger. A Proof of George Andrews’ and David Robbins’ q-TSPP Conjecture, Proceedings of the National Academy of Sciences 108 (6), 2196–2199.

[12] C. Koutschan. HolonomicFunctions (user’s guide), Technical Report 10-01, RISC Report Se-

ries, Johannes Kepler University Linz, 2010. https://risc.jku.at/sw/holonomicfunctions/

[13] C. Koutschan, T. Thanatipanonda. A curious family of binomial determinants that count rhombus tilings of a holey hexagon, Journal of Combinatorial Theory, Series A 166 (2019), 352–381.

[14] C. Krattenthaler. Advanced determinant calculus, Séminaire Lotharingien de Combinatoire, Art. B42q, 42 (1999) (67 pp.).

[15] C. Krattenthaler. Private communication.

[16] C. Krattenthaler. Plane partitions in the work of Richard Stanley and his school, in: The mathematical legacy of Richard P. Stanley (Edited by Patricia Hersh, Thomas Lam, Pavlo Pylyavskyy and Victor Reiner) American Mathematical Society, Providence, RI, 2016, 231–261.

[17] P. A. MacMahon. Combinatory Analysis, Cambridge University Press, 1918 [reprinted by Chelsea, 1984].

[18] W. G. Morris. Constant term identities for finite and infinite root systems, Ph.D. Thesis, University of Wisconsin, Madison, 1982.

[19] R. A. Proctor. New symmetric plane partition identities from invariant theory work of de Concini and Procesi, European Journal of Combinatorics 11 (1990), 289-300 (see p. 292, Theorem 1, CGI).

[20] R. P. Stanley. Symmetries of plane partitions, Journal of Combinatorial Theory, Series A 43 (1), (1986) (see p. 107, Case 6).

[21] H. Widom. On the eigenvalues of certain hermitian operators, Transactions of the AMS 88 (2) (1958), 491–522.

[22] D. Zeilberger. Dodgson’s determinant-evaluation rule prove by two-timing men and women, Electronic Journal of Combinatorics 2 (4) (1997), # R22.

[23] D. Zeilberger. Reverend Charles to the aid of Major Percy and Fields medalist Enrico, American Mathematical Monthly, 103 (1996), 501–502.

[24] D. Zeilberger. The HOLONOMIC ANSATZ II: Automatic DISCOVERY(!) and PROOF(!!) of holonomic determinant evaluations, Annals of Combinatorics 11 (2007), 241–247.

[25] D. Zeilberger. The method of creative telescoping, Journal of Symbolic Computation 11 (1991), 195–204.

[26] D. Zeilberger, Proof of the alternating sign matrix conjecture, Elect. J. of Comb. 3(2)(1996),[ special issue in honor of Dominique Foata’s 60th birthday], R13.

Department of Mathematics, Tulane University, New Orleans, LA 70118, USA

Email address: tamdeber@tulane.edu

Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenberger Strasse 69, 4040 Linz, Austria

Email address: christoph.koutschan@oeaw.ac.at

Department of Mathematics, Rutgers University (New Brunswick),, Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA

Email address: DoronZeil@gmail.com