THEOREMS AND CONJECTURES INVOLVING

ROOK POLYNOMIALS WITH ONLY REAL ZEROS

James Haglund, Ken Ono, and David G. Wagner

Dedicated to Basil Gordon on his sixty fifth birthday.

Abstract. Let A = (a_{ij}) be a real n×n matrix with non-negative entries which are weakly increasing down columns. If B = (b_{ij}) is the n × n matrix where b_{ij} := a_{ij} + z, then we conjecture that all of the roots of the permanent of B, as a polynomial in z, are real. Here we establish several special cases of the conjecture.

1. Introduction and Statement of Results

Throughout A = (a_{ij}) will denote an n × n matrix. A placement of rooks on the squares of A is non-attacking if no two rooks are in the same column, and no two are in the same row. We define the weight of such a placement to be the product of the entries in A which are under the rooks, and we define the kth rook number r_{k}(A) to be the sum of these weights over all non-attacking placements of

1991 Mathematics Subject Classification. Primary 05C70, 05A20. Key words and phrases. rook polynomial, matching polynomial, permanent,

real roots.

The first author is supported by NSF grant DMS-9627432. The second author is supported by NSF grants DMS-9508976 and DMS-9304580, and NSA grant MSPR-97Y012. The third author is supported by the Natural Sciences and Engineering Research Council of Canada under operating grant OGP0105392.

Typeset by AMS-TEX

k rooks on A. Furthermore by convention r_{0}(A) := 1. When n = 2 these rook numbers are

r_{2}(A) = a_{11}a_{22}+a_{12}a_{21}, r_{1}(A) = a_{11}+a_{12}+a_{21}+a_{22} and r_{0}(A) = 1.

Note that r_{n}(A) equals per(A), the permanent of A, defined as

per(A) := ∑_{σ∈S_{n}} ∏_{i=1}^{n} a_{i,σ_{i}}.

If each a_{ij} is zero or one, then A is called a board, and r_{k}(A) is the number of placements of k rooks on the non-zero entries of A.

We call R(z; A) := ∑_{k=0}^{n} r_{k}(A)z^{k} the rook polynomial of A. Nijenhuis [Nij] proved that if the a_{ij} are non-negative real numbers, then all the roots of R(z; A) are real. One application is that the rook numbers r_{k}(A) are log-concave (i.e. r_{i}(A)^{2} ≥ r_{i−1}(A)r_{i+1}(A)). This follows from the fact that if f(z) = ∑_{k} b_{k}z^{k} has only real roots , then the b_{k} are log-concave. In fact more is true, it turns out that [p. 52, HLP]

b_{k}^{2} ≥ b_{k−1}b_{k+1} (1 + \frac{1}{k} ) (1 + \frac{1}{n − k} ) .

E. Bender noted that Nijenhuis’ result follows from the Heilmann-Lieb Theorem [HeLi] which asserts that all of the roots of matching polynomials of simple graphs with non-negative weights are real (the Heilmann-Lieb Theorem has been extensively generalized in Theorem 3.3 of [Wag3]). To see this consider the complete bipartite graph G from n vertices on top to n vertices below, where the edge between vertex i above and vertex j below is assigned weight a_{ij}. Given a matching M with k edges (i.e. any selection of k edges no two of which share a common vertex) one obtains a rook placement by placing a rook on a_{ij} in A if and only if M contains the edge connecting i above to j below. So the weighted matching polynomial of G is just the rook polynomial of A.

Now we briefly describe various combinatorial investigations from which it is known that all of the roots of certain natural polynomials are real. A multiset is a set in which elements can occur more than once. A permutation σ of a multiset L of positive integers is a linear list σ_{1}σ_{2} ⋯ of the elements of L, and a descent of such a σ is a positive integer i such that σ_{i} > σ_{i+1}. Let N_{k}(v) denote the number of permutations of the multiset

v := {1^{v_{1}}2^{v_{2}} ⋯ m^{v_{m}}}

(i^{v_{i}} denotes v_{i} copies of i) with exactly k−1 descents. Simion proved that all the roots of

∑_{k≥1} N_{k}(v)z^{k}  (1)

are real [Sim], and consequently that the N_{k}(v) are log-concave. For example, if v = {1^{3}2^{1}}, the 4 permutations are

1112  1121  1211  2111,

and so (1) is 3z^{2} + z. Simion’s result proves a special case of the famous Neggers-Stanley “Poset Conjecture” [Bre], [Wag2], which says that a certain polynomial associated to a labelled poset has only real zeros.

The hit polynomial T (z; A) of A is

T (z; A) = ∑_{k=0}^{n} k!r_{n−k}(A)(z − 1)^{n−k}.

If A is a board, then its coefficient of z^{k} is called the k^{th} hit number, the number of ways of placing n non-attacking rooks on A where exactly k rooks lie on non-zero entries. In their seminal paper on rook theory [KaRi] (see also [Rio]), Riordan and Kaplansky showed that

∏_{i=1}^{m} v_{i}! ∑_{k≥1} N_{k}(v)z^{k−1}

is the hit polynomial for the “Simon Newcomb board” (see Figure 1). This is the matrix where the entries in the first v_{1} columns are all zero, and the next v_{2} columns have ones in the bottom v_{1} rows and Figure 1. The Simon Newcomb board associated to the multiset {1^{v_{1}} ⋯ m^{v_{m}}}.

