January  2011, 18: 22-30. doi: 10.3934/era.2011.18.22

Realization of joint spectral radius via Ergodic theory

1. 

Department of Mathematics, Nanjing University, Nanjing, 210093

2. 

Department of Mathematics, Zhongshan University, Guangzhou 510275

3. 

Department of Mathematics, Southern Illinois University, Carbondale, IL 62901

Received  August 2010 Revised  March 2011 Published  June 2011

Based on the classic multiplicative ergodic theorem and the semi-uniform subadditive ergodic theorem, we show that there always exists at least one ergodic Borel probability measure such that the joint spectral radius of a finite set of square matrices of the same size can be realized almost everywhere with respect to this Borel probability measure. The existence of at least one ergodic Borel probability measure, in the context of the joint spectral radius problem, is obtained in a general setting.
Citation: Xiongping Dai, Yu Huang, Mingqing Xiao. Realization of joint spectral radius via Ergodic theory. Electronic Research Announcements, 2011, 18: 22-30. doi: 10.3934/era.2011.18.22
References:
[1]

L. Arnold, "Random Dynamical Systems,", Springer Monographs in Math., (1998). Google Scholar

[2]

N. Barabanov, Lyapunov indicators of discrete inclusions I-III,, Autom. Remote Control, 49 (1988), 152. Google Scholar

[3]

J. P. Bell, A gap result for the norms of semigroups of matrices,, Linear Algebra Appl., 402 (2005), 101. doi: 10.1016/j.laa.2004.12.007. Google Scholar

[4]

M. A. Berger and Y. Wang, Bounded semigroups of matrices,, Linear Algebra Appl., 166 (1992), 21. doi: 10.1016/0024-3795(92)90267-E. Google Scholar

[5]

V. D. Blondel, J. Theys and A. A. Vladimirov, An elementary counterexample to the finiteness conjecture,, SIAM J. Matrix Anal. Appl., 24 (2003), 963. doi: 10.1137/S0895479801397846. Google Scholar

[6]

V. D. Blondel and Y. Nesterov, Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices,, SIAM J. Matrix Anal. Appl., 31 (2009), 865. doi: 10.1137/080723764. Google Scholar

[7]

V. D. Blondel, R. Jungers and V. Protasov, On the complexity of computing the capacity of codes that avoid forbidden difference patterns,, IEEE Trans. Inform. Theory, 52 (2006), 5122. doi: 10.1109/TIT.2006.883615. Google Scholar

[8]

V. D. Blondel and J. N. Tsitsiklis, The boundedness of all products of a pair of matrices is undecidable,, Systems Control Lett., 41 (2000), 135. doi: 10.1016/S0167-6911(00)00049-9. Google Scholar

[9]

J. Bochi, Inequalities for numerical invariants of sets of matrices,, Linear Algebra Appl., 368 (2003), 71. doi: 10.1016/S0024-3795(02)00658-4. Google Scholar

[10]

T. Bousch and J. Mairesse, Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture,, J. Amer. Math. Soc., 15 (2002), 77. doi: 10.1090/S0894-0347-01-00378-2. Google Scholar

[11]

D. Colella and C. Heil, The characterization of continuous, four-coefficient scaling functions and wavelets,, IEEE Trans. Inform. Theory, 38 (1992), 876. doi: 10.1109/18.119744. Google Scholar

[12]

X. Dai, Extremal and Barabanov semi-norms of a semigroup generated by a bounded family of matrices,, J. Math. Anal. Appl., 379 (2011), 827. doi: 10.1016/j.jmaa.2010.12.059. Google Scholar

[13]

X. Dai, Weakly Birkhoff recurrent switching signals, almost sure and partial stability of linear switched dynamical systems,, J. Differential Equations, 250 (2011), 3584. doi: 10.1016/j.jde.2011.01.029. Google Scholar

[14]

X. Dai, Optimal state points of the subadditive ergodic theorem,, Nonlinearity, 24 (2011), 1565. doi: 10.1088/0951-7715/24/5/009. Google Scholar

