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).

[2]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[14]

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

[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.

[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.

[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.

[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.

[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.

[20]

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

[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.

[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.

[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.

[24]

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

[25]

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

[26]

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

[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.

[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.

[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.

[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.

[31]

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

[32]

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

[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.

[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.

[35]

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

[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.

[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.

[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.

[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.

[40]

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

[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.

[42]

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

show all references

References:
[1]

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

[2]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[14]

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

[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.

[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.

[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.

[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.

[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.

[20]

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

[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.

[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.

[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.

[24]

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

[25]

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

[26]

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

[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.

[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.

[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.

[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.

[31]

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

[32]

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

[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.

[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.

[35]

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

[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.

[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.

[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.

[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.

[40]

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

[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.

[42]

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

[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]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

François Lalonde, Yasha Savelyev. On the injectivity radius in Hofer's geometry. Electronic Research Announcements, 2014, 21: 177-185. doi: 10.3934/era.2014.21.177

[18]

Antonio Giorgilli, Stefano Marmi. Convergence radius in the Poincaré-Siegel problem. Discrete & Continuous Dynamical Systems - S, 2010, 3 (4) : 601-621. doi: 10.3934/dcdss.2010.3.601

[19]

Manish K. Gupta, Chinnappillai Durairajan. On the covering radius of some modular codes. Advances in Mathematics of Communications, 2014, 8 (2) : 129-137. doi: 10.3934/amc.2014.8.129

[20]

Zenonas Navickas, Rasa Smidtaite, Alfonsas Vainoras, Minvydas Ragulskis. The logistic map of matrices. Discrete & Continuous Dynamical Systems - B, 2011, 16 (3) : 927-944. doi: 10.3934/dcdsb.2011.16.927

2016 Impact Factor: 0.483

Metrics

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

Other articles
by authors

[Back to Top]