zeros above, etc. Therefore Simion’s result implies that all the roots of these polynomials are real, and of course that the hit numbers of these boards are log-concave.

By Laguerre’s Theorem, that if ∑_{k} b_{k}z^{k} has only real roots then

∑_{k} \frac{b_{k}}{k!} z^{k} also has only real roots ([Lag]; see also [Th. 11, GaWa]),

one can deduce that if T (z; A) has only real roots, then so too does R(z; A). The converse of Laguerre’s Theorem is false, and in particular the hit polynomials of boards do not generally have only real roots. However we will show that this is true for Ferrers boards.

Definition 1. Let A be a board with the property that if a_{ij} = 1, then a_{st} = 1 whenever i ≤ s ≤ n and j ≤ t ≤ n. Then A is called a Ferrers board.

Theorem 1. All the roots of the hit polynomial of a Ferrers board are real.

An r-descent of a multiset permutation σ is a value of i such that σ_{i} − σ_{i+1} ≥ r. Let N_{k}(v, r) be the number of permutations of the multiset v = {1^{v_{1}} ⋯ m^{v_{m}}} containing exactly k − 1 r-descents. For example, if v = {1^{1}2^{1}3^{1}}, then the permutations are

123  132  213  231  312  321.

Of these, 231 and 312 have one 2-descent, so N_{2}({1^{1}2^{1}3^{1}}, 2) = 2.

The numbers N_{k}(v, r) are the hit numbers for special Ferrers boards, ones generalizing the Simon Newcomb boards [Hag1,Hag2]. Thus Theorem 1 implies the following, which reduces to Simion’s result when r = 1.

Corollary 1. Let r be a positive integer, and let v be a multiset of positive integers. Then all the roots of

∑_{k} N_{k}(v, r)z^{k}

are real.

It is natural to seek a weighted version of Theorem 1 analogous to the Heilmann-Lieb theorem.

Definition 2. Let A be a real n × n matrix. We call A a Ferrers matrix if a_{ij} ≤ a_{st} whenever i ≤ s ≤ n and j ≤ t ≤ n.

Conjecture 1. If A is a Ferrers matrix, then all the roots of the hit polynomial T (z; A) are real.

Note that if a_{ij} ∈ {0, 1}, then Conjecture 1 holds by Theorem 1. In section 2 we prove Theorem 1 and also the next result.

Theorem 2. Conjecture 1 is true if n ≤ 3.

Let J_{n} denote the n × n matrix, all of whose entries equal one. When expanded out in powers of z, per(zJ_{n} + A) becomes

∑_{k=0}^{n} k!r_{n−k}(A)z^{k}.

Conjecture 1 is thus equivalent to the assertion that per(zJ_{n} + A) has all real zeros whenever A is a Ferrers matrix.

Expressing Conjecture 1 (and also Conjecture 2 below) in terms of permanents has several advantages. One implication is that if z > − min_{ij} a_{ij} (resp. z < − max_{ij} a_{ij}) all the entries of zJ_{n} + A are positive (resp. negative) in which case per(zJ_{n} + A) cannot be zero. Hence if A is Ferrers all real roots of per(zJ_{n} + A) are in the interval [−a_{nn}, −a_{11}]. It is also easy to see that in Conjecture 1 we can assume without loss of generality that

\underline{C1} 0 ≤ a_{ij} ≤ 1 for all 1 ≤ i, j ≤ n.

Less trivially, we can develop recursions by expanding the permanent in terms of permanental minors, a method which plays a crucial role in the broadest special case of Conjecture 1 we can prove. We require some additional hypotheses. Define a_{0j} := 0 for all 0 ≤ j ≤ n + 1, a_{i0} := 0 for all 0 ≤ i ≤ n + 1, a_{n+1,j} := 1 for all 1 ≤ j ≤ n + 1, and a_{i,n+1} := 1 for all 1 ≤ i ≤ n + 1. Also define conditions

\underline{C2}  For all 1 ≤ r < s ≤ n and 0 ≤ t < u < v ≤ n + 1:
(a_{ru} − a_{rt})(a_{sv} − a_{su}) ≤ (a_{rv} − a_{ru})(a_{su} − a_{st}),

and

\underline{C3}  For all 0 ≤ t < u < v ≤ n + 1 and 1 ≤ r < s ≤ n:
(a_{ur} − a_{tr})(a_{vs} − a_{us}) ≤ (a_{vr} − a_{ur})(a_{us} − a_{ts}).

Theorem 3. If A is a Ferrers matrix satisfying \underline{C1}, \underline{C2}, and \underline{C3}, then per(zJ_{n} + A) has all its zeros in the interval [−1, 0].

In section 3 we prove Theorem 3 using mathematical induction and the method of interlacing roots. By the same method, we also prove that Conjecture 1 holds for any n×n Ferrers matrix A provided a_{i,n} ≤ a_{i+1,1} for all 1 ≤ i ≤ n − 1.

By running a program written in Maple which constructs matrices using a random number generator, the authors and E. R. Canfield have verified the following stronger form of Conjecture 1 holds for over 100,000 matrices of sizes ranging from 3 × 3 to 13 × 13.

Conjecture 2. If A is a matrix with real entries where a_{ij} ≤ a_{sj} when s ≥ i, then all the roots of the hit polynomial T (z; A) are real.

