The spectral radius of a pair of matrices is hard to compute
John N. Tsitsiklis, Vincent D. Blondel · 2002
We analyse the computability and the complexity of various definitions of spectral radii for sets of matrices. We show that the joint and generalised spectral radii of two integer matrices are not approximable in polynomial time, and that, two related quantities-the lower spectral radius and the largest Lyapunov exponent-are not algorithmically approximable. As a corollary of these results we show that: 1) the problem of deciding if all possible products of two given matrices are stable is NP-hard, 2) the problem of deciding if at, least one product of two given matrices is stable is undecidable.