ńņš. 1 |

C. KRATTENTHALERā

Institut fĀØr Mathematik der UniversitĀØt Wien,

u a

Strudlhofgasse 4, A-1090 Wien, Austria.

math.CO/9902004 v3 31 May 1999

E-mail: kratt@pap.univie.ac.at

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

Dedicated to the pioneer of determinant evaluations (among many other things),

George Andrews

Abstract. The purpose of this article is threefold. First, it provides the reader with

a few useful and eļ¬cient tools which should enable her/him to evaluate nontrivial de-

terminants for the case such a determinant should appear in her/his research. Second,

it lists a number of such determinants that have been already evaluated, together with

explanations which tell in which contexts they have appeared. Third, it points out

references where further such determinant evaluations can be found.

1. Introduction

Imagine, you are working on a problem. As things develop it turns out that, in

order to solve your problem, you need to evaluate a certain determinant. Maybe your

determinant is

1

det , (1.1)

i+j

1ā¤i,j,ā¤n

or

a+b

det , (1.2)

aā’i+j

1ā¤i,jā¤n

or it is possibly

Āµ+i+j

det , (1.3)

2i ā’ j

0ā¤i,jā¤nā’1

1991 Mathematics Subject Classiļ¬cation. Primary 05A19; Secondary 05A10 05A15 05A17 05A18

05A30 05E10 05E15 11B68 11B73 11C20 15A15 33C45 33D45.

Key words and phrases. Determinants, Vandermonde determinant, Cauchyā™s double alternant,

Pfaļ¬an, discrete Wronskian, Hankel determinants, orthogonal polynomials, Chebyshev polynomials,

Meixner polynomials, Meixnerā“Pollaczek polynomials, Hermite polynomials, Charlier polynomials, La-

guerre polynomials, Legendre polynomials, ultraspherical polynomials, continuous Hahn polynomials,

continued fractions, binomial coeļ¬cient, Genocchi numbers, Bernoulli numbers, Stirling numbers, Bell

numbers, Euler numbers, divided diļ¬erence, interpolation, plane partitions, tableaux, rhombus tilings,

lozenge tilings, alternating sign matrices, noncrossing partitions, perfect matchings, permutations,

inversion number, major index, descent algebra, noncommutative symmetric functions.

ā

Research partially supported by the Austrian Science Foundation FWF, grants P12094-MAT and

P13190-MAT.

1

2 C. KRATTENTHALER

or maybe

x+y+j x+y+j

ā’

det . (1.4)

x ā’ i + 2j x + i + 2j

1ā¤i,jā¤n

Honestly, which ideas would you have? (Just to tell you that I do not ask for something

impossible: Each of these four determinants can be evaluated in āclosed formā. If you

want to see the solutions immediately, plus information where these determinants come

from, then go to (2.7), (2.17)/(3.12), (2.19)/(3.30), respectively (3.47).)

Okay, let us try some row and column manipulations. Indeed, although it is not

completely trivial (actually, it is quite a challenge), that would work for the ļ¬rst two

determinants, (1.1) and (1.2), although I do not recommend that. However, I do not

recommend at all that you try this with the latter two determinants, (1.3) and (1.4). I

promise that you will fail. (The determinant (1.3) does not look much more complicated

than (1.2). Yet, it is.)

So, what should we do instead?

Of course, let us look in the literature! Excellent idea. We may have the problem

of not knowing where to start looking. Good starting points are certainly classics like

[119], [120], [121], [127] and [178]1. This will lead to the ļ¬rst success, as (1.1) does

indeed turn up there (see [119, vol. III, p. 311]). Yes, you will also ļ¬nd evaluations for

(1.2) (see e.g. [126]) and (1.3) (see [112, Theorem 7]) in the existing literature. But at

the time of the writing you will not, to the best of my knowledge, ļ¬nd an evaluation of

(1.4) in the literature.

The purpose of this article is threefold. First, I want to describe a few useful and

eļ¬cient tools which should enable you to evaluate nontrivial determinants (see Sec-

tion 2). Second, I provide a list containing a number of such determinants that have

been already evaluated, together with explanations which tell in which contexts they

have appeared (see Section 3). Third, even if you should not ļ¬nd your determinant

in this list, I point out references where further such determinant evaluations can be

found, maybe your determinant is there.

Most important of all is that I want to convince you that, today,

Evaluating determinants is not (okay: may not be) diļ¬cult!

