Pascal-like Determinants are Recursive

Helena Zakrajšek^{∗} Faculty of Mechanical Engineering University of Ljubljana, Slovenia

Marko Petkovšek^{†} Faculty of Mathematics and Physics University of Ljubljana, Slovenia

Abstract

Let P = [p_{i,j}]_{i,j≥0} be an infinite matrix whose entries satisfy p_{i,j} = μp_{i,j−1} + λp_{i−1,j} + νp_{i−1,j−1} for i, j ≥ 1, and whose first column resp. row satisfy linear recurrences with constant coefficients of orders ρ resp. σ. Then we show that its principal minors d_{n} satisfy d_{n} = ∑_{j=1}^{δ} c_{j}ω^{jn}d_{n−j} where c_{j} are constants, ω = λμ + ν, and δ = \binom{ρ+σ−2}{ρ−1}. This implies a recent conjecture of Bacher [2].

1 Introduction

The problem of symbolic evaluation of determinants has rightly received considerable attention in the literature (see [5] for an excellent survey). Nevertheless, we are still lacking a uniform mechanism for determinant evaluation akin to the well-known Zeilberger’s algorithm for evaluating hypergeometric sums [9]. Given the summand, Zeilberger’s algorithm constructs a recurrence (w.r.t. a parameter) which is satisfied by the sum in question. This recurrence is very useful as it can often be used to evaluate the sum in closed form, or to prove its properties by induction.

There have been attempts to emulate this approach in the determinant calculus, notably by using Dodgson’s recurrence satisfied by the minors of a matrix (see [10] and [1]). However, this recurrence is nonlinear, and furthermore, once unfolded, it involves all the contiguous minors of the starting matrix, which is unfortunate if only some of them (e.g., the principal ones) have a nice evaluation.

For matrices defined by simple linear recurrences with constant coefficients, R. Bacher has recently conjectured ([2, Conjecture 3.3]; see also [6]) that the sequence of their principal minors satisfies such a recurrence as well. More precisely, let P = [p_{i,j}]_{i,j≥0} be an infinite matrix with the following properties:

∗Helena.Zakrajsek@fs.uni-lj.si

†Marko.Petkovsek@fmf.uni-lj.si

1. The elements of the first column (p_{i,0})_{i≥0} satisfy a homogeneous linear recurrence with constant coefficients of order at most ρ, and the elements of the first row (p_{0,j})_{j≥0} satisfy a homogeneous linear recurrence with constant coefficients of order at most σ.

2. The remaining elements of P satisfy Pascal’s rule p_{i,j} = p_{i−1,j} + p_{i,j−1}.

Let d_{n} be the principal minor of P consisting of the elements in its first n + 1 rows and columns. Then Bacher conjectured that the sequence (d_{n})_{n≥0} satisfies a homogeneous linear recurrence with constant coefficients whose order is at most \binom{ρ+σ−2}{ρ−1}. In [2], he proved this conjecture in the case ρ = σ = 2. In the same paper, Bacher conjectured some evaluations of determinants whose entries satisfy the modified Pascal’s rule

p_{i,j} = p_{i−1,j} + p_{i,j−1} + xp_{i−1,j−1}.

These conjectured evaluations were later proved by Krattenthaler [6].

In this paper we prove a generalization of Bacher’s conjecture on principal minors of Pascal-like matrices. We allow that the matrix entries are defined recursively by

p_{i,j} = μp_{i,j−1} + λp_{i−1,j} + νp_{i−1,j−1}.

We show that when the elements of the first row and column (except, maybe, a few starting elements) satisfy homogeneous linear recurrence equations with constant coefficients then the sequence of the principal minors

1. is eventually zero if λμ + ν = 0,

2. satisfies a homogeneous linear recurrence with constant coefficients if λμ+ν = 1 (which implies Bacher’s conjecture where μ = λ = 1, ν = 0),

3. satisfies a homogeneous linear recurrence with exponential coefficients if λμ + ν ≠ 0, 1.

In the latter case, a simple substitution converts the recurrence into one with constant coefficients, so in all three cases it is possible to obtain a closed-form evaluation of the n-th principal minor.

Our proof, like Bacher’s in the case ρ = σ = 2, proceeds in two main steps: first we transform our Pascal-like matrix by determinant-preserving transformations to banddiagonal form. Then we show that the principal minors of every band-diagonal matrix satisfy a nontrivial linear recurrence. To avoid explicit summations in matrix products, we use generating functions. In Section 2 we show how to compute the generating function of a matrix product from the generating functions of its factors (Theorem 1), and characterize Pascal-like matrices through the type of their generating function. We also define (r, s)- banded matrices as band-diagonal matrices of bandwidth r + s + 1, with r subdiagonals and s superdiagonals. In Section 3 we show that the principal minors of any (r, s)-banded matrix M satisfy a homogeneous linear recurrence of order at most \binom{r+s}{r} (Theorem 2). If M is constant along diagonals this recurrence has constant coefficients. In Section 4 we transform a Pascal-like matrix to a (ρ−1, σ−1)-banded matrix while preserving the values of its principal minors (Theorem 3). Finally, in Section 5, we give our main result (Corollary 4) which implies an algorithm for evaluation of Pascal-like determinants in closed form (Remark 3), and present several examples of its use, and of applications of our methods to some other determinant evaluations.

2 Preliminaries

We work with infinite matrices of the form A = [a_{i,j}]_{i,j≥0} and their generating functions F_{A}(x, y) = ∑_{i,j≥0} a_{i,j}x^{i}y^{j}, regarded as formal power series in x and y. First we show how to compute the generating function of a matrix product from the generating functions of its factors.

Definition 1 Let f(u, v) = ∑_{i,j≥0} a_{i,j}u^{i}v^{j} be a formal power series in u and v. Its diagonal is the univariate series diag f = (diag f)(t) = ∑_{k≥0} a_{k,k}t^{k}.

Theorem 1 Let A = [a_{i,j}]_{i,j≥0} and B = [b_{i,j}]_{i,j≥0} be such that the sum ∑_{k≥0} a_{i,k}b_{k,j} has only finitely many nonzero terms for all i, j ≥ 0. Then F_{AB}(x, y) = g(1) where g(t) = (diag f)(t) and f(u, v) = F_{A}(x, u)F_{B}(v, y).

Proof: Write a^{k}(x) = ∑_{i≥0} a_{i,k}x^{i} and b_{k}(y) = ∑_{j≥0} b_{k,j}y^{j}. Then

F_{AB}(x, y) = ∑_{i,j,k≥0} a_{i,k}b_{k,j}x^{i}y^{j} = ∑_{k≥0} ∑_{i≥0} a_{i,k}x^{i} ∑_{j≥0} b_{k,j}y^{j} = ∑_{k≥0} a^{k}(x)b_{k}(y).

As