Since permuting the columns of a matrix doesn’t change the rook numbers, the a_{ij} ∈ {0, 1} case of Conjecture 2 also follows from Theorem 1. Example 1. If a_{ij} := q_{j}, then per(zJ_{n} + A) = n!(z + q_{1})(z + q_{2}) ⋯ (z + q_{n}). Thus the set of polynomials with only real roots and leading coefficient n! are all examples of the phenomenon asserted by Conjectures 1 and 2. Furthermore Conjecture 1 is equivalent to the claim that for any Ferrers matrix A there exists another matrix A′ which is constant down columns and rook equivalent to A (i.e. r_{k}(A) = r_{k}(A′) for 0 ≤ k ≤ n).

2. The Tableau Method

We now turn to the proofs of Theorems 1 and 2. Proof of Theorem 1: Goldman, Joichi, and White [GJW] proved that

∑_{k=0}^{n} x(x − 1) ⋯ (x − k + 1)r_{n−k}(A) = ∏_{i=1}^{n}(x + c_{i} − i + 1), (2)

where c_{i} is the number of ones in (the height of) the ith column of the Ferrers board A. This is equivalent to

∑_{k=0}^{n} \binom{x + k}{n}t_{k}(A) = ∏_{i=1}^{n}(x + c_{i} − i + 1),  (3)

where t_{k}(A) is the coefficient of z^{k} in T (z; A). The result now follows easily by [Bre, p. 43].

Theorem. (Brenti) Let f(x) = ∑_{k=0}^{n} \binom{x+k}{n}b_{k} be a polynomial with all real zeros, with smallest root λ(f) and largest root Λ(f). If all the integers in the intervals [λ, −1] and [0, Λ] are also roots of f, then all the roots of ∑_{k=0}^{n} b_{k}x^{k} are real. □

Proof of Theorem 2: For a 2 × 2 matrix A, the discriminant of per(zJ_{2} + A) is

(a_{11} + a_{12} + a_{21} + a_{22})^{2} − 8(a_{11}a_{22} + a_{12}a_{21})

= a_{11}^{2} + a_{12}^{2} + a_{21}^{2} + a_{22}^{2} + 2a_{11}a_{12} + 2a_{11}a_{21} + 2a_{12}a_{22} + 2a_{21}a_{22} − 6a_{11}a_{22} − 6a_{12}a_{21}.

The roots will all be real if and only if this expression is non-negative. We now describe a method by which this becomes visibly evident if A is Ferrers.

By replacing z by z − min_{ij} a_{ij} we can assume without loss of generality that a_{ij} ≥ 0. Since A is Ferrers, either

0 ≤ a_{11} ≤ a_{12} ≤ a_{21} ≤ a_{22}  (4)

or

0 ≤ a_{11} ≤ a_{21} ≤ a_{12} ≤ a_{22},  (5)

or both. If (4) holds, replace a_{11} by w_{1}, a_{12} by w_{1} + w_{2}, a_{21} by w_{1} + w_{2} + w_{3}, and a_{22} by w_{1} + w_{2} + w_{3} + w_{4}. The inequalities in (4) then imply that all the w_{i} are non-negative. The discriminant now becomes

w_{4}^{2} + w_{2}^{2} + 4w_{3}^{2} + 6w_{4}w_{2} + 4w_{4}w_{3} + 4w_{2}w_{3}.

Note that this is w-monomial positive, i.e. the coefficient of every possible monomial in the w_{i} is non-negative. If (5) holds, replace a_{11} by w_{1}, a_{21} by w_{1} + w_{2}, etc. By symmetry, the discriminant will again be w-monomial positive. Thus Conjecture 1 holds if n = 2.

To the set of inequalities in (4), we can associate the array

1 2 3 4

and to (5) the array

1 3 2 4 .

These arrays are special cases of what are known as standard tableau of square n × n shape, that is n × n Ferrers matrices the set of whose entries equals the set {1, 2, …, n^{2}}. In the second tableau the 2 in square (2, 1) indicates a_{21} is the second-smallest a_{ij}. More generally, we can clearly break up the set of n × n Ferrers matrices into subsets, according to how the a_{ij} are related to one another, with a standard tableau of square n × n shape associated to each subset. The square containing k in such a tableau will indicate the kthsmallest a_{ij}, which we can then parameterize as w_{1} + … + w_{k}, with w_{i} non-negative. Note that if some of the a_{ij} are equal, there is some ambiguity in selecting a representative tableau, but different tableau choices will have the effect of simply replacing certain w_{i} by other w_{i} in the discriminant, which will not affect monomial positivity.

Since a cubic polynomial has only real roots if and only if its discriminant is non-negative, to complete the proof of Theorem 2 it suffices to show that for all possible standard tableaux in the shape of a 3 × 3 square, the discriminant of T (z; A), when expressed in terms of the w_{i}, is w-monomial positive. This has been verified via a long Maple calculation (here the discriminant of T (z; A) typically consists of over 1500 monomials in the w_{i}). □

A similar argument proves the n = 2 case of Conjecture 2; by Theorem 2 we can assume that A is of the form

A := [ \begin{matrix}w_{1} & w_{1} + w_{2} \\ w_{1} + w_{2} + w_{3} + w_{4} & w_{1} + w_{2} + w_{3} \end{matrix} ] ,

in which case the discriminant of per(A + zJ_{n}) equals

(w_{2} − w_{4})^{2} + 4w_{2}w_{3} + 4w_{3}^{2} + 4w_{3}w_{4}.

Although not monomial positive, it is still clearly positive.

