(3.50)

The proof of this result in [94] could be called “heavy”. It proceeded by “identi¬cation

of factors”. Thus, it was only the introduction of the parameter x in the determinant in

(3.49) that allowed the attack on this special case of the conjecture of Bombieri, Hunt

and van der Poorten. However, the authors of [94] (this includes myself) failed to ¬nd a

way to introduce a parameter into the determinant in Theorem 49 for generic N (that

is, in a way such the determinant would still factor nicely). This was accomplished by

van der Poorten [132]. He ¬rst changed the entries in the determinant slightly, without

changing the value of the determinant, and then was able to introduce a parameter. I

state his result, [132, Sec. 5, Main Theorem], in the theorem below. For the proof of

his result he used “identi¬cation of factors” as well, thereby considerably simplifying

and illuminating arguments from [94].

Theorem 51. Let N and l be positive integers. Let M be the matrix with rows labelled

by pairs (i1 , i2) with 0 ¤ i1 ¤ 2l(N ’ i2 ) ’ 1, with columns labelled by pairs (j1 , j2) with

0 ¤ j2 ¤ N and 0 ¤ j1 ¤ lN ’ 1, and entry in row (i1, i2) and column (j1 , j2 ) equal to

’x(N ’ j2 ) j2

(’1)i1 ’j1 . (3.51)

i1 ’ j1 i2

46 C. KRATTENTHALER

Then the determinant of M is given by

(N3 )

+2

l

x+i’1 l+i’1

± .

2i ’ 1 2i ’ 1

i=1

Although not completely obvious, the special case x = ’2l establishes Theorem 49,

see [132]. Van der Poorten proves as well an evaluation that overlaps with the x = 0

case of Theorem 50, see [132, Sec. 6, Example Application].

Let us now turn to a few remarkable Hankel determinant evaluations.

Theorem 52. Let n be a positive integer. Then there hold

n’1

(2i)!2,

det (E2i+2j ) = (3.52)

0¤i,j¤n’1

i=0

where E2k is the (2k)-th (signless) Euler number, de¬ned through the generating function

1/ cos z = ∞ E2k z 2k /(2k)!, and

k=0

n’1

(2i + 1)!2 .

det (E2i+2j+2 ) = (3.53)

0¤i,j¤n’1

i=0

Furthermore, de¬ne the Bell polynomials Bm (x) by Bm (x) = m S(m, k)xk , where

k=1

S(m, k) is a Stirling number of the second kind (the number of partitions of an m-

element set into k blocks; cf. [166, p. 33]). Then

n’1

n(n’1)/2

det (Bi+j (x)) = x i!. (3.54)

0¤i,j¤n’1

i=0

Next, there holds

n’1

n(n’1)/2

det (Hi+j (x)) = (’1) i!, (3.55)

0¤i,j¤n’1

i=0

k

where Hm (x) = k≥0 k! (m’2k)! ’ 1 xm’2k is the m-th Hermite polynomial.

m!

2

Finally, the following Hankel determinant evaluations featuring Bernoulli numbers

hold,

n’1

i!6

n

(Bi+j ) = (’1)( )

det , (3.56)

2

(2i)! (2i + 1)!

0¤i,j,¤n’1

i=1

and

n’1

i!3 (i + 1)!3

)1

n+1