f(u, v) = F_{A}(x, u)F_{B}(v, y) = ∑_{i,k≥0} a_{i,k}x^{i}u^{k} ∑_{m,j≥0} b_{m,j}v^{m}y^{j}
= ∑_{k,m≥0} u^{k}v^{m} ∑_{i≥0} a_{i,k}x^{i} ∑_{j≥0} b_{m,j}y^{j} = ∑_{k,m≥0} a^{k}(x)b_{m}(y)u^{k}v^{m},

it follows that

(diag f)(t) = ∑_{k≥0} a^{k}(x)b_{k}(y)t^{k},

hence F_{AB}(x, y) = (diag f)(1) as claimed. □

Corollary 1 Let A and B be infinite matrices satisfying the assumptions of Theorem 1 and having rational generating functions. Write G(t, z) = F_{A}(x, t/z)F_{B}(z, y)/z. Then

(i) F_{AB}(x, y) = g(1) where g(t) = ∑_{i} Res_{z=z_{i}(t)}G(t, z), and the sum of residues ranges over those poles z = z_{i}(t) of G(t, z) for which lim_{t→0} z_{i}(t) = 0,

(ii) F_{AB}(x, y) is algebraic.

Proof: Item (i) follows from Theorem 1 and [4, Theorem 1] (see also [8, p. 182]), and (ii) is an immediate consequence of (i). □

Remark 1 Note that since the diagonals of f(u, v) and f(v, u) coincide, we may also take G(t, z) = F_{A}(x, z)F_{B}(t/z, y)/z in Corollary 1.

L = [ \begin{matrix}0 & 0 & 0 & 0 & … \\ 1 & 0 & 0 & 0 & … \\ 0 & 1 & 0 & 0 & … \\ 0 & 0 & 1 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ] R = [ \begin{matrix}0 & 1 & 0 & 0 & … \\ 0 & 0 & 1 & 0 & … \\ 0 & 0 & 0 & 1 & … \\ 0 & 0 & 0 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ]

Figure 1: Matrices L and R

Next we assign to each linear recurrence operator with constant coefficients a lower triangular matrix in a natural way. Let E denote the shift operator acting on sequences x = (x_{n})_{n≥0} by (Ex)_{n} = x_{n+1}. Define E^{−1} by (E^{−1}x)_{n} = x_{n−1} for n ≥ 1, (E^{−1}x)_{0} = 0. Clearly E^{−1} is a right inverse of E.

Let p(t) = ∑_{k=0}^{r} c_{k}t^{k} be a polynomial. Then

p(E^{−1}) = ∑_{k=0}^{r} c_{k}E^{−k}

is a linear recurrence operator acting on the space of sequences. Define M(p(E^{−1})) = [m_{i,j}]_{i,j≥0} to be the lower triangular, band-diagonal matrix with elements

m_{i,j} = \{ \begin{matrix}c_{i−j}, & 0 ≤ i − j ≤ r, \\ 0, & otherwise. \end{matrix}

Note that M(p(E^{−1})) is the matrix representing p(E^{−1}) in the canonical basis (e^{(j)})_{j≥0} where e_{n}^{(j)} = δ_{j,n} for all j, n ≥ 0. It is straightforward to compute its generating function

F_{M(p(E^{−1}))}(x, y) = \frac{p(x)}{1 − xy} .

Proposition 1 Denote L = M(E^{−1}) and R = L^{T} (see Fig. 1). Then F_{L^{k}}(x, y) = x^{k}/(1 − xy), F_{R^{k}}(x, y) = y^{k}/(1 − xy), and RL = I. Let A be an infinite matrix. Then LA is A with a new first row of zeros, AL is A without its first column, AR is A with a new first column of zeros, RA is A without its first row, F_{L^{k}A}(x, y) = x^{k}F_{A}(x, y), and F_{AR^{k}}(x, y) = y^{k}F_{A}(x, y). Also, LA = AL iff A is lower triangular and constant along diagonals (i.e., a_{i,j} depends only on i − j), and AR = RA iff A is upper triangular and constant along diagonals.

We omit the straightforward proof.

Definition 2 An infinite matrix P = [p_{i,j}]_{i,j≥0} is Pascal-like with parameters λ, μ, ν if its entries satisfy the recurrence

p_{i,j} = λp_{i−1,j} + μp_{i,j−1} + νp_{i−1,j−1}  for i, j ≥ 1,  (1)

and the generating functions of its first column and row, denoted α(x) = ∑_{i≥0} p_{i,0}x^{i} and β(y) = ∑_{j≥0} p_{0,j}y^{j}, respectively, are rational functions of x and y.

Proposition 2 A matrix P is Pascal-like with parameters λ, μ, ν if and only if its generating function is of the form

F_{P} (x, y) = \frac{f(x) + g(y)}{1 − λx − μy − νxy}  (2)

where f(x) and g(y) are univariate rational functions.

Proof: Let P be Pascal-like with parameters λ, μ, ν. Recurrence (1) is clearly equivalent to the matrix equation

P = λLP + μP R + νLP R + C  (3)

where c_{0,0} = p_{0,0}, c_{i,0} = p_{i,0} − λp_{i−1,0} for i ≥ 1, c_{0,j} = p_{0,j} − μp_{0,j−1} for j ≥ 1, and c_{i,j} = 0 for i, j ≥ 1. From (3) we obtain, by Proposition 1,

F_{P} (x, y) = λxF_{P} (x, y) + μyF_{P} (x, y) + νxyF_{P} (x, y) + F_{C}(x, y)

which implies

F_{P} (x, y) = \frac{F_{C}(x, y)}{1 − λx − μy − νxy}  (4)

where

F_{C}(x, y) = (1 − λx)α(x) + (1 − μy)β(y) − p_{0,0}.  (5)

Conversely, if F_{P} (x, y) = ∑_{i,j≥0} p_{i,j}x^{i}y^{j} is of the form (2) then, by equating the coefficients of like powers of x and y in (2), we obtain (1). The generating functions F_{P} (x, 0) = (f(x) + g(0))/(1 − λx) and F_{P} (0, y) = (f(0) + g(y))/(1 − μy) of the first column and row of P, respectively, are obviously rational. □

Note that (4) also immediately follows from [3, Equation (18)].

Corollary 2 Any submatrix S = [p_{i,j}]_{i≥i_{0},j≥j_{0}} of a Pascal-like matrix P = [p_{i,j}]_{i,j≥0} with parameters λ, μ, ν is again Pascal-like with the same parameters.

Proof: The entries of S clearly satisfy (1). By Proposition 2, the generating function F_{P} (x, y) is rational, hence so are the generating functions of any of its rows and columns. In particular, the generating functions of the first row and column of S, which are truncations of row i_{0} and column j_{0} of P, respectively, are rational. □

Unless noted otherwise, we use the following notation in the rest of the paper:

• P = [p_{i,j}]_{i,j≥0} is a Pascal-like matrix with parameters λ, μ, ν,

• α(x) = a_{1}(x)/a(x) = ∑_{i≥0} p_{i,0}x^{i} where a_{1} and a are polynomials and a(0) = 1,

• β(y) = b_{1}(y)/b(y) = ∑_{j≥0} p_{0,j}y^{j} where b_{1} and b are polynomials and b(0) = 1,

• ρ = deg a, σ = deg b,

• d_{n} = det [p_{i,j}]_{0≤i,j≤n},

• ω = λμ + ν.

Definition 3 Let r and s be nonnegative integers. An infinite matrix A = [a_{i,j}]_{i,j≥0} is (r, s)-banded if a_{i,j} = 0 unless −s ≤ i − j ≤ r.

Note that an (r, s)-banded matrix is band-diagonal with bandwidth at most r + s + 1. In particular, an (r, r)-banded matrix is (2r + 1)-diagonal.

Definition 4 Infinite matrices A = [a_{i,j}]_{i,j≥0} and B = [b_{i,j}]_{i,j≥0} are equimodular if the sequences of their principal minors agree, i.e., det[a_{i,j}]_{0≤i,j≤n} = det[b_{i,j}]_{0≤i,j≤n} for all n ≥ 0.

For example, if A is lower triangular with unit diagonal, then P, AP, and P A^{T} are equimodular matrices.

3 A recurrence for band-diagonal determinants

In this section we show that the sequence of principal minors of an (r, s)-banded matrix satisfies a homogeneous linear recurrence of order δ = \binom{r+s}{r}. This is a generalization of the well-known three-term recurrence satisfied by the principal minors of tridiagonal matrices, and also of [2, Theorem 7.1] which proves this result for matrices M satisfying m_{i,j} = m_{i−p,j−p} (p-periodic matrices).

Definition 5 A rational function f(x_{1}, …, x_{n}) is homogeneous of order k if f(tx_{1}, …, tx_{n}) = t^{k}f(x_{1}, …, x_{n}) where t is another indeterminate.

Theorem 2 Let A = [a_{i,j}]_{i,j≥0} be an (r, s)-banded matrix and δ = \binom{r+s}{r}. Denote by d_{n} the principal minor of A consisting of the elements in rows 0, 1, …, n and columns 0, 1, …, n of A. Then for n ≥ δ the sequence (d_{n})_{n≥0} satisfies a nontrivial homogeneous linear recurrence of the form d_{n} = ∑_{k=1}^{δ} R_{k}d_{n−k} where each R_{k} is a homogeneous rational function of order k of entries a_{n−i,n−j} (0 ≤ i ≤ δ − 1, −s ≤ j ≤ r + δ − 1).

Proof: Denote by

A \binom{c_{0}, c_{1}, …, c_{n}}{r_{0}, r_{1}, …, r_{n}}

the submatrix of A consisting of the elements in rows r_{0}, r_{1}, …, r_{n} and columns c_{0}, c_{1}, …, c_{n}. For 1 ≤ j_{1} < j_{2} < ⋯ < j_{r} ≤ r + s, define

A_{n}^{(j_{1},j_{2},...,j_{r})} = \{ \begin{matrix}A \binom{0,1,...,n−r,n−r+j_{1},n−r+j_{2},...,n−r+j_{r}}{0,1,...,n} , & n ≥ r, \\ A \binom{n−r+j_{r−n},n−r+j_{r−n+1},...,n−r+j_{r}}{0,1,...,n} , & n < r, \end{matrix}

and

d_{n}^{(j_{1},j_{2},...,j_{r})} = det A_{n}^{(j_{1},j_{2},...,j_{r})}.

Note that j_{s} ≥ s, so n − r + j_{r−n} ≥ 0. Also,

d_{n}^{(1,2,...,r)} = d_{n}.

Let n ≥ δ. To obtain a system of recurrences satisfied by d_{n}^{(j_{1},j_{2},...,j_{r})}, expand d_{n}^{(j_{1},j_{2},...,j_{r})} w.r.t. its last row. There are two cases to distinguish: a) If j_{r} = r + s, the expansion has only a single nonzero term:

d_{n}^{(j_{1},j_{2},...,j_{r})} = a_{n,n+s} d_{n−1}^{(1,j_{1}+1,j_{2}+1,...,j_{r−1}+1)}.  (6)

b) If j_{r} < r + s, we obtain the expansion