The n = 3 case of Conjecture 2 is still open, as the discriminant of T (z; A) for a typical matrix A (parameterized to reflect the column monotone condition) consists of over a thousand monomials, many of which have negative coefficients.

3. Interlacing Arguments

Before presenting the proof of Theorem 3, we consider three particularly interesting special cases.

\underline{U} a_{ij} ∈ \{0, 1\} for all 1 ≤ i, j ≤ n.

\underline{Π} There are positive real numbers p_{i} for 1 ≤ i ≤ n and q_{j} for

1 ≤ j ≤ n such that a_{ij} = p_{i}q_{j} for all 1 ≤ i, j ≤ n.

\underline{Σ} There exist positive real numbers p_{i} for 1 ≤ i ≤ n and q_{j} for 1 ≤ j ≤ n such that a_{ij} = p_{i} + q_{j} for all 1 ≤ i, j ≤ n.

Lemma 1. If A is a Ferrers matrix satisfying \underline{U}, then A satisfies \underline{C1}, \underline{C2}, and \underline{C3}.

P roof : Condition \underline{C1} is a trivial consequence of \underline{U}. The hypothesis A being Ferrers and \underline{U}, and the conclusion \underline{C2} and \underline{C3} are symmetric under transposition A ↦ A^{⊤}; hence we need only prove \underline{C2}. Fix any 1 ≤ r < s ≤ n and 0 ≤ t < u < v ≤ n + 1; there are ten cases for the 2-by-3 submatrix

[ \begin{matrix}a_{rt} & a_{ru} & a_{rv} \\ a_{st} & a_{su} & a_{sv} \end{matrix} ] ,

leading to eight cases for the differences

[ \begin{matrix}a_{ru} − a_{rt} & a_{rv} − a_{ru} \\ a_{su} − a_{st} & a_{sv} − a_{su} \end{matrix} ] .

In each case the inequality \underline{C2} is easily seen to hold. □

Theorem 3 therefore implies Theorem 1.

Lemma 2. If A is Ferrers and satisfies \underline{C1} and \underline{Π}, then A satisfies \underline{C2} and \underline{C3}.

P roof : Again by symmetry, we only need to prove \underline{C2}, so fix any 1 ≤ r < s ≤ n and 0 ≤ t < u ≤ v ≤ n + 1; we separate four cases for

[ \begin{matrix}a_{rt} & a_{ru} & a_{rv} \\ a_{st} & a_{su} & a_{sv} \end{matrix} ] .

If 1 ≤ t and v ≤ n then a_{ij} = p_{i}q_{j} for all these entries of A, and \underline{C2} reduces to

p_{r}(q_{u} − q_{t})p_{s}(q_{v} − q_{u}) ≤ p_{r}(q_{v} − q_{u})p_{s}(q_{u} − q_{t}),

which is trivial. If 1 ≤ t and v = n + 1 then \underline{C2} reduces to

p_{r}(q_{u} − q_{t})(1 − p_{s}q_{u}) ≤ p_{s}(q_{u} − q_{t})(1 − p_{r}q_{u}),

which (since A Ferrers implies q_{t} ≤ q_{u}) reduces to p_{r} ≤ p_{s}, which again follows if A is Ferrers. If 0 = t and v ≤ n then \underline{C2} reduces to

p_{r}q_{u}p_{s}(q_{v} − q_{u}) ≤ p_{s}q_{u}p_{r}(q_{v} − q_{u}),

which is trivial. Finally, if 0 = t and v = n + 1 then \underline{C2} reduces to

p_{r}q_{u}(1 − p_{s}q_{u}) ≤ p_{s}q_{u}(1 − p_{r}q_{u}),

which (since q_{u} ≥ 0), by \underline{C1} reduces to p_{r} ≤ p_{s} which follows when A is Ferrers. □

Corollary 2. If A is a Ferrers matrix satisfying \underline{C1} and \underline{Π}, then per(zJ_{n} + A) has all its zeros in the interval [−1, 0].

One of the strongest theorems involving polynomials having only real zeros is Corollary 3 below, which Szegö proved under the more general assumption that the roots of f(z) are all real but need not all be non-positive [Sze], [PoSz,Problem 154]. Our proof of the weaker result is quite different from his proof, which uses Grace’s Apolarity Theorem [Gra], [Vle].

Corollary 3. (Szegö) If f(z) := ∑_{k=0}^{n} b_{k}z^{k} and g(z) := ∑_{k=0}^{n} d_{k}z^{k} are polynomials of degree n all of whose roots are non-positive real numbers, then the polynomial

∑_{k=0}^{n} b_{k}d_{k}k!(n − k)!z^{k}

has only real roots.

P roof : Let f(z) := b_{n}(z + p_{1})(z + p_{2}) ⋯ (z + p_{n}) and g(z) := d_{n}(z + q_{1})(z + q_{2}) ⋯ (z + q_{n}), where 0 ≤ p_{1} ≤ … ≤ p_{n} and 0 ≤ q_{1} ≤ … ≤ q_{n}. Let e_{k}(X) denote the kth elementary symmmetric function in the set of variables X := {x_{1}, x_{2}, …, x_{n}}. Then if a_{ij} := p_{i}q_{j}, per(zJ_{n} + A) becomes

∑_{k=0}^{n} z^{k}k!(n − k)!e_{n−k}(P)e_{n−k}(Q),

