For a single matrix (operator) it is well-known that the spectral gap is an important quantity, as well as its estimate and computation. Here we consider, for the first time in the literature, the computation of its extension to a finite family of matrices, in other words the difference between the joint spectral radius (in short JSR, which we call here the first Lyapunov exponent) and the second Lyapunov exponent (denoted as SLE). The knowledge of joint spectral characteristics and of the spectral gap of a family of matrices is important in several applications, as in the analysis of the regularity of wavelets, multiplicative matrix semigroups and the convergence speed in consensus algorithms. As far as we know the methods we propose are the first able to compute this quantity to any given accuracy.<\/p>\n\n
For computation of the spectral gap one needs first to compute the JSR. A popular tool that is used to this purpose is the invariant polytope algorithm, which relies on the finiteness property of the family of matrices, when this holds true.<\/p>\n\n
In this paper we show that the SLE may not possess the finiteness property, although it can be efficiently approximated with an arbitrary precision. The corresponding algorithm and two effective estimates are presented. Moreover, we prove that the SLE possesses a weak finiteness property, whenever the leading eigenvalue of the dominant product is real. This allows us to find in certain situations the precise value of the SLE. Numerical results are demonstrated along with applications in the theory of multiplicative matrix semigroups and in the wavelets theory.<\/p>","DOI":"10.1090\/mcom\/3856","type":"journal-article","created":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T13:06:52Z","timestamp":1686143212000},"page":"259-291","source":"Crossref","is-referenced-by-count":1,"title":["Computing the spectral gap of a family of matrices"],"prefix":"10.1090","volume":"93","author":[{"given":"Nicola","family":"Guglielmi","sequence":"first","affiliation":[]},{"given":"Vladimir","family":"Protasov","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2023,6,7]]},"reference":[{"issue":"2","key":"1","first-page":"40","article-title":"On the Lyapunov exponent of discrete inclusions. I","author":"Barabanov, N. E.","year":"1988","journal-title":"Avtomat. i Telemekh.","ISSN":"http:\/\/id.crossref.org\/issn\/0005-2310","issn-type":"print"},{"issue":"4","key":"2","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1137\/S0895479801397846","article-title":"An elementary counterexample to the finiteness conjecture","volume":"24","author":"Blondel, Vincent D.","year":"2003","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"1","key":"3","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1090\/S0894-0347-01-00378-2","article-title":"Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture","volume":"15","author":"Bousch, Thierry","year":"2002","journal-title":"J. Amer. Math. Soc.","ISSN":"http:\/\/id.crossref.org\/issn\/0894-0347","issn-type":"print"},{"key":"4","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0024-3795(92)90267-E","article-title":"Bounded semigroups of matrices","volume":"166","author":"Berger, Marc A.","year":"1992","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"5","doi-asserted-by":"crossref","unstructured":"Y. Chen, J. L\u00fc, H. Dong, and X. Yu, On the Lyapunov exponent of consensus algorithm, Proceedings of the 10th World Congress on Intelligent Control and Automation (2012), 931\u2013936.","DOI":"10.1109\/WCICA.2012.6358012"},{"key":"6","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.laa.2020.12.013","article-title":"On the gap between deterministic and probabilistic joint spectral radii for discrete-time linear systems","volume":"613","author":"Chitour, Yacine","year":"2021","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"7","doi-asserted-by":"crossref","unstructured":"V.Crespi, G.Cybenko, and G.Jiang, The theory of trackability with applications to sensor networks, ACM Tran. Sensor Networks 4 (2008), no. 3, 1\u201342.","DOI":"10.1145\/1362542.1362547"},{"issue":"7","key":"8","doi-asserted-by":"publisher","first-page":"1512","DOI":"10.1016\/j.automatica.2011.02.034","article-title":"Periodically switched stability induces exponential stability of discrete-time linear switched systems in the sense of Markovian probabilities","volume":"47","author":"Dai, Xiongping","year":"2011","journal-title":"Automatica J. IFAC","ISSN":"http:\/\/id.crossref.org\/issn\/0005-1098","issn-type":"print"},{"issue":"1","key":"9","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF01889598","article-title":"Symmetric iterative interpolation processes","volume":"5","author":"Deslauriers, Gilles","year":"1989","journal-title":"Constr. Approx.","ISSN":"http:\/\/id.crossref.org\/issn\/0176-4276","issn-type":"print"},{"issue":"4","key":"10","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.1137\/0523059","article-title":"Two-scale difference equations. II. Local regularity, infinite products of matrices and fractals","volume":"23","author":"Daubechies, Ingrid","year":"1992","journal-title":"SIAM J. Math. Anal.","ISSN":"http:\/\/id.crossref.org\/issn\/0036-1410","issn-type":"print"},{"key":"11","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0024-3795(94)00082-4","article-title":"Computing the joint spectral radius","volume":"234","author":"Gripenberg, Gustaf","year":"1996","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"1","key":"12","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s10208-012-9121-0","article-title":"Exact computation of joint spectral characteristics of linear operators","volume":"13","author":"Guglielmi, Nicola","year":"2013","journal-title":"Found. Comput. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"issue":"1","key":"13","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1137\/15M1006945","article-title":"Invariant polytopes of sets of matrices with application to regularity of wavelets and subdivisions","volume":"37","author":"Guglielmi, Nicola","year":"2016","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"3","key":"14","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/040606818","article-title":"Complex polytope extremality results for families of matrices","volume":"27","author":"Guglielmi, N.","year":"2005","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"issue":"10","key":"15","doi-asserted-by":"publisher","first-page":"2265","DOI":"10.1016\/j.laa.2007.07.009","article-title":"An algorithm for finding extremal polytope norms of matrix families","volume":"428","author":"Guglielmi, Nicola","year":"2008","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"2","key":"16","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1137\/080715718","article-title":"Finding extremal complex polytope norms for families of real matrices","volume":"31","author":"Guglielmi, N.","year":"2009","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"17","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/978-3-319-01300-8_5","article-title":"Stability of linear problems: joint spectral radius of sets of matrices","author":"Guglielmi, Nicola","year":"2014"},{"key":"18","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0024-3795(95)90006-3","article-title":"Stability of discrete linear inclusion","volume":"231","author":"Gurvits, Leonid","year":"1995","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"19","series-title":"Lecture Notes in Control and Information Sciences","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95980-9","volume-title":"The joint spectral radius","volume":"385","author":"Jungers, Rapha\u00ebl","year":"2009","ISBN":"http:\/\/id.crossref.org\/isbn\/9783540959793"},{"issue":"10","key":"20","doi-asserted-by":"publisher","first-page":"2296","DOI":"10.1016\/j.laa.2007.08.001","article-title":"Efficient algorithms for deciding the type of growth of products of integer matrices","volume":"428","author":"Jungers, Rapha\u00ebl M.","year":"2008","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"6","key":"21","doi-asserted-by":"publisher","first-page":"4667","DOI":"10.1016\/j.aim.2010.12.012","article-title":"An explicit counterexample to the Lagarias-Wang finiteness conjecture","volume":"226","author":"Hare, Kevin G.","year":"2011","journal-title":"Adv. Math.","ISSN":"http:\/\/id.crossref.org\/issn\/0001-8708","issn-type":"print"},{"key":"22","doi-asserted-by":"crossref","unstructured":"V.S. Kozyakin, Structure of extremal trajectories of discrete linear systems and the finiteness conjecture, Automat. Remote Control 68 (2007), 174\u2013209.","DOI":"10.1134\/S0005117906040171"},{"issue":"5","key":"23","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1134\/s0005231019050015","article-title":"Consensus in asynchronous multiagent systems. II. The joint spectral radius method","author":"Kozyakin, V. S.","year":"2019","journal-title":"Avtomat. i Telemekh.","ISSN":"http:\/\/id.crossref.org\/issn\/0005-2310","issn-type":"print"},{"key":"24","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0024-3795(93)00052-2","article-title":"The finiteness conjecture for the generalized spectral radius of a set of matrices","volume":"214","author":"Lagarias, Jeffrey C.","year":"1995","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"25","series-title":"Systems \\& Control: Foundations \\& Applications","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0017-8","volume-title":"Switching in systems and control","author":"Liberzon, Daniel","year":"2003","ISBN":"http:\/\/id.crossref.org\/isbn\/0817642978"},{"issue":"2","key":"26","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0304-3975(77)90001-9","article-title":"On finite semigroups of matrices","volume":"5","author":"Mandel, Arnaldo","year":"1977","journal-title":"Theoret. Comput. Sci.","ISSN":"http:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"issue":"3","key":"27","doi-asserted-by":"publisher","first-page":"Art. 29, 26","DOI":"10.1145\/3408891","article-title":"Algorithm 1011: improved invariant polytope algorithm and applications","volume":"46","author":"Mejstrik, Thomas","year":"2020","journal-title":"ACM Trans. Math. Software","ISSN":"http:\/\/id.crossref.org\/issn\/0098-3500","issn-type":"print"},{"key":"28","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.laa.2014.08.009","article-title":"A tree-based approach to joint spectral radius determination","volume":"463","author":"M\u00f6ller, Claudia","year":"2014","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"29","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1016\/0021-8693(75)90184-2","article-title":"The Burnside problem for semigroups","volume":"34","author":"McNaughton, Robert","year":"1975","journal-title":"J. Algebra","ISSN":"http:\/\/id.crossref.org\/issn\/0021-8693","issn-type":"print"},{"key":"30","series-title":"Translations of Mathematical Monographs","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1090\/mmono\/239","volume-title":"Wavelet theory","volume":"239","author":"Novikov, I. Ya.","year":"2011","ISBN":"http:\/\/id.crossref.org\/isbn\/9780821849842"},{"key":"31","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0024-3795(95)00544-7","article-title":"Irreducible semigroups with multiplicative spectral radius","volume":"251","author":"Omladi\u010d, Matja\u017e","year":"1997","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"11","key":"32","doi-asserted-by":"publisher","first-page":"4439","DOI":"10.1016\/j.laa.2013.01.034","article-title":"On matrix semigroups bounded above and below","volume":"438","author":"Popov, Alexey I.","year":"2013","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"5","key":"33","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1070\/im1997v061n05ABEH000161","article-title":"A generalized joint spectral radius. A geometric approach","volume":"61","author":"Protasov, V. Yu.","year":"1997","journal-title":"Izv. Ross. Akad. Nauk Ser. Mat.","ISSN":"http:\/\/id.crossref.org\/issn\/1607-0046","issn-type":"print"},{"issue":"5","key":"34","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1070\/IM2006v070n05ABEH002335","article-title":"Fractal curves and wavelets","volume":"70","author":"Protasov, V. Yu.","year":"2006","journal-title":"Izv. Ross. Akad. Nauk Ser. Mat.","ISSN":"http:\/\/id.crossref.org\/issn\/1607-0046","issn-type":"print"},{"key":"35","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1016\/j.laa.2016.10.013","article-title":"Matrix semigroups with constant spectral radius","volume":"513","author":"Protasov, V. Yu.","year":"2017","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"36","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/S1385-7258(60)50046-1","article-title":"A note on the joint spectral radius","volume":"22","author":"Rota, Gian-Carlo","year":"1960","journal-title":"Indag. Math."},{"key":"37","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0024-3795(01)00446-3","article-title":"The generalized spectral radius and extremal norms","volume":"342","author":"Wirth, Fabian","year":"2002","journal-title":"Linear Algebra Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2024-93-345\/S0025-5718-2023-03856-X\/mcom3856_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/www.ams.org\/mcom\/2024-93-345\/S0025-5718-2023-03856-X\/S0025-5718-2023-03856-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T18:42:04Z","timestamp":1697222524000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2024-93-345\/S0025-5718-2023-03856-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,7]]},"references-count":37,"journal-issue":{"issue":"345","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["S0025-5718-2023-03856-X"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3856","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["0025-5718","1088-6842"],"issn-type":[{"value":"0025-5718","type":"print"},{"value":"1088-6842","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,7]]}}}