Joint bounds for the Perron roots of nonnegative matrices with applications

Yu. A. Alpin   ; L. Yu. Kolotilina   ; N. N. Korneeva

Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms. Part XIX, Tome 334 (2006), pp. 30-56

Résumé

Given a finite set $\{A^{(x)}\}_{x\in X}$ of nonnegative matrices, we derive joint upper and lower bounds for the row sums of the matrices $D^{-1}A^{(x)}D$, $x\in X$, where $D$ is a specially chosen nonsingular diagonal matrix. These bounds, depending only on the sparsity patterns of the matrices $A^{(x)}$ and their row sums, are used to obtain joint two-sided bounds for the Perron roots of given nonnegative matrices, joint upper bounds for the spectral radii of given complex matrices, bounds for the joint and lower spectral radii of a matrix set, and conditions sufficient for all convex combinations of given matrices to be Schur stable.

Bibliographie

[1] Yu. A. Alpin, “Granitsy dlya perronova kornya neotritsatelnoi matritsy, uchityvayuschie svoistva ee grafa”, Matem. zametki, 58 (1995), 635–637 | MR

[2] F. R. Gantmakher, Teoriya matrits, Nauka, M., 1967 | MR

[3] L. Yu. Kolotilina, “Otsenki i neravenstva dlya perronovskogo kornya neotritsatelnoi matritsy”, Zap. nauchn. semin. POMI, 284, 2002, 77–122 | MR | Zbl

[4] L. Yu. Kolotilina, “Otsenki i neravenstva dlya perronovskogo kornya neotritsatelnoi matritsy, II”, Zap. nauchn. semin. POMI, 296, 2003, 60–88 | MR | Zbl

[5] V. P. Chistyakov, “K otsenke perronova kornya neotritsatelnykh matrits”, Dokl. AN SSSR, 246 (1979), 548–550 | MR | Zbl

[6] M. A. Berger, Y. Wang, “Bounded semigroups of matrices”, Linear Algebra Appl., 166 (1992), 21–27 | DOI | MR | Zbl

[7] V. D. Blondel, Yu. Nesterov, “Computationally efficient approximations of the joint spectral radius”, SIAM J. Matrix Anal. Appl., 27 (2005), 256–272 | DOI | MR | Zbl

[8] V. D. Blondel, Yu. Nesterov, J. Theys, “Computing the joint spectral radius of a set of matrices”, Proceedings of the 23rd Benelux Meeting on Systems and Control, Helvoirt, The Netherlands, paper FrP06-3, March 17–19, 2004

[9] I. Daubechies, J. C. Lagarias, “Sets of matrices all infinite products of which converge”, Linear Algebra Appl., 162 (1992), 227–263 | DOI | MR

[10] L. Elsner, “The generalized spectral-radius theorem: An analytic-geometric proof”, Linear Algebra Appl., 220 (1995), 151–159 | DOI | MR | Zbl

[11] L. Elsner, T. Szulc, “Convex combinations of matrices – nonsingularity and Schur stability”, Proceedings of the First Workshop on Numerical Analysis and Applications (Rousse, Bulgaria, 1996), eds. L. Vulkov, J. Wasniewski, P. Yalamov, Springer-Verlag, 1997, 170–175 | MR

[12] L. Elsner, T. Szulc, “Convex combinations of matrices – nonsingularity and Schur stability characterizations”, Linear Multilinear Algebra, 44 (1998), 301–312 | DOI | MR | Zbl

[13] L. Gurwits, “Stability of discrete linear inclusion”, Linear Algebra Appl., 231 (1995), 47–85 | DOI | MR

[14] F. Harary, Graph Theory, Addison–Wesley Publ. Co., 1969 | MR | Zbl

[15] C. R. Johnson, M. J. Tsatsomeros, “Convex sets of nonsingular and P-matrices”, Linear Multilinear Algebra, 38 (1995), 233–240 | DOI | MR

[16] J. C. Lagarias, Y. Wang, “The finiteness conjecture for the generalized spectral radius of a set of matrices”, Linear Algebra Appl., 214 (1995), 17–42 | DOI | MR | Zbl

[17] G.-C. Rota, W. G. Strang, “A note on the joint spectral radius”, Nederl. Akad. Wet., Proc., Ser. A, 63 (1960), 379–381 | MR | Zbl

[18] C. B. Soh, “Schur stability of convex combinations of matrices”, Linear Algebra Appl., 128 (1990), 159–168 | DOI | MR | Zbl

[19] J. N. Tsitsiklis, 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, Syst., 10 (1997), 17–42 | MR

[20] A. A. Vladimirov, L. Elsner, W.-J. Beyn, “Stability and paracontractivity of discrete linear inclusions”, Linear Algebra Appl., 312 (2000), 125–134 | DOI | MR | Zbl