[15]

X. Dai, Y. Huang and M. Xiao, Almost sure stability of discrete-time switched linear systems: A topological point of view,, SIAM J. Control Optim., 47 (2008), 2137. doi: 10.1137/070699676. Google Scholar

[16]

X. Dai, Y. Huang, and M. Xiao, Periodically switched stability induces exponential stability of discrete-time linear switched systems in the sense of Markovian probabilities,, Automatica, 47 (2011), 1512. doi: doi: 10.1016/j.automatica.2011.02.034. Google Scholar

[17]

I. Daubechies and J. C. Lagarias, Two scale difference equations. I. Existence and global regularity of solutions,, SIAM J. Math. Anal., 22 (1991), 1388. doi: 10.1137/0522089. Google Scholar

[18]

I. Daubechies and J. C. Lagarias, Two scale difference equations. II. Local regularity, infinite products of matrices and fractals,, SIAM J. Math. Anal., 23 (1992), 1031. doi: 10.1137/0523059. Google Scholar

[19]

I. Daubechies and J. C. Lagarias, Sets of matrices all infinite products of which converge,, Linear Algebra Appl., 161 (1992), 227. doi: 10.1016/0024-3795(92)90012-Y. Google Scholar

[20]

I. Daubechies and J. C. Lagarias, Sets of matrices all infinite products of which converge,, Linear Algebra Appl., 161 (1992), 227. Google Scholar

[21]

L. Elsner, The generalized spectral-radius theorem: An analytic-geometric proof,, Linear Algebra Appl., 220 (1995), 151. doi: 10.1016/0024-3795(93)00320-Y. Google Scholar

[22]

L. Gurvits and A. Olshevsky, On the NP-hardness of checking matrix polytope stability and continuous-time switching stability,, IEEE Trans. Automat. Control, 54 (2009), 337. doi: 10.1109/TAC.2008.2007177. Google Scholar

[23]

K. G. Hare, I. D. Morris, N. Sidorov and J. Theys, An explicit counterexample to the Lagarias-Wang finiteness conjecture,, Adv. Math., 226 (2011), 4667. doi: 10.1016/j.aim.2010.12.012. Google Scholar

[24]

C. Heil and G. Strang, Continuity of the joint spectral radius: Applications to wavelets,, in, 69 (1995), 51. Google Scholar

[25]

L. Gurvits, Stability of discrete linear inclusions,, Linear Algebra Appl., 231 (1995), 47. doi: 10.1016/0024-3795(95)90006-3. Google Scholar

[26]

H. Furstenberg and H. Kesten, Products of random matrices,, Ann. Math. Statist., 31 (1960), 457. doi: 10.1214/aoms/1177705909. Google Scholar

[27]

R. Jungers, V. Protasov and V. Blondel, Efficient algorithms for deciding the type of growth of products of integer matrices,, Linear Algebra Appl., 428 (2008), 2296. doi: 10.1016/j.laa.2007.08.001. Google Scholar

[28]

V. S. Kozyakin, Structure of extremal trajectories of discrete linear systems and the finiteness conjecture,, Autom. Remote Control, 68 (2007), 174. doi: 10.1134/S0005117906040171. Google Scholar

[29]

J. C. Lagarias and Y. Wang, The finiteness conjecture for the generalized spectral radius of a set of matrices,, Linear Algebra Appl., 214 (1995), 17. doi: 10.1016/0024-3795(93)00052-2. Google Scholar

[30]

B. E. Moision, A. Orlitsky and P. H. Siegel, On codes that avoid specified differences,, IEEE Trans. Inform. Theory, 47 (2001), 433. doi: 10.1109/18.904557. Google Scholar

[31]

V. V. Nemytskii and V. V. Stepanov, "Qualitative Theory of Differential Equations,", Princeton University Press, (1960). Google Scholar

[32]

