Rectangular Scott-type Permanents

Guo-Niu Han et Christian Krattenthaler

Abstract. — Let x_{1}, x_{2}, …, x_{n} be the zeroes of a polynomial P (x) of degree n and y_{1}, y_{2}, …, y_{m} be the zeroes of another polynomial Q(y) of degree m. Our object of study is the permanent per(1/(x_{i} − y_{j}))_{1≤i≤n, 1≤j≤m}, here named “Scott-type” permanent, the case of P (x) = x^{n} − 1 and Q(y) = y^{n} + 1 having been considered by R. F. Scott. We present an efficient approach to determining explicit evaluations of Scott-type permanents, based on generalizations of classical theorems by Cauchy and Borchardt, and of a recent theorem by Lascoux. This continues and extends the work initiated by the first author (“Généralisation de l’identité de Scott sur les permanents,” to appear in Linear Algebra Appl.). Our approach enables us to provide numerous closed form evaluations of Scott-type permanents for special choices of the polynomials P (x) and Q(y), including generalizations of all the results from the above mentioned paper and of Scott’s permanent itself. For example, we prove that if P (x) = x^{n} − 1 and Q(y) = y^{2n} + y^{n} + 1 then the corresponding Scott-type permanent is equal to (−1)^{n+1}n!.

Résumé. — Soient x_{1}, x_{2}, …, x_{n} les zéros d’un polynôme P (x) de degré n et y_{1}, y_{2}, …, y_{m} les zéros d’un autre polynôme Q(y) de degré m. Notre objet d’étude est le permanent per(1/(x_{i} − y_{j}))_{1≤i≤n, 1≤j≤m}, appelé ici permanent de type Scott. Le cas de P (x) = x^{n} − 1 et Q(y) = y^{n} + 1 a été considéré par R. F. Scott. Nous présentons une approche efficace pour déterminer les évaluations explicites des permanents de type Scott, basée sur des généralisations des théorèmes classiques de Cauchy et Borchardt, et d’un théorème récent de Lascoux. La présente étude prolonge le travail du premier auteur (“Généralisation de l’identité de Scott sur les permanents,” à apparaître dans Linear Algebra Appl.). Notre approche nous permet de fournir de nombreuses évaluations explicites des permanents de type Scott pour des choix spéciaux des polynômes P (x) et Q(y), y compris des généalisations de tous les résultats de l’article mentionné ci-dessus et du permanent de Scott lui-même. Par exemple, nous prouvons que si P (x) = x^{n} − 1 et Q(y) = y^{2n} + y^{n} + 1 alors le permanent correspondant de type Scott est égal à (−1)^{n+1}n!.

1. Introduction

In 1881, Scott [16] stated, without proof, the following result: Let x_{1}, x_{2}, …, x_{n} be the zeroes of x^{n} − 1 and y_{1}, y_{2}, …, y_{n} be the zeroes of y^{n} + 1. Let A be the n × n matrix (1/(x_{i} − y_{j}))_{1≤i,j≤n}. Then

