Suppose that $A$ is a $n \times n$ matrix with $\rho(A) \leq 1$ and $\|A\|_2 \leq R$, where $R>1$. How can I show an upper bound on $\|A^k\|_2$ that is polynomial in $k$? A trivial upper bound is by the sub-multiplicative property of the norm $ \|A^k\|_2 \leq R^k$, but this bound is exponential in $k$.
My attempt:
(1) Suppose that $A$ is symmetric, then $\|A\|_2 = \rho(A)$ and we have $\|A^n\|_2 \leq 1$.
(2) It seems to me that if we show an upper bound on $A$ with all eigenvalues equal to 1, then that bound should work for any $A$ with $\rho(A) \leq 1$. I use a similar method as in the proof of this theorem. Let $A = P J P^{-1}$ be the Jordan form of $A$ with all eigenvalues equal to 1. Suppose $k > n$. For $A^k = P J^k P^{-1}$ according to this, we have
\begin{align} J^k = \begin{bmatrix} 1 & {k \choose 1} & {k \choose 2} & \dots & {k \choose n-1}\\ 0 & 1 & {k \choose 1} & \dots & {k \choose n-2}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \dots & 1 \end{bmatrix} \end{align} Then $\|A^k\|_2 \leq \|P\|_2 \|J^k\|_2 \|P^{-1}\|_2 \leq \|P\|_2 \|P^{-1}\|_2 n^2 k^n$, that is polynomial in $k$. There are a couple of issues with this argument. First, how can I argue that $A$ with all real eigenvalues equal to 1 is the worst case? How do I deal with the case of complex eigenvalues with absolute value 1? Second, how can I bound the norms of $\|P\|$ and $\|P^{-1}\|$? Maybe using the information that $\|A\|_2 \leq R$?