V. I. Oseledec, A multiplicative ergodic theorem. Characteristic Lyapunov, exponents of dynamical systems,, Trudy Mosk Mat. Obšč., 19 (1968), 179. Google Scholar

[33]

E. Plischke and F. Wirth, Duality results for the joint spectral radius and transient behavior,, Linear Algebra Appl., 428 (2008), 2368. doi: 10.1016/j.laa.2007.12.009. Google Scholar

[34]

E. S. Pyatnitskiĭ and L. B. Rapoport, Periodic motion and tests for absolute stability of nonlinear time-dependent systems,, Automat. Remote Control, 52 (1991), 1379. Google Scholar

[35]

G.-C. Rota and G. Strang, A note on the joint spectral radius,, Indag. Math., 22 (1960), 379. Google Scholar

[36]

S. J. Schreiber, On growth rates of subadditive functions for semi-flows,, J. Differential Equations, 148 (1998), 334. doi: 10.1006/jdeq.1998.3471. Google Scholar

[37]

M.-H. Shih, J.-W. Wu and C.-T. Pang, Asymptotic stability and generalized Gelfand spectral radius formula,, Linear Algebra Appl., 252 (1997), 61. doi: 10.1016/0024-3795(95)00592-7. Google Scholar

[38]

R. Shorten, F. Wirth, O. Mason, K. Wulff and C. King, Stability criteria for switched and hybrid systems,, SIAM Rev., 49 (2007), 545. doi: 10.1137/05063516X. Google Scholar

[39]

R. Sturman and J. Stark, Semi-uniform ergodic theorems and applications to forced systems,, Nonlinearity, 13 (2000), 113. doi: 10.1088/0951-7715/13/1/306. Google Scholar

[40]

J. Theys, "Joint Spectral Radius: Theory and Approximations,", Ph.D thesis, (2005). Google Scholar

[41]

J. N. Tsitsiklis and V. D. Blondel, 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 (1997), 31. doi: 10.1007/BF01219774. Google Scholar

[42]

P. Walters, "An Introduction to Ergodic Theory,", G.T.M., 79 (1982). Google Scholar

show all references

References:
[1]

L. Arnold, "Random Dynamical Systems,", Springer Monographs in Math., (1998). Google Scholar

[2]

N. Barabanov, Lyapunov indicators of discrete inclusions I-III,, Autom. Remote Control, 49 (1988), 152. Google Scholar

[3]

J. P. Bell, A gap result for the norms of semigroups of matrices,, Linear Algebra Appl., 402 (2005), 101. doi: 10.1016/j.laa.2004.12.007. Google Scholar

[4]

M. A. Berger and Y. Wang, Bounded semigroups of matrices,, Linear Algebra Appl., 166 (1992), 21. doi: 10.1016/0024-3795(92)90267-E. Google Scholar

[5]

V. D. Blondel, J. Theys and A. A. Vladimirov, An elementary counterexample to the finiteness conjecture,, SIAM J. Matrix Anal. Appl., 24 (2003), 963. doi: 10.1137/S0895479801397846. Google Scholar

[6]

V. D. Blondel and Y. Nesterov, Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices,, SIAM J. Matrix Anal. Appl., 31 (2009), 865. doi: 10.1137/080723764. Google Scholar

[7]

V. D. Blondel, R. Jungers and V. Protasov, On the complexity of computing the capacity of codes that avoid forbidden difference patterns,, IEEE Trans. Inform. Theory, 52 (2006), 5122. doi: 10.1109/TIT.2006.883615. Google Scholar

[8]

V. D. Blondel and J. N. Tsitsiklis, The boundedness of all products of a pair of matrices is undecidable,, Systems Control Lett., 41 (2000), 135. doi: 10.1016/S0167-6911(00)00049-9. Google Scholar

[9]

J. Bochi, Inequalities for numerical invariants of sets of matrices,, Linear Algebra Appl., 368 (2003), 71. doi: 10.1016/S0024-3795(02)00658-4. Google Scholar

[10]