d_{n}^{(j_{1},j_{2},...,j_{r})} = (−1)^{r}a_{n,n−r} d_{n−1}^{(j_{1}+1,j_{2}+1,...,j_{r}+1)}
+ ∑_{i=1}^{r}(−1)^{r+i}a_{n,n−r+j_{i}} d_{n−1}^{(1,j_{1}+1,...,j_{i−1}+1,j_{i+1}+1,...,j_{r}+1)}  (7)

where a_{n,j} = 0 if j < 0.

Let S_{1}, S_{2}, …, S_{δ} be an enumeration of all r-subsets of {1, 2, …, r + s}, such that S_{1} = {1, 2, …, r}. If S_{i} = {j_{1}, j_{2}, …, j_{r}}, denote

d_{n}^{(i)} = d_{n}^{(j_{1},j_{2},...,j_{r})}.

Then (6) and (7) can be written uniformly as

d_{n}^{(i)} = ∑_{k=1}^{δ} c_{i,k}(n) d_{n−1}^{(k)} (1 ≤ i ≤ δ)  (8)

where each nonzero c_{i,k}(n) is one of a_{n,n−j} (−s ≤ j ≤ r) or its negative. By shifting (8) down δ − 1 times w.r.t. n we obtain δ^{2} linear equations

d_{n−j+1}^{(i)} = ∑_{k=1}^{δ} c_{i,k}(n − j + 1) d_{n−j}^{(k)} (1 ≤ i ≤ δ, 1 ≤ j ≤ δ).  (9)

The entries of A involved are a_{n−i,n−j} (0 ≤ i ≤ δ − 1, −s ≤ j ≤ r + δ − 1), where entries with a negative index are taken to be zero. We claim that these equations for the unknowns d_{n−j}^{(i)}, 1 ≤ i ≤ δ, 0 ≤ j ≤ δ, are linearly independent. To prove this, assume that a linear combination L of them vanishes identically. As each d_{n}^{(i)}, 1 ≤ i ≤ δ, appears in a single equation, and its coefficient in that equation equals 1, all the coefficients in L corresponding to these δ equations (which have j = 1) must vanish. But now each d_{n−1}^{(i)}, 1 ≤ i ≤ δ, appears in a single equation as well, and its coefficient in that equation equals 1, so again all the coefficients in L corresponding to these δ equations (which have j = 2) must vanish. Inductively, we see that all the coefficients in L vanish, which proves the claim.

It follows that from (9) we can eliminate (by Gaussian elimination, say) the δ^{2} − 1 unknowns d_{n−j}^{(i)}, 2 ≤ i ≤ δ, 0 ≤ j ≤ δ. This leaves us with a nontrivial linear equation involving the unknowns d_{n−j}^{(1)}, 0 ≤ j ≤ δ, which is the desired recurrence satisfied by the sequence (d_{n}^{(1)})_{n≥0} = (d_{n})_{n≥0}.

