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

DOI:
https://doi.org/10.1090/S0002-9939-08-09701-3

Published electronically:
January 2, 2009

MathSciNet review:
2470809

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 |\lambda _i|$, $i=1,\ldots ,r$, $r \leq \ n$, then for all $x \geq \lambda _0$, \begin{equation} \prod _{i=0}^{r} (x-\lambda _i) \leq x^{r+1}-\lambda _0^{r+1}.\tag *{$(\ast )$} \end{equation}

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 |\lambda _i|$, $i=1,\ldots , r$, and the trace conditions: \begin{equation} \sum _{i=0}^{r} \lambda _i^k \geq 0, \ \mbox {for all} k \geq 1.\tag *{$(\ast \ast )$} \end{equation} 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.

- S. Ambikkumar and S. W. Drury,
*Some remarks on a conjecture of Boyle and Handelman*, Linear Algebra Appl.**264**(1997), 63â€“99. MR**1465857**, DOI https://doi.org/10.1016/S0024-3795%2896%2900402-8 - 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**, DOI https://doi.org/10.1016/0024-3795%2887%2990081-4 - 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**, DOI https://doi.org/10.2307/2944339 - M. Fiedler, Untitled private communication, 1982.
- 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**, DOI https://doi.org/10.13001/1081-3810.1082 - Roger A. Horn and Charles R. Johnson,
*Matrix analysis*, Cambridge University Press, Cambridge, 1985. MR**832183** - Julian Keilson and George P. H. Styan,
*Markov chains and $M$-matrices: inequalities and equalities*, J. Math. Anal. Appl.**41**(1973), 439â€“459. MR**314873**, DOI https://doi.org/10.1016/0022-247X%2873%2990219-9 - 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**, DOI https://doi.org/10.1080/03081089308818282 - 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**

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

Email:
assafg@post.tau.ac.il

**Michael Neumann**

Affiliation:
Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269â€“3009

Email:
neumann@math.uconn.edu

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.