T. Bousch and J. Mairesse, Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture,, J. Amer. Math. Soc., 15 (2002), 77. doi: 10.1090/S0894-0347-01-00378-2. Google Scholar

[11]

D. Colella and C. Heil, The characterization of continuous, four-coefficient scaling functions and wavelets,, IEEE Trans. Inform. Theory, 38 (1992), 876. doi: 10.1109/18.119744. Google Scholar

[12]

X. Dai, Extremal and Barabanov semi-norms of a semigroup generated by a bounded family of matrices,, J. Math. Anal. Appl., 379 (2011), 827. doi: 10.1016/j.jmaa.2010.12.059. Google Scholar

[13]

X. Dai, Weakly Birkhoff recurrent switching signals, almost sure and partial stability of linear switched dynamical systems,, J. Differential Equations, 250 (2011), 3584. doi: 10.1016/j.jde.2011.01.029. Google Scholar

[14]

X. Dai, Optimal state points of the subadditive ergodic theorem,, Nonlinearity, 24 (2011), 1565. doi: 10.1088/0951-7715/24/5/009. Google Scholar

[15]

X. Dai, Y. Huang and M. Xiao, Almost sure stability of discrete-time switched linear systems: A topological point of view,, SIAM J. Control Optim., 47 (2008), 2137. doi: 10.1137/070699676. Google Scholar

[16]

X. Dai, Y. Huang, and M. Xiao, Periodically switched stability induces exponential stability of discrete-time linear switched systems in the sense of Markovian probabilities,, Automatica, 47 (2011), 1512. doi: doi: 10.1016/j.automatica.2011.02.034. Google Scholar

[17]

I. Daubechies and J. C. Lagarias, Two scale difference equations. I. Existence and global regularity of solutions,, SIAM J. Math. Anal., 22 (1991), 1388. doi: 10.1137/0522089. Google Scholar

[18]

I. Daubechies and J. C. Lagarias, Two scale difference equations. II. Local regularity, infinite products of matrices and fractals,, SIAM J. Math. Anal., 23 (1992), 1031. doi: 10.1137/0523059. Google Scholar

[19]

I. Daubechies and J. C. Lagarias, Sets of matrices all infinite products of which converge,, Linear Algebra Appl., 161 (1992), 227. doi: 10.1016/0024-3795(92)90012-Y. Google Scholar

[20]

I. Daubechies and J. C. Lagarias, Sets of matrices all infinite products of which converge,, Linear Algebra Appl., 161 (1992), 227. Google Scholar

[21]

L. Elsner, The generalized spectral-radius theorem: An analytic-geometric proof,, Linear Algebra Appl., 220 (1995), 151. doi: 10.1016/0024-3795(93)00320-Y. Google Scholar

[22]

L. Gurvits and A. Olshevsky, On the NP-hardness of checking matrix polytope stability and continuous-time switching stability,, IEEE Trans. Automat. Control, 54 (2009), 337. doi: 10.1109/TAC.2008.2007177. Google Scholar

[23]

K. G. Hare, I. D. Morris, N. Sidorov and J. Theys, An explicit counterexample to the Lagarias-Wang finiteness conjecture,, Adv. Math., 226 (2011), 4667. doi: 10.1016/j.aim.2010.12.012. Google Scholar

[24]

C. Heil and G. Strang, Continuity of the joint spectral radius: Applications to wavelets,, in, 69 (1995), 51. Google Scholar

[25]

L. Gurvits, Stability of discrete linear inclusions,, Linear Algebra Appl., 231 (1995), 47. doi: 10.1016/0024-3795(95)90006-3. Google Scholar

[26]

H. Furstenberg and H. Kesten, Products of random matrices,, Ann. Math. Statist., 31 (1960), 457. doi: 10.1214/aoms/1177705909. Google Scholar

[27]

R. Jungers, V. Protasov and V. Blondel, Efficient algorithms for deciding the type of growth of products of integer matrices,, Linear Algebra Appl., 428 (2008), 2296. doi: 10.1016/j.laa.2007.08.001. Google Scholar