and has only real zeros by Corollary 2. Since e_{n−k}(P) = b_{k}/b_{n} and e_{n−k}(Q) = d_{k}/d_{n}, the thesis follows. □ Remark 1 : The case where a_{ij} := p_{i}q_{j} with p_{1} ≤ p_{2} ≤ … ≤ p_{n} and 0 ≤ q_{1} ≤ q_{2} ≤ … ≤ q_{n} doesn’t follow from Corollary 2 since if some of the p_{i} are negative A need need be Ferrers. However, this matrix will still be weakly increasing down columns, and so Szegö’s Theorem is equivalent to this special case of Conjecture 2.

Lemma 3. If A is a Ferrers matrix satisfying \underline{Σ}, then A satisfies \underline{C2} and \underline{C3}.

P roof : Yet again, by symmetry, we need only prove \underline{C2}, so fix any 1 ≤ r < s ≤ n and 0 ≤ t < u < v ≤ n + 1; we again separate four cases for

[ \begin{matrix}a_{rt} & a_{ru} & a_{rv} \\ a_{st} & a_{su} & a_{sv} \end{matrix} ] .

If 1 ≤ t and v ≤ n then a_{ij} = p_{i} + q_{j} for all these entries of A, and \underline{C2} reduces to

(q_{u} − q_{t})(q_{v} − q_{u}) ≤ (q_{v} − q_{u})(q_{u} − q_{t}),

which is trivial. If 1 ≤ t and v = n + 1 then \underline{C2} reduces to

(q_{u} − q_{t})(1 − p_{s} − q_{u}) ≤ (q_{u} − q_{t})(1 − p_{r} − q_{u}),

which (given that A is Ferrers implies q_{t} ≤ q_{u}) reduces to p_{r} ≤ p_{s}, and this also follows when A is Ferrers. If 0 = t and v ≤ n then \underline{C2} reduces to

(p_{r} + q_{u})(q_{v} − q_{u}) ≤ (p_{s} + q_{u})(q_{v} − q_{u}),

which reduces to p_{r} ≤ p_{s} and follows from A being Ferrers. Finally, if 0 = t and v = n + 1 then \underline{C2} reduces to

(p_{r} + q_{u})(1 − p_{s} − q_{u}) ≤ (p_{s} + q_{u})(1 − p_{r} − q_{u}),

which reduces to p_{r} ≤ p_{s} and follows if A is Ferrers. □

Corollary 4. If A is a Ferrers matrix satisfying \underline{C1} and \underline{Σ}, then all the roots of per(zJ_{n} + A) are in the interval [−1, 0].

To prove Theorem 3 we need some lemmas about polynomials with only real zeros. A polynomial P ∈ ℝ[z] is standard if either P ≡ 0 or the leading coefficient of P is positive. Let P, Q ∈ ℝ[z] be two such polynomials, of degrees p and q respectively. Let the zeros of P be

ξ_{1} ≤ ⋯ ≤ ξ_{p}

and let the zeros of Q be

θ_{1} ≤ ⋯ ≤ θ_{q}.

We say that P alternates left of Q if p = q and

ξ_{1} ≤ θ_{1} ≤ ⋯ ≤ ξ_{p} ≤ θ_{p}.

This is denoted P ⟨⟨ Q.

We say that P interlaces Q if q = p + 1 and

θ_{1} ≤ ξ_{1} ≤ ⋯ ≤ θ_{p} ≤ ξ_{p} ≤ θ_{p+1}.

This is denoted P † Q.

Furthermore if P ⟨⟨ Q or P † Q, then we use the notation P ≺ Q. Moreover by convention if P has only real zeros, then P ⟨⟨ 0, 0 ⟨⟨ P, P † 0, and 0 † P.

Lemmas 4 and 5 can be proved using the techniques from section 3 of [Wag1].

Lemma 4. Let P, Q, S ∈ ℝ[z] be standard, with all zeros real and in the interval [α, β], and with S ≢ 0.

(a) P ⟨⟨ Q if and only if (z − α)Q ⟨⟨ (z − β)P.

(b) If S ≺ P and S ≺ Q then S ≺ P + Q.

(c) If P ≺ S and Q ≺ S then P + Q ≺ S. If P ≺ Q then P ≺ P + Q ≺ Q. (d)

Lemma 5. Let P_{1}, …, P_{m} ∈ ℝ[z] be standard, with only real nonpositive zeros, and such that P_{i} ≢ 0 for all 1 ≤ i ≤ m. If P_{1} ≺ ⋯ ≺ P_{m} and P_{1} ≺ P_{m} then P_{h} ≺ P_{i} for all 1 ≤ h < i ≤ m.

Lemma 6. Let P_{1}, …, P_{m} ∈ ℝ[z] be standard, with only real nonpositive zeros, and such that P_{h} ≺ P_{i} for all 1 ≤ h < i ≤ m. For any c_{1}, …, c_{m} ≥ 0, P_{1} ≺ c_{1}P_{1} + ⋯ + c_{m}P_{m} ≺ P_{m}.

P roof : We may reduce to the case that c_{i} > 0 and P_{i} ≢ 0 for all 1 ≤ i ≤ m. Since P_{1} ≺ c_{i}P_{i} for all 1 ≤ i ≤ m, Lemma 4(b) (and induction on m) show that P_{1} ≺ c_{1}P_{1} + ⋯ + c_{m}P_{m}. Similar reasoning shows that c_{1}P_{1} + ⋯ + c_{m}P_{m} ≺ P_{m}. □

