## The spectra of nonnegative integer matrices via formal power series

HTML articles powered by AMS MathViewer

- by Ki Hang Kim, Nicholas S. Ormes and Fred W. Roush PDF
- J. Amer. Math. Soc.
**13**(2000), 773-806 Request permission

## Abstract:

We characterize the possible nonzero spectra of primitive integer matrices (the integer case of Boyle and Handelman’s Spectral Conjecture). Characterizations of nonzero spectra of nonnegative matrices over ${\mathbb Z}$ and ${\mathbb Q}$ follow from this result. For the proof of the main theorem we use polynomial matrices to reduce the problem of realizing a candidate spectrum $(\lambda _1,\lambda _2,\ldots ,\lambda _d)$ to factoring the polynomial $\prod _{i=1}^d (1-\lambda _it)$ as a product $(1-r(t))\prod _{i=1}^n (1-q_i(t))$ where the $q_i$’s are polynomials in $t{\mathbb Z}_+[t]$ satisfying some technical conditions and $r$ is a formal power series in $t{\mathbb Z}_+[[t]]$. To obtain the factorization, we present a hierarchy of estimates on coefficients of power series of the form $\prod _{i=1}^d (1-\lambda _it)/\prod _{i=1}^n (1-q_i(t))$ to ensure nonpositivity in nonzero degree terms.## References

- Louis Block, John Guckenheimer, MichałMisiurewicz, and Lai Sang Young,
*Periodic points and topological entropy of one-dimensional maps*, Global theory of dynamical systems (Proc. Internat. Conf., Northwestern Univ., Evanston, Ill., 1979) Lecture Notes in Math., vol. 819, Springer, Berlin, 1980, pp. 18–34. MR**591173** - 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 10.2307/2944339 - Mike Boyle and David Handelman,
*Algebraic shift equivalence and primitive matrices*, Trans. Amer. Math. Soc.**336**(1993), no. 1, 121–149. MR**1102219**, DOI 10.1090/S0002-9947-1993-1102219-4 - Alberto Borobia,
*On the nonnegative eigenvalue problem*, Linear Algebra Appl.**223/224**(1995), 131–140. Special issue honoring Miroslav Fiedler and Vlastimil Pták. MR**1340689**, DOI 10.1016/0024-3795(94)00343-C - Mike Boyle,
*Symbolic dynamics and matrices*, Combinatorial and graph-theoretical problems in linear algebra (Minneapolis, MN, 1991) IMA Vol. Math. Appl., vol. 50, Springer, New York, 1993, pp. 1–38. MR**1240955**, DOI 10.1007/978-1-4613-8354-3_{1} - Abraham Berman and Robert J. Plemmons,
*Nonnegative matrices in the mathematical sciences*, Classics in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. Revised reprint of the 1979 original. MR**1298430**, DOI 10.1137/1.9781611971262 - P. G. Ciarlet,
*Some results in the theory of nonnegative matrices*, Linear Algebra Appl.**1**(1968), no. 1, 139–152. MR**223386**, DOI 10.1016/0024-3795(68)90054-2 - Miroslav Fiedler,
*Eigenvalues of nonnegative symmetric matrices*, Linear Algebra Appl.**9**(1974), 119–142. MR**364288**, DOI 10.1016/0024-3795(74)90031-7 - Shmuel Friedland,
*On an inverse problem for nonnegative and eventually nonnegative matrices*, Israel J. Math.**29**(1978), no. 1, 43–60. MR**492634**, DOI 10.1007/BF02760401 - Charles R. Johnson, Thomas J. Laffey, and Raphael Loewy,
*The real and the symmetric nonnegative inverse eigenvalue problems are different*, Proc. Amer. Math. Soc.**124**(1996), no. 12, 3647–3651. MR**1350951**, DOI 10.1090/S0002-9939-96-03587-3 - Charles R. Johnson,
*Row stochastic matrices similar to doubly stochastic matrices*, Linear and Multilinear Algebra**10**(1981), no. 2, 113–130. MR**618581**, DOI 10.1080/03081088108817402 - R. Bruce Kellogg,
*Matrices similar to a positive or essentially positive matrix*, Linear Algebra Appl.**4**(1971), 191–204. MR**288133**, DOI 10.1016/0024-3795(71)90015-2 - K. H. Kim, F. W. Roush, and J. B. Wagoner,
*Inert actions on periodic points*, Electron. Res. Announc. Amer. Math. Soc.**3**(1997), 55–62. MR**1464576**, DOI 10.1090/S1079-6762-97-00024-3 - D. A. Lind,
*The entropies of topological Markov shifts and a related class of algebraic integers*, Ergodic Theory Dynam. Systems**4**(1984), no. 2, 283–300. MR**766106**, DOI 10.1017/S0143385700002443 - Raphael Loewy and David London,
*A note on an inverse problem for nonnegative matrices*, Linear and Multilinear Algebra**6**(1978/79), no. 1, 83–90. MR**480563**, DOI 10.1080/03081087808817226 - Douglas Lind and Brian Marcus,
*An introduction to symbolic dynamics and coding*, Cambridge University Press, Cambridge, 1995. MR**1369092**, DOI 10.1017/CBO9780511626302 - Thomas J. Laffey and Eleanor Meehan,
*A refinement of an inequality of Johnson, Loewy and London on nonnegative matrices and some applications*, Electron. J. Linear Algebra**3**(1998), 119–128. MR**1637415**, DOI 10.13001/1081-3810.1018
[LM99]LafMee2 T. J. Laffey and E. Meehan, - Henryk Minc,
*Nonnegative matrices*, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1988. A Wiley-Interscience Publication. MR**932967** - Brian Marcus and Selim Tuncel,
*The weight-per-symbol polytope and scaffolds of invariants associated with Markov chains*, Ergodic Theory Dynam. Systems**11**(1991), no. 1, 129–180. MR**1101088**, DOI 10.1017/S0143385700006052 - Sam Perlis,
*Maximal orders in rational cyclic algebras of composite degree*, Trans. Amer. Math. Soc.**46**(1939), 82–96. MR**15**, DOI 10.1090/S0002-9947-1939-0000015-X - Dominique Perrin,
*On positive matrices*, Theoret. Comput. Sci.**94**(1992), no. 2, 357–366. Discrete mathematics and applications to computer science (Marseille, 1989). MR**1157864**, DOI 10.1016/0304-3975(92)90043-F
[Rea94]ReamsPhD R. Reams, - Robert Reams,
*An inequality for nonnegative matrices and the inverse eigenvalue problem*, Linear and Multilinear Algebra**41**(1996), no. 4, 367–375. MR**1481909**, DOI 10.1080/03081089608818485 - Frank L. Salzmann,
*A note on eigenvalues of nonnegative matrices*, Linear Algebra Appl.**5**(1972), 329–338. MR**320034** - George W. Soules,
*Constructing symmetric nonnegative matrices*, Linear and Multilinear Algebra**13**(1983), no. 3, 241–251. MR**700887**, DOI 10.1080/03081088308817523 - Morgan Ward and R. P. Dilworth,
*The lattice theory of ova*, Ann. of Math. (2)**40**(1939), 600–608. MR**11**, DOI 10.2307/1968944 - Guo Wuwen,
*Eigenvalues of nonnegative matrices*, Linear Algebra Appl.**266**(1997), 261–270. MR**1473205**, DOI 10.1016/S0024-3795(96)00007-9