When George Andrews, who must be rightly called the pioneer of determinant evalua-

tions, in the seventies astounded the combinatorial community by his highly nontrivial

determinant evaluations (solving diļ¬cult enumeration problems on plane partitions),

it was really diļ¬cult. His method (see Section 2.6 for a description) required a good

āguesserā and an excellent āhypergeometerā (both of which he was and is). While at

that time especially to be the latter was quite a task, in the meantime both guessing and

evaluating binomial and hypergeometric sums has been largely trivialized, as both can

be done (most of the time) completely automatically. For guessing (see Appendix A)

1

Turnbullā™s book [178] does in fact contain rather lots of very general identities satisļ¬ed by determi-

nants, than determinant āevaluationsā in the strict sense of the word. However, suitable specializations

of these general identities do also yield āgenuineā evaluations, see for example Appendix B. Since the

value of this book may not be easy to appreciate because of heavy notation, we refer the reader to

[102] for a clariļ¬cation of the notation and a clear presentation of many such identities.

ADVANCED DETERMINANT CALCULUS 3

this is due to tools like Superseeker2, gfun and Mgfun3 [152, 24], and Rate4 (which is

by far the most primitive of the three, but it is the most eļ¬ective in this context). For

āhypergeometricsā this is due to the āWZ-machineryā5 (see [130, 190, 194, 195, 196]).

And even if you should meet a case where the WZ-machinery should exhaust your com-

puterā™s capacity, then there are still computer algebra packages like HYP and HYPQ6,

or HYPERG7, which make you an expert hypergeometer, as these packages comprise

large parts of the present hypergeometric knowledge, and, thus, enable you to con-

veniently manipulate binomial and hypergeometric series (which George Andrews did

largely by hand) on the computer. Moreover, as of today, there are a few new (perhaps

just overlooked) insights which make life easier in many cases. It is these which form

large parts of Section 2.

So, if you see a determinant, donā™t be frightened, evaluate it yourself!

2. Methods for the evaluation of determinants

In this section I describe a few useful methods and theorems which (may) help you

to evaluate a determinant. As was mentioned already in the Introduction, it is always

possible that simple-minded things like doing some row and/or column operations, or

applying Laplace expansion may produce an (usually inductive) evaluation of a deter-

minant. Therefore, you are of course advised to try such things ļ¬rst. What I am

mainly addressing here, though, is the case where that ļ¬rst, āsimple-mindedā attempt

failed. (Clearly, there is no point in addressing row and column operations, or Laplace

expansion.)

Yet, we must of course start (in Section 2.1) with some standard determinants, such

as the Vandermonde determinant or Cauchyā™s double alternant. These are of course

well-known.

In Section 2.2 we continue with some general determinant evaluations that generalize

the evaluation of the Vandermonde determinant, which are however apparently not

equally well-known, although they should be. In fact, I claim that about 80 % of the

determinants that you meet in āreal life,ā and which can apparently be evaluated, are a

special case of just the very ļ¬rst of these (Lemma 3; see in particular Theorem 26 and

the subsequent remarks). Moreover, as is demonstrated in Section 2.2, it is pure routine

to check whether a determinant is a special case of one of these general determinants.

Thus, it can be really considered as a āmethodā to see if a determinant can be evaluated

by one of the theorems in Section 2.2.

2

the electronic version of the āEncyclopedia of Integer Sequencesā [162, 161], written and developed

by Neil Sloane and Simon Plouļ¬e; see http://www.research.att.com/˜njas/sequences/ol.html

3

written by Bruno Salvy and Paul Zimmermann, respectively Frederic Chyzak; available from

http://pauillac.inria.fr/algo/libraries/libraries.html

4

written in Mathematica by the author; available from http://radon.mat.univie.ac.at/People/kratt;

the Maple equivalent GUESS by FranĀøois BĀ“raud and Bruno Gauthier is available from

c e

http://www-igm.univ-mlv.fr/˜gauthier

5

Maple implementations written by Doron Zeilberger are available from

Mathematica implementations written by

http://www.math.temple.edu/˜zeilberg,

Peter Paule, Axel Riese, Markus Schorn, Kurt Wegschaider are available from

http://www.risc.uni-linz.ac.at/research/combinat/risc/software

6

written in Mathematica by the author; available from http://radon.mat.univie.ac.at/People/kratt

7

written in Maple by Bruno Ghauthier; available from http://www-igm.univ-mlv.fr/˜gauthier