(Bi+j+1 ) = (’1)(

det , (3.57)

2

2 (2i + 1)! (2i + 2)!

0¤i,j,¤n’1

i=1

and

n’1

i! (i + 1)!4 (i + 2)!

1 n

det (Bi+j+2 ) = (’1)( ) , (3.58)

2

6 (2i + 2)! (2i + 3)!

0¤i,j,¤n’1

i=1

ADVANCED DETERMINANT CALCULUS 47

and

n’1

(2i)! (2i + 1)!4 (2i + 2)!

det (B2i+2j+2 ) = , (3.59)

(4i + 2)! (4i + 3)!

0¤i,j,¤n’1

i=0

and

n

(2i ’ 1)! (2i)!4 (2i + 1)!

n

det (B2i+2j+4 ) = (’1) . (3.60)

(4i)! (4i + 1)!

0¤i,j,¤n’1

i=1

All these evaluations can be deduced from continued fractions and orthogonal poly-

nomials, in the way that was described in Section 2.7. To prove (3.52) and (3.53)

one would resort to suitable special cases of Meixner“Pollaczek polynomials (see [81,

Sec. 1.7]), and use an integral representation for Euler numbers, given for example in

[122, p. 75],

√

√ ∞ ’1

(2z)2ν

’1

ν+1

E2ν = (’1) dz.

√

’∞ ’1 cos πz

Slightly di¬erent proofs of (3.52) can be found in [1] and [108, App. A.5], together

with more Hankel determinant evaluations (among which are also (3.56) and (3.58),

respectively). The evaluation (3.54) can be derived by considering Charlier polyno-

mials (see [35] for such a derivation in a special case). The evaluation (3.55) follows

from the fact that Hermite polynomials are moments of slightly shifted Hermite poly-

nomials, as explained in [71]. In fact, the papers [71] and [72] contain more examples

of orthogonal polynomials which are moments, thus in particular implying Hankel de-

terminant evaluations whose entries are Laguerre polynomials, Meixner polynomials,

and Al-Salam“Chihara polynomials. Hankel determinants where the entries are (clas-

sical) orthogonal polynomials are also considered in [77], where they are related to

Wronskians of orthogonal polynomials. In particular, there result Hankel determinant

evaluations with entries being Legendre, ultraspherical, and Laguerre polynomials [77,

(12.3), (14.3), (16.5), § 28], respectively. The reader is also referred to [103], where

illuminating proofs of these identities between Hankel determinants and Wronskians

are given, by using the fact that Hankel determinants can be seen as certain Schur

functions of rectangular shape, and by applying a ˜master identity™ of Turnbull [178,

p. 48] on minors of a matrix. (The evaluations (3.52), (3.55) and (3.56) can be found in

[103] as well, as corollaries to more general results.) Alternative proofs of (3.52), (3.54)

and (3.55) can be found in [141], see also [139] and [140].

Clearly, to prove (3.56)“(3.58) one would proceed in the same way as in Section 2.7.

(Identity (3.58) is in fact the evaluation (2.38) that we derived in Section 2.7.) The

evaluations (3.59) and (3.60) are equivalent to (3.58), because the matrix underlying

the determinant in (3.58) has a checkerboard pattern (recall that Bernoulli numbers

with odd indices are zero, except for B1 ), and therefore decomposes into the prod-

uct of a determinant of the form (3.59) and a determinant of the form (3.60). Very

interestingly, variations of (3.56)“(3.60) arise as normalization constants in statistical

mechanics models, see e.g. [14, (4.36)], [32, (4.19)], and [108, App. A.5]. A common

generalization of (3.56)“(3.58) can be found in [51, Sec. 5]. Strangely enough, it was

needed there in the enumeration of rhombus tilings.

48 C. KRATTENTHALER

In view of Section 2.7, any continued fraction expansion of the form (2.30) gives rise

to a Hankel determinant evaluation. Thus, many more Hankel determinant evaluations

follow e.g. from work by Rogers [151], Stieltjes [171, 172], Flajolet [44], Han, Randri-

anarivony and Zeng [65, 64, 142, 143, 144, 145, 146, 201], Ismail, Masson and Valent

[70, 73] or Milne [113, 114, 115, 116], in particular, evaluations of Hankel determinant

featuring Euler numbers with odd indices (these are given through the generating func-

tion tan z = ∞ E2k+1 z 2k+1/(2k + 1)!), Genocchi numbers, q- and other extensions of

k=0

Catalan, Euler and Genocchi numbers, and coe¬cients in the power series expansion

of Jacobi elliptic functions. Evaluations of the latter type played an important role in

Milne™s recent beautiful results [113, 114] on the number of representations of integers

as sums of m-th powers (see also [108, App. A.5]).

For further evaluations of Hankel determinants, which apparently do not follow from

known results about continued fractions or orthogonal polynomials, see [68, Prop. 14]

and [51, Sec. 4].

Next we state two charming applications of Lemma 16 (see [189]).

Theorem 53. Let x be a nonnegative integer. For any nonnegative integer n there

hold

n+1

x (2)

(xi)!

det S(xi + j, xi) = (3.61)

(xi + j)! 2

0¤i,j¤n

where S(m, k) is a Stirling number of the second kind (the number of partitions of an

m-element set into k blocks; cf. [166, p. 33]), and

n+1

x (2)

(xi)!

s(xi + j, xi) = ’

det , (3.62)

(xi + j)! 2

0¤i,j¤n

where s(m, k) is a Stirling number of the ¬rst kind (up to sign, the number of permu-

tations of m elements with exactly k cycles; cf. [166, p. 18]).

Theorem 54. Let Aij denote the number of representations of j as a sum of i squares

of nonnegative integers. Then det0¤i,j¤n (Aij ) = 1 for any nonnegative integer n. The

same is true if “squares” is replaced by “cubes,” etc.

After having seen so many determinants where rows and columns are indexed by

integers, it is time for a change. There are quite a few interesting determinants whose

rows and columns are indexed by (other) combinatorial objects. (Actually, we already

encountered one in Conjecture 49.)

We start by a determinant where rows and columns are indexed by permutations.

Its beautiful evaluation was obtained at roughly the same time by Varchenko [184] and

Zagier [193].

Theorem 55. For any positive integer n there holds

n

inv(σπ’1 )

n

(1 ’ q i(i’1))( i )(i’2)! (n’i+1)! ,

det q = (3.63)

σ,π∈Sn

i=2

where Sn denotes the symmetric group on n elements.

ADVANCED DETERMINANT CALCULUS 49

This determinant evaluation appears in [193] in the study of certain models in in¬nite

statistics. However, as Varchenko et al. [20, 153, 184] show, this determinant evaluation

is in fact just a special instance in a whole series of determinant evaluations. The

latter papers give evaluations of determinants corresponding to certain bilinear forms

associated to hyperplane arrangements and matroids. Some of these bilinear forms

are relevant to the study of hypergeometric functions and the representation theory

of quantum groups (see also [185]). In particular, these results contain analogues of

(3.63) for all ¬nite Coxeter groups as special cases. For other developments related to

Theorem 55 (and di¬erent proofs) see [36, 37, 40, 67], tying the subject also to the

representation theory of the symmetric group, to noncommutative symmetric functions,

and to free Lie algebras, and [109]. For more remarkable determinant evaluations related

to hyperplane arrangements see [39, 182, 183]. For more determinant evaluations related

to hypergeometric functions and quantum groups and algebras, see [175, 176], where

determinants arising in the context of Knizhnik-Zamolodchikov equations are computed.

The results in [20, 153] may be considered as a generalization of the Shapovalov de-

terminant evaluation [159], associated to the Shapovalov form in Lie theory. The latter

has since been extended to Kac“Moody algebras (although not yet in full generality),

see [31].

There is a result similar to Theorem 55 for another prominent permutation statistics,

MacMahon™s major index. (The major index maj(π) is de¬ned as the sum of all positions

of descents in the permutation π, see e.g. [46].)

Theorem 56. For any positive integer n there holds

n

maj(σπ’1 )

(1 ’ q i )n! (i’1)/i.

det q = (3.64)

σ,π∈Sn

i=2

As Jean“Yves Thibon explained to me, this determinant evaluation follows from

results about the descent algebra of the symmetric group given in [95], presented

there in an equivalent form, in terms of noncommutative symmetric functions. For

the details of Thibon™s argument see Appendix C. Also the bivariate determinant

’1 ’1

detσ,π∈Sn xdes(σπ ) q maj(σπ ) seems to possess an interesting factorization.

The next set of determinant evaluations shows determinants where the rows and

columns are indexed by set partitions. In what follows, the set of all partitions of

{1, 2, . . . , n} is denoted by Πn . The number of blocks of a partition π is denoted by

bk(π). A partition π is called noncrossing, if there do not exist i < j < k < l such

that both i and k belong to one block, B1 say, while both j and l belong to another

block which is di¬erent from B1 . The set of all noncrossing partitions of {1, 2, . . . , n}

is denoted by NCn . (For more information about noncrossing partitions see [160].)

Further, poset-theoretic, notations which are needed in the following theorem are:

Given a poset P , the join of two elements x and y in P is denoted by x ∨P y, while

the meet of x and y is denoted by x §P y. The characteristic polynomial of a poset

P is written as χP (q) (that is, if the maximum element of P has rank h and µ is the

ˆ , where ˆ stands for the

h’rank(p)

M¨bius function of P , then χP (q) :=

o p∈P µ(0, p)q 0

minimal element of P ). The symbol χP (q) denotes the reciprocal polynomial q h χP (1/q)

˜

—

of χP (q). Finally, P is the order-dual of P .

50 C. KRATTENTHALER

Theorem 57. Let n be a positive integer. Then

n

(n)B(n’i)

i

bk(π§Πn γ)

det q = q χΠ— (q)

˜i , (3.65)

π,γ∈Πn

i=1

where B(k) denotes the k-th Bell number (the total number of partitions of a k-element

set; cf. [166, p. 33]). Furthermore,

n

S(n,i)

q bk(π∨Πn γ) =

det q χΠi (q) , (3.66)

π,γ∈Πn

i=1

where S(m, k) is a Stirling number of the second kind (the number of partitions of an

m-element set into k blocks; cf. [166, p. 33]). Next,

n

(2n’1’i)

2n’1

= q( n )

n’1

bk(π§NCn γ)

det q χNCi (q)

˜ , (3.67)

π,γ∈NCn

i=1

and

n

(2n’1’i)

2n

1

() n’1

bk(π∨NCn γ)

det q =q χNCi (q) , (3.68)

n+1 n

π,γ∈NCn

i=1

Finally,

√ 2n

i+1

( )

n’1

Ui+1 ( q/2) n n’1’i

2n’1

= q( ) √

bk(π∨Πn γ)

det q , (3.69)

n

qUi’1 ( q/2)

π,γ∈NCn

i=1

j m’j

(2x)m’2j is the m-th Chebyshev polynomials of the

where Um (x) := j≥0 (’1) j

second kind.

The evaluations (3.65)“(3.68) are due to Jackson [75]. The last determinant eval-

uation, (3.69), is the hardest among those. It was proved independently by Dahab

[33] and Tutte [181]. All these determinants are related to the so-called Birkho¬“Lewis

equation from chromatic graph theory (see [33, 180] for more information).

A determinant of somewhat similar type appeared in work by Lickorish [104] on 3-

manifold invariants. Let NCmatch(2n) denote the set of all noncrossing perfect match-

ings of 2n elements. Equivalently, NCmatch(2n) can be considered as the set of all

noncrossing partitions of 2n elements with all blocks containing exactly 2 elements.

Lickorish considered a bilinear form on the linear space spanned by NCmatch(2n). The

corresponding determinant was evaluated by Ko and Smolinsky [80] using an elegant

recursive approach, and independently by Di Francesco [47], whose calculations are

done within the framework of the Temperley“Lieb algebra (see also [49]).

Theorem 58. For ±, β ∈ NCmatch(2n), let c(±, β) denote the number of connected

components when the matchings ± and β are superimposed. Equivalently, c(±, β) =

bk(± ∨Π2n β). For any positive integer n there holds

n

c(±,β)

Ui (q/2)a2n,2i ,

det q = (3.70)

±,β∈NCmatch(2n)

i=1

where Um (q) is the Chebyshev polynomial of the second kind as given in Theorem 57,

and where a2n,2i = c2n,2i ’ c2n,2i+2 with cn,h = (n’h)/2 ’ (n’h)/2’1 .

n n

ADVANCED DETERMINANT CALCULUS 51

Di Francesco [47, Theorem 2] does also provide a generalization to partial matchings,

and in [48] a generalization in an SU(n) setting, the previously mentioned results being

situated in the SU(2) setting. While the derivations in [47] are mostly combinatorial,

the derivations in [48] are based on computations in quotients of type A Hecke algebras.

There is also an interesting determinant evaluation, which comes to my mind, where

rows and columns of the determinant are indexed by integer partitions. It is a result

due to Reinhart [147]. Interestingly, it arose in the analysis of algebraic di¬erential

equations.

In concluding, let me attract your attention to other determinant evaluations which

I like, but which would take too much space to state and introduce properly.

For example, there is a determinant evaluation, conjectured by Good, and proved by

Goulden and Jackson [60], which arose in the calculation of cumulants of a statistic anal-

ogous to Pearson™s chi-squared for a multinomial sample. Their method of derivation

is very combinatorial, in particular making use of generalized ballot sequences.

Determinants arising from certain raising operators of sl(2)-representations are pre-

sented in [136]. As special cases, there result beautiful determinant evaluations where

rows and columns are indexed by integer partitions and the entries are numbers of

standard Young tableaux of skew shapes.

In [84, p. 4] (see also [192]), an interesting mixture of linear algebra and combinatorial

matrix theory yields, as a by-product, the evaluation of the determinant of certain

incidence mappings. There, rows and columns of the relevant matrix are indexed by all

subsets of an n-element set of a ¬xed size.

As a by-product of the analysis of an interesting matrix in quantum information

theory [93, Theorem 6], the evaluation of a determinant of a matrix whose rows and

columns are indexed by all subsets of an n-element set is obtained.

Determinant evaluations of q-hypergeometric functions are used in [177] to compute

q-Selberg integrals.

And last, but not least, let me once more mention the remarkable determinant evalu-

ation, arising in connection with holonomic q-di¬erence equations, due to Aomoto and

Kato [11, Theorem 3], who thus proved a conjecture by Mimachi [118].

Appendix A: A word about guessing

The problem of guessing a formula for the generic element an of a sequence (an )n≥0

out of the ¬rst few elements was present at many places, in particular this is crucial for

a successful application of the “identi¬cation of factors” method (see Section 2.4) or of

LU-factorization (see Section 2.6). Therefore some elaboration on guessing is in order.