[28]

V. S. Kozyakin, Structure of extremal trajectories of discrete linear systems and the finiteness conjecture,, Autom. Remote Control, 68 (2007), 174. doi: 10.1134/S0005117906040171. Google Scholar

[29]

J. C. Lagarias and Y. Wang, The finiteness conjecture for the generalized spectral radius of a set of matrices,, Linear Algebra Appl., 214 (1995), 17. doi: 10.1016/0024-3795(93)00052-2. Google Scholar

[30]

B. E. Moision, A. Orlitsky and P. H. Siegel, On codes that avoid specified differences,, IEEE Trans. Inform. Theory, 47 (2001), 433. doi: 10.1109/18.904557. Google Scholar

[31]

V. V. Nemytskii and V. V. Stepanov, "Qualitative Theory of Differential Equations,", Princeton University Press, (1960). Google Scholar

[32]

V. I. Oseledec, A multiplicative ergodic theorem. Characteristic Lyapunov, exponents of dynamical systems,, Trudy Mosk Mat. Obšč., 19 (1968), 179. Google Scholar

[33]

E. Plischke and F. Wirth, Duality results for the joint spectral radius and transient behavior,, Linear Algebra Appl., 428 (2008), 2368. doi: 10.1016/j.laa.2007.12.009. Google Scholar

[34]

E. S. Pyatnitskiĭ and L. B. Rapoport, Periodic motion and tests for absolute stability of nonlinear time-dependent systems,, Automat. Remote Control, 52 (1991), 1379. Google Scholar

[35]

G.-C. Rota and G. Strang, A note on the joint spectral radius,, Indag. Math., 22 (1960), 379. Google Scholar

[36]

S. J. Schreiber, On growth rates of subadditive functions for semi-flows,, J. Differential Equations, 148 (1998), 334. doi: 10.1006/jdeq.1998.3471. Google Scholar

[37]

M.-H. Shih, J.-W. Wu and C.-T. Pang, Asymptotic stability and generalized Gelfand spectral radius formula,, Linear Algebra Appl., 252 (1997), 61. doi: 10.1016/0024-3795(95)00592-7. Google Scholar

[38]

R. Shorten, F. Wirth, O. Mason, K. Wulff and C. King, Stability criteria for switched and hybrid systems,, SIAM Rev., 49 (2007), 545. doi: 10.1137/05063516X. Google Scholar

[39]

R. Sturman and J. Stark, Semi-uniform ergodic theorems and applications to forced systems,, Nonlinearity, 13 (2000), 113. doi: 10.1088/0951-7715/13/1/306. Google Scholar

[40]

J. Theys, "Joint Spectral Radius: Theory and Approximations,", Ph.D thesis, (2005). Google Scholar

[41]

J. N. Tsitsiklis and V. D. Blondel, 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 (1997), 31. doi: 10.1007/BF01219774. Google Scholar

[42]

P. Walters, "An Introduction to Ergodic Theory,", G.T.M., 79 (1982). Google Scholar

[1]

Victor Kozyakin. Iterative building of Barabanov norms and computation of the joint spectral radius for matrix sets. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 143-158. doi: 10.3934/dcdsb.2010.14.143

[2]

Victor Kozyakin. Minimax joint spectral radius and stabilizability of discrete-time linear switching control systems. Discrete & Continuous Dynamical Systems - B, 2019, 24 (8) : 3537-3556. doi: 10.3934/dcdsb.2018277

[3]

Chaoqian Li, Yaqiang Wang, Jieyi Yi, Yaotang Li. Bounds for the spectral radius of nonnegative tensors. Journal of Industrial & Management Optimization, 2016, 12 (3) : 975-990. doi: 10.3934/jimo.2016.12.975

[4]

Janusz Mierczyński. Averaging in random systems of nonnegative matrices. Conference Publications, 2015, 2015 (special) : 835-840. doi: 10.3934/proc.2015.0835