4 C. KRATTENTHALER

The next method which I describe is the so-called ācondensation methodā (see Sec-

tion 2.3), a method which allows to evaluate a determinant inductively (if the method

works).

In Section 2.4, a method, which I call the āidentiļ¬cation of factorsā method, is de-

scribed. This method has been extremely successful recently. It is based on a very

simple idea, which comes from one of the standard proofs of the Vandermonde deter-

minant evaluation (which is therefore described in Section 2.1).

The subject of Section 2.5 is a method which is based on ļ¬nding one or more diļ¬eren-

tial or diļ¬erence equations for the matrix of which the determinant is to be evaluated.

Section 2.6 contains a short description of George Andrewsā™ favourite method, which

basically consists of explicitly doing the LU-factorization of the matrix of which the

determinant is to be evaluated.

The remaining subsections in this section are conceived as a complement to the pre-

ceding. In Section 2.7 a special type of determinants is addressed, Hankel determinants.

(These are determinants of the form det1ā¤i,jā¤n (ai+j ), and are sometimes also called per-

symmetric or TurĀ“nian determinants.) As is explained there, you should expect that a

a

Hankel determinant evaluation is to be found in the domain of orthogonal polynomials

and continued fractions. Eventually, in Section 2.8 a few further, possibly useful results

are exhibited.

Before we ļ¬nally move into the subject, it must be pointed out that the methods

of determinant evaluation as presented here are ordered according to the conditions a

determinant must satisfy so that the method can be applied to it, from āstringentā to

āless stringentā. I. e., ļ¬rst come the methods which require that the matrix of which

the determinant is to be taken satisļ¬es a lot of conditions (usually: it contains a lot of

parameters, at least, implicitly), and in the end comes the method (LU-factorization)

which requires nothing. In fact, this order (of methods) is also the order in which I

recommend that you try them on your determinant. That is, what I suggest is (and

this is the rule I follow):

(0) First try some simple-minded things (row and column operations, Laplace expan-

sion). Do not waste too much time. If you encounter a Hankel-determinant then

see Section 2.7.

(1) If that fails, check whether your determinant is a special case of one of the general

determinants in Sections 2.2 (and 2.1).

(2) If that fails, see if the condensation method (see Section 2.3) works. (If necessary,

try to introduce more parameters into your determinant.)

(3) If that fails, try the āidentiļ¬cation of factorsā method (see Section 2.4). Alterna-

tively, and in particular if your matrix of which you want to ļ¬nd the determinant

is the matrix deļ¬ning a system of diļ¬erential or diļ¬erence equations, try the dif-

ferential/diļ¬erence equation method of Section 2.5. (If necessary, try to introduce

a parameter into your determinant.)

(4) If that fails, try to work out the LU-factorization of your determinant (see Sec-

tion 2.6).

(5) If all that fails, then we are really in trouble. Perhaps you have to put more eļ¬orts

into determinant manipulations (see suggestion (0))? Sometimes it is worthwile

to interpret the matrix whose determinant you want to know as a linear map and

try to ļ¬nd a basis on which this map acts triangularly, or even diagonally (this

ADVANCED DETERMINANT CALCULUS 5

requires that the eigenvalues of the matrix are āniceā; see [47, 48, 84, 93, 192] for

examples where that worked). Otherwise, maybe something from Sections 2.8 or

3 helps?

A ļ¬nal remark: It was indicated that some of the methods require that your deter-

minant contains (more or less) parameters. Therefore it is always a good idea to:

Introduce more parameters into your determinant!

(We address this in more detail in the last paragraph of Section 2.1.) The more param-

eters you can play with, the more likely you will be able to carry out the determinant

evaluation. (Just to mention a few examples: The condensation method needs, at least,

two parameters. The āidentiļ¬cation of factorsā method needs, at least, one parameter,

as well as the diļ¬erential/diļ¬erence equation method in Section 2.5.)

2.1. A few standard determinants. Let us begin with a short proof of the Van-

dermonde determinant evaluation

(Xj ā’ Xi ).

Xijā’1 =

det (2.1)

1ā¤i,jā¤n

1ā¤i<jā¤n

Although the following proof is well-known, it makes still sense to quickly go through

it because, by extracting the essence of it, we will be able to build a very powerful

method out of it (see Section 2.4).

If Xi1 = Xi2 with i1 = i2, then the Vandermonde determinant (2.1) certainly vanishes

