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), 773806
MSC (1991):
Primary 15A18; Secondary 15A36, 58F03, 58F20
Published electronically:
June 21, 2000
MathSciNet review:
1775737
Fulltext 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
onedimensional 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
(82j:58097)
 [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
(92d:58057), http://dx.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
(93e:58050), http://dx.doi.org/10.1090/S00029947199311022194
 [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
(96e:15009), http://dx.doi.org/10.1016/00243795(94)00343C
 [Boy93]
Mike
Boyle, Symbolic dynamics and matrices, Combinatorial and
graphtheoretical problems in linear algebra (Minneapolis, MN, 1991) IMA
Vol. Math. Appl., vol. 50, Springer, New York, 1993,
pp. 1–38. MR 1240955
(94g:58062), http://dx.doi.org/10.1007/9781461383543_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
(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 0223386
(36 #6434)
 [Fie74]
Miroslav
Fiedler, Eigenvalues of nonnegative symmetric matrices, Linear
Algebra and Appl. 9 (1974), 119–142. MR 0364288
(51 #543)
 [Fri78]
Shmuel
Friedland, On an inverse problem for nonnegative and eventually
nonnegative matrices, Israel J. Math. 29 (1978),
no. 1, 43–60. MR 492634
(80h:15010), http://dx.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
(97b:15009), http://dx.doi.org/10.1090/S0002993996035873
 [Joh81]
Charles
R. Johnson, Row stochastic matrices similar to doubly stochastic
matrices, Linear and Multilinear Algebra 10 (1981),
no. 2, 113–130. MR 618581
(82g:15016), http://dx.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
(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 1464576
(98i:54021), http://dx.doi.org/10.1090/S1079676297000243
 [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
(86c:58092), http://dx.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 (58 #722)
 [LM95]
Douglas
Lind and Brian
Marcus, An introduction to symbolic dynamics and coding,
Cambridge University Press, Cambridge, 1995. MR 1369092
(97a:58050)
 [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 (electronic). MR 1637415
(99f:15031)
 [LM99]
T. J. Laffey and E. Meehan, A characterization of trace zero nonnegative matrices, Linear Algebra Appl. 302303 (1999), 295302. CMP 2000:07
 [Min88]
Henryk
Minc, Nonnegative matrices, WileyInterscience Series in
Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New
York, 1988. A WileyInterscience Publication. MR 932967
(89i:15001)
 [MT91]
Brian
Marcus and Selim
Tuncel, The weightpersymbol polytope and scaffolds of invariants
associated with Markov chains, Ergodic Theory Dynam. Systems
11 (1991), no. 1, 129–180. MR 1101088
(92g:28038), http://dx.doi.org/10.1017/S0143385700006052
 [Per53]
Hazel
Perfect, Methods of constructing certain stochastic matrices,
Duke Math. J. 20 (1953), 395–404. MR 0055969
(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
(93f:15018), http://dx.doi.org/10.1016/03043975(92)90043F
 [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
(99c:15031), http://dx.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
(47 #8575)
 [Sou83]
George
W. Soules, Constructing symmetric nonnegative matrices, Linear
and Multilinear Algebra 13 (1983), no. 3,
241–251. MR
700887 (84m:15016), http://dx.doi.org/10.1080/03081088308817523
 [Sul49]
H.
R. Suleĭmanova, Stochastic matrices with real characteristic
numbers, Doklady Akad. Nauk SSSR (N.S.) 66 (1949),
343–345 (Russian). MR 0030496
(11,4d)
 [Wuw97]
Guo
Wuwen, Eigenvalues of nonnegative matrices, Linear Algebra
Appl. 266 (1997), 261–270. MR 1473205
(98h:15039), http://dx.doi.org/10.1016/S00243795(96)000079
 [BGMY80]
 L. Block, J. Guckenheimer, M. Misiurewicz, and L. S. Young, Periodic points and topological entropy of onedimensional maps, Global theory of dynamical systems (Proc. Internat. Conf., Northwestern Univ., Evanston, Ill., 1979), Lecture Notes in Math., vol. 819, Springer, Berlin, 1980, pp. 1834. 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, 249316. MR 92d:58057
 [BH93]
 M. Boyle and D. Handelman, Algebraic shift equivalence and primitive matrices, Trans. Amer. Math. Soc. 336 (1993), no. 1, 121149. MR 93e:58050
 [Bor95]
 A. Borobia, On the nonnegative eigenvalue problem, Linear Algebra Appl. 223/224 (1995), 131140, Special issue honoring Miroslav Fiedler and Vlastimil Pták. MR 96e:15009
 [Boy93]
 M. Boyle, Symbolic dynamics and matrices, Combinatorial and graphtheoretical problems in linear algebra (Minneapolis, MN, 1991), IMA Vol. Math. Appl., vol. 50, Springer, New York, 1993, pp. 138. 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, 139152. MR 36:6434
 [Fie74]
 M. Fiedler, Eigenvalues of nonnegative symmetric matrices, Linear Algebra and Appl. 9 (1974), 119142. MR 51:543
 [Fri78]
 S. Friedland, On an inverse problem for nonnegative and eventually nonnegative matrices, Israel J. Math. 29 (1978), no. 1, 4360. 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, 36473651. MR 97b:15009
 [Joh81]
 C. R. Johnson, Row stochastic matrices similar to doubly stochastic matrices, Linear and Multilinear Algebra 10 (1981), no. 2, 113130. MR 82g:15016
 [Kel71]
 R. B. Kellogg, Matrices similar to a positive or essentially positive matrix, Linear Algebra and Appl. 4 (1971), 191204. 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), 5562 (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, 283300. 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, 8390. 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), 119128 (electronic). MR 99f:15031
 [LM99]
 T. J. Laffey and E. Meehan, A characterization of trace zero nonnegative matrices, Linear Algebra Appl. 302303 (1999), 295302. CMP 2000:07
 [Min88]
 H. Minc, Nonnegative matrices, WileyInterscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1988, A WileyInterscience Publication. MR 89i:15001
 [MT91]
 B. Marcus and S. Tuncel, The weightpersymbol polytope and scaffolds of invariants associated with Markov chains, Ergodic Theory Dynamical Systems 11 (1991), no. 1, 129180. MR 92g:28038
 [Per53]
 H. Perfect, Methods of constructing certain stochastic matrices, Duke Math. J. 20 (1953), 395404. MR 15:3h
 [Per92]
 D. Perrin, On positive matrices, Theoret. Comput. Sci. 94 (1992), no. 2, 357366, 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, 367375. MR 99c:15031
 [Sal72]
 F. L. Salzmann, A note on eigenvalues of nonnegative matrices, Linear Algebra and Appl. 5 (1972), 329338. MR 47:8575
 [Sou83]
 G. W. Soules, Constructing symmetric nonnegative matrices, Linear and Multilinear Algebra 13 (1983), no. 3, 241251. MR 84m:15016
 [Sul49]
 H. R. Sulemanova, Stochastic matrices with real characteristic numbers, Doklady Akad. Nauk SSSR (N.S.) 66 (1949), 343345. MR 11:4d
 [Wuw97]
 G. Wuwen, Eigenvalues of nonnegative matrices, Linear Algebra Appl. 266 (1997), 261270. 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 361010271 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 062693009
Email:
ormes@math.utexas.edu
Fred W. Roush
Affiliation:
Mathematics Research Group, Alabama State University, Montgomery, Alabama 361010271
Email:
froush@gmail.alasu.edu
DOI:
http://dx.doi.org/10.1090/S0894034700003428
PII:
S 08940347(00)003428
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
