1 Introduction
Our main objective is to prove a conjecture of Xin and Zhang [Reference Xin and Zhang13], which gives a product formula for the characteristic polynomial of a certain tridiagonal matrix.
Conjecture 1.1 [Reference Xin and Zhang13, Conjecture 4.8].
Let n be a positive integer and let C be the
$(n-1) \times (n-1)$
matrix defined by
Then,
$\det C$
is equal to
This conjecture arises in the study of the Ehrhart polynomial
$H_n(t)$
of the nth Birkhoff polytope, where
$H_n(t)$
counts the number of
$n \times n$
nonnegative integer matrices with all row and column sums equal to t. The computation of
$H_n(t)$
has been a subject of extensive research (see, for example, [Reference Alexandersson, Hopkins and Zaimi1, Reference Chan and Robbins5, Reference De Loera, Liu and Yoshida6, Reference MacMahon8–Reference Stanley11, Reference Xin, Zhang, Zhou and Zhong14]). So far,
$H_n(t)$
is known only for
$n \leq 9$
, with
$H_9(t)$
computed by Beck and Pixton [Reference Beck and Pixton3] using residue techniques.
From [Reference Beck and Pixton3, Corollary 4],
where the sum is over all nonnegative integer sequences
$\boldsymbol {m} = (m_1, m_2, \ldots , m_n)$
such that
$\sum _{i=1}^n m_i = n$
and
$\sum _{i=1}^r m_i> r$
for
$1 \le r < n$
. Here,
$\mathop {\mathrm {CT}}\limits _{\boldsymbol {x}} f$
denotes the constant term of the Laurent series f in
$\boldsymbol {x} = (x_1, x_2, \ldots , x_n)$
and
In particular, for
$\boldsymbol {m} = (2, 1^{n-2}, 0)$
, we define
Noting the similarity with the Morris constant term identity studied in [Reference Baldoni-Silva and Vergne2, Reference Xin12], Xin and Zhang [Reference Xin and Zhang13] derived a recurrence for
$h_n(t)$
of the form
in which
$c_0(t) = \det C$
. Therefore, if Conjecture 1.1 holds, then (1.1) indeed yields a recurrence when
The ideas in [Reference Xin and Zhang13] also apply to
$\mathop {\mathrm {CT}}\limits _{\boldsymbol {x}} \mathcal {H}^{(k, 1^{n-k}, 0^{\,k-1})}(t)$
for
$3 \le k \le n-1$
. Moreover, the determinant
$\det C$
arises in a similar but more complicated recurrence. These aspects will be elaborated on in an upcoming paper [Reference Zhang15].
Further developments motivate us to consider the equivalent determinant of
where I is the identity matrix and
$\widetilde {C}^{(n)}$
is an
$n \times n$
tridiagonal matrix with entries
It is hard to determine the characteristic polynomial of
$\widetilde {C}^{(n)}$
: none of the minors of
$tI-\widetilde {C}^{(n)}$
admits a simple factorisation. This prevents us from proving the conjecture by traditional techniques such as diagonalisation, LU decompositions, continued fractions and so on. Ultimately, we discovered that
$\widetilde {C}^{(n)}$
is similar to a lower triangular matrix. It is noteworthy that the similar matrix is a variation of Pascal’s triangle. We state this result as the following theorem.
Theorem 1.2. For a positive integer n, let
$\widetilde {C}^{(n)}$
be the matrix defined in (1.2). There exists an
$n \times n$
nonsingular upper triangular matrix U with entries
such that
$U \widetilde {C}^{(n)} U^{-1}$
is a lower triangular matrix whose entries are given by
Consequently, Conjecture 1.1 holds and we have the nice formula
For instance,
In Section 2, we prove Theorem 1.2 using an explicit formula for
$U^{-1}$
, together with several combinatorial identities. Section 3 contains concluding remarks.
2 The proof of Theorem 1.2
Our proof of Theorem 1.2 is based on the following well-known combinatorial identities (the proofs are omitted):
where
$n \ge k \ge j$
are nonnegative integers.
Proof of Theorem 1.2.
By [Reference Call and Velleman4, Theorem 1], the entries of
$U^{-1}$
are given by
Consider the
$(i,j)$
-entry of
$U \widetilde {C}^{(n)} U^{-1}$
:
where the second equality holds because
$(\widetilde {C}^{(n)})_{l,m} = 0$
when
$|l-m|>1$
. Observe that
$(\widetilde {C}^{(n)})_{l,l} = (\widetilde {C}^{(n)})_{l,l-1} + (\widetilde {C}^{(n)})_{l,l+1}$
, and the formulae for
$(\widetilde {C}^{(n)})_{l,l-1}$
and
$(\widetilde {C}^{(n)})_{l,l+1}$
vanish when
$l=1$
and
$l=n$
, respectively. The computation is naturally divided into two parts, denoted by
$S_1$
and
$S_2$
. In detail,
Similarly,
Using (2.2), we can further compute
$S_2$
:
Then,
It is clear that the above formula equals
$0$
when
$i> j + 1$
and equals
$(1-i)(n+1-i)$
when
$i = j + 1$
. When
$i \le j$
, we can further write
This completes the proof.
As a byproduct, we have the following result.
Proposition 2.1. Let U be the matrix with entries as in (1.3) and M be a matrix satisfying
$M_{i,j} =0$
whenever
$i-j \ge 2$
. Then,
$(UMU^{-1})_{i,\,j} = M_{i,\,j}$
whenever
$i - j \ge 1$
.
Proposition 2.1 can be visualised as
where ‘
$*$
’ and ‘
$\triangle $
’ stand for unspecified entries.
Proof of Proposition 2.1.
Consider the
$(i,j)$
-entry of
$UMU^{-1}$
:
For fixed i and j, we have
$\binom {n-i}{n-l} \binom {n-m}{n-j} = 0$
unless
$l \ge i$
and
$m \le j$
.
In the case where
$i - j \ge 2$
, the condition
$l \ge i$
and
$m \le j$
implies that
$l - m \ge i - j \ge 2$
. Hence,
$M_{l,m} = 0$
and so
$(UMU^{-1})_{i,\,j} = 0 = M_{i,\,j}$
.
In the case where
$i - j = 1$
,
Hence,
$(UMU^{-1})_{i, i-1} = M_{i,i-1}$
. This completes the proof.
3 Concluding remarks
The observation
$(\widetilde {C}^{(n)})_{i,i} = (\widetilde {C}^{(n)})_{i,i-1} + (\widetilde {C}^{(n)})_{i,i+1}$
leads us to consider a matrix A satisfying
$A_{i,i} = r + A_{i,i-1} + A_{i,i+1}$
, where r is a parameter. Further exploration gives a generalisation of Theorem 1.2, which requires a cumbersome condition. We elaborate on this generalisation in the extended version [Reference Hu and Zhang7, Section 3].
Acknowledgements
The authors would like to thank Professors Guoce Xin (Capital Normal University) and Arthur L. B. Yang (Nankai University) for helpful discussions.