because in that case two rows of the determinant are identical. Hence, (Xi1 ā’ Xi2 )

divides the determinant as a polynomial in the Xi ā™s. But that means that the complete

product 1ā¤i<jā¤n (Xj ā’ Xi ) (which is exactly the right-hand side of (2.1)) must divide

the determinant.

On the other hand, the determinant is a polynomial in the Xi ā™s of degree at most

n

. Combined with the previous observation, this implies that the determinant equals

2

the right-hand side product times, possibly, some constant. To compute the constant,

compare coeļ¬cients of X1 X2 Ā· Ā· Ā· Xn on both sides of (2.1). This completes the proof

01 nā’1

of (2.1).

At this point, let us extract the essence of this proof as we will come back to it in

Section 2.4. The basic steps are:

1. Identiļ¬cation of factors

2. Determination of degree bound

3. Computation of the multiplicative constant.

An immediate generalization of the Vandermonde determinant evaluation is given by

the proposition below. It can be proved in just the same way as the above proof of the

Vandermonde determinant evaluation itself.

Proposition 1. Let X1 , X2 , . . . , Xn be indeterminates. If p1 , p2 , . . . , pn are polynomials

of the form pj (x) = aj xjā’1 + lower terms, then

det (pj (Xi )) = a1 a2 Ā· Ā· Ā· an (Xj ā’ Xi ). (2.2)

1ā¤i,jā¤n

1ā¤i<jā¤n

6 C. KRATTENTHALER

The following variations of the Vandermonde determinant evaluation are equally easy

to prove.

Lemma 2. The following identities hold true:

n

Xiā’j ) = (X1 Ā· Ā· Ā· Xn )ā’n

ā’ (Xi ā’ Xj )(1 ā’ Xi Xj ) (Xi2 ā’ 1),

(Xij

det

1ā¤i,jā¤n

i=1

1ā¤i<jā¤n

(2.3)

ā’(jā’1/2)

jā’1/2

ā’ Xi

det (Xi )

1ā¤i,jā¤n

n

= (X1 Ā· Ā· Ā· Xn )ā’n+1/2 (Xi ā’ Xj )(1 ā’ Xi Xj ) (Xi ā’ 1), (2.4)

1ā¤i<jā¤n i=1

ā’(jā’1)

) = 2 Ā· (X1 Ā· Ā· Ā· Xn )ā’n+1 (Xi ā’ Xj )(1 ā’ Xi Xj ) ,

det (Xijā’1 + Xi (2.5)

1ā¤i,jā¤n

1ā¤i<jā¤n

ā’(jā’1/2)

jā’1/2

det (Xi + Xi )

1ā¤i,jā¤n

n

ā’n+1/2

= (X1 Ā· Ā· Ā· Xn ) (Xi ā’ Xj )(1 ā’ Xi Xj ) (Xi + 1). (2.6)

1ā¤i<jā¤n i=1

We remark that the evaluations (2.3), (2.4), (2.5) are basically the Weyl denominator

factorizations of types C, B, D, respectively (cf. [52, Lemma 24.3, Ex. A.52, Ex. A.62,

Ex. A.66]). For that reason they may be called the āsymplecticā, the āodd orthogonalā,

and the āeven orthogonalā Vandermonde determinant evaluation, respectively.

Ī»

If you encounter generalizations of such determinants of the form det1ā¤i,jā¤n (xi j )

ā’Ī»

Ī»

or det1ā¤i,jā¤n (xi j ā’ xi j ), etc., then you should be aware that what you encounter is

basically Schur functions, characters for the symplectic groups, or characters for the

orthogonal groups (consult [52, 105, 137] for more information on these matters; see

in particular [105, Ch. I, (3.1)], [52, p. 403, (A.4)], [52, (24.18)], [52, (24.40) + ļ¬rst

paragraph on p. 411], [137, Appendix A2], [52, (24.28)]). In this context, one has to

also mention Okadaā™s general results on evaluations of determinants and Pfaļ¬ans (see

Section 2.8 for deļ¬nition) in [124, Sec. 4] and [125, Sec. 5].

Another standard determinant evaluation is the evaluation of Cauchyā™s double alter-

nant (see [119, vol. III, p. 311]),

ā’ Xj )(Yi ā’ Yj )