per(A) = \{ \begin{matrix}(−1)^{\frac{n−1}{2}} \frac{n(1 · 3 · 5 ⋯ (n − 2))^{2}}{2^{n}} , & if n is odd, \\ 0, & if n is even. \end{matrix}

In 1978, in his monograph Permanents, Minc [13, p. 155] included this result in a list of conjectures on permanents. Since then, several proofs have been given [3, 8, 14, 17], one of which by Minc himself. All of these proofs are heavily based on the fact that the zeroes of the polynomials x^{n} − 1 and y^{n} + 1 can be written in simple explicit terms. Thus, neither of these proofs extends to the more general problem which is the subject of this paper:

Given a polynomial P (x) of degree n and a polynomial Q(y) of degree m, let x_{1}, x_{2}, …, x_{n} be the zeroes of P (x) and y_{1}, y_{2}, …, y_{m} be the zeroes of Q(y). Evaluate the permanent of the n × m matrix (1/(x_{i} − y_{j}))_{1≤i≤n, 1≤j≤m}.

As usual, the permanent per(A) of an n × m matrix A is defined as the sum of all possible products of n coefficients of A chosen such that no two of the coefficients are taken from the same row nor from the same column (see [13, Ch. 1, (1.1)]). Given the assumptions of the above problem, we call the permanent of the matrix (1/(x_{i} − y_{j}))_{1≤i≤n, 1≤j≤m} a Scott-type permanent, and denote it by PER(P (x), Q(y)).

In [6], the first author presented a new approach to this type of problem in the case n = m, i.e., in the case that both polynomials have the same degree. This approach does not rely at all on explicit analytic forms of zeroes of polynomials. Instead, it makes essential use of recent symmetric functions techniques, in particular of a theorem due to Lascoux [11], which the latter author established in his étude on the square ice model of statistical mechanics.

In the present paper, we are going to extend this approach to arbitrary n and m. This requires extensions of classical theorems of Cauchy and Borchardt (see Theorems (Cauchy+) and (Borchardt+) in Section 2), and an extension of Lascoux’s theorem (see Theorem (Lascoux+)). As a result (see Theorem 1), we are able to express any Scott-type permanent as the quotient of a determinant which features complete homogeneous and elementary symmetric functions in the zeroes of the two polynomials, divided by the resultant of the two polynomials. In particular, it follows immediately that any Scott-type permanent is rational in the coefficients of the polynomials P (x) and Q(y).

In Section 5 we apply this result to obtain explicit evaluations of Scotttype permanents in numerous special cases. Amongst others, we provide generalizations of all the results from [6], thus also covering Scott’s permanent itself. For the proofs of the results in Section 5, we make use of two particular specializations of our main theorem, Theorem 1, which we derive in Section 3 (see Theorems 3 and 4), and of four determinant evaluations, which we state and establish separately in Section 4.

Finally, we also comment briefly on an alternative approach to the evaluation of Scott-type determinants, due to the first author [5]. It allows to express Scott-type permanents in terms of weighted sums over involutions (see Theorem 2 in Section 2). By combining this result with some of the evaluations in Section 5, we obtain interesting summation theorems, which are presented in Section 6.

2. The general theory

In [6], the main ingredients are theorems by Cauchy, Borchardt, Lascoux, and a lemma on the resultant. Since we intend to extend the approach of [6] to the case of rectangular Scott-type permanents (corresponding to polynomials of, possibly, different degrees), we have to first provide the appropriate extensions of these theorems.

Given positive integers m and n and two sets X = {x_{1}, x_{2}, …, x_{n}} and Y = {y_{1}, y_{2}, …, y_{m}} of variables, we use the following notations:

R(X, Y) := ∏_{i=1}^{n} ∏_{j=1}^{m}(x_{i} − y_{j}) and Δ(X) := ∏_{i<j}(x_{i} − x_{j}).

(\frac{1}{x_{i} − y_{j}} ) := ( \begin{matrix}\frac{1}{x_{1} − y_{1}} & \frac{1}{x_{1} − y_{2}} & ⋯ & \frac{1}{x_{1} − y_{m}} \\ \frac{1}{x_{2} − y_{1}} & \frac{1}{x_{2} − y_{2}} & ⋯ & \frac{1}{x_{2} − y_{m}} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ \frac{1}{x_{n} − y_{1}} & \frac{1}{x_{n} − y_{2}} & ⋯ & \frac{1}{x_{n} − y_{m}} \end{matrix} ) .

We first state a variation on Cauchy’s evaluation of his double alternant (cf. [4; 15, vol. 1, pp. 342–345]).

Theorem (Cauchy+). — For m ≥ n, let

C(X, Y) := ( \begin{matrix}\frac{1}{x_{1} − y_{1}} & \frac{1}{x_{1} − y_{2}} & ⋯ & \frac{1}{x_{1} − y_{m}} \\ \frac{1}{x_{2} − y_{1}} & \frac{1}{x_{2} − y_{2}} & ⋯ & \frac{1}{x_{2} − y_{m}} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ \frac{1}{x_{n} − y_{1}} & \frac{1}{x_{n} − y_{2}} & ⋯ & \frac{1}{x_{n} − y_{m}} \\ 1 & 1 & ⋯ & 1 \\ y_{1} & y_{2} & ⋯ & y_{m} \\ y_{1}^{2} & y_{2}^{2} & ⋯ & y_{m}^{2} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ y_{1}^{m−n−1} & y_{2}^{m−n−1} & ⋯ & y_{m}^{m−n−1} \end{matrix} ) .

Then

det(C(X, Y)) = (−1)^{n(n−1)/2} \frac{Δ(X)Δ(Y)}{R(X, Y)}.

Proof. — If n = m, this is exactly Cauchy’s theorem. The general case can be either established directly, or, it may be observed that the “general” case is in fact implied by Cauchy’s theorem. To see this, consider the above identity with n = m. Given k < m, expand both sides as power series in 1/x_{k+1}, …, 1/x_{m}, and compare coefficients of 1/x_{k+1}x_{k+2}^{2} ⋯ x_{m}^{m−k} on both sides.

Next we state the required extension of Borchardt’s theorem [2; 15, vol. 2, pp. 173–175]. It can be established by reading through the proof of Borchardt’s theorem given in [1, Proof of Cor. 5.1], ignoring however the restriction m = n (see also [5]).

Theorem (Borchardt+). — For m ≥ n, let

B(X, Y) := ( \begin{matrix}\frac{1}{(x_{1} − y_{1})^{2}} & \frac{1}{(x_{1} − y_{2})^{2}} & ⋯ & \frac{1}{(x_{1} − y_{m})^{2}} \\ \frac{1}{(x_{2} − y_{1})^{2}} & \frac{1}{(x_{2} − y_{2})^{2}} & ⋯ & \frac{1}{(x_{2} − y_{m})^{2}} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ \frac{1}{(x_{n} − y_{1})^{2}} & \frac{1}{(x_{n} − y_{2})^{2}} & ⋯ & \frac{1}{(x_{n} − y_{m})^{2}} \\ 1 & 1 & ⋯ & 1 \\ y_{1} & y_{2} & ⋯ & y_{m} \\ y_{1}^{2} & y_{2}^{2} & ⋯ & y_{m}^{2} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ y_{1}^{m−n−1} & y_{2}^{m−n−1} & ⋯ & y_{m}^{m−n−1} \end{matrix} ) .

Then

det(B(X, Y)) = det(C(X, Y)) × per (\frac{1}{x_{i} − y_{j}} ) .

Our next goal is to derive the required extension of (a special case of) Lascoux’s theorem [11, Theorem q]. Let Z = {z_{1}, z_{2}, …, z_{n}} be another set of variables, of equal cardinality as X. For 1 ≤ i ≤ n we define the divided difference ∂_{i} by

∂_{i} : f ↦ \frac{f − f^{σ_{i}}}{x_{i} − z_{i}} ,

where σ_{i} is the transposition which interchanges x_{i} and z_{i}. It is easy to see that

∂_{i} \frac{1}{z_{i} − y} = \frac{1}{(x_{i} − y)(z_{i} − y)}.

Since the operator ∂_{i} acts only on one row of the matrix C(Z, Y) (to be precise, the i-th row), it follows that

∂_{1}∂_{2} ⋯ ∂_{n}(det(C(Z, Y))|_{Z=X} = det(B(X, Y)).  (1)

Now, to generalize Lascoux’s theorem to our case, one simply reads through the proof of Theorem q in [11], on introducing slight modifications if necessary. The result is:

Theorem (Lascoux+). — Let H(X) be the n × (m + n − 1) matrix defined by

H(X) := (h_{j−i}(X))_{1≤i≤n,1≤j≤m+n−1},

where h_{s}(X) denotes the complete homogeneous symmetric function of degree s in the variables X (cf. [12, Ch. 1]), and E(Y) be the (m+n−1)×n matrix defined by

E(Y) := ((j − 2k + 2)(−1)^{m−j+k−1}e_{m−j+k−1}(Y))_{1≤j≤m+n−1,1≤k≤n},

where e_{s}(Y) denotes the elementary symmetric function of degree s in the variables Y (cf. [12, Ch. 1]). Then

∂_{1}∂_{2} ⋯ ∂_{n}(Δ(Z)R(X, Y))|_{Z=X} = Δ(X) det(H(X)E(Y)).

Now we are in the position to state our main theorem, which will enable us, in Section 5, to evaluate numerous Scott-type permanents in closed form. The theorem implies immediately that any Scott-type permanent PER(P (x), Q(y)) is a rational function in the coefficients of the two polynomials P (x) and Q(y).

Theorem 1. — Let m and n be arbitrary positive integers, and let X = {x_{1}, x_{2}, …, x_{n}} and Y = {y_{1}, y_{2}, …, y_{m}} be two sets of variables. Then

per (\frac{1}{x_{i} − y_{j}} ) = \frac{det(H(X)E(Y))}{R(X, Y)}.

Proof. — First let m ≥ n. By combining Theorems (Cauchy+) and (Borchardt+), and Equation (1), we obtain

(−1)^{n(n−1)/2} \frac{R(X, Y)}{Δ(X)Δ(Y)}∂_{1}∂_{2} ⋯ ∂_{n}(det(C(Z, Y))|_{Z=X}

for the permanent. Now we apply Theorem (Cauchy+) again in order to replace C(Z, Y) by the corresponding product form guaranteed by the theorem. After having used that the divided differences ∂_{i} commute with Δ(Y)/R(X, Y)R(Z, Y) (because the latter expression is symmetric in x_{i} and z_{i}), Theorem (Lascoux+) applies and yields the desired result.

If m < n, the permanent clearly vanishes. According to Theorem (Lascoux+), it suffices to establish that

U := ∂_{1}∂_{2} ⋯ ∂_{n}(Δ(Z)R(X, Y)) = 0.

To begin with, we rewrite the Vandermonde determinant evaluation as Δ(Z)R(X, Y) = (−1)^{n(n−1)/2} det(z_{i}^{j−1}R(x_{i}, Y)). Writing Q(x_{i}) := R(x_{i}, Y) = a_{m}x_{i}^{m} + ⋯ + a_{1}x_{i} + a_{0}, we obtain for U the expression

U = det(∂_{i}z_{i}^{j−1}R(x_{i}, Y)) = det(z_{i}^{j−1}Q(x_{i}) − x_{i}^{j−1}Q(z_{i}))/ ∏(x_{i} − z_{i}).

Since for m < n, we have

∑_{j=0}^{m} a_{m}(z_{i}^{j}Q(x_{i}) − x_{i}^{j}Q(z_{i})) = 0,

the m + 1 elements z_{i}^{j}Q(x_{i}) − x_{i}^{j}Q(z_{i}), 0 ≤ j ≤ m, are linearly dependent. Hence, U = 0.

In [5], the first author obtained another expression for the permanent, in form of a certain weighted sum over involutions. To state and explain this formula, for s ∈ X define

L(s; X, Y) := ∑_{x≠s} \frac{1}{x − s} + ∑_{y∈Y} \frac{1}{s − y} .

Let us denote by I(n) the set of involutions on {1, 2, …, n}. Given an involution σ ∈ I(n), we define the weight Ψ(σ) of σ by

Ψ(σ; X, Y) := ∏_{(ij)∈σ} \frac{1}{(x_{i} − x_{j})^{2}} ∏_{(k)∈σ} L(x_{k}; X, Y)

where the first product is over all transpositions (ij) in the disjoint cycle decomposition of σ, and where the second product is over all fixed points k of σ. Then the result from [5] is the following.

Theorem 2. — Let m and n be arbitrary positive integers, and let X = {x_{1}, x_{2}, …, x_{n}} and Y = {y_{1}, y_{2}, …, y_{m}} be two sets of variables. Then

per (\frac{1}{x_{i} − y_{j}} ) = ∑_{σ∈I(n)} Ψ(σ; X, Y).

Example 1. — Let n = 1, X = {x}, Y = {y_{1}, y_{2}, …, y_{m}}. Then

H(X) := (h_{j−1}(X))_{i=1,1≤j≤m} = (h_{0}(x), h_{1}(x), …, h_{m−1}(x)),
E(Y) := (j(−1)^{m−j}e_{m−j}(Y))_{1≤j≤m,k=1}
= (1(−1)^{m−1}e_{m−1}(Y), 2(−1)^{m−2}e_{m−2}(Y), …, me_{0}(Y))^{t}.

We have

H(X)E(Y) = ∑_{j=0}^{m−1}(j + 1)(−1)^{m−j−1}e_{m−j−1}(Y)x^{j}.

Therefore,

per (\frac{1}{x − y} ) = \frac{1}{x − y_{1}} + \frac{1}{x − y_{2}} + ⋯ + \frac{1}{x − y_{m}} [Definition, Th. 2]

= \frac{∑_{j=0}^{m−1}(j + 1)(−1)^{m−j−1}e_{m−j−1}(Y)x^{j}}{(x − y_{1})(x − y_{2}) ⋯ (x − y_{m})} . [Th. 1]

Example 2. — For n = 4 and m = 3, Theorem 1 yields the following identity:

det ((\begin{matrix}h_{0} & h_{1} & h_{2} & h_{3} & h_{4} & h_{5} \\ 0 & h_{0} & h_{1} & h_{2} & h_{3} & h_{4} \\ 0 & 0 & h_{0} & h_{1} & h_{2} & h_{3} \\ 0 & 0 & 0 & h_{0} & h_{1} & h_{2} \end{matrix}) × (\begin{matrix}e_{2} & e_{3} & 0 & 0 \\ −2e_{1} & 0 & 2e_{3} & 0 \\ 3e_{0} & −e_{1} & −e_{2} & 3e_{3} \\ 0 & 2e_{0} & 0 & −2e_{2} \\ 0 & 0 & e_{0} & e_{1} \\ 0 & 0 & 0 & 0 \end{matrix})) = 0.

For n = 2 and m = 1, Theorem 2 yields

\frac{1}{(x_{1} − x_{2})^{2}} + (\frac{1}{x_{2} − x_{1}} + \frac{1}{x_{1} − y} ) (\frac{1}{x_{1} − x_{2}} + \frac{1}{x_{2} − y} ) = 0.

3. The case of P (x) = x^{n} − 1 and of P (x) = x^{n−1} + ⋯ + x + 1 In this section we specialize Theorem 1 to the case that the x_{i}’s are the

zeroes of the polynomial P (x) = x^{n} −1 or of P (x)+x^{n−1} +⋯+x+1, and the y_{i}’s are the zeroes of an arbitrary other polynomial. (This covers, for example, the case of Scott’s identity). For the remainder of this section, we fix m and n, m ≥ n.

Let X = {x_{1}, x_{2}, …, x_{n}} be the set of zeroes of x^{n} − 1, and let Y = {y_{1}, y_{2}, …, y_{m}} be the set of zeroes of Q(x) = a_{m}y^{m} + a_{m−1}y^{m−1} + ⋯ + a_{1}y^{1} + a_{0}, with a_{m} = 1. We write

PER(P, Q) := per (\frac{1}{x_{i} − y_{j}} ) = \frac{det(H(X)E(Y))}{R(X, Y)}.  (2)

Since

∑ h_{i}(X)t^{i} = \frac{1}{∏_{i}(1 − tx_{i})} = \frac{1}{(1 − t^{n})} = 1 + t^{n} + t^{2n} + ⋯,

we have

h_{k}(X) = \{ \begin{matrix}1, & if k = 0 (mod n), \\ 0, & if k ≠ 0 (mod n). \end{matrix}

We denote by I_{k} the k × k identity matrix, and by 0_{l,c} the l × c matrix with all entries equal to 0. For all r, we write r%n for the number between 1 and n that satisfies r (mod n) = r%n (mod n). Then we have

H(X) = ( I_{n} I_{n}  ⋯ I_{n}  \begin{matrix}I & m′ \\ 0 & n−m′,m′ \end{matrix} ) ,

with m′ = (m + n − 1)%n.

Furthermore, let diag_{n}^{i}(c_{1}, c_{2}, …, c_{n}) denote the n × n “diagonal” matrix, in which the (broken) diagonal starts in the i-th row,

( \begin{matrix}0_{i−1,n−i+1} & diag_{i−1}(c_{n−i+2}, c_{n−i+3}, …, c_{n}) \\ diag_{n−i+1}(c_{1}, c_{2}, …, c_{n−i+1}) & 0_{n−i+1,i−1} \end{matrix} ) .

According to the definition of E(Y), a simple calculation yields that

H(X)E(Y) = ∑_{r=0}^{m} diag_{n}^{r%n}(ra_{r}, (r − 1)a_{r}, …, (r − n + 1)a_{r}).

Example 3. — For n = 3 and m = 4, let P (x) = x^{3} − 1 and Q(y) = y^{4} + a_{3}y^{3} + a_{2}y^{2} + a_{1}y + a_{0}. Then H(X)E(Y) is the sum of the following matrices:

(\begin{matrix}0 & −a_{0} & 0 \\ 0 & 0 & −2a_{0} \\ 0 & 0 & 0 \end{matrix}) + (\begin{matrix}a_{1} & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & −a_{1} \end{matrix}) + (\begin{matrix}0 & 0 & 0 \\ 2a_{2} & 0 & 0 \\ 0 & a_{2} & 0 \end{matrix}) + (\begin{matrix}0 & 2a_{3} & 0 \\ 0 & 0 & a_{3} \\ 3a_{3} & 0 & 0 \end{matrix}) + (\begin{matrix}4 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 2 \end{matrix}) .

In the theorem below, we summarize our findings.

Theorem 3. — Let P (x) = x^{n}−1 and Q(y) = a_{m}y^{m}+⋯+a_{1}y^{1}+a_{0}, a_{m} not necessarily 1. Writing

Fes(Q) = det(∑_{r=0}^{m} diag_{n}^{r%n}(ra_{r}, (r − 1)a_{r}, …, (r − n + 1)a_{r})), (3)

we have

PER(P, Q) = \frac{Fes(Q)}{Res(P, Q)},

where Res is the classical resultant of two polynomials.

Proof. — We have already seen that the theorem is true for a_{m} = 1. On the other hand, there hold Fes(λQ) = λ^{n}Fes(Q) and Res(P, λQ) = λ^{n}Res(P, Q), as is easily verified.

Now let us consider the case that X = {x_{1}, x_{2}, …, x_{n−1}} is the set of zeroes of P (x) = x^{n−1} + ⋯ + x + 1. We perform an analysis very similar to the one before, using the fact that we have

∑ h_{i}(X)t^{i} = \frac{1}{∏_{i}(1 − tx_{i})} = \frac{1 − t}{∏_{i}(1 − t^{n})} = 1 − t + t^{n} − t^{n+1} + − · · · .

In order to state the result, we introduce the following notation: We write d̃iag_{n−1}^{i}(c_{1}, c_{2}, …, c_{n−1}) for the (n − 1) × (n − 1) matrix

( \begin{matrix}0_{i−1,n−i} & 0_{i−1,1} & diag_{i−2}(c_{n−i+2}, c_{n−i+3}, …, c_{n−1}) \\ diag_{n−i}(c_{1}, c_{2}, …, c_{n−i}) & 0_{n−i,1} & 0_{n−i+1,i−2} \end{matrix} )

if i > 1, respectively diag_{n−1}(c_{1}, c_{2}, …, c_{n−1}) if i = 1. This is again a matrix with a (possibly broken) diagonal, in which the diagonal “jumps over” one row and column in the case that it is broken. (Note the slight discrepancy in dimension between the diagonal and the zero matrices.)

Theorem 4. — Let P (x) = x^{n−1} + ⋯ + x + 1 and Q(y) = a_{m}y^{m} + ⋯ + a_{1}y^{1} + a_{0}, a_{m} not necessarily 1. Writing

F̃es(Q) = det(∑_{r=0}^{m} d̃iag_{n−1}^{r%n}(ra_{r}, (r − 1)a_{r}, …, (r − n + 2)a_{r})

− ∑_{r=0}^{m} d̃iag_{n−1}^{(r−1)%n}(ra_{r}, (r − 1)a_{r}, …, (r − n + 2)a_{r})),

(4)

we have

PER(P, Q) = \frac{F̃es(Q)}{Res(P, Q)},

where, again, Res is the classical resultant of two polynomials.

According to Theorems 3 and 4, for accomplishing the evaluation of the permanent, it is necessary to evaluate the numerator Fes(Q), respectively F̃es(Q), and the denominator Res(P, Q). For the evaluation of the resultant Res(P, Q), we make use of the following lemma, which, for example, appears explicitly in [7]. (In fact, it follows from a special case of Proposition 6 in the next section.)

Lemma 5. — Let d be the greatest common divisor of m and n, and let A and C be two nonzero constants. Then the resultant of the two polynomials Ax^{m} − B and Cx^{n} − D is given by

Res(Ax^{m} − B, Cx^{n} − D) = (−1)^{m}(A^{n/d}D^{m/d} − B^{n/d}C^{m/d})^{d}.

What concerns the evaluation of Fes(Q), respectively F̃es(Q), we refer the reader to the next section for the determinant evaluations that we are going to use. In combination with Lemma 5, these will allow us to evaluate Scott-type permanents in numerous special cases, see Section 5.

4. Determinant evaluations

Proposition 6. — Let n and r be positive integers, r ≤ n, and x_{1}, x_{2}, …, x_{n}, y_{1}, y_{2}, …, y_{n} be indeterminates. Then, with d = gcd(r, n), we have

\begin{aligned}det & ( \begin{matrix}x_{1} & 0 & … & 0 & y_{n−r+1} & 0 \\ 0 & x_{2} & 0 & & 0 & y_{n−r+2} & 0 \\ & & ... & & & & ... & 0 \\ 0 & & & & & & 0 & y_{n} \\ y_{1} & 0 \\ 0 & y_{2} & 0 \\ & 0 & ... & 0 & & & ... & 0 \\ & & 0 & y_{n−r} & 0 & & 0 & x_{n} \end{matrix} ) \\ & = ∏_{i=1}^{d} ( ∏_{j=1}^{n/d} x_{i+(j−1)d} − (−1)^{n/d} ∏_{j=1}^{n/d} y_{i+(j−1)d}). \end{aligned}

(5)

(I.e., in the matrix there are only nonzero entries along two diagonals, one of which is a broken diagonal.)

Proof. — Let A = (A_{ij})_{1≤i,j≤n} be the matrix of which the determinant is taken in (5). By definition, we have

det A = ∑_{σ∈S_{n}} sgn σ ∏_{i=1}^{n} A_{iσ(i)},  (6)

where S_{n} denotes the symmetric group of order n. Since the matrix A is a sparse matrix, only those permutations σ contribute to the sum which have the property σ(i) = i or σ(i) = i + r mod n for all i. Thus, the decomposition into disjoint cycles of such a permutation consists only of cycles of length 1, and of cycles of length n/d of the form (i, i + r, …, i + (n/d − 1)r) (where, again, all integers have to be taken modulo n). Using these observations and the fact that the sign of any cycle of length n/d is (−1)^{n/d−1} in (6) yields (5) immediately.

Theorem 7. — Let a, b, c, d, e be indeterminates. For any positive integer n and integers i, j let n(i, j) denote 1 plus (the representative between 0 and n − 1 of) the residue class of i − j mod n. Then

det_{1≤i,j≤n} ((n(i, j) + c)(n(i, j)a + b) + d − (j − 1)(n(i, j)a + e))

= det ( \begin{matrix}(c + 1)(a + b) & (c + n)(na + b) & & (c + 2)(2a + b) \\ +d & +d − (na + e) & … & +d − (n − 1)(2a + e) \\ (c + 2)(2a + b) & (c + 1)(a + b) & & (c + 3)(3a + b) \\ +d & +d − (a + e) & … & +d − (n − 1)(3a + e) \\ ⋮ & ⋮ & … & ⋮ \\ (c + n)(na + b) & (c + n − 1) & & (c + 1)(a + b) \\ +d & ×((n − 1)a + b) + d & … & +d − (n − 1)(a + e) \\ & −((n − 1)a + e) \end{matrix} )

= (−n)^{n−1}U_{n}(a, b, c, d, e) ∏_{i=3}^{n}(ia + b + ca), (7)

where U_{n}(a, b, c, d, e) is the polynomial

U_{n}(a, b, c, d, e) = \frac{(n + 1)(n + 2)}{3} a^{2} + \frac{(n + 1)(2n + 7)}{6} ab + \frac{(n + 1)}{2} b^{2}

+ \frac{(n + 1)(2n + 7)}{6} a^{2}c + \frac{(3n + 5)}{2} abc + b^{2}c + \frac{(n + 1)}{2} a^{2}c^{2} + abc^{2} + \frac{(n + 3)}{2} ad

+ bd + acd − \frac{(n − 1)(2n + 5)}{6} ae − \frac{(n − 1)}{2} be − \frac{(n − 1)}{2} ace.

In the case that n = 2, the product in (7) has to be read as 1, and in the case that n = 1, the product has to be interpreted as 1/(2a + b + ca).

Proof. — In the cases n = 1 and n = 2, the claim can be verified directly. For n ≥ 3, we use the “identification of factors” method as explained in [10, Sec. 2.4] or [9, Sec. 2].

We proceed in several steps. An outline is as follows. In the first step we show that ∏_{i=3}^{n}(ia + b + ca) is a factor of the determinant as a polynomial in a, b, c, d, e. In the second step we prove that U_{n}(a, b, c, d, e) is a factor of the determinant. Then, in the third step, we determine the maximal degree of the determinant as a polynomial in a, and also in b, c, d, and in e. It turns out that the maximal degree is n as a polynomial in a, the same being true as a polynomial in b and as a polynomial in c, while it is 1 as a polynomial in d, the same being true as a polynomial in e. On the other hand, the degree in a, and also in b and in c, of the product on the right-hand side of (7), which by the first two steps divides the determinant, is exactly n. It is exactly 1 in d and also in e. Therefore we are forced to conclude that the determinant equals

C(n)U_{n}(a, b, c, d, e) ∏_{i=3}^{n}(ia + b + ca),  (8)

where C(n) is a constant independent of a, b, c, d, e. Finally, in the fourth step, we determine the constant C(n), which turns out to equal (−n)^{n−1}. Clearly, this would finish the proof of theorem.

Step 1. For i = 3, …, n the term (ia + b + ca) is a factor of the determinant. We claim that, if b = −ia − ca, we have

− (row (n − i)) + 3(row (n − i + 1))
− 3(row (n − i + 2)) + (row (n − i + 3)) = 0

as long as n > i. (Here, (row i) denotes the i-th row of the matrix underlying the determinant in (7).) In the case that n = i, we claim that we have

−3(row 1) + 3(row 2) − (row 3) + (row n) = 0

as long as n > 3, and that we have −(row 1) + (row 2) = 0 if n = 3. All these claims are easily verified by an obvious case-by-case analysis.

Step 2. The polynomial U_{n}(a, b, c, d, e) is a factor of the determinant. We claim that if d is chosen so that U_{n}(a, b, c, d, e) vanishes, we have

∑_{j=1}^{n}((j + 1)a + b + ca)(column j) = 0.

Again, it is a routine task to verify this identity.

Step 3. The determinant is a polynomial in a (in b, respectively in c) of maximal degree n, and a polynomial in d (respectively in e) of maximal degree 1. The first claim follows from the fact that each term in the defining expansion of the determinant has degree n in a (as well as in b, respectively in c). To establish the second claim, we simply subtract the first row of the determinant from all other rows, with the effect that only the entries in the first row contain d and e after these transformations. Since the right-hand side of (7), which by Steps 1 and 2 divides the determinant as a polynomial in a, b, c, d, e, also has degree n in a, in b, and in c, and degree 1 in d, and in e, the determinant and the right-hand side of (7) differ only by a multiplicative constant.

Step 4. The evaluation of the multiplicative constant. By the preceding steps we know that the determinant equals (8). In particular, if we set a = c = d = e = 0 and b = 1, we have

det_{1≤i,j≤n} (n(i, j)) = C(n)(n + 1)/2.  (9)

The matrix on the left-hand side of (9) is a circulant matrix with entries 1, 2, …, n. Hence, its determinant equals

∏_{ω : zero of x^{n}−1}(1 + 2ω + 3ω^{2} + ⋯ + nω^{n−1}).

The sum is easily evaluated by observing that it is the derivative of a geometric series. It turns out to be equal to −n/(1 − ω). The resulting product simplifies by the observation

∏_{ω : zero of x^{n}−1, ω≠1}(1 − ω) = (1 + x + ⋯ + x^{n−1})|_{x=1} = n.  (10)

Thus, the determinant in (9) equals (−n)^{n−1}(n + 1)/2. Therefore C(n) is equal to (−n)^{n−1}.

This finishes the proof of (7) and thus of the theorem.

Theorem 8. — Let a be an indeterminate. For any positive integer n and integers i, j let s(i, j) denote (the representative between 0 and n−1 of) the residue class of i − j + 1 mod n. Then

det_{1≤i,j≤n−1}(\{ \begin{matrix}(n − m − 1) + j(1 + a − n) & if i = j − 2 (mod n) \\ (n − 1)(m − 1) + j(1 − a) & if i = j − 3 (mod n) \\ (n − m − 3 − 2s(i, j)) + j & otherwise \end{matrix} \})

= (−1)^{n−1} \frac{1}{n} ∏_{i=2}^{n}(nm − ia). (11)

Proof. — The matrix underlying this determinant is a matrix whose elements have a uniform definition, except for two (broken) diagonals, the one with i = j − 2 (mod n), and the one with i = j − 3 (mod n).

To begin with, we reorder the rows so that the next-to-last row becomes the first row, the last row becomes the second row, and then follow the remaining rows in their original order.

Now we add all the rows to the (new) last row. In the resulting matrix, we change the sign of the last row and, subsequently, move it up so that it becomes the third row. As a result of these manipulations, we obtain

(−1)^{n−1} det_{1≤i,j≤n−1} (\{ \begin{matrix}(n − 1)(m − 1) + j(1 − a) & if i = j \\ (n − m − 1) + j(a − n + 1) & if i = j + 1 \\ −m − n + 1 − 2i + 3j & if i < j \\ −m + n + 1 − 2i + 3j & if i > j + 1 \end{matrix} \}) . (12)

Next we apply further row operations. We subtract the second row from the first, the third from the second, …, the (n − 1)-st row from the (n − 2)-nd row, in that order. Subsequently, we repeat the same kind of operations, but stop before the last row, i.e., we subtract the second row from the first, the third from the second, …, the (n − 2)-nd row from the (n − 3)-rd row, in that order. As a result, the above determinant is converted into the determinant of the following matrix

(\{ \begin{matrix}nm − ja & if i = j − 2 \\ −2nm + 2n − j(3a − n) & if i = j − 1 and i < n − 2 \\ nm − 2n − j(3a − 2n) & if i = j and i < n − 2 \\ j(a − n) & if i = j + 1 and i < n − 2 \\ 2 & if i = n − 2 and j ≤ n − 4 \\ (n − 3)(a − n) + 2 & if i = n − 2 and j = n − 3 \\ nm − 2n + 2 − (n − 2)(2a − n) & if i = n − 2 and j = n − 2 \\ n − nm + 1 + (n − 1)(a − 1) & if i = n − 2 and j = n − 1 \\ −m − n + 3 + 3j & if i = n − 1 and j ≤ n − 3 \\ n − m − 1 + (n − 2)(a − n + 1) & if i = n − 1 and j = n − 2 \\ (n − 1)(m − a) & if i = n − 1 and j = n − 1 \\ 0 & otherwise \end{matrix} \}) .

(13)

This is a matrix with four “special” diagonals (the diagonals with i = j−2, j − 1, j, j + 1, respectively) and two “special” rows (the last two rows). All other entries are zero.

Now we factor (nm−3a) out of the first row. Subsequently, we substract (a−n) times the (new) first row from the second. Now one is able to factor (nm − 4a) out of the (new) second row. Next, we substract 2(a − n) times the (new) second row from the third row. Etc. We stop this procedure in the (n − 3)-rd row. Thus, the determinant of the matrix in (13) is equal to ∏_{i=3}^{n−1}(nm − ia) times the determinant of the matrix

( \begin{matrix}1 & −2 & 1 & 0 & … \\ 0 & 1 & −2 & 1 & 0 & … \\ ⋮ & ... & ... & ... & ... & ⋮ \\ ⋮ & ... & ... & ... & ... & 0 \\ 0 & 1 & −2 & 1 \\ a_{n−2,1} & a_{n−2,2} & . . . . . . . . . . . . . . . . . . . & a_{n−2,n−1} \\ a_{n−1,1} & a_{n−1,2} & . . . . . . . . . . . . . . . . . . . & a_{n−1,n−1} \end{matrix} ) ,  (14)

where the entries in the last two rows are still the same as in (13).

We now perform the final set of transformations. We add column 1 through column n − 2 to column n − 1, and then we add

∑_{j=1}^{n−3}(n − j − 1)(column j)

to column n − 2. The effect is that a block matrix is obtained of the form

( \begin{matrix}U & 0 \\ ∗ & M \end{matrix} ) ,

where U is an (n − 3) × (n − 3) upper-triangular matrix with 1s on the diagonal, and where M is the 2 × 2 matrix

( \begin{matrix}nm − n − 2a + 2 & n − 2 \\ \frac{1}{2}(n − 2)(n + m + 2a − nm − 3) & \frac{5}{2}n − \frac{n^{2}}{2} + m − a − 3 \end{matrix} ) .

Clearly, the determinant of U is 1, while the determinant of M is (m − a)(nm − 2a). Putting everything together, we have completed the proof of (11).

Corollary 9. — Let a be an indeterminate. For any positive integer n and integers i, j let s(i, j) denote (the representative between 0 and n−1 of) the residue class of i − j + 1 mod n. Then

det_{1≤i,j≤n−1} (\{ \begin{matrix}−2s(i, j) − a + j − 1 & if i ≠ j − 2 (mod n) \\ (n − 1)(n + a − j − 1) & if i = j − 2 (mod n) \end{matrix} \})

= n^{n−2} ∏_{i=0}^{n−2}(i + a). (15)

Proof. — In the determinant, we move the last row on top, replace the (now) last row by the sum of all the rows, factor (−1) out of the resulting row, and finally move it up so that it becomes the second row, retaining the order of all the other rows. These operations did not change the value of the determinant. However, the resulting determinant is exactly the determinant in (12) with a = n and m = a + n. As we have shown in the proof of Theorem 8, the latter determinant differs from the determinant in (11) just by a sign of (−1)^{n−1}. Thus, we obtain the right-hand side of (15).

5. Closed form evaluations for Scott-type permanents

Theorem 10. — Let n, m and r be positive integers and d = gcd(n, r). Then

\begin{matrix}PER(x^{n} − 1, ∑_{ℓ=0}^{m} a_{ℓ}y^{ℓn} + ∑_{ℓ=0}^{m} b_{ℓ}y^{ℓn+r}) \\ = − \frac{\begin{matrix}d^{n} ∏_{i=1}^{d} (( ∑_{ℓ=0}^{m} a_{ℓ})^{n/d}( ∑_{ℓ=0}^{m}(i − nℓ − 1)a_{ℓ}/ ∑_{ℓ=0}^{m} da_{ℓ})_{n/d} \\ − ( − ∑_{ℓ=0}^{m} b_{ℓ})^{n/d}( ∑_{ℓ=0}^{m}(i − r − nℓ − 1)b_{ℓ}/ ∑_{ℓ=0}^{m} db_{ℓ})_{n/d}) \end{matrix}}{(( ∑_{ℓ=0}^{m} a_{ℓ})^{n/d} − ( − ∑_{ℓ=0}^{m} b_{ℓ})^{n/d})^{d}} , \end{matrix}

where (α)_{k} is the standard notation for shifted factorials, (α)_{k} := α(α + 1) ⋯ (α + k − 1), k ≥ 1, and (α)_{0} := 1.

Proof. — Let us first consider the case that n ∤ r. According to Theorem 3, we have to compute the quotient Fes(Q)/Res(x^{n} − 1, Q), where Q = ∑_{ℓ=0}^{m} a_{ℓ}y^{ℓn} + ∑_{ℓ=0}^{m} b_{ℓ}y^{ℓn+r}. In order to compute Fes(Q), in (3) we replace a_{ℓn} by a_{ℓ} and a_{ℓn+r} by b_{ℓ}, ℓ = 0, 1, …, m, and set all other a_{ℓ}’s equal to zero. In the resulting determinant we move the last row to the top, thus creating a sign of (−1)^{n−1}, and finally apply Proposition 6 with x_{j} = ∑_{ℓ=0}^{m}(nℓ − j + 1)a_{ℓ} and y_{j} = ∑_{ℓ=0}^{m}(nℓ + r − j + 1)b_{ℓ}, j = 1, 2, …, n. For the evaluation of Res(x^{n} − 1, Q) we note that

Res(x^{n} − 1, ∑_{ℓ=0}^{m} a_{ℓ}y^{ℓn} + ∑_{ℓ=0}^{m} b_{ℓ}y^{ℓn+r})

= ∏_{ω : zero of x^{n}−1} ( ∑_{ℓ=0}^{m} a_{ℓ} + ω^{r} ∑_{ℓ=0}^{m} b_{ℓ}) = Res(x^{n} − 1, y^{r} ∑_{ℓ=0}^{m} b_{ℓ} + ∑_{ℓ=0}^{m} a_{ℓ}).

Now we can apply Lemma 5.

If on the other hand n | r, then d = n. It can be verified directly that the claimed formula remains valid in that case, too.

Remark. — Given a polynomial Q(y), there is no unique way to write it in the form ∑_{ℓ=0}^{m} a_{ℓ}y^{ℓn} + ∑_{ℓ=0}^{m} b_{ℓ}y^{ℓn+r}. For example, we may write Q(y) = y^{n} + a + b as Q(y) = (y^{n} + ay^{0}) + b, or as Q(y) = (y^{n} + (a + b)) (i.e., either with a_{1} = 1, a_{0} = a, r = 0, b_{0} = b, or with a_{1} = 1, a_{0} = a + b, b_{ℓ} = 0 for all ℓ). Regardless which choice we make, Theorem 10 yields

PER(x^{n} − 1, y^{n} + a + b) = (−1)^{n+1} \frac{∏_{i=1}^{n}(i − (n − i)(a + b))}{(a + b + 1)^{n}}.

Corollary 11. — Let n and m be positive integers. Then

PER(x^{n} − 1, ∑_{ℓ=0}^{m} a_{ℓ}y^{ℓn}) = −( − n ∑_{ℓ=0}^{m} ℓa_{ℓ}/ ∑_{ℓ=0}^{m} a_{ℓ})_{n}.

Corollary 12. — We have

PER(x^{n} − 1, y^{mn} + ⋯ + y^{2n} + y^{n} + 1) = −(−mn/2)_{n}.

Corollary 13. — If m is even then

PER(x^{n} + 1, y^{mn} + ⋯ + y^{2n} + y^{n} + 1) = (−mn/2)_{n}.

Proof. — We use the case a_{ℓ} = (−1)^{ℓ} in Corollary 11, and the fact that

per (\frac{1}{x_{i} ^{n} \sqrt{−1} − y_{j}} )_{1≤i≤n, 1≤j≤mn}= −per (\frac{1}{x_{i} − y_{j}/ ^{n} \sqrt{−1}})_{1≤i≤n, 1≤j≤mn} .

Corollary 14. — We have

PER(x^{n} − 1, ∑_{ℓ=0}^{m} ℓy^{ℓn}) = −(−n(2m + 1)/3)_{n}.

Corollary 15. — We have

PER(x^{n} − 1, ∑_{ℓ=0}^{m} ℓy^{ℓ^{2}n}) = −(−nm(m + 1)/2)_{n}.

Corollary 16. — We have

PER(x^{n} − 1, y^{mn} + ay^{rn} + b) = −(−(m + ra)n/(a + b + 1))_{n}.

Corollary 17. — We have

PER(x^{n} − 1, y^{mn} + 1) = −(−mn/2)_{n}.

For m = 1 one recovers Scott’s identity stated at the beginning of the introduction.

Corollary 18. — If m + ra = a + b + 1 ≠ 0, then

PER(x^{n} − 1, y^{mn} + ay^{rn} + b) = (−1)^{n+1}n!.

Corollary 19. — If a ≠ −2 then

PER(x^{n} − 1, y^{2n} + ay^{n} + 1) = (−1)^{n+1}n!.

Corollary 20. — If m + ra = 0 and a + b + 1 ≠ 0, then

PER(x^{n} − 1, y^{mn} + ay^{rn} + b) = 0.

Corollary 21. — If b ≠ 1 then

PER(x^{n} − 1, y^{2n} − 2y^{n} + b) = 0.

Corollary 22. — Let n and m be positive integers and d = gcd(n, m). Then

PER(x^{n} − 1, y^{m} + b) = −\frac{d^{n} ∏_{i=1}^{d} ((\frac{i−m−1}{d})_{n/d} − (−b)^{n/d} (\frac{i−1}{d})_{n/d})}{(1 − (−b)^{n/d})^{d}}.

Proof. — In Theorem 10, set m = 0, a_{0} = b, b_{0} = 1, and replace r by m, in this order.

Corollary 23. — If gcd(m, n) = 1, then

PER(x^{n} − 1, y^{m} + b) = (−1)^{n+1} \frac{m(m − 1) ⋯ (m − n + 1)}{1 − (−b)^{n}}.

Corollary 24. — If gcd(m, n) = 1, then

\begin{matrix}PER(x^{s(n−1)} + ⋯ + x^{2s} + x^{s} + 1, y^{s(m−1)} + ⋯ + y^{2s} + y^{s} + 1) \\ = \frac{∏_{i=0}^{s−1} ( ∏_{ℓ=0}^{n−1}(i + ℓs) − ∏_{ℓ=0}^{n−1}(i + ℓs − ms))}{(mns)^{s}}. \end{matrix}

Proof. — Consider the Scott-type permanent PER(x^{sn} − 1, y^{sm} − q^{sm}) (expressed in terms of its definition). When we multiply it by (1 − q)^{s} and then perform the limit q → 1, then the permanent reduces to PER(x^{s(n−1)} + ⋯ + x^{s} + 1, y^{s(m−1)} + ⋯ + y^{s} + 1), as is straightforward to see. On the other hand, the permanent that we started with is the permanent in Corollary 22 with n replaced by sn, m replaced by sm, and b = −q^{sm}. Indeed, if we multiply the right-hand side from Corollary 22 (with these choices for the parameters) by (1 − q)^{sm}, and then perform the limit q → 1, we obtain exactly the claimed result.

Corollary 25. — If gcd(m, n) = 1, then

\begin{matrix}PER(x^{n−1} + ⋯ + x + 1, y^{m−1} + ⋯ + y + 1) \\ = (−1)^{n+1} \frac{(m − 1) ⋯ (m − n + 1)}{n}. \end{matrix}

Corollary 26. — If gcd(m, n) = 1 and n is odd, then

PER(x^{n} − 1, y^{m} + 1) = \frac{m(m − 1) ⋯ (m − n + 1)}{2}.

Corollary 27. — If n is odd, then

PER(x^{n} − 1, y^{n+1} + 1) = \frac{(n + 1)!}{2}.

Corollary 28. — Let n and r be positive integers (not necessarily n > r) and d = gcd(n, r). Then

\begin{matrix}PER(x^{n} − 1, y^{n} + ay^{r} + b) \\ = −\frac{d^{n} ∏_{i=1}^{d}((b + 1)^{\frac{n}{d}} (\frac{ib − b + i − n − 1}{d(b + 1)})_{\frac{n}{d}} − (−a)^{\frac{n}{d}} (\frac{i − r − 1}{d})_{\frac{n}{d}} )}{((b + 1)^{\frac{n}{d}} − (−a)^{\frac{n}{d}} )^{d}}. \end{matrix}

Proof. — In Theorem 10, set m = 1, a_{0} = b, a_{1} = 1, b_{0} = a, and b_{1} = 0.

Corollary 29. — Let n and r be positive integers (not necessarily n > r) and gcd(n, r) = 1. Then

PER(x^{n} − 1, y^{n} + ay^{r} + b) = (−1)^{n+1} \frac{∏_{i=1}^{n}(i − (n − i)b)) − a^{n}(−r)_{n}}{(b + 1)^{n} − (−a)^{n}} .

If 1 ≤ r ≤ n − 1 then (−r)_{n} = 0. Thus, one recovers the results in [6]. On the other hand, if we set r = n + 1, we obtain, for example, the following result.

Corollary 30. — We have

PER(x^{n} − 1, y^{n+1} + y^{n} − 1) = n^{n} − (−1)^{n}(n + 1)!.

Corollary 31. — We have

PER(x^{n} − 1, y^{n} + ny − 1) = 1.

Theorem 32. — Let n and m be positive integers and a be an arbitrary number. Then

\begin{matrix}PER(x^{n} − 1, ∑_{ℓ=0}^{mn−1}(ℓ + a)y^{ℓ}) \\ = (−1)^{n−1} \frac{n(m − 1) V_{n}(a, m)}{6 (mn + 2a − 1)} (a + (m − 1)n + 1)_{n−2} , \end{matrix}

where V_{n}(a, m) is the polynomial

V_{n}(a, m) = 1 − 6a + 6a^{2} + n − 2an − 5mn + 10amn − mn^{2} + 4m^{2}n^{2}.

Proof. — Let Q = ∑_{ℓ=0}^{mn−1}(ℓ + a)y^{ℓ}. Using Theorem 3 again, we have to compute Fes(Q)/Res(x^{n} − 1, Q). In order to compute Fes(Q), in (3) set a_{ℓ} = ℓ + a, ℓ = 0, 1, …, mn − 1. In the resulting determinant we move the last row to the top, thus creating a sign of (−1)^{n−1}, and finally apply Theorem 7 with a = 1, b = (m − 1)n − 1, c = a − 1, d = n^{2}(m − 1)(2m − 1)/6 − an(m − 1)/2 and e = a + n(m − 1)/2 − 1.

For the computation of Res(x^{n} − 1, Q) we note that

Res(x^{n} − 1, Q) = ∏_{ω : zero of x^{n}−1} ( ∑_{ℓ=0}^{mn−1}(ℓ + a)ω^{ℓ})

= (\binom{mn}{2} + mna) ∏_{ω : zero of x^{n}−1, ω≠1} ( ∑_{ℓ=1}^{mn} ℓω^{ℓ−1}).

The sum in the last line is the derivative of a geometric series, and is therefore easily evaluated. The result of the summation turns out to be −mn/(1−ω). The computation is completed by the observation (10), and some simplification.

Corollary 33. — Let n and m be positive integers, n ≥ 2. Then

PER(x^{n} − 1, ∑_{ℓ=0}^{mn−1} ℓy^{ℓ}) = (−1)^{n−1} \frac{(4mn − n − 1)(mn − 2)!}{6(mn − n − 1)!}.

Corollary 34. — Let n and m be positive integers, n ≥ 2. Then

PER(x^{n}−1, ∑_{ℓ=0}^{mn−1}(ℓ+1)y^{ℓ}) = (−1)^{n−1} \frac{(4mn − n + 1)(mn − n)(mn − 1)!}{6(mn − n + 1)!}.

Corollary 35. — Let n and m be positive integers, n ≥ 2. Then

PER(x^{n} − 1, ∑_{ℓ=0}^{mn−1}(mn − ℓ)y^{ℓ}) = \frac{(m − 1) (n + 1)!}{6}.

Corollary 36. — Let n and m be positive integers, n ≥ 2. Then

PER(x^{n} − 1, ∑_{ℓ=0}^{mn−1}(mn − ℓ − 1)y^{ℓ}) = \frac{(m − 1) n!}{6}.

Remark. — It is also possible to move forward and derive formulas for PER (x^{n} − 1, ∑_{ℓ=0}^{mn/s−1}(ℓ + a)y^{ℓs}), where s is some positive integer. This would require to find analogues of Theorem 7 in which n(i, j) is replaced by D n(i, j), where D is the inverse of s/gcd(n, s) modulo n/gcd(n, s). As calculations aided by the computer indicate, the resulting determinant evaluations have forms very similar to (7). That is, the result shows a product of linear factors in a and b as the one on the right-hand side of (7), and one irreducible polynomial of higher degree (such as U_{n}(a, b, c, d, e) in (7)). However, as D increases, the degree of the irreducible polynomial also increases, whereas the amount of linear factors in a and b decreases, so that the results become more and more unwieldy. We therefore content ourselves with stating the result when s divides n.

Theorem 37. — Let n, m and s be positive integers so that s | n, and let a be an arbitrary number. Then

\begin{matrix}PER(x^{n} − 1, ∑_{ℓ=0}^{\frac{mn}{s} −1}(ℓ + a)y^{ℓs}) = (−1)^{n−1} \frac{s^{n−2s}}{6^{s} (mn + 2as − s)^{s}} \\ × ∏_{k=0}^{s−1} ((a + \frac{1}{s}(nm − n − k) + 1)_{n/s−2} V_{n,s}(a, m, k)) , \end{matrix}

where V_{n,s}(a, m, k) is the polynomial

V_{n,s}(a, m, k) = 6k^{2}mn + 6kmn^{2} − 10km^{2}n^{2} + mn^{3} − 5m^{2}n^{3} + 4m^{3}n^{3} − 6k^{2}s
+ 12ak^{2}s − 6kns + 12akns + 12kmns − 24akmns − n^{2}s + 2an^{2}s + 6mn^{2}s
− 12amn^{2}s − 5m^{2}n^{2}s + 10am^{2}n^{2}s − 2ks^{2} + 12aks^{2} − 12a^{2}ks^{2} − ns^{2}
+ 6ans^{2} − 6a^{2}ns^{2} + mns^{2} − 6amns^{2} + 6a^{2}mns^{2}.

Proof. — Let Q = ∑_{ℓ=0}^{mn−1}(ℓ + a)y^{ℓs}. Again, according to Theorem 3, we have to compute Fes(Q)/Res(x^{n} − 1, Q). In order to compute Fes(Q), in (3) set a_{ℓs} = ℓ + a, ℓ = 0, 1, …, mn/s − 1, and all other a_{i}’s to zero. In the resulting determinant we move the last row to the top, thus creating a sign of (−1)^{n−1}. Since only every s-th a_{i} is nonzero, we are dealing with a determinant of a matrix in which a lot of entries are zero. If we permute rows and columns so that first come the rows and columns whose indices are congruent 1 mod s, then come the rows and columns whose indices are congruent 2 mod s, etc., then the matrix of which we want to compute the determinant assumes a block form, with (n/s) × (n/s) blocks on the diagonal, and zeroes otherwise. Therefore the determinant equals the product of the determinants of the s matrices of dimension (n/s) × (n/s) on the diagonal. Each of these determinants can be evaluated by means of Theorem 7. We leave it to the reader to fill in the details.

For the computation of Res(x^{n} − 1, Q) we proceed as in the proof of Theorem 32.

Theorem 38. — Let n and m be positive integers, n ≥ 2, and a be an arbitrary number. Then

\begin{matrix}PER(x^{n−1} + ⋯ + x + 1, ∑_{ℓ=0}^{mn−1}(ℓ + a)y^{ℓ}) \\ = (−1)^{n−1} (a + (m − 1)n + 1)_{n−1} . \end{matrix}

Proof. — Let P (x) = x^{n−1} + ⋯ + x + 1 and Q(y) = ∑_{ℓ=0}^{mn−1}(ℓ + a)y^{ℓ}. This time we apply Theorem 4. According to that theorem, we have to compute F̃es(Q)/Res(P, Q). In order to compute F̃es(Q), in (4) we set a_{ℓ} = ℓ+a, ℓ = 0, 1, …, mn−1. The resulting determinant is exactly m^{n−1} times the determinant in Corollary 9 with a replaced by ((m−1)n+a+1). For the computation of the resultant of P and Q we proceed as in the proof of Theorem 7. Simplification of the result yields the claimed expression.

Theorem 39. — Let n and m be positive integers, n ≥ 2, and a be an arbitrary number. Then

\begin{matrix}PER(x^{n−1} + ⋯ + x + 1, ∑_{ℓ=0}^{mn−2}(ℓ + a)y^{ℓ}) \\ = (−1)^{n−1} \frac{(nm − n)_{n−1} (nm + a − 1)^{n−1}}{(mn + a − 1)^{n} − (a − 1)^{n}} . \end{matrix}

Proof. — Let P (x) = x^{n−1} + ⋯ + x + 1 and Q(y) = ∑_{ℓ=0}^{mn−1}(ℓ + a)y^{ℓ}. Using Theorem 4 again, we have to compute F̃es(Q)/Res(P, Q). In order to compute F̃es(Q), in (4) we set a_{ℓ} = ℓ + a, ℓ = 0, 1, …, mn − 2. The resulting determinant is exactly m^{n−1} times the determinant in Theorem 8 with m replaced by mn + A − 1, a replaced by (mn + A − 1)/m, and A replaced by a, in that order.

For the computation of Res(x^{n} + ⋯ + x + 1, Q) we proceed similarly as in the proof of Theorem 32. Using an observation from that proof, we note that

Res(x^{n} + ⋯ + x + 1, Q) = ∏_{ω : zero of x^{n}−1, x≠1} ( ∑_{ℓ=0}^{mn−2}(ℓ + a)ω^{ℓ})

= ∏_{ω : zero of x^{n}−1, x≠1} (−\frac{mn}{1 − ω} − (mn + a − 1)ω^{mn−1})

= (−1)^{n−1} ∏_{ω : zero of x^{n}−1, x≠1} \frac{mn + a − 1 + ω(1 − a)}{ω(1 − ω)}

= \frac{(mn + a − 1)^{n} − (a − 1)^{n}}{n^{2}m} .

The result follows now upon some simplification.

6. Sums of involutions

As in [6, Sec. 4], we may obtain interesting summation theorems by combining special evaluations of Scott-type determinants (see Section 5) with Theorem 2. For example, if we combine Corollary 19 with Theorem 2, we obtain the following result.

Proposition 40. — Let x_{1}, x_{2}, …, x_{n} be the zeroes of x^{n} − 1. Then

∑_{σ∈I(n)} ∏_{(ij)∈σ} \frac{1}{(x_{i} − x_{j})^{2}} ∏_{(k)∈σ} \frac{n + 1}{2x_{k}} = (−1)^{n+1}n!,

where the first product is over all transpositions (ij) of σ in its disjoint cycle decomposition, and where the second product is over all fixed points k of σ.

Similarly, if we combine Corollary 21 with Theorem 2, we obtain the result below.

Proposition 41. — Let x_{1}, x_{2}, …, x_{n} be the zeroes of x^{n} − 1. Then

∑_{σ∈I(n)} ∏_{(ij)∈σ} \frac{1}{(x_{i} − x_{j})^{2}} ∏_{(k)∈σ} \frac{n − 1}{2x_{k}} = 0,

where the first product is over all transpositions (ij) of σ in its disjoint cycle decomposition, and where the second product is over all fixed points k of σ.

If we combine Corollary 31 with Theorem 2, then we obtain the following result.

Proposition 42. — Let x_{1}, x_{2}, …, x_{n} be the zeroes of x^{n} − 1. Then

∑_{σ∈I(n)} ∏_{(ij)∈σ} \frac{1}{(x_{i} − x_{j})^{2}} ∏_{(k)∈σ} \frac{2n + (n + 1)x_{k}}{2x_{k}^{2}} = 1,

where the first product is over all transpositions (ij) of σ in its disjoint cycle decomposition, and where the second product is over all fixed points k of σ.

Finally, if we combine Corollary 27 with Theorem 2, we obtain the result below.

Proposition 43. — Let n be odd, and let x_{1}, x_{2}, …, x_{n} be the zeroes of x^{n} − 1. Then

∑_{σ∈I(n)} ∏_{(ij)∈σ} \frac{1}{(x_{i} − x_{j})^{2}} ∏_{(k)∈σ} \frac{1 − n + (3 + n)x_{k}}{2(1 + x_{k})x_{k}} = \frac{(n + 1)!}{2},

where the first product is over all transpositions (ij) of σ in its disjoint cycle decomposition, and where the second product is over all fixed points k of σ.

References

[1] G. E. Andrews, I. P. Goulden, D. M. Jackson. — Generalizations of Cauchy’s summation theorem for Schur functions, Trans. Amer. Math. Soc. 310 (1988), pp. 805–820.

[2] C. W. Borchardt. — Bestimmung der symmetrischen Verbindungen vermittelst ihrer erzeugenden Funktion, Crelle J. 53 (1855), pp. 193–198.

[3] D. Callan. — On evaluating permanents and a matrix of cotangents, Linear and Multilinear Algebra 38 (1995), pp. 193–205.

[4] A. L. Cauchy. — Mémoire sur les fonctions alternées et les sommes alternées, Exercices d’analyse et de phys. math. 2 (1841), pp. 151–159.

[5] G.-N. Han. — Interpolation entre Cauchy et Borchardt, in preparation, 1999.

[6] G.-N. Han. — Généralisation de l’identité de Scott sur les permanents, Linear Algebra Appl. (to appear).

[7] J.-P. Jouanolou. — Polynômes cyclotomiques : Théorie élémentaire et applications. — Prépublication, Université de Strasbourg I, 96 pages, 1990.

[8] R. Kittappa. — Proof of a conjecture of 1881 on permanents, Linear and Multilinear Algebra 10 (1981), pp. 75–82.

[9] C. Krattenthaler. — An alternative evaluation of the Andrews–Burge determinant, in: Mathematical Essays in Honor of Gian-Carlo Rota, B. E. Sagan, R. P. Stanley, eds., Progress in Math., vol. 161, Birkhäuser, Boston, 1999, pp. 263–270.

[10] C. Krattenthaler. — Advanced determinant calculus, Séminaire Lotharingien Combin. 42, “The Andrews Festschrift” (1999), paper B42q, 67 pp.

[11] A. Lascoux. — Square-ice Enumeration, Séminaire Lotharingien Combin. 42, “The Andrews Festschrift” (1999), paper B42p, 15 pp.

[12] I. G. Macdonald. — Symmetric functions and Hall polynomials, second edition. Clarendon Press, Oxford, 1995.

[13] H. Minc. — Permanents. — Encyclopedia of mathematics and its applications, vol. 6, Addison-Wesley, Mass., 1978.

[14] H. Minc. — On a conjecture of R. F. Scott, Linear Algebra Appl. 28 (1979), pp. 141–153.

[15] T. Muir. — The theory of determinants in the historical order of development, 4 vols. — Macmillan, London, 1906–1923.

[16] R. F. Scott. — Mathematical notes, Messenger of Math. 10 (1881), pp. 142– 149.

[17] D. Svrtan. — Proof of Scott’s conjecture, Proc. Amer. Math. Soc. 87 (1983), pp. 203–207.

I.R.M.A. and C.N.R.S.

Université Louis Pasteur 7, rue René-Descartes F-67084 Strasbourg, France

       guoniu@math.u-strasbg.fr

Institut für Mathematik Universität Wien Strudlhofgasse 4 A-1090 Vienna, Austria

                                 kratt@ap.univie.ac.at