On the joint spectral radius of nonnegative matrices

DOI10.1016/J.LAA.2022.08.029MaRDI QIDQ2080245zbMATH OpenOpenAlexWikidataFDO

Authors Vuong Bui

Publication date 7 October 2022

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2104.13073

zbMATH Keywords

Fekete's lemmajoint spectral radiusjoint spectral radius theoremnonnegative matrices

Mathematics Subject Classification ID

Miscellaneous inequalities involving matrices (15A45) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Numerical range, numerical radius (47A12)

Abstract: We give an effective bound of the joint spectral radius $ho(Sigma)$ for a finite set $Sigma$ of nonnegative matrices: For every $n$, [ sqrt[n]{left(frac{V}{UD} ight)^{D} max_C max_{i,jin C} max_{A_1,dots,A_ninSigma}(A_1dots A_n)_{i,j}} le ho(Sigma) le sqrt[n]{D max_C max_{i,jin C} max_{A_1,dots,A_ninSigma}(A_1dots A_n)_{i,j}}, ] where $DimesD$ is the dimension of the matrices, $U,V$ are respectively the largest entry and the smallest entry over all the positive entries of the matrices in $Sigma$, and $C$ is taken over all strongly connected components in the dependency graph. The dependency graph is a directed graph where the vertices are the dimensions and there is an edge from $i$ to $j$ if and only if $A_{i,j}e0$ for some matrix $AinSigma$. Furthermore, a bound on the norm is also given: If $ho(Sigma)>0$ then there exist a nonnegative integer $r$ and two positive numbers $$ so that for every $n$, [ alpha n^r{ ho(Sigma)}^n le max_{A_1,dots,A_ninSigma} |A_1dots A_n| le �eta n^r{ ho(Sigma)}^n. ] Corollaries of the approach include a simple proof for the joint spectral theorem for finite sets of nonnegative matrices and the convergence rate of some sequences. The method in use is mostly based on Fekete's lemma, for both submultiplicative and supermultiplicative sequences.

Review text

The author studies the joint spectral radius of nonnegative matrices and gives an effective bound of the joint spectral radius of a finite set of nonnegative matrices. Given a finite set \(\Sigma\) of square matrices in \(\mathbb{C}^{d\times d}\), the joint spectral radius \(\rho(\Sigma)\) of \(\Sigma\) is defined to be the limit \[ \rho(\Sigma)=\lim_{n\to \infty} \sqrt[n]{\|\Sigma^n\|}, \] where \(\|\Sigma^n\|=\max_{A_1,\dots,A_n\in \Sigma} \|A_1\dots A_n\|\). The existence of the limit is shown in Proposition 1. Though \(\rho(\Sigma)\) is also defined for infinite bounded sets \(\Sigma\), only finite sets are considered in this paper. For a component \(C\) and every \(m\), denote \[ \|\Sigma^n\|_C=\max_{A_1,\dots,A_n\in \Sigma} \ \max_{i,j\in C} \ |(A_1\dots A_n)_{i,j}| \] and \[ P_m(\Sigma)=\max_{A_1,\dots,A_m\in \Sigma}\ \rho(A_1\dots A_m). \] Given a finite set \(\Sigma\) of nonnegative matrices and \(n\), the author gives the bound of \(\rho(\Sigma)\) in Theorem 2 as follows: \[ \sqrt[n]{\left(\frac{V}{UD}\right)^D\max_C\|\Sigma^n\|_C}\leq \rho(\Sigma)\leq \sqrt[n]{D\max_C\|\Sigma^n\|_C}, \] where \(D\times D\) is the dimension of the matrices, \(U\), \(V\) are respectively the largest entry and the smallest entry over all the positive entries of the matrices in \(\Sigma\), and \(C\) is taken over all components in the dependency graph (see Definition 1). The method for estimating the joint spectral radius in Theorem 2 is better than the one for the popular bound \( \sqrt[m]{P_m(\Sigma)}\leq \rho(\Sigma)\leq \sqrt[m]{D\|\Sigma^m\|}\) in [\textit{R. M. Jungers}, The joint spectral radius. Theory and applications. Berlin: Springer (2009; \url{doi:10.1007/978-3-540-95980-9})] by a root of a polynomial of degree \(r\). The author also gives the following bound on \(\|\Sigma^n\|\): Theorem. If \(\rho(\Sigma)>0\), then there exist a non-negative integer \(r\) and two positive numbers \(\alpha\), \(\beta\) so that for every \(n\) there holds \[ \alpha n^r \rho(\Sigma)^n \leq \|\Sigma\|^n \leq \beta n^r\rho(\Sigma)^n. \]

Recommendations

• Bounds for joint spectral radii of a set of nonnegative matrices
• Computationally Efficient Approximations of the Joint Spectral Radius
• Polynomial-Time Computation of the Joint Spectral Radius for Some Sets of Nonnegative Matrices
• Rank-one characterization of joint spectral radius of finite matrix family
• On the computational aspects of the theory of joint spectral radius

Cites work

• Bounded semigroups of matrices
• Computing the joint spectral radius
• scientific article; zbMATH DE number 3155071 (Why is no real title available?)
• On accuracy of approximation of the spectral radius by the Gelfand formula
• On the accuracy of the ellipsoid norm approximation of the joint spectral radius
• On the calculation of time-varying stability radii
• Sets of matrices all infinite products of which converge
• The boundedness of all products of a pair of matrices is undecidable
• The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate

Cited in

(10)

• Limit eigenvalues of nonnegative matrices
• Bounds for joint spectral radii of a set of nonnegative matrices
• Efficient algorithms for deciding the type of growth of products of integer matrices
• Joint bounds for the Perron roots of nonnegative matrices and their applications
• Polynomial-Time Computation of the Joint Spectral Radius for Some Sets of Nonnegative Matrices
• Approximation of the Joint Spectral Radius of a Set of Matrices Using Sum of Squares
• Comparing the Spectral Radii of Two Nonnegative Matrices
• Growth of bilinear maps. II: Bounds and orders
• A bound on the joint spectral radius using the diagonals
• A Kantorovich type inequality for positive matrices

This page was built for publication: On the joint spectral radius of nonnegative matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2080245)