Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



An upper bound on the characteristic polynomial of a nonnegative matrix leading to a proof of the Boyle-Handelman conjecture

Authors: Assaf Goldberger and Michael Neumann
Journal: Proc. Amer. Math. Soc. 137 (2009), 1529-1538
MSC (2000): Primary 15A48, 15A18, 11C08
Published electronically: January 2, 2009
MathSciNet review: 2470809
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In their celebrated 1991 paper on the inverse eigenvalue problem for nonnegative matrices, Boyle and Handelman conjectured that if $ A$ is an $ (n+1)\times (n+1)$ nonnegative matrix whose nonzero eigenvalues are: $ \lambda_0 \geq \vert\lambda_i\vert$, $ i=1,\ldots,r$, $ r \leq n$, then for all $ x \geq \lambda_0$,

$\displaystyle \prod_{i=0}^{r} (x-\lambda_i) \leq x^{r+1}-\lambda_0^{r+1}.$ $ (\ast)$

To date the status of this conjecture is that Ambikkumar and Drury (1997) showed that the conjecture is true when $ 2(r+1)\geq (n+1)$, while Koltracht, Neumann, and Xiao (1993) showed that the conjecture is true when $ n\leq 4$ and when the spectrum of $ A$ is real. They also showed that the conjecture is asymptotically true with the dimension.

Here we prove a slightly stronger inequality than in $ (\ast)$, from which it follows that the Boyle-Handelman conjecture is true. Actually, we do not start from the assumption that the $ \lambda_i$'s are eigenvalues of a nonnegative matrix, but that $ \lambda_1,\ldots, \lambda_{r+1}$ satisfy $ \lambda_0\geq \vert\lambda_i\vert$, $ i=1,\ldots, r$, and the trace conditions:

$\displaystyle \sum_{i=0}^{r} \lambda_i^k \geq 0, \ $   for all$\displaystyle k \geq 1.$ $ (\ast\ast)$

A strong form of the Boyle-Handelman conjecture, conjectured in 2002 by the present authors, says that ($ *$) continues to hold if the trace inequalities in ($ **$) hold only for $ k=1,\ldots,r$. We further improve here on earlier results of the authors concerning this stronger form of the Boyle-Handelman conjecture.

References [Enhancements On Off] (What's this?)

  • 1. S. Ambikkumar and S.W. Drury.
    Some remarks on a conjecture of Boyle and Handelman.
    Linear Alg. Appl. 264:63-99, 1997. MR 1465857 (98h:15036)
  • 2. J. Ashley.
    On the Perron-Frobenius eigenvector for nonnegative integral matrices whose largest eigenvalue is integral.
    Linear Alg. Appl., 94:103-108, 1987. MR 902070 (88h:15033)
  • 3. M. Boyle and D. Handelman.
    The spectra of nonnegative matrices via symbolic dynamics.
    Ann. of Math. (2), 133:249-316, 1991. MR 1097240 (92d:58057)
  • 4. M. Fiedler, Untitled private communication, 1982.
  • 5. A. Goldberger and M. Neumann.
    On a strong form of a conjecture of Boyle and Handelman.
    Electron. J. Linear Alg., 9:138-149, 2002. MR 1920915 (2003h:15033)
  • 6. R. A. Horn and C. R. Johnson.
    Matrix Analysis.
    Cambridge University Press, Cambridge, 1985. MR 832183 (87e:15001)
  • 7. J. Keilson and G. Styan.
    Markov chains and $ M$-matrices: Inequalities and equalities.
    J. of Math. Anal. Appl., 41:439-459, 1973. MR 0314873 (47:3422)
  • 8. I. Koltracht, M. Neumann, and D. Xiao.
    On a question of Boyle and Handelman concerning eigenvalues of nonnegative matrices.
    Linear Multilinear Alg., 36:125-140, 1993. MR 1308915 (95k:15027)
  • 9. I. G. MacDonald.
    Symmetric Functions and Orthogonal Polynomials.
    University Lecture Series, 12, Amer. Math. Soc., Providence, RI, 1998. MR 1488699 (99f:05116)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 15A48, 15A18, 11C08

Retrieve articles in all journals with MSC (2000): 15A48, 15A18, 11C08

Additional Information

Assaf Goldberger
Affiliation: School of Mathematical Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel

Michael Neumann
Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269–3009

Keywords: Nonnegative matrices, the inverse eigenvalue problem for nonnegative matrices, characteristic polynomial
Received by editor(s): May 5, 2008
Published electronically: January 2, 2009
Additional Notes: The research of the second author was supported in part by NSA Grant No. 06G–232
Dedicated: Dedicated to the memory of our dear colleague Professor Israel Koltracht, 1949–2008
Communicated by: Martin Lorenz
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society