×

Efficient algorithms for deciding the type of growth of products of integer matrices. (English) Zbl 1145.65030

For a given set \(\Sigma\) of matrices, the joint spetral radius of \(\Sigma\), denoted \(\rho(\Sigma)\), is defined by the limit \(\rho(\Sigma)=\lim_{t\rightarrow \infty}\max\{\| A_1\cdots A_t\| ^{1/t}: A_t\in\Sigma\}\) independently of any norm. For any finite set \(\Sigma\) of \(n\times n\) matrices with nonnegative integer entries, the authors show that there is a polynomial algorithm that decides between the four cases: \(\rho=0\), \(\rho=1\) and bounded, \(\rho=1\) and polynomial growth, and \(\rho>1\). The polynomial solvability for \(\rho>1\) is somewhat surprising.

MSC:

65F30 Other matrix algorithms (MSC2010)
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors
15B36 Matrices of integers
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bell, J. P., A gap result for the norms of semigroups of matrices, Linear Algebra Appl., 402, 101-110 (2005) · Zbl 1074.15033
[2] Berger, M. A.; Wang, Y., Bounded semigroups of matrices, J. Linear Algebra Appl., 166, 21-27 (1992) · Zbl 0818.15006
[3] Blondel, V. D.; Tsitsiklis, J. N., The boundedness of all products of a pair of matrices is undecidable, Systems Control Lett., 41, 2, 135-140 (2000) · Zbl 0985.93042
[4] Blondel, V. D.; Canterini, V., Undecidable problems for probabilistic automata of fixed dimension, Theory Comput. Syst., 36, 231-245 (2003) · Zbl 1039.68061
[5] Blondel, V. D.; Jungers, R.; Protasov, V., On the complexity of computing the capacity of codes that avoid forbidden difference patterns, IEEE Trans. Inform. Theory, 52, 11, 5122-5127 (2006) · Zbl 1320.94039
[6] Blondel, V. D.; Nesterov, Y., Computationally efficient approximations of the joint spectral radius, SIAM J. Matrix Anal., 27, 1, 256-272 (2005) · Zbl 1089.65031
[7] Blondel, V. D.; Tsitsiklis, J. N., A survey of computational complexity results in systems and control, Automatica, 36, 9, 1249-1274 (2000) · Zbl 0989.93006
[8] Blondel, V. D.; Theys, J.; Vladimirov, A. A., An elementary counterexample to the finiteness conjecture, SIAM J. Matrix Anal., 24, 4, 963-970 (2003) · Zbl 1043.15007
[9] Mc Naughton, R.; Zalcstein, Y., The Burnside problem for semigroups, J. Algebra, 34, 292-299 (1975) · Zbl 0302.20054
[10] Bousch, T.; Mairesse, J., Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture, J. Amer. Math. Soc., 15, 1, 77-111 (2002) · Zbl 1057.49007
[11] Collela, D.; Heil, D., Characterization of scaling functions. I. Continuous solutions, SIAM J. Matrix Analy. Appl., 15, 496-518 (1994)
[12] V. Crespi, G.V. Cybenko, G. Jiang, The Theory of Trackability with Applications to Sensor Networks. Technical Report TR2005-555, Dartmouth College, Computer Science, Hanover, NH, August 2005.; V. Crespi, G.V. Cybenko, G. Jiang, The Theory of Trackability with Applications to Sensor Networks. Technical Report TR2005-555, Dartmouth College, Computer Science, Hanover, NH, August 2005.
[13] Daubechies, I.; Lagarias, J. C., Two-scale difference equations. II. Local regularity, infinite products of matrices and fractals, SIAM J. Math. Anal., 23, 1031-1079 (1992) · Zbl 0788.42013
[14] de Rham, G., Sur les courbes limites de polygones obtenus par trisection, Enseign. Math., II, 5, 29-43 (1959) · Zbl 0092.15101
[15] Dubuc, S., Interpolation through an iterative scheme, J. Math. Anal. Appl., 114, 1, 185-204 (1986) · Zbl 0615.65005
[16] L. Gurvits, Stability of Linear Inclusions - Part 2. NECI Technical Report TR, 1996, pp. 96-173.; L. Gurvits, Stability of Linear Inclusions - Part 2. NECI Technical Report TR, 1996, pp. 96-173.
[17] He, X. G.; Lau, K.-S., Characterization of tile digit sets with prime determinants, Appl. Comput. Harmon. Anal., 16, 3, 159-173 (2004) · Zbl 1065.52014
[18] Jacob, G., Un Algorithme Calculant le Cardinal, Fini ou Infini, des Demi-Groupes de Matrices, Theor. Comput. Sci., 5, 183-204 (1977) · Zbl 0388.15001
[19] Kozyakin, V., Structure of extremal trajectories of discrete linear systems and the finiteness conjecture, Automat. Remote Control, 68, 1, 174-209 (2007) · Zbl 1195.93082
[20] Mandel, A.; Simon, I., On finite semigroups of matrices, Theor. Comput. Sci., 5, 101-111 (1977) · Zbl 0368.20049
[21] Moision, B. E.; Orlitsky, A.; Siegel, P. H., On codes with local joint constraints, Linear Algebra Appl., 422, 442-454 (2007) · Zbl 1180.68207
[22] B.E. Moision, A. Orlitsky, P.H. Siegel. Bounds on the rate of codes which forbid specified difference sequences. in: Proceedings of 1999 IEEE Global Telecommunications Conference (GLOBECOM ’99), December 1999.; B.E. Moision, A. Orlitsky, P.H. Siegel. Bounds on the rate of codes which forbid specified difference sequences. in: Proceedings of 1999 IEEE Global Telecommunications Conference (GLOBECOM ’99), December 1999.
[23] Moision, B. E.; Orlitsky, A.; Siegel, P. H., On codes that avoid specified differences, IEEE Trans. Inform. Theory, 47 (2001) · Zbl 0998.94563
[24] Protasov, V., The joint spectral radius and invariant sets of linear operators, Fundam. Prikl. Mat., 2, 1, 205-231 (1996) · Zbl 0899.47002
[25] Protasov, V., On the asymptotics of the partition function, Sb. Math., 191, 3-4, 381-414 (2000)
[26] Protasov, V., The generalized spectral radius. The geometric approach, Izv. Math., 61, 5, 995-1030 (1997) · Zbl 0893.15002
[27] Protasov, V., Fractal curves and wavelets, Izv. Math., 70, 5, 123-162 (2006) · Zbl 1157.26003
[28] B. Reznick, Some binary partition functions, in: B.C. Berndt, H.G. Diamond, H. Halberstam, A. Hildebrand (Eds.), Analytic Number Theory. Proceedings of a Conference in Honor of Paul T. Bateman, Birkhäuser, Boston, 1990, pp. 451-477 (MR 91k.11092).; B. Reznick, Some binary partition functions, in: B.C. Berndt, H.G. Diamond, H. Halberstam, A. Hildebrand (Eds.), Analytic Number Theory. Proceedings of a Conference in Honor of Paul T. Bateman, Birkhäuser, Boston, 1990, pp. 451-477 (MR 91k.11092). · Zbl 0721.11037
[29] Rioul, O., Simple regularity criteria for subdivision schemes, SIAM J. Math. Anal., 23, 1544-1576 (1999) · Zbl 0761.42016
[30] Tarjan, R., Depth first search and linear graph algorithms, SIAM J. Comput., 1, 2, 146-160 (1972) · Zbl 0251.05107
[31] Tsitsiklis, J. N.; Blondel, V. D., The Lyapunov exponent and joint spectral radius of pairs of matrices are hard – when not impossible – to compute and to approximate, Math. Control Signals Systems, 10, 31-40 (1997) · Zbl 0888.65044
[32] Vinogradov, I. M., Elements of Number Theory (1954), Dover Publications: Dover Publications New York, (Translated by S. Kravetz) · Zbl 0057.28201
[33] Wirth, F., The generalized spectral radius and extremal norms, Linear Algebra Appl., 342, 17-40 (2000) · Zbl 0996.15020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.