Rank-one characterization of joint spectral radius of finite matrix family (Q1947089)

Let \(\mathcal{F}\) be a finite set of \(n\times n\) complex matrices and for each \(k\geq1\) let \(\mathcal{F}_{k}\) denote the set of all products \(A_{1}\dots A_{k}\) of length \(k\) with each \(A_{i}\in\mathcal{F}\). The joint spectral radius of \(\mathcal{F}\) is defined as \(\rho(\mathcal{F} ):=\inf_{\left\| {}\right\| }\max_{A\in\mathcal{F}}\left\| A\right\| \) where the infimum is taken over all sub-multiplicative matrix norms. The authors are interested in methods of computing \(\rho(\mathcal{F})\). It can be shown that \[ \max_{A\in\mathcal{F}_{k}}\rho(A)^{1/k}\leq\rho(\mathcal{F)}\leq\max _{A\in\mathcal{F}_{k}}\left\| A\right\| ^{1/k}\text{ for all }k\geq1 \] where \(\rho(A)\) denotes the spectral radius of \(A\) and \(\left\| ~\right\| \) is any sub-multiplicative norm. Furthermore, the right hand side converges to \(\rho(\mathcal{F})\) as \(k\rightarrow\infty\) (see [\textit{G.-C. Rota} and \textit{W. G. Strang}, Nederl. Akad. Wet., Proc., Ser. A 63, 379--381 (1960; Zbl 0095.09701)]) and the \(\lim\sup\) of the left hand side is also equal to \(\rho(\mathcal{F})\). The set \(\mathcal{F}\) is said to have the finiteness property if \(\rho(\mathcal{F})\) is equal to \(\rho(A)^{1/k}\) for some \(k\) and some \(A\in\mathcal{F}_{k}\). Although not every finite set \(\mathcal{F}\) has the finiteness property, there are some important classes of sets of matrices which do have this property, and when this holds there may be more efficient ways to compute the value of \(\rho(\mathcal{F)}\). The first part of the present paper proves that if \(\mathcal{F}\) contains at most one matrix of rank \(>1\), then \(\mathcal{F}\) has the finiteness property. Moreover, if all matrices in \(\mathcal{F}\) have rank \(1\) and \(k\) is the least value for which there there exists \(A\in\mathcal{F}_{k}\) such that \(\rho(\mathcal{F)=}\) \(\rho(A)^{1/k}\), then \(A\) is a product of \(k\) distinct matrices from \(\mathcal{F}\). In this special case, for small sets \(\mathcal{F}\), this gives an efficient way to compute \(\rho(\mathcal{F})\) (see also [\textit{A. A. Ahmadi} and \textit{P. A. Parrilo}, ``Joint spectral radius of rank one matrices and the maximum cycle mean problem'', in: Proc. 51st IEEE Conf. on Decision and Control, 731--733 (2012)]). To extend beyond this limited case, the authors consider the set \(P(\mathcal{F} _{k})\) of rank one approximations to the elements in \(\mathcal{F}_{k}\) (which may be obtained using singular value decompositions) and prove that \(\rho(\mathcal{F})=\lim\sup_{k\rightarrow\infty}\rho(P(\mathcal{F}_{k} ))^{1/k}\). In the special case where each matrix in \(\mathcal{F}\) has nonnegative real entries and some product of matrices in \(\mathcal{F}\) has all entries \(>0\), there is a simpler formula: \(\rho(\mathcal{F)}\) is equal to the limit of \(\max_{A\in\mathcal{F}_{k}}~(\operatorname{tr}~A)^{1/k}\) as \(k\rightarrow\infty\). Numerical examples are given to show how these formulae may be used in practice.