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

For a finite collection \(\Sigma\) of \(q\times q\) matrices, its generalized spectral radius \(\rho (\Sigma)\) is defined as the lim sup of the maximal \(n^{\text{th}}\) root of the spectral radius of words of length \(n\) from \(\Sigma\) as \(n\to\infty\). This concept has applications to wavelets. For fixed \(n\), the naive computation of \(\rho_n (\Sigma)= \max_{A\in \Sigma^n} |\rho (A) |^{1\over n}\) takes \(|\Sigma |^n\) spectral radii evaluations to find the maximum. This paper shortens the process to \(|\Sigma |^n/ n\) evaluations by 1) observing that cyclically rearranged words from \(\Sigma^n\) have the same characteristic polynomial, hence spectral radius, 2) by eliminating products that are a power of shorter products and 3) by using the Dedekind-Liouville transforms from arithmetic number theory on the MacMahon formula for counting cyclically different words of length \(n\).