It remains to show that this recurrence has the promised form. Call a linear equation E of the form ∑_{k=1}^{δ} ∑_{j=0}^{σ} R_{j,k}d_{n−j}^{(k)} = 0 uniform if each coefficient R_{j,k} is a rational function of the matrix entries, homogeneous of degree j + t_{E} where t_{E} depends only on E. Equations (8) are clearly uniform in this sense, and Gaussian elimination preserves uniformity of equations. Hence the final equation (involving only d_{n−j} for 0 ≤ j ≤ δ) is uniform as well. Division by the highest nonzero coefficient, and some shifts if necessary, put it into the desired form. □

Remark 2 The asymmetry in the ranges of row and column indices of entries a_{n−i,n−j} which appear in the coefficients of the recurrence obtained in Theorem 2 ( 0 ≤ i ≤ δ − 1 vs. −s ≤ j ≤ r + δ − 1) seems to be an artefact of our proof. Had we expanded d_{n}^{(j_{1},j_{2},...,j_{r})} w.r.t. its last column rather than row (or equivalently, if we wrote down the recurrence for the transposed matrix A^{T}, then rewrote the coefficients in terms of the entries of A), the ranges would be −r ≤ i ≤ s + δ − 1 and 0 ≤ j ≤ δ − 1. But since elimination can be performed in such a way that the obtained recurrence is of minimal order, both recurrences should be the same. This argument, if made rigorous (which we believe could be done), would imply that the actual ranges are 0 ≤ i, j ≤ δ − 1, and that the recurrence is invariant under transposition a_{i,j} ↔ a_{j,i}. Both claims are supported by the example below.

Example 1 We wrote a Mathematica program based on the proof of Theorem 2 which computes a recurrence satisfied by the sequence of principal minors of an (r, s)-banded matrix. For a generic tridiagonal matrix (r = s = 1), we obtain for n ≥ 2

d_{n} = a_{n,n} d_{n−1} − a_{n−1,n} a_{n,n−1} d_{n−2}.  (10)

This recurrence is well known in numerical linear algebra where it is used in certain methods for computing eigenvalues of symmetric matrices.

For a generic pentadiagonal matrix (r = s = 2), we obtain for n ≥ 6

d_{n−6} a_{n−5,n−3} a_{n−4,n−2} a_{n−3,n−5} a_{n−3,n−1} a_{n−2,n−4} a_{n−1,n−3} (a_{n−2,n−1} a_{n−1,n} a_{n,n−2} −

a_{n−2,n} a_{n−1,n−2} a_{n,n−1}) +

d_{n−5} a_{n−4,n−2} a_{n−3,n−1} a_{n−2,n−4} a_{n−1,n−3} (a_{n−3,n−1} a_{n−2,n−3} a_{n−1,n} a_{n,n−2} −

a_{n−3,n−3} a_{n−2,n−1} a_{n−1,n} a_{n,n−2} − a_{n−3,n−2} a_{n−2,n} a_{n−1,n−3} a_{n,n−1} +
a_{n−3,n−3} a_{n−2,n} a_{n−1,n−2} a_{n,n−1}) −

d_{n−4} a_{n−3,n−1} a_{n−1,n−3} (a_{n−3,n−2} a_{n−2,n−1} a_{n−2,n} a_{n−1,n−3} a_{n,n−2} − a_{n−3,n−1} a_{n−2,n−3} a_{n−2,n} a_{n−1,n−2} a_{n,n−2} + a_{n−3,n−1} a_{n−2,n−3} a_{n−2,n−2} a_{n−1,n} a_{n,n−2} − a_{n−3,n−2} a_{n−2,n−3} a_{n−2,n−1} a_{n−1,n} a_{n,n−2} − a_{n−3,n−2} a_{n−2,n−2} a_{n−2,n} a_{n−1,n−3} a_{n,n−1} +

a_{n−3,n−2} a_{n−2,n−3} a_{n−2,n} a_{n−1,n−2} a_{n,n−1}) −

d_{n−3} (a_{n−3,n−2} a_{n−1,n−3} a_{n−1,n} a_{n,n−2} a_{n−2,n−1}^{2} −

a_{n−3,n−2} a_{n−2,n} a_{n−1,n−3} a_{n−1,n−1} a_{n,n−2} a_{n−2,n−1} −
a_{n−3,n−1} a_{n−2,n−2} a_{n−1,n−3} a_{n−1,n} a_{n,n−2} a_{n−2,n−1} +
a_{n−3,n−1} a_{n−2,n−3} a_{n−2,n} a_{n−1,n−2} a_{n−1,n−1} a_{n,n−2} −
a_{n−3,n−1} a_{n−2,n−3} a_{n−2,n} a_{n−1,n−2}^{2} a_{n,n−1} +
a_{n−3,n−1} a_{n−2,n−2} a_{n−2,n} a_{n−1,n−3} a_{n−1,n−2} a_{n,n−1}) −

d_{n−2} (a_{n−3,n−1} a_{n−2,n−1} a_{n−1,n−3} a_{n−1,n} a_{n,n−2} − a_{n−3,n−1} a_{n−2,n−3} a_{n−1,n−1} a_{n−1,n} a_{n,n−2} − a_{n−3,n−1} a_{n−2,n} a_{n−1,n−3} a_{n−1,n−2} a_{n,n−1} + a_{n−3,n−2} a_{n−2,n} a_{n−1,n−3} a_{n−1,n−1} a_{n,n−1} − a_{n−3,n−2} a_{n−2,n−1} a_{n−1,n−3} a_{n−1,n} a_{n,n−1} + a_{n−3,n−1} a_{n−2,n−3} a_{n−1,n−2} a_{n−1,n} a_{n,n−1}) −

d_{n−1} (a_{n−3,n−1} a_{n−2,n−3} a_{n−1,n} a_{n,n−2} − a_{n−3,n−2} a_{n−2,n} a_{n−1,n−3} a_{n,n−1} +

a_{n−3,n−2} a_{n−2,n−1} a_{n−1,n−3} a_{n,n} − a_{n−3,n−1} a_{n−2,n−3} a_{n−1,n−2} a_{n,n}) +

d_{n} (a_{n−3,n−2} a_{n−2,n−1} a_{n−1,n−3} − a_{n−3,n−1} a_{n−2,n−3} a_{n−1,n−2}) = 0.

The recurrence is simpler when the matrix A is constant along diagonals. Writing a_{n+2,n} = a, a_{n+1,n} = b, a_{n,n} = c, a_{n,n+1} = d, and a_{n,n+2} = e, we obtain for n ≥ 6

d_{n−6} a^{3} e^{3} − d_{n−5} a^{2} c e^{2} − d_{n−4} a e (a e − b d) − d_{n−3} (e b^{2} + a d^{2} − 2 a c e) +
d_{n−2} (b d − a e) − d_{n−1} c + d_{n} = 0.  (11)

If, in addition, the matrix A is symmetric (i.e., a = e and b = d), the order of the recurrence decreases by one. In this case we obtain for n ≥ 5