1ā¤i<jā¤n (Xi

1

det = . (2.7)

Xi + Yj (Xi + Yj )

1ā¤i,jā¤n

1ā¤i,jā¤n

Once you have seen the above proof of the Vandermonde determinant evaluation, you

will immediately know how to prove this determinant evaluation.

On setting Xi = i and Yi = i, i = 1, 2, . . . , n, in (2.7), we obtain the evaluation of our

ļ¬rst determinant in the Introduction, (1.1). For the evaluation of a mixture of Cauchyā™s

double alternant and Vandermondeā™s determinant see [15, Lemma 2].

ADVANCED DETERMINANT CALCULUS 7

Whether or not you tried to evaluate (1.1) directly, here is an important lesson to be

learned (it was already mentioned earlier): To evaluate (1.1) directly is quite diļ¬cult,

whereas proving its generalization (2.7) is almost completely trivial. Therefore, it is

always a good idea to try to introduce more parameters into your determinant. (That is,

in a way such that the more general determinant still evaluates nicely.) More parameters

mean that you have more objects at your disposal to play with.

The most stupid way to introduce parameters is to just write Xi instead of the row

index i, or write Yj instead of the column index j.8 For the determinant (1.1) even

both simultaneously was possible. For the determinant (1.2) either of the two (but not

both) would work. On the contrary, there seems to be no nontrivial way to introduce

more parameters in the determinant (1.4). This is an indication that the evaluation of

this determinant is in a diļ¬erent category of diļ¬culty of evaluation. (Also (1.3) belongs

to this ādiļ¬erent categoryā. It is possible to introduce one more parameter, see (3.32),

but it does not seem to be possible to introduce more.)

2.2. A general determinant lemma, plus variations and generalizations.

In this section I present an apparently not so well-known determinant evaluation that

generalizes Vandermondeā™s determinant, and some companions. As Lascoux pointed

out to me, most of these determinant evaluations can be derived from the evaluation

of a certain determinant of minors of a given matrix due to Turnbull [179, p. 505], see

Appendix B. However, this (these) determinant evaluation(s) deserve(s) to be better

known. Apart from the fact that there are numerous applications of it (them) which I

am aware of, my proof is that I meet very often people who stumble across a special

case of this (these) determinant evaluation(s), and then have a hard time to actually

do the evaluation because, usually, their special case does not show the hidden general

structure which is lurking behind. On the other hand, as I will demonstrate in a mo-

ment, if you know this (these) determinant evaluation(s) then it is a matter completely

mechanical in nature to see whether it (they) is (are) applicable to your determinant

or not. If one of them is applicable, you are immediately done.

The determinant evaluation of which I am talking is the determinant lemma from

[85, Lemma 2.2] given below. Here, and in the following, empty products (like (Xi +

An)(Xi + Anā’1 ) Ā· Ā· Ā· (Xi + Aj+1 ) for j = n) equal 1 by convention.

Lemma 3. Let X1 , . . . , Xn , A2, . . . , An, and B2 , . . . , Bn be indeterminates. Then there

holds

(Xi + An)(Xi + Anā’1 ) Ā· Ā· Ā· (Xi + Aj+1 )(Xi + Bj )(Xi + Bjā’1 ) Ā· Ā· Ā· (Xi + B2 )

det

1ā¤i,jā¤n

(Xi ā’ Xj ) (Bi ā’ Aj ). (2.8)

=

1ā¤i<jā¤n 2ā¤iā¤jā¤n

8

Other common examples of introducing more parameters are: Given that the (i, j)-entry of your

determinant is a binomial such as 2iā’j , try x+i+j (that works; see (3.30)), or even x+y+i+j (that

i+j

2iā’j y+2iā’j

x+i+j y+i+j

does not work; but see (1.2)), or 2iā’j + 2iā’j (that works; see (3.32), and consult Lemma 19

and the remarks thereafter). However, sometimes parameters have to be introduced in an unexpected

way, see (3.49). (The parameter x was introduced into a determinant of Bombieri, Hunt and van der

Poorten, which is obtained by setting x = 0 in (3.49).)

8 C. KRATTENTHALER

Once you have guessed such a formula, it is easily proved. In the proof in [85] the

determinant is reduced to a determinant of the form (2.2) by suitable column operations.

Another proof, discovered by Amdeberhan (private communication), is by condensation,

see Section 2.3. For a derivation from the above mentioned evaluation of a determinant

of minors of a given matrix, due to Turnbull, see Appendix B.

Now let us see what the value of this formula is, by checking if it is of any use in the

ńņš. 1 |