Computing the spectral gap of a family of matrices
HTML articles powered by AMS MathViewer
- by Nicola Guglielmi and Vladimir Yu. Protasov;
- Math. Comp. 93 (2024), 259-291
- DOI: https://doi.org/10.1090/mcom/3856
- Published electronically: June 7, 2023
- HTML | PDF | Request permission
Abstract:
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.
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.
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.
References
- N. E. Barabanov, On the Lyapunov exponent of discrete inclusions. I, Avtomat. i Telemekh. 2 (1988), 40–46 (Russian, with English summary); English transl., Automat. Remote Control 49 (1988), no. 2, 152–157. MR 940263
- Vincent D. Blondel, Jacques Theys, and Alexander A. Vladimirov, An elementary counterexample to the finiteness conjecture, SIAM J. Matrix Anal. Appl. 24 (2003), no. 4, 963–970. MR 2003315, DOI 10.1137/S0895479801397846
- Thierry Bousch and Jean Mairesse, Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture, J. Amer. Math. Soc. 15 (2002), no. 1, 77–111. MR 1862798, DOI 10.1090/S0894-0347-01-00378-2
- Marc A. Berger and Yang Wang, Bounded semigroups of matrices, Linear Algebra Appl. 166 (1992), 21–27. MR 1152485, DOI 10.1016/0024-3795(92)90267-E
- Y. Chen, J. Lü, 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–936.
- Yacine Chitour, Guilherme Mazanti, and Mario Sigalotti, On the gap between deterministic and probabilistic joint spectral radii for discrete-time linear systems, Linear Algebra Appl. 613 (2021), 24–45. MR 4192243, DOI 10.1016/j.laa.2020.12.013
- 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–42.
- Xiongping Dai, Yu Huang, and Mingqing Xiao, Periodically switched stability induces exponential stability of discrete-time linear switched systems in the sense of Markovian probabilities, Automatica J. IFAC 47 (2011), no. 7, 1512–1519. MR 2889251, DOI 10.1016/j.automatica.2011.02.034
- Gilles Deslauriers and Serge Dubuc, Symmetric iterative interpolation processes, Constr. Approx. 5 (1989), no. 1, 49–68. Fractal approximation. MR 982724, DOI 10.1007/BF01889598
- Ingrid Daubechies and Jeffrey C. Lagarias, Two-scale difference equations. II. Local regularity, infinite products of matrices and fractals, SIAM J. Math. Anal. 23 (1992), no. 4, 1031–1079. MR 1166574, DOI 10.1137/0523059
- Gustaf Gripenberg, Computing the joint spectral radius, Linear Algebra Appl. 234 (1996), 43–60. MR 1368770, DOI 10.1016/0024-3795(94)00082-4
- Nicola Guglielmi and Vladimir Protasov, Exact computation of joint spectral characteristics of linear operators, Found. Comput. Math. 13 (2013), no. 1, 37–97. MR 3009529, DOI 10.1007/s10208-012-9121-0
- Nicola Guglielmi and Vladimir Yu. Protasov, Invariant polytopes of sets of matrices with application to regularity of wavelets and subdivisions, SIAM J. Matrix Anal. Appl. 37 (2016), no. 1, 18–52. MR 3447127, DOI 10.1137/15M1006945
- N. Guglielmi, F. Wirth, and M. Zennaro, Complex polytope extremality results for families of matrices, SIAM J. Matrix Anal. Appl. 27 (2005), no. 3, 721–743. MR 2208331, DOI 10.1137/040606818
- Nicola Guglielmi and Marino Zennaro, An algorithm for finding extremal polytope norms of matrix families, Linear Algebra Appl. 428 (2008), no. 10, 2265–2282. MR 2405244, DOI 10.1016/j.laa.2007.07.009
- N. Guglielmi and M. Zennaro, Finding extremal complex polytope norms for families of real matrices, SIAM J. Matrix Anal. Appl. 31 (2009), no. 2, 602–620. MR 2530266, DOI 10.1137/080715718
- Nicola Guglielmi and Marino Zennaro, Stability of linear problems: joint spectral radius of sets of matrices, Current challenges in stability issues for numerical differential equations, Lecture Notes in Math., vol. 2082, Springer, Cham, 2014, pp. 265–313. MR 3204994, DOI 10.1007/978-3-319-01300-8_{5}
- Leonid Gurvits, Stability of discrete linear inclusion, Linear Algebra Appl. 231 (1995), 47–85. MR 1361100, DOI 10.1016/0024-3795(95)90006-3
- Raphaël Jungers, The joint spectral radius, Lecture Notes in Control and Information Sciences, vol. 385, Springer-Verlag, Berlin, 2009. Theory and applications. MR 2507938, DOI 10.1007/978-3-540-95980-9
- Raphaël M. Jungers, Vladimir Protasov, and Vincent D. Blondel, Efficient algorithms for deciding the type of growth of products of integer matrices, Linear Algebra Appl. 428 (2008), no. 10, 2296–2311. MR 2405246, DOI 10.1016/j.laa.2007.08.001
- Kevin G. Hare, Ian D. Morris, Nikita Sidorov, and Jacques Theys, An explicit counterexample to the Lagarias-Wang finiteness conjecture, Adv. Math. 226 (2011), no. 6, 4667–4701. MR 2775881, DOI 10.1016/j.aim.2010.12.012
- V. S. Kozyakin, Structure of extremal trajectories of discrete linear systems and the finiteness conjecture, Automat. Remote Control 68 (2007), 174–209.
- V. S. Kozyakin, N. A. Kuznetsov, and P. Yu. Chebotarev, Consensus in asynchronous multiagent systems. II. The joint spectral radius method, Avtomat. i Telemekh. 5 (2019), 3–31 (Russian, with Russian summary); English transl., Autom. Remote Control 80 (2019), no. 5, 791–812. MR 3962445, DOI 10.1134/s0005231019050015
- Jeffrey C. Lagarias and Yang Wang, The finiteness conjecture for the generalized spectral radius of a set of matrices, Linear Algebra Appl. 214 (1995), 17–42. MR 1311628, DOI 10.1016/0024-3795(93)00052-2
- Daniel Liberzon, Switching in systems and control, Systems & Control: Foundations & Applications, Birkhäuser Boston, Inc., Boston, MA, 2003. MR 1987806, DOI 10.1007/978-1-4612-0017-8
- Arnaldo Mandel and Imre Simon, On finite semigroups of matrices, Theoret. Comput. Sci. 5 (1977/78), no. 2, 101–111. MR 473070, DOI 10.1016/0304-3975(77)90001-9
- Thomas Mejstrik, Algorithm 1011: improved invariant polytope algorithm and applications, ACM Trans. Math. Software 46 (2020), no. 3, Art. 29, 26. MR 4161245, DOI 10.1145/3408891
- Claudia Möller and Ulrich Reif, A tree-based approach to joint spectral radius determination, Linear Algebra Appl. 463 (2014), 154–170. MR 3262394, DOI 10.1016/j.laa.2014.08.009
- Robert McNaughton and Yechezkel Zalcstein, The Burnside problem for semigroups, J. Algebra 34 (1975), 292–299. MR 374301, DOI 10.1016/0021-8693(75)90184-2
- I. Ya. Novikov, V. Yu. Protasov, and M. A. Skopina, Wavelet theory, Translations of Mathematical Monographs, vol. 239, American Mathematical Society, Providence, RI, 2011. Translated from the 2005 Russian original by Evgenia Sorokina. MR 2779330, DOI 10.1090/mmono/239
- Matjaž Omladič and Heydar Radjavi, Irreducible semigroups with multiplicative spectral radius, Linear Algebra Appl. 251 (1997), 59–72. MR 1421265, DOI 10.1016/0024-3795(95)00544-7
- Alexey I. Popov, On matrix semigroups bounded above and below, Linear Algebra Appl. 438 (2013), no. 11, 4439–4447. MR 3034542, DOI 10.1016/j.laa.2013.01.034
- V. Yu. Protasov, A generalized joint spectral radius. A geometric approach, Izv. Ross. Akad. Nauk Ser. Mat. 61 (1997), no. 5, 99–136 (Russian, with Russian summary); English transl., Izv. Math. 61 (1997), no. 5, 995–1030. MR 1486700, DOI 10.1070/im1997v061n05ABEH000161
- V. Yu. Protasov, Fractal curves and wavelets, Izv. Ross. Akad. Nauk Ser. Mat. 70 (2006), no. 5, 123–162 (Russian, with Russian summary); English transl., Izv. Math. 70 (2006), no. 5, 975–1013. MR 2269711, DOI 10.1070/IM2006v070n05ABEH002335
- V. Yu. Protasov and A. S. Voynov, Matrix semigroups with constant spectral radius, Linear Algebra Appl. 513 (2017), 376–408. MR 3573807, DOI 10.1016/j.laa.2016.10.013
- Gian-Carlo Rota and Gilbert Strang, A note on the joint spectral radius, Indag. Math. 22 (1960), 379–381. Nederl. Akad. Wetensch. Proc. Ser. A 63. MR 147922, DOI 10.1016/S1385-7258(60)50046-1
- Fabian Wirth, The generalized spectral radius and extremal norms, Linear Algebra Appl. 342 (2002), 17–40. MR 1873424, DOI 10.1016/S0024-3795(01)00446-3
Bibliographic Information
- Nicola Guglielmi
- Affiliation: Gran Sasso Science Institute (GSSI), via Crispi 7, I-67010 L’ Aquila, Italy
- MR Author ID: 603494
- Email: nicola.guglielmi@gssi.it
- Vladimir Yu. Protasov
- Affiliation: DISIM, University of L’Aquila, via Vetoio 1, I-67010 L’Aquila, Italy
- MR Author ID: 607472
- ORCID: 0000-0003-1862-2046
- Email: vladimir.protasov@univaq.it
- Received by editor(s): May 9, 2022
- Received by editor(s) in revised form: March 13, 2023, and March 26, 2023
- Published electronically: June 7, 2023
- Additional Notes: The first author was supported by funds from the Italian MUR (Ministero dell’Università e della RicerSca) within the PRIN 2017 Project “Discontinuous dynamical systems: theory, numerics and applications”. The first author was also supported by the INdAM Research group GNCS (Gruppo Nazionale di Calcolo Scientifico). The second author was supported by the RFBR grant 20-01-00469.
This article is dedicated to Sara - © Copyright 2023 American Mathematical Society
- Journal: Math. Comp. 93 (2024), 259-291
- MSC (2020): Primary 15A60, 15A42; Secondary 93D20, 47D03
- DOI: https://doi.org/10.1090/mcom/3856
- MathSciNet review: 4654622