[5]

Vladimir Müller, Aljoša Peperko. On the Bonsall cone spectral radius and the approximate point spectrum. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5337-5354. doi: 10.3934/dcds.2017232

[6]

Rui Zou, Yongluo Cao, Gang Liao. Continuity of spectral radius over hyperbolic systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (8) : 3977-3991. doi: 10.3934/dcds.2018173

[7]

Vladimir Müller, Aljoša Peperko. Lower spectral radius and spectral mapping theorem for suprema preserving mappings. Discrete & Continuous Dynamical Systems - A, 2018, 38 (8) : 4117-4132. doi: 10.3934/dcds.2018179

[8]

Leonid Golinskii, Mikhail Kudryavtsev. An inverse spectral theory for finite CMV matrices. Inverse Problems & Imaging, 2010, 4 (1) : 93-110. doi: 10.3934/ipi.2010.4.93

[9]

Shengtian Yang, Thomas Honold. Good random matrices over finite fields. Advances in Mathematics of Communications, 2012, 6 (2) : 203-227. doi: 10.3934/amc.2012.6.203

[10]

Chen Ling, Liqun Qi. Some results on $l^k$-eigenvalues of tensor and related spectral radius. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 381-388. doi: 10.3934/naco.2011.1.381

[11]

Wen Jin, Horst R. Thieme. An extinction/persistence threshold for sexually reproducing populations: The cone spectral radius. Discrete & Continuous Dynamical Systems - B, 2016, 21 (2) : 447-470. doi: 10.3934/dcdsb.2016.21.447

[12]

Daria Bugajewska, Mirosława Zima. On the spectral radius of linearly bounded operators and existence results for functional-differential equations. Conference Publications, 2003, 2003 (Special) : 147-155. doi: 10.3934/proc.2003.2003.147

[13]

Ghalip Abdukerim, Eziz Tursun, Yating Yang, Xiao Li. Uyghur morphological analysis using joint conditional random fields: Based on small scaled corpus. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 823-836. doi: 10.3934/dcdss.2019055

[14]

Jean-Pierre Conze, Y. Guivarc'h. Ergodicity of group actions and spectral gap, applications to random walks and Markov shifts. Discrete & Continuous Dynamical Systems - A, 2013, 33 (9) : 4239-4269. doi: 10.3934/dcds.2013.33.4239

[15]

A. M. López. Finiteness and existence of attractors and repellers on sectional hyperbolic sets. Discrete & Continuous Dynamical Systems - A, 2017, 37 (1) : 337-354. doi: 10.3934/dcds.2017014

[16]

Liu Liu. Uniform spectral convergence of the stochastic Galerkin method for the linear semiconductor Boltzmann equation with random inputs and diffusive scaling. Kinetic & Related Models, 2018, 11 (5) : 1139-1156. doi: 10.3934/krm.2018044

[17]

Esther S. Daus, Shi Jin, Liu Liu. Spectral convergence of the stochastic galerkin approximation to the boltzmann equation with multiple scales and large random perturbation in the collision kernel. Kinetic & Related Models, 2019, 12 (4) : 909-922. doi: 10.3934/krm.2019034

[18]

Marshall Hampton, Anders Nedergaard Jensen. Finiteness of relative equilibria in the planar generalized $N$-body problem with fixed subconfigurations. Journal of Geometric Mechanics, 2015, 7 (1) : 35-42. doi: 10.3934/jgm.2015.7.35

[19]

Kai Zehmisch. The codisc radius capacity. Electronic Research Announcements, 2013, 20: 77-96. doi: 10.3934/era.2013.20.77

[20]

Shi Jin, Yingda Li. Local sensitivity analysis and spectral convergence of the stochastic Galerkin method for discrete-velocity Boltzmann equations with multi-scales and random inputs. Kinetic & Related Models, 2019, 12 (5) : 969-993. doi: 10.3934/krm.2019037

2018 Impact Factor: 0.263

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]