Bounding the spectral radius and powers of nonnegative matrices
Vuong Bui · arXiv (Cornell University) · 2020
Given a nonnegative square matrix $A$, the $n$-th root of the largest entry of $A^n$ is well known to converge to the spectral radius $\rho(A)$ of $A$ when $n$ tends to infinity. We give another proof of the convergence by showing \[ \lim_{n\to\infty} \max_i\max_j \sqrt[n]{(A^n)_{i,j}} = \max_i \sup_n \sqrt[n]{(A^n)_{i,i}}. \] As the sequence $\{(A^n)_{i,i}\}_n$ for every $i$ is shown to be both supermultiplicative and submultiplicative in a weak form, an extension of Fekete's lemma concludes that the subsequence of positive $\sqrt[n]{(A^n)_{i,i}}$, if not empty, converges to $\sup_n \sqrt[n]{(A^n)_{i,i}} = \inf \{\sqrt[n]{K_i (A^n)_{i,i}}: (A^n)_{i,i} > 0\}$ for some constant $K_i$. A corollary is the following bound of $\rho(A)$: \[ \max_i \sqrt[m_i]{(A^{m_i})_{i,i}} \le \rho(A) \le \max_i \sqrt[m_i]{K_i (A^{m_i})_{i,i}}, \] where $m_i$ satisfies $(A^{m_i})_{i,i}>0$ for each $i$, or we just set $m_i=1$ if there is no such $m_i$. An unoptimized setting for the constants is $K_i = D^3 (\frac{U}{V})^{6D^2}$ for every $i$, where $D\times D$ is the dimension of $A$, and $U,V$ are respectively the largest and smallest entry of $A$. The order of $(A^n)_{i,i}$ also gives another proof of the formula $\lambda=\max_i \sup_n \sqrt[n]{(A^n)_{i,i}}$ for the limit using Wimmer's formula. Yet another proof is however also given. Although the third one is much more complex, it gives a more precise growth: There exists some nonnegative integer $r$ such that for every $n$, \[ \operatorname{const} n^r\lambda^n\le \max_i \max_j (A^n)_{i,j} \le \operatorname{const} n^r\lambda^n. \] The approach in use is more combinatorial than the traditional algebraic approach.