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
Abstract: In their celebrated 1991 paper on the inverse eigenvalue problem for nonnegative matrices, Boyle and Handelman conjectured that if is an nonnegative matrix whose nonzero eigenvalues are: , , , then for all ,
To date the status of this conjecture is that Ambikkumar and Drury (1997) showed that the conjecture is true when , while Koltracht, Neumann, and Xiao (1993) showed that the conjecture is true when and when the spectrum of is real. They also showed that the conjecture is asymptotically true with the dimension.
Here we prove a slightly stronger inequality than in , from which it follows that the Boyle-Handelman conjecture is true. Actually, we do not start from the assumption that the 's are eigenvalues of a nonnegative matrix, but that satisfy , , and the trace conditions:
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 . We further improve here on earlier results of the authors concerning this stronger form of the Boyle-Handelman conjecture.
- 1. S. Ambikkumar and S. W. Drury, Some remarks on a conjecture of Boyle and Handelman, Linear Algebra Appl. 264 (1997), 63–99. MR 1465857, https://doi.org/10.1016/S0024-3795(96)00402-8
- 2. Jonathan Ashley, On the Perron-Frobenius eigenvector for nonnegative integral matrices whose largest eigenvalue is integral, Linear Algebra Appl. 94 (1987), 103–108. MR 902070, https://doi.org/10.1016/0024-3795(87)90081-4
- 3. Mike Boyle and David Handelman, The spectra of nonnegative matrices via symbolic dynamics, Ann. of Math. (2) 133 (1991), no. 2, 249–316. MR 1097240, https://doi.org/10.2307/2944339
- 4. M. Fiedler, Untitled private communication, 1982.
- 5. Assaf Goldberger and Michael Neumann, On a strong form of a conjecture of Boyle and Handelman, Electron. J. Linear Algebra 9 (2002), 138–149. MR 1920915, https://doi.org/10.13001/1081-3810.1082
- 6. Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183
- 7. Julian Keilson and George P. H. Styan, Markov chains and 𝑀-matrices: inequalities and equalities, J. Math. Anal. Appl. 41 (1973), 439–459. MR 0314873, https://doi.org/10.1016/0022-247X(73)90219-9
- 8. I. Koltracht, M. Neumann, and D. Xiao, On a question of Boyle and Handelman concerning eigenvalues of nonnegative matrices, Linear and Multilinear Algebra 36 (1993), no. 2, 125–140. MR 1308915, https://doi.org/10.1080/03081089308818282
- 9. I. G. Macdonald, Symmetric functions and orthogonal polynomials, University Lecture Series, vol. 12, American Mathematical Society, Providence, RI, 1998. Dean Jacqueline B. Lewis Memorial Lectures presented at Rutgers University, New Brunswick, NJ. MR 1488699
- 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)
- 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)
- 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)
- M. Fiedler, Untitled private communication, 1982.
- 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)
- R. A. Horn and C. R. Johnson.
Cambridge University Press, Cambridge, 1985. MR 832183 (87e:15001)
- J. Keilson and G. Styan.
Markov chains and -matrices: Inequalities and equalities.
J. of Math. Anal. Appl., 41:439-459, 1973. MR 0314873 (47:3422)
- 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)
- I. G. MacDonald.
Symmetric Functions and Orthogonal Polynomials.
University Lecture Series, 12, Amer. Math. Soc., Providence, RI, 1998. MR 1488699 (99f:05116)
Affiliation: School of Mathematical Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel
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.