Lemma 7. Let P_{1}, …, P_{m} ∈ ℝ[z] be standard, with only real nonpositive zeros, and such that P_{h} ≺ P_{i} for all 1 ≤ h < i ≤ m. For 1 ≤ i ≤ m let S′_{i} := P_{1} + ⋯ + P_{i} and S_{i} := P_{i} + ⋯ + P_{m}. Then

S′_{1} ≺ ⋯ ≺ S′_{m} = S_{1} ≺ ⋯ ≺ S_{m}  and  S′_{1} ≺ S_{m}.

P roof : Since P_{1} ≺ P_{2}, Lemma 4 (d) implies that S′_{1} ≺ S′_{2} ≺ P_{2}. Assume, inductively, that S′_{1} ≺ ⋯ ≺ S′_{i} ≺ P_{i} where i < m. By the hypothesis and Lemma 6, S′_{i} ≺ P_{i+1}; thus Lemma 4 (d) implies that S′_{i} ≺ S′_{i+1} ≺ P_{i+1}. By induction we conclude that S′_{1} ≺ ⋯ ≺ S′_{m}. A similar argument shows that S_{1} ≺ ⋯ ≺ S_{m}. Finally, S′_{1} = P_{1} ≺ P_{m} = S_{m} is part of the hypothesis. □

Lemma 8. Let P_{1}, …, P_{m} ∈ ℝ[z] be standard, with only real nonpositive zeros, and such that P_{h} ≺ P_{i} for all 1 ≤ h < i ≤ m. Let b_{1}, …, b_{m} ≥ 0 and c_{1}, …, c_{m} ≥ 0 be such that b_{i}c_{i+1} ≤ c_{i}b_{i+1} for all 1 ≤ i ≤ m − 1. Then c_{1}P_{1} + ⋯ + c_{m}P_{m} ≺ b_{1}P_{1} + ⋯ + b_{m}P_{m}.

P roof : We may reduce to the case that b_{i} > 0 and c_{i} > 0 for all 1 ≤ i ≤ m by a limiting argument. The inequalities imply that b_{h}c_{i} ≤ c_{h}b_{i} for all 1 ≤ h < i ≤ m, and thus we may reduce to the case that P_{i} ≢ 0 for all 1 ≤ i ≤ m. Replacing P_{i} by P_{i}/c_{i} for 1 ≤ i ≤ m we reduce further to the case c_{1} = ⋯ c_{m} = 1 and b_{1} ≤ ⋯ ≤ b_{m}. For 1 ≤ i ≤ m let S_{i} := P_{i} + ⋯ + P_{m}. Lemmas 5 and 7 imply that S_{h} ≺ S_{i} for all 1 ≤ h < i ≤ m. Now, with b_{0} := 0, Lemma 6 implies that

S_{1} ≺ ∑_{i=1}^{m} (b_{i} − b_{i−1}) S_{i} ≺ S_{m},

proving the result. □ Proof of Theorem 3: We proceed by induction on n, dividing the induction hypothesis into two parts, I(n) and II(n).

I(n): For a square Ferrers matrix A of side m ≤ n satisfying \underline{C1}, \underline{C2}, and \underline{C3}, per(zJ_{m} + A) has all zeros in the interval [−1, 0]. For an m-by-m matrix A and 1 ≤ i, j ≤ m let T_{ij}A denote the (m − 1)-by-(m − 1) submatrix of A obtained by deleting the i-th row and j-th column of A, and let Q_{ij} := per(zJ_{m−1} + T_{ij}A).

II(n): For a square Ferrers matrix A of side m ≤ n satisfying \underline{C1}, \underline{C2}, and \underline{C3}, both of the following conditions hold.

\underline{C4}  For any 1 ≤ r ≤ m: Q_{rj} ⟨⟨ Q_{rk} for all 1 ≤ j < k ≤ m.

\underline{C5}  For any 1 ≤ c ≤ m: Q_{hc} ⟨⟨ Q_{ic} for all 1 ≤ h < i ≤ m.

The bases of induction, I(1) and II(1), are trivial. The next cases, I(2) and II(2), also follow easily. We divide the induction step into two parts: I(n) and II(n) imply II(n + 1), and I(n) and II(n + 1) imply I(n + 1).

For the first part of the induction step, assume I(n) and II(n), and let A be an (n + 1) × (n + 1) Ferrers matrix satisfying \underline{C1}, \underline{C2}, and \underline{C3}. By the symmetry A ↦ A^{⊤} it suffices to prove \underline{C4}. Fix a row 1 ≤ r ≤ n + 1 and two columns 1 ≤ j < k ≤ n + 1. By I(n) we know that both Q_{rj} and Q_{rk} have all their zeros in [−1, 0]; we must show that Q_{rj} ⟨⟨ Q_{rk}. Notice that for all 1 ≤ i ≤ n, T_{i,k−1}T_{rj}A = T_{ij}T_{rk}A, and define P_{i} := per(zJ_{n−1} + T_{ij}T_{rk}A) for all 1 ≤ i ≤ n. By II(n) we have P_{h} ⟨⟨ P_{i} for all 1 ≤ h < i ≤ n. Also, defining

