POLYNOMIAL-TIME COMPUTATION OF THE JOINT SPECTRALRADIUS FOR SOME SETS OF NONNEGATIVE MATRICES

摘要

We propose two simple upper bounds for the joint spectral radius of sets of nonneg-ative matrices. These bounds, the joint column radius and the joint row radius, can be computedin polynomial time as solutions of convex optimization problems. We show that these bounds arewithin a factor 1 of the exact value, where n is the size of the matrices. Moreover, for sets ofmatrices with independent column uncertainties or with independent row uncertainties, the corre-sponding bounds coincide with the joint spectral radius. In these cases, the joint spectral radius isalso given by the largest spectral radius of the matrices in the set. As a by-product of these results,we propose a polynomial-time technique for solving Boolean optimization problems related to thespectral radius. We also describe economics and engineering applications of our results.