Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

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 ${\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 [Enhancements On Off] (What's this?)

  • [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 $5 \times 5$ 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. Sule{\u{\i}}\kern.15emmanova, 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

Similar Articles

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

American Mathematical Society