Computing the spectral gap of a family of matrices

Guglielmi, Nicola; Protasov, Vladimir

doi:10.1090/mcom/3856

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