b_{i} := \{ \begin{matrix}a_{ij} & if 1 ≤ i ≤ r − 1, \\ a_{i+1,j} & if r ≤ i ≤ n, \end{matrix}

and

c_{i} := \{ \begin{matrix}a_{ik} & if 1 ≤ i ≤ r − 1, \\ a_{i+1,k} & if r ≤ i ≤ n, \end{matrix}

we have

Q_{rj} = ∑_{i=1}^{n}(z + c_{i})P_{i} and Q_{rk} = ∑_{i=1}^{n}(z + b_{i})P_{i}.

For 1 ≤ i ≤ n let F_{i} := P_{i} + ⋯ + P_{n}, and let F_{n+1} :≡ 0.

For 1 ≤ i ≤ n, the polynomial P_{i} is standard, not identically zero, and has all its zeros in the interval [−1, 0], by I(n). Thus we see that

(z + 1)P_{1} ⟨⟨ ⋯ ⟨⟨ (z + 1)P_{n} ⟨⟨ zP_{1} ⟨⟨ ⋯ ⟨⟨ zP_{n}.

Thus, for any 1 ≤ g ≤ n we have

(z + 1)P_{g} ⟨⟨ ⋯ ⟨⟨ (z + 1)P_{n} ⟨⟨ zP_{1} ⟨⟨ ⋯ ⟨⟨ zP_{g} and (z + 1)P_{g} ⟨⟨ zP_{g}.

(6)

Apply Lemmas 5 and 7 to (6) to see that

S′_{1} ≺ S′_{2} ≺ ⋯ ≺ S′_{n+1} ≺ S_{1} ≺ ⋯ ≺ S_{n+1} and S′_{1} ≺ S_{n+1},

in which case S′_{i} is the sum of the first i terms of (6), and S_{i} is the sum of the last n + 2 − i terms of (6).

From Lemma 5 applied to this sequence, we see in particular that S′_{n} ≺ S_{2}. But

S′_{n} = (z + 1)P_{g} + … + (z + 1)P_{n} + zP_{1} + … + zP_{g−1} = zF_{1} + F_{g}

and

S_{2} = (z + 1)P_{g+1} + … + (z + 1)P_{n} + zP_{1} + … + zP_{g} = zF_{1} + F_{g+1}.

Also, one sees directly that

zF_{1} + F_{1} = (z + 1)F_{1} ⟨⟨ zF_{1} = zF_{1} + F_{n+1}.

From Lemma 5 we conclude that

zF_{1} + F_{g} ⟨⟨ zF_{1} + F_{h}  for all  1 ≤ g < h ≤ n + 1.

Putting c_{0} := 0 and c_{n+1} := 1 and b_{0} := 0 and b_{n+1} := 1 we have

Q_{rj} = ∑_{g=1}^{n+1}(c_{g}−c_{g−1})(zF_{1}+F_{g}) and Q_{rk} = ∑_{g=1}^{n+1}(b_{g}−b_{g−1})(zF_{1}+F_{g}).

Condition \underline{C3} implies that for all 1 ≤ g ≤ n,

(b_{g} − b_{g−1})(c_{g+1} − c_{g}) ≤ (c_{g} − c_{g−1})(b_{g+1} − b_{g}).

Lemma 8 now implies that Q_{rj} ⟨⟨ Q_{rk}, completing the first part of the induction step.

For the second part of the induction step assume I(n) and II(n+1), and let A be an (n + 1) × (n + 1) Ferrers matrix satisfying \underline{C1}, \underline{C2}, and \underline{C3}. Let P_{i} := per(zJ_{n} + T_{i1}A) for 1 ≤ i ≤ n + 1; each P_{i} has all its zeros in the interval [−1, 0], by I(n), and P_{h} ⟨⟨ P_{i} for all 1 ≤ h < i ≤ n + 1, by II(n + 1). Moreover,

per(zJ_{n+1} + A) = ∑_{i=1}^{n+1}(z + a_{i1})P_{i}.

If A is Ferrers and \underline{C1} holds we have 0 ≤ a_{i1} ≤ ⋯ ≤ a_{n+1,1} ≤ 1, so for all 1 ≤ i ≤ n + 1 we have a_{i1}(1 − a_{i+1,1}) ≤ a_{i+1,1}(1 − a_{i1}), where a_{01} := 0 and a_{n+2,1} := 1. By Lemmas 6 and 8 we have

P_{1} ⟨⟨ ∑_{i=1}^{n+1}(1 − a_{i1})P_{i} ⟨⟨ ∑_{i=1}^{n+1} a_{i1}P_{i} ⟨⟨ P_{n+1}.

Since the zeros of these polynomials are all in the interval [−1, 0], Lemma 4 (a) implies that

(z + 1) ∑_{i=1}^{n+1} a_{i1}P_{i} ⟨⟨ z ∑_{i=1}^{n+1}(1 − a_{i1})P_{i}.

Applying Lemma 4 (d) to this we obtain

(z + 1) ∑_{i=1}^{n+1} a_{i1}P_{i} ⟨⟨ ∑_{i=1}^{n+1}(z + a_{i1})P_{i} ⟨⟨ z ∑_{i=1}^{n+1}(1 − a_{i1})P_{i},

and so per(zJ_{n+1} + A) has all its zeros in the interval [−1, 0]. This completes the proof. □

We can also show Conjecture 1 is true if the underlying tableau is the trivial staircase

1  2 … n
n + 1  n + 2 … 2n
⋮  ⋮
n^{2} − n + 1  … n^{2}

Theorem 4. Conjecture 1 is true provided the tableau associated to A is the one above, i.e. if a_{1,n} ≤ a_{2,1}, a_{2,n} ≤ a_{3,1}, …, a_{n−1,n} ≤ a_{n,1}. Furthermore, under these assumptions, with P (z) := per(zJ_{n} + A),

P (z) > 0 for z > −a_{11},
P (z) < 0 for − a_{21} < z < −a_{1n},
…, (−1)^{n}P (z) < 0 for − a_{n1} < z < −a_{n−1,n},
(−1)^{n}P (z) > 0 for z < −a_{nn}.

(7)

P roof : By induction on n. First assume that the inequalities on the a_{ij} are strict, and note that (7) then guarantees that P (z) has n distinct roots in [−a_{nn}, −a_{11}]. Let P_{ij}(z) denote the permanent of the matrix obtained by deleting row i and column j of zJ_{n} + A. By expanding in minors we have

P (z) = (a_{11} +z)P_{11}(z)+(a_{12} +z)P_{12}(z)+…+(a_{1n} +z)P_{1n}(z). (8)

Applying the induction hypothesis to the P_{1j} we get

P_{11}(z) > 0 for z > −a_{22},
P_{12}(z) > 0 for z > −a_{21}, …,
P_{1n}(z) > 0 for z > −a_{21}.

By (8) this implies

P (z) > 0 for z > −a_{11}, and P (z) < 0 for − a_{21} < z < −a_{1n}.

Similarly using

P_{11}(z) < 0 for − a_{32} < z < −a_{2n}, …,
P_{1n}(z) < 0 for − a_{31} < z < −a_{2,n−1}

we get

P (z) > 0 for − a_{31} < z < −a_{2n}.

Continuing in this manner we easily verify the rest of (7). The case where some of the a_{ij} are equal follows from a simple continuity argument using the argument principle. □

Acknowledgments

The authors would like to thank E. R. Canfield for suggesting the parameterization of the matrix A in terms of the w_{i}, H. Wilf for bringing Szegö’s result to their attention, and R. Stanley for observing that Conjecture 1 could be formulated in terms of permanents.

References

[Bre] F. Brenti, Unimodal, log-concave and Pólya frequency series in combinatorics, Mem. Amer. Math. Soc. 413 (1989).

[GaWa] J. Garloff and D.G. Wagner, Hadamard products of stable polynomials are stable, J. Math. Anal. Appl. 202 (1996), 797-809.

[GJW] J. R. Goldman, J. T. Joichi, and D. E. White, Rook theory I: Rook equivalence of Ferrers boards, Proc. Amer. Math. Soc. 52 (1975), 485– 492.

[Gra] J. H. Grace, The zeros of a polynomial, Proc. Cambridge Phil. Soc. 11 (1900-1902), 352-357.

[Hag1] J. Haglund, Compositions, Rook Placements, and Permutations of Vectors, Ph.D. Thesis, University of Georgia, 1993.

[Hag2] J. Haglund, Rook theory, compositions, and zeta functions, Trans. Amer. Math. Soc. 348 (1996), 3799–3825.

[HeLi] O. Heilmann and E. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190–232.

[HLP] G. Hardy, J. Littlewood and G. Pólya, Inequalities, 2nd ed., Cambridge Univ. Press, Cambridge, 1952.

[KaRi] I. Kaplansky and J. Riordan, The problem of the rooks and its applications, Duke Math. J. 13 (1946), 259–268.

[Lag] E. Laguerre, Oeuvres, vol. I, Gauther-Villars, Paris, 1898.

[Lev] B. Levin, Distribution of Zeros of Entire Functions, Transl. of Mathematical Monographs, vol. 5, Amer. Math. Soc., Providence, Rhode Island, 1964.

[Nij] A. Niejenhuis, On permanents and the zeros of the rook polynomials, J. Combin. Theory (A) 21 (1976), 240–244.

[PoSz] G. Polya and G. Szegö, Problems and Theorems in Analysis, Volume II, Springer-Verlag, New York, 1976.

[Rio] J. Riordan, An Introduction to Combinatorial Analysis, John Wiley, New York, NY, 1958.

[Sch] I. Schur, Zwei Sätze über algebraische gleichungen mit laiter reellen wurzeln, J. reine angew. Math. 144 (1914), 75–88.

[Sim] R. Simion, A multi-indexed Sturm sequence of polynomials and unimodality of certain combinatorial sequences, J. Combin. Theory (A) 36 (1984), 15-22.

[Sze] G. Szegö, Bemerkungen zu einem Satz von J. H. Grace über die Wurzeln algebraischer Gleichungen, Math. Z. 13 (1922), 28–55.

[Vle] E. B. Van Vleck, On the location of roots of polynomials and entire functions, Bull. Amer. Math. Soc. 35 (1929), 643–683.

[Wag1] D.G. Wagner, Total positivity of Hadamard Products, J. Math. Anal. Appl. 163 (1992), 459-483.

[Wag2] D.G. Wagner, Enumeration of functions from posets to chains, Europ. J. Combin. 13 (1992), 313-324.

[Wag3] D.G. Wagner, Multipartition series, S.I.A.M. J. Discrete Math. 9 (1996), 529-544.

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

E-mail address: haglund@math.mit.edu

Department of Mathematics, Penn State University. University Park, Pennsylvania 18602

E-mail address: ono@math.psu.edu

University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

E-mail address: dwagner@uwaterloo.ca