The spectra of nonnegative integer matrices via formal power series

Authors:
Ki Hang Kim, Nicholas S. Ormes and Fred W. Roush

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

Published electronically:
June 21, 2000

MathSciNet review:
1775737

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 and follow from this result. For the proof of the main theorem we use polynomial matrices to reduce the problem of realizing a candidate spectrum to factoring the polynomial as a product where the 's are polynomials in satisfying some technical conditions and is a formal power series in . To obtain the factorization, we present a hierarchy of estimates on coefficients of power series of the form to ensure nonpositivity in nonzero degree terms.

**[BGMY80]**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****[BH91]**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**[BH93]**Mike Boyle and David Handelman,*Algebraic shift equivalence and primitive matrices*, Trans. Amer. Math. Soc.**336**(1993), no. 1, 121–149. MR**1102219**, https://doi.org/10.1090/S0002-9947-1993-1102219-4**[Bor95]**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**, https://doi.org/10.1016/0024-3795(94)00343-C**[Boy93]**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**, https://doi.org/10.1007/978-1-4613-8354-3_1**[BP94]**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****[Cia68]**P. G. Ciarlet,*Some results in the theory of nonnegative matrices*, Linear Algebra and Appl.**1**(1968), no. 1, 139–152. MR**0223386****[Fie74]**Miroslav Fiedler,*Eigenvalues of nonnegative symmetric matrices*, Linear Algebra and Appl.**9**(1974), 119–142. MR**0364288****[Fri78]**Shmuel Friedland,*On an inverse problem for nonnegative and eventually nonnegative matrices*, Israel J. Math.**29**(1978), no. 1, 43–60. MR**492634**, https://doi.org/10.1007/BF02760401**[JLL96]**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**, https://doi.org/10.1090/S0002-9939-96-03587-3**[Joh81]**Charles R. Johnson,*Row stochastic matrices similar to doubly stochastic matrices*, Linear and Multilinear Algebra**10**(1981), no. 2, 113–130. MR**618581**, https://doi.org/10.1080/03081088108817402**[Kel71]**R. Bruce Kellogg,*Matrices similar to a positive or essentially positive matrix*, Linear Algebra and Appl.**4**(1971), 191–204. MR**0288133****[KRW97]**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**, https://doi.org/10.1090/S1079-6762-97-00024-3**[Lin84]**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**, https://doi.org/10.1017/S0143385700002443**[LL79]**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**0480563**, https://doi.org/10.1080/03081087808817226**[LM95]**Douglas Lind and Brian Marcus,*An introduction to symbolic dynamics and coding*, Cambridge University Press, Cambridge, 1995. MR**1369092****[LM98]**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**, https://doi.org/10.13001/1081-3810.1018**[LM99]**T. J. Laffey and E. Meehan,*A characterization of trace zero nonnegative matrices*, Linear Algebra Appl.**302-303**(1999), 295-302. CMP**2000:07****[Min88]**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****[MT91]**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**, https://doi.org/10.1017/S0143385700006052**[Per53]**H. Perfect,*Methods of constructing certain stochastic matrices*, Duke Math. J.**20**(1953), 395-404. MR**15:3h****[Per92]**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**, https://doi.org/10.1016/0304-3975(92)90043-F**[Rea94]**R. Reams,*Topics in matrix theory*, Ph.D. thesis, National University of Ireland, Dublin, 1994.**[Rea96]**Robert Reams,*An inequality for nonnegative matrices and the inverse eigenvalue problem*, Linear and Multilinear Algebra**41**(1996), no. 4, 367–375. MR**1481909**, https://doi.org/10.1080/03081089608818485**[Sal72]**Frank L. Salzmann,*A note on eigenvalues of nonnegative matrices*, Linear Algebra and Appl.**5**(1972), 329–338. MR**0320034****[Sou83]**George W. Soules,*Constructing symmetric nonnegative matrices*, Linear and Multilinear Algebra**13**(1983), no. 3, 241–251. MR**700887**, https://doi.org/10.1080/03081088308817523**[Sul49]**H. R. Sulemanova,*Stochastic matrices with real characteristic numbers*, Doklady Akad. Nauk SSSR (N.S.)**66**(1949), 343-345. MR**11:4d****[Wuw97]**Guo Wuwen,*Eigenvalues of nonnegative matrices*, Linear Algebra Appl.**266**(1997), 261–270. MR**1473205**, https://doi.org/10.1016/S0024-3795(96)00007-9

Retrieve articles in *Journal of the American Mathematical Society*
with MSC (1991):
15A18,
15A36,
58F03,
58F20

Retrieve articles in all journals with MSC (1991): 15A18, 15A36, 58F03, 58F20

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

Email:
ormes@math.utexas.edu

**Fred W. Roush**

Affiliation:
Mathematics Research Group, Alabama State University, Montgomery, Alabama 36101-0271

Email:
froush@gmail.alasu.edu

DOI:
https://doi.org/10.1090/S0894-0347-00-00342-8

Keywords:
Spectrum of nonnegative matrix,
zeta function of subshift of finite type

Received by editor(s):
August 19, 1998

Received by editor(s) in revised form:
February 1, 2000

Published electronically:
June 21, 2000

Article copyright:
© Copyright 2000
American Mathematical Society