Given a matrix

$$ A = \begin{bmatrix} 0 & 3 \\ -2 & 5 \\ \end{bmatrix} $$

and a vector $x = \begin{bmatrix}1&0\end{bmatrix}$, compute $\lim_{n\to\infty} \frac{\|A^{n+2}(x)\|}{\|A^{n}(x)\|}$.

So, I've computed the eigenvalues and eigenvectors of $A$, and noted that since $S^{-1}AS = D$, where $D$ is the diagonal matrix with the eigenvalues of $A$ on the diagonal and the columns of $S$ are the eigenvectors of $A$, then $$A = SDS^{-1},$$ and that now $A^n$ is just simply $$A^n = SD^nS^{-1}.$$

But, how do I actually compute the above limit? I tried simplifying the norm expression and arrived at $\|A^2\|$ by "cancelling" an $\|A^n (x)\|$ from the numerator and denominator, since the norm function is multiplicative. Is this valid? I am not getting an answer that matches the solution.

My work at the end is $\|A^2\| = \| SD^2S^{-1}\|$.

Edit: I am sure that my answer is wrong, since I didn't even get to use the vector (1,0) (from the cancelling of $A^n(x)$.)


Direct calculation gives $$\|A^n x\|^2 = x' A^{\prime n} A^n x = x' S^{\prime -1}D^nS'SD^nS^{-1} x.$$ If the eigenvalues are $\lambda_1,\lambda_2$, then $D^n = \begin{pmatrix} \lambda_1^n & 0 \\ 0 & \lambda_2^n \end{pmatrix}$, and so, letting $T = S'S$, $$ D^n T D^n = \begin{pmatrix} \lambda_1^{2n} T_{11} & \sqrt{\lambda_1 \lambda_2}^{2n} T_{12} \\ \sqrt{\lambda_1 \lambda_2}^{2n} T_{21} & \lambda_2^{2n} T_{22} \end{pmatrix}. $$ It follows that $\|A^n x\|^2 = \alpha \lambda_1^{2n} + \beta \sqrt{\lambda_1 \lambda_2}^{2n} + \gamma \lambda_2^{2n}$ for some $\alpha,\beta,\gamma$.

In your case $\lambda_1 = 3$ and $\lambda_2 = 2$, and so $$ \frac{\|A^{n+2} x\|}{\|A^n x\|} = \sqrt{\frac{\alpha 3^{2n+4} + \beta \sqrt{6}^{2n+4} + \gamma 2^{2n+4}}{\alpha 3^{2n} + \beta \sqrt{6}^{2n} + \gamma 2^{2n}}}. $$ If $\alpha \neq 0$, then the limit of this expression is $$ \lim_{n\to\infty} \frac{\|A^{n+2} x\|}{\|A^n x\|} = \lim_{n\to\infty} \sqrt{\frac{\alpha 3^{2n+4}(\tfrac{\beta}{\alpha}\sqrt{2/3}^{2n+4} + \tfrac{\gamma}{\alpha} (2/3)^{2n+4})}{\alpha 3^{2n}(\tfrac{\beta}{\alpha}\sqrt{2/3}^{2n} + \tfrac{\gamma}{\alpha} (2/3)^{2n})}} = 9. $$ If $\alpha = 0$ and $\beta \neq 0$ then the limit is $6$, and if $\alpha = \beta = 0$ but $\gamma \neq 0$ then the limit is $4$. For a random $x$, $\alpha \neq 0$, and so the answer is probably $9$; to be sure, you'll have to calculate $\alpha$ explicitly.

  • $\begingroup$ Hi, @YuvalFilmus: can explain how you got the first line of equalities and also the second equation with the two summands? I'm a little confused. But your answer of 9 matches the solution. Thanks so much for writing this up. $\endgroup$ – user247041 Jun 10 '15 at 2:53
  • $\begingroup$ The first equation uses the definition of norm, $\|x\|^2 = \langle x,x \rangle = x'x$. The second equation is a simple calculation which I encourage you to do. $\endgroup$ – Yuval Filmus Jun 10 '15 at 2:54
  • $\begingroup$ Ok, thanks so much @YuvalFilmus. $\endgroup$ – user247041 Jun 10 '15 at 2:55
  • $\begingroup$ @YuvalFilmus the formula $$ \|A^n x\|^2 = x' A^{2n} x $$ would only hold if $A$ (or $A^n$) is symmetric. Otherwise, we should have $$ x'(A^n)'A^nx $$ or am I missing something? $\endgroup$ – Ben Grossmann Jun 10 '15 at 23:29
  • $\begingroup$ @Omnomnomnom You're right, let me fix that. $\endgroup$ – Yuval Filmus Jun 11 '15 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.