d_{n−5} a^{5} + d_{n−4} a^{3} (a − c) + d_{n−3} a (b^{2} − a c) − d_{n−2} (b^{2} − a c) − d_{n−1} (a − c) − d_{n} = 0. (12)

4 Transformation to band-diagonal form

In this section we show how to transform a Pascal-like matrix P to a band-diagonal matrix by a sequence of determinant-preserving elementary row and column operations. Following Bacher’s proof of his conjecture in the case ρ = σ = 2, we do this in two steps. At the first step, we multiply P with operator matrices corresponding to annihilators of its first column and row from the left and from the right, respectively.

Lemma 1 Let A = M(a(E^{−1})) and B = M(b(E^{−1})). Then

F_{AP B^{T}} (x, y) = \frac{F_{ACB^{T}} (x, y)}{1 − λx − μy − νxy}  (13)

where

F_{ACB^{T}} (x, y) = (1 − λx)a_{1}(x)b(y) + (1 − μy)a(x)b_{1}(y) − p_{0,0}a(x)b(y)  (14)

is a polynomial in x and y.

Proof: Multiply (3) by A from the left and by B^{T} from the right. Proposition 1 implies that AL = LA and RB^{T} = B^{T} R, hence

AP B^{T} = λLAP B^{T} + μAP B^{T} R + νLAP B^{T} R + ACB^{T} ,

which gives (13). Now we compute F_{ACB^{T}} (x, y) using Corollary 1, Remark 1, and Equation (5). The rational function

\frac{F_{A}(x, t/z)F_{C}(z, y)}{z} = \frac{a(x)}{z − xt}((1 − λz)α(z) + (1 − μy)β(y) − p_{0,0})

has a single pole z = xt satisfying z → 0 as t → 0, hence F_{AC}(x, y) = a(x)F_{C}(x, y). Similarly, from the residue of F_{AC}(x, z)F_{B^{T}} (t/z, y)/z at z = yt we obtain F_{ACB^{T}} (x, y) = a(x)b(y)F_{C}(x, y) which implies (14). □

It turns out that for each j there is a polynomial q_{j} with deg q_{j} ≤ j − 1 such that for i ≥ j + ρ, the i-th element of the j-th column of AP B^{T} equals q_{j}(i)λ^{i}. An analogous statement holds for the rows of AP B^{T}. Thus, at the second step, we annihilate these “out-of-the-band” entries by multiplying AP B^{T} with suitable lower resp. upper triangular matrices from the left resp. from the right.

Let S(c) = [s_{i,j}]_{i,j≥0} denote the infinite matrix with entries

