Joint spectral radius of matrices: applications and methods of computation

Abstract. The joint spectral radius (JSR) of a family of matrices is the exponent of the largest possible growth of norms of products of those matrices. For one matrix, JSR coincides with the usual spectral radius. For families of matrices, the JSR originated with G.C.Rota and D.Strang in 1960. It has found many applications in functional analysis, dynamical systems, discrete mathematics, combinatorics, etc. Some of them will be discussed in the talk. The computing or estimating the joint spectral radius is a notoriously hard problem. It is known to be NP-hard in general, even for 0-1 matrices. Nevertheless, recently several efficient methods were elaborated involving modern tools of convex optimization. We discuss, in particular, the polytope norm algorithm (N.Giglielmi, V.Protasov, 2013) that finds the exact value of JSR (as a root of some polynomial) for vast majority of matrix families in dimensions op to 20 (for nonnegative matrices it is applicable in dimension 100 and higher).