Let $A$ be a $n\times n$ matrix. Let $\|A\|$ be the spectral norm of $A$, and $\rho(A)$ be the spectral radius. I am wondering whether the following statement is true.
There exists universal constant $c > 0$ such that for any $n$ and any matrix $A$ with $\|A\|\le 10$ and $\rho(A) < 0.9$, it holds that for any $k > n^c$, $\|A^k\| \le .01$
Thanks!
(Note that this is closely related to a previously closed question. I guess now it is well-stated to be an non open-ended question)
Yes, this is true for any $c>1$ and large enough $n$.
Let $p(z)=\prod_{i=1}^n (z-\lambda_i)$ be characteristic polynomial of $A$. Denote by $r_k(z)=c_0(k)+c_1(k)z+\dots +c_{n-1}(k)z^{n-1}$ the remainder of polynomial $z^k$ modulo $p(z)$. Then $A^k=\sum_{i=0}^{n-1} c_i(k) A^i$, $\|A^k\|\leqslant \|A\|^n \sum |c_i(k)|$. Well, $c_i(k)$ may be found from the linear system $\sum c_i(k) \lambda_j^i=\lambda_j^{k}$ (we may now suppose that all $\lambda$'s are different and then use continuity of the solution). Solve this system using Kramer's rule, we get that $c_i(k)$ are ratios of some antisymmetric determinant (namely, Vandermonde determinant without $i$-th column $\lambda_j^i$ but with $\lambda_j^k$ instead) and Vandermonde determinant itself. This is known as $\pm$ Schur's function and we really need that it has non-negative coefficients as a polynomial in $\lambda$'s.
Thus maximal value of $|c_i(k)|$ for $|\lambda_i|\leqslant \rho$ is obtained if $\lambda_1=\lambda_2=\dots=\lambda_n=\rho$. We have to find remainder of $z^k$ modulo $(z-\rho)^n$. Not a big deal: $$z^k=((z-\rho)+\rho)^k\equiv \rho^k+k\rho^{k-1}(z-\rho)+\binom{k}2 \rho^{k-2}(z-\rho)^2+\dots+\binom{k}{n-1}\rho^{k-n+1}(z-\rho)^{n-1}\pmod {(z-\rho)^n}.$$ Sum of abosulte values of coefficients of this polynomial admits a bound like $2^nk^n\rho^{k-n}$. Totally we get $$\|A^k\|\leqslant \left(2 k\|A\|\right)^n \rho^{k-n},$$ this is small for $k=n^c$, given $\|A\|$ and given $\rho(A)<1$ for any fixed $c>1$ and large enough $n$.
I think that it is true. That follows is a plan of attack for this purchase. According to the Schur theorem, we may assume that $A=[a_{i,j}]\in M_n(\mathbb{C})$ is upper-triangular. Let $f(n)$ be the integer (if it exists) s.t $A\in M_n(\mathbb{C})$, $\rho(A)\leq .9$, $||A||_2\leq 10$ and $k\geq f(n)$ imply that $||A^k||_2\leq 0.01$.
We consider matrices s.t. $|a_{i,i}|\leq 0.9$ or better $|a_{i,i}|= 0.9$ and s.t. $\rho(AA^*)=100$. We want that the $(A^k)$ are as big as possible; thus good candidates to approach the limit value $f(n)$ are matrices $A$ s.t. $a_{i,j}\geq 0$.
When $n=2,3$ the best candidates, in the previous context, are in the form $A=0.9 I_n+tJ_n$ where $J_n$ is the nilpotent Jordan block of dimension $n$. For $n=2$, we obtain $max(t)=9.919$ and (?) $f(2)=112$; for $n=3$, we obtain $max(t)=9.5$ and (?) $f(3)=181$.
I conjecture that, when $n>2$, the matrices that "realize $f(n)$" have the above form. If it's true, then $f(n)\approx 70 n$. For instance, when $n=23$, $max(t)\approx 9.107$ and (?) $f(23)=1608$.
