Maximal exponents of polyhedral cones (III)
HTML articles powered by AMS MathViewer
- by Raphael Loewy, Micha A. Perles and Bit-Shun Tam PDF
- Trans. Amer. Math. Soc. 365 (2013), 3535-3573 Request permission
Abstract:
Let $K$ be a proper (i.e., closed, pointed, full, convex) cone in $\mathbb {R}^n$. An $n\times n$ matrix $A$ is said to be $K$-primitive if $AK\subseteq K$ and there exists a positive integer $k$ such that $A^k(K \setminus \{ 0 \}) \subseteq$ int $K$; the least such $k$ is referred to as the exponent of $A$ and is denoted by $\gamma (A)$. For a polyhedral cone $K$, the maximum value of $\gamma (A)$, taken over all $K$-primitive matrices $A$, is denoted by $\gamma (K)$. It is proved that for any positive integers $m,n, 3 \le n \le m$, the maximum value of $\gamma (K)$, as $K$ runs through all $n$-dimensional polyhedral cones with $m$ extreme rays, equals $(n-1)(m-1)+\frac {1}{2}\left (1+(-1)^{(n-1)m}\right )$. For the $3$-dimensional case, the cones $K$ and the corresponding $K$-primitive matrices $A$ such that $\gamma (K)$ and $\gamma (A)$ attain the maximum value are identified up to respectively linear isomorphism and cone-equivalence modulo positive scalar multiplication.References
- George Phillip Barker, Theory of cones, Linear Algebra Appl. 39 (1981), 263–291. MR 625256, DOI 10.1016/0024-3795(81)90310-4
- R. W. Barnard, W. Dayawansa, K. Pearce, and D. Weinberg, Polynomials with nonnegative coefficients, Proc. Amer. Math. Soc. 113 (1991), no. 1, 77–85. MR 1072329, DOI 10.1090/S0002-9939-1991-1072329-2
- Peter Borwein and Tamás Erdélyi, Polynomials and polynomial inequalities, Graduate Texts in Mathematics, vol. 161, Springer-Verlag, New York, 1995. MR 1367960, DOI 10.1007/978-1-4612-0793-1
- G. R. Belitskiĭ and Yu. I. Lyubich, Matrix norms and their applications, Operator Theory: Advances and Applications, vol. 36, Birkhäuser Verlag, Basel, 1988. Translated from the Russian by A. Iacob. MR 1015711, DOI 10.1007/978-3-0348-7400-7
- 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, DOI 10.1137/1.9781611971262
- Richard A. Brualdi and Herbert J. Ryser, Combinatorial matrix theory, Encyclopedia of Mathematics and its Applications, vol. 39, Cambridge University Press, Cambridge, 1991. MR 1130611, DOI 10.1017/CBO9781107325708
- George Phillip Barker and Bit Shun Tam, Graphs for cone preserving maps, Linear Algebra Appl. 37 (1981), 199–204. MR 636222, DOI 10.1016/0024-3795(81)90180-4
- Ronald Evans and John Greene, Polynomials with nonnegative coefficients whose zeros have modulus one, SIAM J. Math. Anal. 22 (1991), no. 4, 1173–1182. MR 1112073, DOI 10.1137/0522076
- Miroslav Fiedler and Vlastimil Pták, Diagonals of convex sets, Czechoslovak Math. J. 28(103) (1978), no. 1, 25–44 (English, with Russian summary). MR 467532
- David Gale, Neighborly and cyclic polytopes, Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Soc., Providence, R.I., 1963, pp. 225–232. MR 0152944
- V. S. Grinberg, Wielandt-type estimates for primitive mappings of partially ordered sets, Mat. Zametki 45 (1989), no. 6, 30–35, 110 (Russian); English transl., Math. Notes 45 (1989), no. 5-6, 450–454. MR 1019033, DOI 10.1007/BF01158232
- Branko Grünbaum, Convex polytopes, Pure and Applied Mathematics, Vol. 16, Interscience Publishers John Wiley & Sons, Inc., New York, 1967. With the cooperation of Victor Klee, M. A. Perles and G. C. Shephard. MR 0226496
- Peter Gritzmann, Victor Klee, and Bit Shun Tam, Cross-positive matrices revisited, Linear Algebra Appl. 223/224 (1995), 285–305. Special issue honoring Miroslav Fiedler and Vlastimil Pták. MR 1340696, DOI 10.1016/0024-3795(93)00364-6
- Leslie Hogben (ed.), Handbook of linear algebra, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2007. Associate editors: Richard Brualdi, Anne Greenbaum and Roy Mathias. MR 2279160
- Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183, DOI 10.1017/CBO9780511810817
- Robert E. Hartwig and Michael Neumann, Bounds on the exponent of primitivity which depend on the spectrum and the minimal polynomial, Linear Algebra Appl. 184 (1993), 103–122. MR 1209386, DOI 10.1016/0024-3795(93)90373-V
- Steve Kirkland, An eigenvalue region for Leslie matrices, SIAM J. Matrix Anal. Appl. 13 (1992), no. 2, 507–529. MR 1152766, DOI 10.1137/0613033
- Steve Kirkland, On the spectrum of a Leslie matrix with a near-periodic fecundity pattern, Linear Algebra Appl. 178 (1993), 261–279. MR 1197508, DOI 10.1016/0024-3795(93)90345-O
- Steve Kirkland, A note on the eigenvalues of a primitive matrix with large exponent, Linear Algebra Appl. 253 (1997), 103–112. MR 1431168, DOI 10.1016/0024-3795(95)00701-6
- Peter Lancaster and Miron Tismenetsky, The theory of matrices, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1985. MR 792300
- Raphael Loewy and Bit-Shun Tam, Maximal exponents of polyhedral cones. I, J. Math. Anal. Appl. 365 (2010), no. 2, 570–583. MR 2587059, DOI 10.1016/j.jmaa.2009.11.016
- Raphael Loewy and Bit-Shun Tam, Maximal exponents of polyhedral cones. II, Linear Algebra Appl. 432 (2010), no. 11, 2861–2878. MR 2639250, DOI 10.1016/j.laa.2009.12.026
- I. G. Macdonald, Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1979. MR 553598
- Carl Meyer, Matrix analysis and applied linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. With 1 CD-ROM (Windows, Macintosh and UNIX) and a solutions manual (iv+171 pp.). MR 1777382, DOI 10.1137/1.9780898719512
- Jan Mařík and Vlastimil Pták, Norms, spectra and combinatorial properties of matrices, Czechoslovak Math. J. 10(85) (1960), 181–196 (English, with Russian summary). MR 120243
- Stewart W. Neufeld, A diameter bound on the exponent of a primitive directed graph, Linear Algebra Appl. 245 (1996), 27–47. MR 1404168, DOI 10.1016/0024-3795(94)00203-7
- M.A. Perles, Critical Exponents of Convex Bodies, Ph.D. thesis, Hebrew University, August 1964, 169+VIII pages. (Hebrew, with English summary.)
- Vlastimil Pták, Critical exponents, Proc. Colloquium on Convexity (Copenhagen, 1965) Kobenhavns Univ. Mat. Inst., Copenhagen, 1967, pp. 244–248. MR 0217571
- Vlastimil Pták, Critical exponents, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 1237–1257. MR 1243008
- R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683
- Bruce E. Sagan, The symmetric group, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1991. Representations, combinatorial algorithms, and symmetric functions. MR 1093239
- R.F. Scott, Note on a theorem of Prof. Cayley, Messeng. Math. 8 (1879), 155–157.
- Jian Shen, Proof of a conjecture about the exponent of primitive matrices, Linear Algebra Appl. 216 (1995), 185–203. MR 1319984, DOI 10.1016/0024-3795(93)00132-J
- Jian Shen, A bound on the exponent of primitivity in terms of diameter, Linear Algebra Appl. 244 (1996), 21–33. MR 1403273, DOI 10.1016/0024-3795(94)00205-3
- Bit Shun Tam, On the distinguished eigenvalues of a cone-preserving map, Linear Algebra Appl. 131 (1990), 17–37. MR 1057062, DOI 10.1016/0024-3795(90)90372-J
- Bit Shun Tam, On the structure of the cone of positive operators, Linear Algebra Appl. 167 (1992), 65–85. Sixth Haifa Conference on Matrix Theory (Haifa, 1990). MR 1155442, DOI 10.1016/0024-3795(92)90339-C
- Bit-Shun Tam, A cone-theoretic approach to the spectral theory of positive linear operators: the finite-dimensional case, Taiwanese J. Math. 5 (2001), no. 2, 207–277. MR 1832167, DOI 10.11650/twjm/1500407336
- Bit-Shun Tam, The Perron generalized eigenspace and the spectral cone of a cone-preserving map, Linear Algebra Appl. 393 (2004), 375–429. MR 2098599, DOI 10.1016/j.laa.2004.08.020
- B.-S. Tam, On local Perron-Frobenius theory, in preparation.
- Bit Shun Tam and George Phillip Barker, Graphs and irreducible cone preserving maps, Linear and Multilinear Algebra 31 (1992), no. 1-4, 19–25. MR 1199037, DOI 10.1080/03081089208818118
- Bit Shun Tam and Hans Schneider, On the core of a cone-preserving map, Trans. Amer. Math. Soc. 343 (1994), no. 2, 479–524. MR 1242787, DOI 10.1090/S0002-9947-1994-1242787-6
- Bit-Shun Tam and Hans Schneider, On the invariant faces associated with a cone-preserving map, Trans. Amer. Math. Soc. 353 (2001), no. 1, 209–245. MR 1707205, DOI 10.1090/S0002-9947-00-02597-6
- Bit-Shun Tam and Hans Schneider, Linear equations over cones and Collatz-Wielandt numbers, Linear Algebra Appl. 363 (2003), 295–332. Special issue on nonnegative matrices, $M$-matrices and their generalizations (Oberwolfach, 2000). MR 1969074, DOI 10.1016/S0024-3795(01)00565-1
- Leslie Hogben (ed.), Handbook of linear algebra, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2007. Associate editors: Richard Brualdi, Anne Greenbaum and Roy Mathias. MR 2279160
- Bit Shun Tam and Shiow Fang Wu, On the Collatz-Wielandt sets associated with a cone-preserving map, Linear Algebra Appl. 125 (1989), 77–95. MR 1024484, DOI 10.1016/0024-3795(89)90033-5
- Helmut Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z. 52 (1950), 642–648 (German). MR 35265, DOI 10.1007/BF02230720
- Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028, DOI 10.1007/978-1-4613-8431-1
Additional Information
- Raphael Loewy
- Affiliation: Department of Mathematics, Technion - Israel Institute of Technology, Haifa 32000, Israel
- Email: loewy@techunix.technion.ac.il
- Micha A. Perles
- Affiliation: Institute of Mathematics, The Hebrew University of Jerusalem, Givat Ram, Jerusalem 91904, Israel
- Email: perles@math.huji.ac.il
- Bit-Shun Tam
- Affiliation: Department of Mathematics, Tamkang University, Tamsui, Taiwan 251, Republic of China
- Email: bsm01@mail.tku.edu.tw
- Received by editor(s): August 2, 2011
- Published electronically: March 18, 2013
- Additional Notes: The third author (the corresponding author) was supported by the National Science Council of the Republic of China (Grant No. NSC 98–2115–M–032 –007 –MY3)
- © Copyright 2013
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 365 (2013), 3535-3573
- MSC (2010): Primary 15B48, 47A65, 05C50, 52B99
- DOI: https://doi.org/10.1090/S0002-9947-2013-05879-5
- MathSciNet review: 3042594