*A characterization of trace zero nonnegative $5 \times 5$ matrices*, Linear Algebra Appl.

**302-303**(1999), 295–302.

*Topics in matrix theory*, Ph.D. thesis, National University of Ireland, Dublin, 1994.

## Additional Information

**Ki Hang Kim**- Affiliation: Mathematics Research Group, Alabama State University, Montgomery, Alabama 36101-0271 and Korean Academy of Science and Technology
- Email: kkim@gmail.alasu.edu
**Nicholas S. Ormes**- Affiliation: Department of Mathematics, C1200, University of Texas, Austin, Texas 78712
- Address at time of publication: Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269-3009
- MR Author ID: 620777
- Email: ormes@math.utexas.edu
**Fred W. Roush**- Affiliation: Mathematics Research Group, Alabama State University, Montgomery, Alabama 36101-0271
- Email: froush@gmail.alasu.edu
- Received by editor(s): August 19, 1998
- Received by editor(s) in revised form: February 1, 2000
- Published electronically: June 21, 2000
- © Copyright 2000 American Mathematical Society
- Journal: J. Amer. Math. Soc.
**13**(2000), 773-806 - MSC (1991): Primary 15A18; Secondary 15A36, 58F03, 58F20
- DOI: https://doi.org/10.1090/S0894-0347-00-00342-8
- MathSciNet review: 1775737