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

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]**L. Block, J. Guckenheimer, M. Misiurewicz, and L. S. 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**82j:58097****[BH91]**M. Boyle and D. Handelman,*The spectra of nonnegative matrices via symbolic dynamics*, Ann. of Math. (2)**133**(1991), no. 2, 249-316. MR**92d:58057****[BH93]**M. Boyle and D. Handelman,*Algebraic shift equivalence and primitive matrices*, Trans. Amer. Math. Soc.**336**(1993), no. 1, 121-149. MR**93e:58050****[Bor95]**A. Borobia,*On the nonnegative eigenvalue problem*, Linear Algebra Appl.**223/224**(1995), 131-140, Special issue honoring Miroslav Fiedler and Vlastimil Pták. MR**96e:15009****[Boy93]**M. 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**94g:58062****[BP94]**A. Berman and R. 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**95e:15013****[Cia68]**P. G. Ciarlet,*Some results in the theory of nonnegative matrices*, Linear Algebra and Appl.**1**(1968), no. 1, 139-152. MR**36:6434****[Fie74]**M. Fiedler,*Eigenvalues of nonnegative symmetric matrices*, Linear Algebra and Appl.**9**(1974), 119-142. MR**51:543****[Fri78]**S. Friedland,*On an inverse problem for nonnegative and eventually nonnegative matrices*, Israel J. Math.**29**(1978), no. 1, 43-60. MR**80h:15010****[JLL96]**C. R. Johnson, T. J. Laffey, and R. Loewy,*The real and the symmetric nonnegative inverse eigenvalue problems are different*, Proc. Amer. Math. Soc.**124**(1996), no. 12, 3647-3651. MR**97b:15009****[Joh81]**C. R. Johnson,*Row stochastic matrices similar to doubly stochastic matrices*, Linear and Multilinear Algebra**10**(1981), no. 2, 113-130. MR**82g:15016****[Kel71]**R. B. Kellogg,*Matrices similar to a positive or essentially positive matrix*, Linear Algebra and Appl.**4**(1971), 191-204. MR**44:5331****[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 (electronic). MR**98i:54021****[Lin84]**D. A. Lind,*The entropies of topological Markov shifts and a related class of algebraic integers*, Ergodic Theory Dynamical Systems**4**(1984), no. 2, 283-300. MR**86c:58092****[LL79]**R. Loewy and D. London,*A note on an inverse problem for nonnegative matrices*, Linear and Multilinear Algebra**6**(1978/79), no. 1, 83-90. MR**58:722****[LM95]**D. Lind and B. Marcus,*An introduction to symbolic dynamics and coding*, Cambridge University Press, Cambridge, 1995. MR**97a:58050****[LM98]**T. J. Laffey and E. 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 (electronic). MR**99f:15031****[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]**H. Minc,*Nonnegative matrices*, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1988, A Wiley-Interscience Publication. MR**89i:15001****[MT91]**B. Marcus and S. Tuncel,*The weight-per-symbol polytope and scaffolds of invariants associated with Markov chains*, Ergodic Theory Dynamical Systems**11**(1991), no. 1, 129-180. MR**92g:28038****[Per53]**H. Perfect,*Methods of constructing certain stochastic matrices*, Duke Math. J.**20**(1953), 395-404. MR**15:3h****[Per92]**D. Perrin,*On positive matrices*, Theoret. Comput. Sci.**94**(1992), no. 2, 357-366, Discrete mathematics and applications to computer science (Marseille, 1989). MR**93f:15018****[Rea94]**R. Reams,*Topics in matrix theory*, Ph.D. thesis, National University of Ireland, Dublin, 1994.**[Rea96]**R. Reams,*An inequality for nonnegative matrices and the inverse eigenvalue problem*, Linear and Multilinear Algebra**41**(1996), no. 4, 367-375. MR**99c:15031****[Sal72]**F. L. Salzmann,*A note on eigenvalues of nonnegative matrices*, Linear Algebra and Appl.**5**(1972), 329-338. MR**47:8575****[Sou83]**G. W. Soules,*Constructing symmetric nonnegative matrices*, Linear and Multilinear Algebra**13**(1983), no. 3, 241-251. MR**84m:15016****[Sul49]**H. R. Sulemanova,*Stochastic matrices with real characteristic numbers*, Doklady Akad. Nauk SSSR (N.S.)**66**(1949), 343-345. MR**11:4d****[Wuw97]**G. Wuwen,*Eigenvalues of nonnegative matrices*, Linear Algebra Appl.**266**(1997), 261-270. MR**98h:15039**

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