Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard
Vincent D. Blondel, Stéphane Gaubert, John N. Tsitsiklis · IEEE Transactions on Automatic Control · 2000
The lower and average spectral radii measure, respectively, the minimal and average growth rates of long products of matrices taken from a finite set. The logarithm of the average spectral radius is traditionally called the Lyapunov exponent. When one performs these products in the max-algebra, we obtain quantities that measure the performance of discrete event systems. We show that approximating the lower and average max-algebraic spectral radii is NP-hard.