An efficient lower bound for the generalized spectral radius of a set of matrices

The generalized spectral radius (GSR) is a fundamental concept in studying the regularity of compactly supported wavelets. Here we describe an efficient method for estimating a lower bound for the GSR. Let M(q) be the set of all q x q matrices with complex entries. Suppose Sigma = {A(0),..., A(m-1)} is a collection of m matrices in M(q). Let L(n) be the set of all products of length n of the elements of Sigma. Define rho(n)(Sigma) = max(A is an element of Ln)[rho(A)](1/n), where rho(A) is the spectral radius of A. The generalized spectral radius of Sigma is then rho(Sigma) = limsup(n-->infinity)rho(n)(Sigma). The standard method for estimating rho(Sigma), from below and at level n, is to calculate the spectral radii of all m(n) products in L(n) and select the largest. Here we use three elementary theorems from linear algebra, combinatorics, and number theory to show that the same result can be obtained with no more than m(n)/n matrix calculations.