13

How can I calculate this limit:

$\displaystyle\lim_{n\to\infty}\begin{bmatrix}0.9 & 0.2\\0.1 & 0.8\end{bmatrix}^n$

What is the tool that i need to aply? eigenvalues and eigenvectors? diagonalization? canonical form?

(This came in a contest and was the only problem i cannont have an idea for solve it).

JimmyK4542
  • 54,331
Julio
  • 581
  • After diagnolizing the matrix it should be fairly easy to see how to proceed - Raising the matrix to the $n^{th}$ power then becomes very easy and then you can proceed by analyzing the sequences formed within the diagonal matrix. – DanZimm Jun 22 '14 at 21:25
  • That matrix is diagonalizable (with distinct (real) eigenvalues). However, one eigenvalue is exactly $1.0$. So this is very "sensitive" to rounding errors. So don't calculate the matrix powers with binaray floating point computer arithmetic. – Jeppe Stig Nielsen Jun 22 '14 at 21:43
  • Note that if you have any square matrix $A$ than existence of the limit $L$ determines that $A\cdot L=L$, so if $\det(A−E)\neq 0$ then $L=0$, you can also consider the Cayley–Hamilton theorem.Here matrix $A$ has only $2$ dimensions so, it's possible using a vertex form of the characteristic polynomial and deducing suitable form for any $2\times2$ matrix with remembering that $A^n$ can be expressed as $\sum_{i=0}^n b_i(A−x_0 E)^i$. – Darius Jun 22 '14 at 23:11

4 Answers4

12

Diagonalization is precisely the tool you need.

If you can write $A = PDP^{-1}$, where $D$ is a diagonal matrix, then $A^n = PD^nP^{-1}$, where $D^n$ is also diagonal, and its entries are just the $n$-th power of the entries in $D$.

Then, $\displaystyle\lim_{n\to\infty}A^n = \lim_{n\to\infty}PD^nP^{-1}$ is easy to compute.

JimmyK4542
  • 54,331
7

$$A=\begin{bmatrix}\frac{9}{10} & \frac{2}{10}\\\frac{1}{10} & \frac{8}{10}\end{bmatrix}$$

$$A=PDP^{-1}$$ where $$P=\begin{bmatrix}2 & -1\\1 & 1\end{bmatrix}$$

$$D=\begin{bmatrix}1 & 0\\0 & 7/10\end{bmatrix}$$

So the limit is given by:

$$\lim_{n\to\infty} A^n=\lim_{n\to\infty} PD^nP^{-1}=PD_{\infty}P^{-1}......(1)$$

where $$D_{\infty}=\begin{bmatrix}1 & 0\\0 & \lim_{n\to\infty}(7/10)^n\end{bmatrix}=\begin{bmatrix}1 & 0\\0 & 0\end{bmatrix}......(2)$$

Substitution of $D_{\infty}$ into (1) leads to:

$$\lim_{n\to\infty} A^n=PD_{\infty}P^{-1}=\begin{bmatrix}\frac23 & \frac23\\\frac13 & \frac13\end{bmatrix}$$

mike
  • 5,604
5

Note that your matrix is not an arbitrary matrix --- it is a column stochastic matrix and thus a Markov transition matrix. Hence, from the Perron-Frobenius theorem you will know that each column of the limit matrix will be the normalized eigenvector of your matrix corresponding to the eigenvalue $1$, and as you can check

$$\begin{bmatrix}0.9 & 0.2\\0.1 & 0.8\end{bmatrix}\begin{bmatrix}2/3\\1/3\end{bmatrix}=\begin{bmatrix}2/3\\1/3\end{bmatrix},$$

so that, indeed, $\lim_{n\rightarrow\infty}\begin{bmatrix}0.9 & 0.2\\0.1 & 0.8\end{bmatrix}^n=\begin{bmatrix}2/3 & 2/3\\1/3 & 1/3\end{bmatrix}$.

This methodology applies generally: If you have a column stochastic matrix $B$ with strictly positive entries, its (power) limit exists and each column of $\lim_n B^n$ is given by the normalized eigenvector of $B$ corresponding to the eigenvalue $1$.

mathse
  • 2,438
  • 12
  • 18
  • I know this comment is old, but follow-up question to your response: Do you really mean normalized "the eigenvector corresponding to the eigenvalue 1"? Because the vector you gave does not have a norm of 1. Do you instead maybe mean "the eigenvector whose values sum to 1 corresponding to the eigenvalue 1"? – NoseKnowsAll May 31 '15 at 04:15
  • 1
    There are different norms, right? L_1 norm is the sum of absolute values, for example. – mathse Jun 02 '15 at 11:26
  • Fair point. Probably should mention that you're using the $L_1$ norm then. I think most people would assume $L_2$ when anyone mentions normalized vectors. – NoseKnowsAll Jun 02 '15 at 14:55
5

Because that is a stochastic matrix you just need to fine the fixed probability vector or steady state vector.

$$(t1,t2)\cdot\left( \begin{array}{cc} 0.9 & 0.1 \\ 0.2 & 0.8 \\ \end{array} \right)=(t1,t2)$$

Notice I have transposed A for convenience and this yields the simultaneous set of equations

$$.9 \cdot t1+.2 \cdot t2=\text{t1}$$

$$.1 \cdot t1+.8 \cdot t2=\text{t2}$$

$$t1 + t2 = 1$$

this is easily solved to get

$t1=\frac{2}{3}$

$t2=\frac{1}{3}$

Because this is a regular Markov chain all the rows of $A^{\infty} $ are equal to $(t1,t2)$, so

$$A^{\infty} = \left( \begin{array}{cc} \frac{2}{3} & \frac{1}{3} \\ \frac{2}{3} & \frac{1}{3} \\ \end{array} \right)$$

Transpose A back:

$$A^{\infty} = \left( \begin{array}{cc} \frac{2}{3} & \frac{2}{3} \\ \frac{1}{3} & \frac{1}{3} \\ \end{array} \right)$$

bobbym
  • 2,546