s_{i,j} = \{ \begin{matrix}(−c)^{i−j}\binom{i}{j}, & i ≥ j, \\ 0, & i < j, \end{matrix}

whose generating function is

F_{S(c)}(x, y) = \frac{1}{1 + cx − xy} .  (15)

Further, let S_{r}(c) denote the block-diagonal matrix

S_{r}(c) = [ \begin{matrix}I_{r} & 0 \\ 0 & S(c) \end{matrix} ]

where I_{r} is the identity matrix of order r. Note that S_{r}(c) is lower triangular with unit diagonal, and that F_{S_{r}(c)}(x, y) = (1 − x^{r}y^{r})/(1 − xy) + x^{r}y^{r}/(1 + cx − xy). In particular,

F_{S_{1}(c)}(x, y) = \frac{1 + cx}{1 + cx − xy} .  (16)

Lemma 2 Let P be a Pascal-like matrix with parameters λ, μ, ν whose first column is zero. Then S(λ)P is an upper triangular matrix with zero diagonal.

Proof: By assumption, α(x) = 0. We use Corollary 1, (15), and (4). From the residue of

F_{S(λ)}(x, t/z)F_{P} (z, y)/z = \frac{1}{z(1 + λx) − xt} · \frac{(1 − μy)β(y)}{1 − λz − μy − νyz}

at z = xt/(1 + λx) we obtain

F_{S(λ)P} (x, y) = \frac{(1 − μy)β(y)}{1 − μy − ωxy} .

Hence F_{S(λ)P} (x, y) = f(y, xy) where

f(u, v) := \frac{(1 − μu)β(u)}{1 − μu − ωv}.

Thus F_{S(λ)P} (x, y) is a power series in y and xy, showing that S(λ)P is upper triangular, and the generating function of its diagonal is f(0, t) = β(0)/(1 − ωt) = p_{0,0}/(1 − ωt) = 0. □

Lemma 3 Let P be a Pascal-like matrix with parameters λ, μ, ν whose first column and row have generating functions of the form α(x) = a_{1}(x)/(1 − λx)^{ρ} and β(y) = b_{1}(y)/(1 − μy)^{σ}, respectively, where deg a_{1} < ρ and deg b_{1} < σ. Then

F_{S(λ)P S(μ)^{T}} (x, y) = \frac{(1 + λx)^{ρ−1}a_{1}(x/(1 + λx)) + (1 + μy)^{σ−1}b_{1}(y/(1 + μy)) − p_{0,0}}{1 − ωxy} (17)

where ω = λμ + ν.

Proof: We use Corollary 1, Remark 1, (15), and (4). From the residue of F_{S(λ)}(x, t/z)F_{P} (z, y)/z at z = xt/(1 + λx) we have

F_{S(λ)P} (x, y) = \frac{(1 + λx)^{ρ−1}a_{1}(x/(1 + λx)) + (1 − μy)^{1−σ}b_{1}(y) − p_{0,0}}{1 − μy − ωxy} .

From the residue of F_{S(λ)P} (x, z)F_{S(μ)^{T}} (t/z, y)/z at z = yt/(1 + μy) we obtain (17). □

Corollary 3 Let P satisfy the assumptions of Lemma 3. Then Q = S(λ)P S(μ)^{T} is an (ρ − 1, σ − 1)-banded matrix, and the sequence of elements along each diagonal is geometric with quotient ω.

Proof: This follows from the shape of the denominator of (17), and from the fact that the numerator of (17) is a sum of two polynomials, one of degree ρ − 1 and depending only on x, the other of degree σ − 1 and depending only on y. □

Now we have everything that we need to transform a general Pascal-like matrix to banddiagonal form.

Theorem 3 Let P be a Pascal-like matrix with deg a_{1} < ρ + k and deg b_{1} < σ + l where k and l are nonnegative integers. If A = M(a(E^{−1})) and B = M(b(E^{−1})) then M := S_{ρ+k}(λ)AP B^{T} S_{σ+l}(μ)^{T} is an (ρ+k −1, σ +l −1)-banded matrix, and each diagonal sequence (m_{i,i+d})_{i≥max{ρ+k,σ+l−d}} where −(ρ + k) ≤ d ≤ σ + l is geometric with quotient ω.

Proof: By Lemma 1,

F_{AP B^{T}} (x, y) = \frac{F_{ACB^{T}} (x, y)}{1 − λx − μy − νxy}

where F_{ACB^{T}} (x, y) is given in (14). The matrix Q := AP B^{T} is, in general, not Pascal-like. But it is only in the upper-left ((ρ + k) × (σ + l))-corner that recurrence (1) is not satisfied, therefore we divide Q in blocks as follows:

Q = [ \begin{matrix}Q_{1} \\ Q_{2} \end{matrix} ] = [ Q_{3} Q_{4} ] = [ \begin{matrix}Q_{1,1} & Q_{1,2} \\ Q_{2,1} & Q_{2,2} \end{matrix} ] ,

where Q_{1} has ρ+k rows, Q_{3} has σ+l columns, and Q_{1,1} is of order (ρ+k)×(σ+l). Recalling that

S_{ρ+k}(λ) = [ \begin{matrix}I_{ρ+k} & 0 \\ 0 & S(λ) \end{matrix} ] , S_{σ+l}(μ)^{T} = [ \begin{matrix}I_{σ+l} & 0 \\ 0 & S(μ)^{T} \end{matrix} ] ,

we have

M = S_{ρ+k}(λ)QS_{σ+l}(μ)^{T} = [ \begin{matrix}Q_{1,1} & Q_{1,2}S(μ)^{T} \\ S(λ)Q_{2,1} & S(λ)Q_{2,2}S(μ)^{T} \end{matrix} ] .

We are going to show that S(λ)Q_{2,1} is upper triangular with zero diagonal, Q_{1,2}S(μ)^{T} is lower triangular with zero diagonal, and N := S(λ)Q_{2,2}S(μ)^{T} is (σ +l −1, ρ+k −1)-banded. As n_{i,j} = m_{i+ρ+k,j+σ+l}, this will imply that M itself is (ρ + k − 1, σ + l − 1)-banded.

Clearly Q_{2} = R^{ρ+k}Q, Q_{4} = QL^{σ+l}, and Q_{2,2} = Q_{2}L^{σ+l} = R^{ρ+k}Q_{4}. From the residue of

\frac{z^{ρ+k}F_{ACB^{T}} (t/z, y)}{(1 − xz)((1 − μy)z − (λ + νy)t)}

at z = t(λ + νy)/(1 − μy) we have

F_{Q_{2}}(x, y) = (\frac{λ + νy}{1 − μy} )^{ρ+k} \frac{F_{ACB^{T}} ((1 − μy)/(λ + νy), y)}{1 − λx − μy − νxy}.

Similarly we obtain

F_{Q_{4}}(x, y) = (\frac{μ + νx}{1 − λx})^{σ+l} \frac{F_{ACB^{T}} (x, (1 − λx)/(μ + νx))}{1 − λx − μy − νxy}.

By Proposition 2, both Q_{2} and Q_{4} are Pascal-like matrices with parameters λ, μ, ν, and by Corollary 2, so is their common submatrix Q_{2,2}.

If λ ≠ 0 then the generating function of the first column of Q_{2} is, by (14) and (5),

F_{Q_{2}}(x, 0) = λ^{ρ+k} \frac{F_{ACB^{T}} (1/λ, 0)}{1 − λx} = λ^{ρ+k} \frac{a(1/λ)F_{C}(1/λ, 0)}{1 − λx} = 0.

It can be seen that F_{Q_{2}}(x, 0) = 0 also when λ = 0. By Lemma 2, it follows that S(λ)Q_{2} is upper triangular with zero diagonal. The same is then also true of S(λ)Q_{2,1}, which is composed of the first σ + l columns of S(λ)Q_{2}. In an analogous way, it can be shown that Q_{1,2}S(μ)^{T} is lower triangular with zero diagonal.

The generating function of the first row of Q_{2} is

F_{Q_{2}}(0, y) = (\frac{λ + νy}{1 − μy} )^{ρ+k} \frac{F_{ACB^{T}} ((1 − μy)/(λ + νy), y)}{1 − μy}.

From (14) it follows that f(y) := (λ + νy)^{ρ+k}F_{ACB^{T}} ((1 − μy)/(λ + νy), y) is a polynomial in y of degree at most ρ + k + σ + l. If μ ≠ 0 then f(1/μ) = (ω/μ)^{ρ+k}F_{ACB^{T}} (0, 1/μ) = (ω/μ)^{ρ+k}a(0)b(1/μ)F_{C}(0, 1/μ) = 0, so f(y) is divisible by 1 − μy. Hence F_{Q_{2}}(0, y) = f_{1}(y)/(1 − μy)^{ρ+k} where f_{1}(y) is a polynomial in y of degree less than ρ + k + σ + l. This can be seen to hold also when μ = 0.

By applying Extended Euclidean Algorithm to the coprime polynomials (1 − μy)^{ρ+k} and y^{σ+l} we can find polynomials p(y) and f_{2}(y) such that deg p < σ + l, deg f_{2} < ρ + k, and f_{1}(y) = (1 − μy)^{ρ+k}p(y) + y^{σ+l}f_{2}(y). Hence F_{Q_{2}}(0, y) = p(y) + y^{σ+l}f_{2}(y)/(1 − μy)^{ρ+k} where deg p < σ + l, so the generating function F_{Q_{2,2}}(0, y) of the first row of Q_{2,2} equals f_{2}(y)/(1 − μy)^{ρ+k} where deg f_{2} < ρ + k.

Similarly we can see that the generating function F_{Q_{2,2}}(x, 0) of the first column of Q_{2,2} is g_{2}(x)/(1 − λx)^{σ+l} where deg g_{2} < σ + l. Therefore, by Corollary 3, S(λ)Q_{2,2}S(μ)^{T} is an (σ + l − 1, ρ + k − 1)-banded matrix whose diagonals are geometric sequences with quotient ω. As already mentioned, this implies that M is (ρ + k − 1, σ + l − 1)-banded. □

5 Results and examples

Corollary 4 Let P be a Pascal-like matrix with deg a_{1} < ρ + k and deg b_{1} < σ + l where k and l are nonnegative integers, and let δ = \binom{ρ+k+σ+l−2}{ρ+k−1}. Then the sequence of its principal minors (d_{n})_{n≥0} for n ≥ δ + max(ρ + k, σ + l) satisfies a nontrivial linear recurrence of the form d_{n} = ∑_{j=1}^{δ} c_{j}ω^{jn}d_{n−j} where c_{j} are constants.

Proof: By Theorem 3, P is equimodular with an (ρ + k − 1, σ + l − 1)-banded matrix M whose nonzero entries are of the form m_{n,n+d} = m_{d} · ω^{n} for n ≥ max(ρ + k, σ + l − d) and −(ρ + k) ≤ d ≤ σ + l, where m_{d} depends only on d. By Theorem 2 and Remark 2, the sequence (d_{n})_{n≥0} for n ≥ δ satisfies a nontrivial recurrence of the form d_{n} = ∑_{j=1}^{δ} R_{j}d_{n−j} where each R_{j} is a rational function of m_{n−u,n−v} (0 ≤ u, v ≤ δ − 1). As R_{j} is homogeneous of order j and m_{n−u,n−v} = ω^{n} · m_{u−v}/ω^{u} for n − u ≥ ρ + k and n − v ≥ σ + l, this can be written in the announced form. □

Corollary 5 Let P and δ be as in Corollary 4. Then there are a nonnegative integer m ≤ δ, polynomials p_{1}(n), …, p_{m}(n), and algebraic numbers γ_{1}, …, γ_{m} of degree at most δ such that d_{n} = ω^{\binom{n}{2}} ∑_{i=0}^{m} p_{i}(n)γ_{i}^{n}, for all n ≥ max(ρ + k, σ + l).

Proof: Let n ≥ δ+max(ρ+k, σ+l). By Corollary 4, d_{n} = ∑_{j=1}^{δ} c_{j}ω^{jn}d_{n−j}. Write d_{n} = ω^{\binom{n}{2}}e_{n}. Then e_{n} = ∑_{j=1}^{δ} b_{j}e_{n−j} where b_{j} = c_{j}ω^{\binom{j+1}{2}}. The assertion now follows from the well-known theory of linear recurrences with constant coefficients. □

Remark 3 Let P be Pascal-like with deg a_{1} < ρ + k and deg b_{1} < σ + l. Denote δ = \binom{ρ+k+σ+l−2}{ρ+k−1} and m = max(ρ + k, σ + l). The closed-form expression for its n-th principal minor d_{n} as described in Corollary 5 can be obtained by the following algorithm:

1. For n = m, m + 1, …, m + 2δ − 1 evaluate e_{n} = d_{n}/ω^{\binom{n}{2}}.

2. Solve the Hankel system of δ linear algebraic equations

e_{n} = ∑_{j=1}^{δ} b_{j}e_{n−j} (m + δ ≤ n ≤ m + 2δ − 1)

for the unknown coefficients b_{1}, b_{2}, …, b_{δ}.

3. Find a closed-form representation of the sequence η_{n} which satisfies the recurrence

η_{n} = ∑_{j=1}^{δ} b_{j}η_{n−j} (n ≥ m + δ)

and initial conditions η_{n} = e_{n}, for n = m, m + 1, …, m + δ − 1. This step involves computation with algebraic numbers.

4. If n < m then compute d_{n} directly, else d_{n} = η_{n}ω^{\binom{n}{2}}.

Example 2 We illustrate the algorithm of Remark 3 on a “random” example. Let P = [p_{i,j}]_{i,j≥0} be the matrix defined by p_{0,0} = 1, p_{1,0} = 2, p_{0,1} = 1,

p_{i,0} = 3p_{i−1,0} − p_{i−2,0} (i ≥ 2),
p_{0,j} = p_{0,j−1} + p_{0,j−2} (j ≥ 2),
p_{i,j} = 2p_{i−1,j} + 3p_{i,j−1} − p_{i−1,j−1} (i, j ≥ 1).

This is a Pascal-like matrix with λ = 2, μ = 3, ν = −1, ω = 5, ρ = σ = 2, k = l = 0, δ = \binom{2}{1} = 2. Let d_{n} be its principal minor of order n + 1 and let e_{n} = d_{n}/5^{\binom{n}{2}}. Then by Corollary 4, e_{n} for n ≥ 4 satisfies a recurrence of order 2 with constant coefficients. From its initial values 1, 5, 24, 111, 495, 2124, 8721, 33885, 121824, 384831, 905175, … we find the recurrence e_{n} = 9e_{n−1} − 21e_{n−2} which happens to be valid for all n ≥ 2. We solve it and obtain the evaluation

d_{n} = \frac{2}{\sqrt{3}} (\frac{21}{5})^{n/2} 5^{n^{2}/2} cos (\frac{π}{6} − n arctan (\frac{\sqrt{3}}{9})) (n ≥ 0).

We conclude by giving several determinant evaluations which imply or generalize some results and examples from the literature.

Example 3 As a special case, Lemma 3 implies [6, Theorem 3] where P is given by

p_{i,j} = p_{i,j−1} + p_{i−1,j} + νp_{i−1,j−1}, i, j ≥ 1,

and p_{i,0} = −p_{0,i} = i for i ≥ 0. Here ρ = σ = 2, λ = μ = 1, ω = 1+ν, a(x) = b(x) = (1−x)^{2}, and a_{1}(x) = −b_{1}(x) = x. By Lemma 3, F_{S(λ)P S(μ)^{T}} (x, y) = (x − y)/(1 − ωxy), so P is equimodular with the tridiagonal matrix

[ \begin{matrix}0 & −1 & 0 & 0 & … \\ 1 & 0 & −ω & 0 & … \\ 0 & ω & 0 & −ω^{2} & … \\ 0 & 0 & ω^{2} & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ] .

Hence, by (10), the sequence (d_{n})_{n≥0} of principal minors of P satisfies the recurrence d_{n} = ω^{2n−2}d_{n−2} for n ≥ 2. Together with d_{0} = 0 and d_{1} = 1 this gives d_{2n} = 0, d_{2n−1} = ω^{2n(n−1)}.

Example 4 Let P be given by

p_{i,j} = p_{i,j−1} + p_{i−1,j} + νp_{i−1,j−1}, i, j ≥ 1,

p_{0,0} = 0, and p_{i,0} = −p_{0,i} = q^{i−1} for i ≥ 1 where q is a constant. Here μ = λ = 1, α(x) = −β(x) = x/(1 − qx), ρ = σ = k = l = 1, ω = 1 + ν, hence Theorem 3 implies that P is equimodular with a tridiagonal matrix whose diagonals (with the first two elements deleted) are geometric with quotient ω. In fact, following the proof of Theorem 3, this matrix turns out to be

[ \begin{matrix}0 & −1 & 0 & 0 & … \\ 1 & 0 & −(ν + q) & 0 & … \\ 0 & ν + q & 0 & −(ν + q)ω & … \\ 0 & 0 & (ν + q)ω & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ] .

Hence, by (10), the sequence (d_{n})_{n≥0} of principal minors of P satisfies the recurrence d_{n} = (ν + q)^{2}ω^{2n−4}d_{n−2}. Together with initial conditions d_{0} = 0, d_{1} = 1 this implies d_{2n} = 0 and d_{2n−1} = (ν + q)^{2n−2}ω^{2(n−1)^{2}}, in agreement with [6, Theorem 2].

Example 5 Let P be given by

p_{i,j} = p_{i,j−1} + p_{i−1,j}, i, j ≥ 1

with a 3-periodic sequence

(p_{0}, p_{1}, p_{2}, …, p_{k} = p_{k−3}, …)

as its first row and column. It is conjectured in [2, Example 3.5] that the sequence (d_{n})_{n≥0} of principal minors of P satisfies a certain recurrence of order 5. Indeed, Theorem 3 implies that P is equimodular with a pentadiagonal matrix which, starting with the third element, is constant along each diagonal. In fact, following the proof of Theorem 3, this matrix turns out to be

[ \begin{matrix}p_{0} & p_{1} & p_{2} & 0 & 0 & 0 & … \\ p_{1} & 2p_{1} & 2p_{1} + p_{2} & a & 0 & 0 & … \\ p_{2} & 2p_{1} + p_{2} & 4p_{1} + 2p_{2} & p_{0} + 6p_{1} + 2p_{2} & a & 0 & … \\ 0 & a & p_{0} + 6p_{1} + 2p_{2} & c & b & a & … \\ 0 & 0 & a & b & c & b & … \\ 0 & 0 & 0 & a & b & c & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ]

where a = p_{0} + p_{1} + p_{2}, b = 2p_{0} + 7p_{1} + 3p_{2}, c = p_{0} + 12p_{1} + 6p_{2}. Hence the sequence (d_{n})_{n≥0} satisfies recurrence (12) for n ≥ 9 (as it turns out, (12) holds for all n ≥ 5).

The following is a generalization of [6, Theorem 1] (see also [2, Theorem 1.5]).

Lemma 4 Let P be a matrix which satisfies (1), and whose first column has generating function of the form α(x) = p_{0,0}/(1 − qx). If A(q) = M(1 − qE^{−1}) then S_{1}(λ)A(q)P is an upper triangular matrix with diagonal elements

p_{0,0}, ξ, ξω, ξω^{2}, ξω^{3} …  (18)

where ξ = p_{0,0}ω + (p_{0,1} − μp_{0,0})(λ − q).

Proof: We use Corollary 1, Remark 1, (4), and (16). From the residue of

F_{A(q)}(x, t/z)F_{P} (z, y)/z = \frac{1 − qx}{z − xt} · \frac{F_{C}(z, y)}{1 − λz − μy − νzy}

at z = xt we obtain

F_{A(q)P} (x, y) = (1 − qx)F_{P} (x, y).

From the residue of

F_{S_{1}(λ)}(x, t/z)F_{A(q)P} (z, y)/z = \frac{(1 + λx)(1 − qz)}{z + λxz − xt}F_{P} (z, y)

at z = xt/(1 + λx) we obtain

F_{S_{1}(λ)A(q)P} (x, y) = \frac{(1 − μy)β(y) + (λ − q)x ((1 − μy)β(y) − p_{0,0})}{1 − μy − ωxy}.

The numerator can be rewritten as (1 − μy)β(y) + (λ − q)xy (∑_{k≥0} p_{0,k+1}y^{k} − μβ(y)), hence F_{S_{1}(λ)A(q)P} (x, y) = f(y, xy) where

f(u, v) := \frac{(1 − μu)β(u) + (λ − q)v (∑_{k≥0} p_{0,k+1}u^{k} − μβ(u))}{1 − μu − ωv}.

Thus F_{S_{1}(λ)A(q)P} (x, y) is a power series in y and xy, showing that S_{1}(λ)A(q)P is upper triangular. The generating function of its main diagonal is

f(0, t) = \frac{p_{0,0} + (p_{0,1} − μp_{0,0})(λ − q)t}{1 − ωt}

which gives (18). □

Remark 4 Note that in Lemma 4, the matrix P need not be Pascal-like (i.e., the lemma holds regardless of the algebraic nature of the first row of P).

Corollary 6 Let P satisfy the assumptions of Lemma 4. Then d_{n} = p_{0,0} ξ^{n} ω^{\binom{n}{2}}.

Our methods can also be applied to evaluate some determinants whose entries do not necessarily satisfy recurrence (1).

Lemma 5 Let M be a matrix whose i-th element of the j-th column is of the form q_{j}(i), where q_{j} is a polynomial with deg q_{j} = j. Then S(1)M is an upper triangular matrix with diagonal elements

(j! lc(q_{j}))_{j≥0},

where lc(q_{j}) denotes the leading coefficient of q_{j}.

Proof: Let N = S(1)M. As row k of S(1) consists of the coefficients of operator (1 − E^{−1})^{k}, the entries n_{k,0}, n_{k,1}, …, n_{k,k−1} all vanish, and n_{k,k} = (1 − E^{−1})^{k}q_{k}(i)|_{i=k} = k! lc(q_{k}). □

Example 6 Let

M_{n}(a, b, x; k) = [\binom{ai + bj + x}{j − k}]_{0≤i,j≤n} , a, b, x ∈ ℂ, k ∈ ℕ.

In [6, Theorem 4] it is shown that

det(M_{n}(2, 2, x; 0) − M_{n}(2, 2, x; 1)) = 2^{\binom{n+1}{2}}.

Using Lemma 5 this result can be extended. As for each j ∈ ℕ

\binom{ai + bj + x}{j − k}

is a polynomial in variable i of degree j − k whose leading coefficient is a^{j−k}/(j − k)! we obtain that

det M_{n}(a, b, x; k) = \{ \begin{matrix}a^{\binom{n+1}{2}}, & k = 0, \\ 0, & k > 0. \end{matrix}

Let M = ∑_{m=0}^{l} μ_{m}M_{n}(a_{m}, b_{m}, x_{m}; 0) be a linear combination of matrices of this type. Obviously, column j of M is a polynomial in the row index of degree j with leading coefficient ∑_{m=0}^{l} μ_{m}a_{m}^{j}/j!, therefore, by Lemma 5,

det ( ∑_{m=0}^{l} μ_{m}M_{n}(a_{m}, b_{m}, x_{m}; 0)) = ∏_{j=0}^{n} ( ∑_{m=0}^{l} μ_{m}a_{m}^{j}) .

Similarly, if M = ∑_{k=0}^{l} μ_{k}M_{n}(a_{k}, b_{k}, x_{k}; k) then column j of M is a polynomial in the row index of degree j with leading coefficient μ_{0}a_{0}^{j}/j!, thus

det (∑_{k=0}^{l} μ_{k}M_{n}(a_{k}, b_{k}, x_{k}; k)) = μ_{0}^{n+1}a\binom{n+1}{2}_{0}.

Acknowledgement

The second author wishes to express his thanks to Andrej Kmet for his help with Section 3. In particular, Andrej was the first to derive the seven-term recurrence (11).

References

[1] T. Amdeberhan, D. Zeilberger: Determinants through the looking glass, Adv. Appl. Math. 27 (2001), 225–230.

[2] R. Bacher: Determinants of matrices related to the Pascal triangle, J. Théorie Nombres Bordeaux 14 (2002), 19–41.

[3] M. Bousquet-Mélou, M. Petkovšek: Linear recurrences with constant coefficients: the multivariate case, Discrete Math. 225 (2000), 51–57.

[4] M. L. J. Hautus, D. A. Klarner: The diagonal of a double power series, Duke Math. J. 38 (1971), 229–235.

[5] C. Krattenthaler: Advanced determinant calculus, Séminaire Lotharingien Combin. 42 (2002), Article B42q, 67 pp.

[6] C. Krattenthaler: Evaluations of some determinants of matrices related to the Pascal triangle, Séminaire Lotharingien Combin. 47 (2002), Article B47g, 19 pp.

[7] R. P. Stanley: Generating functions, MAA Studies in Combinatorics (ed. G. C. Rota), Mathematical Association of America, 100–141.

[8] R. P. Stanley: Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge 1999.

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

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