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 ${\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.

- 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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0024-3795%2894%2900343-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 https://doi.org/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** - P. G. Ciarlet,
*Some results in the theory of nonnegative matrices*, Linear Algebra Appl.**1**(1968), no. 1, 139–152. MR**223386**, DOI https://doi.org/10.1016/0024-3795%2868%2990054-2 - Miroslav Fiedler,
*Eigenvalues of nonnegative symmetric matrices*, Linear Algebra Appl.**9**(1974), 119–142. MR**364288**, DOI https://doi.org/10.1016/0024-3795%2874%2990031-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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0024-3795%2871%2990015-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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1080/03081087808817226 - Douglas Lind and Brian Marcus,
*An introduction to symbolic dynamics and coding*, Cambridge University Press, Cambridge, 1995. MR**1369092** - 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 https://doi.org/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 https://doi.org/10.1017/S0143385700006052
[Per53]Perfect H. Perfect, - 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 https://doi.org/10.1016/0304-3975%2892%2990043-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 https://doi.org/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 https://doi.org/10.1080/03081088308817523
[Sul49]Suli H. R. Suleĭmanova, - Guo Wuwen,
*Eigenvalues of nonnegative matrices*, Linear Algebra Appl.**266**(1997), 261–270. MR**1473205**, DOI https://doi.org/10.1016/S0024-3795%2896%2900007-9

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

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

*Methods of constructing certain stochastic matrices*, Duke Math. J.

**20**(1953), 395–404.

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

*Stochastic matrices with real characteristic numbers*, Doklady Akad. Nauk SSSR (N.S.)

**66**(1949), 343–345.

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

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

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