5
$\begingroup$

Given $4\times4$ matrix, $$A= \begin{bmatrix} 0.4&0.3&0.2&0.1\\ 0.1&0.4&0.3&0.2\\ 0.3&0.2&0.1&0.4\\ 0.2&0.1&0.4&0.3 \end{bmatrix} .$$ Can we proof $$\lim\limits_{n\to\infty} A^n= \begin{bmatrix} 0.25&0.25&0.25&0.25\\ 0.25&0.25&0.25&0.25\\ 0.25&0.25&0.25&0.25\\ 0.25&0.25&0.25&0.25 \end{bmatrix}$$ manually? I tried to find $A^2$, and $A^3$ for a long long time. Any ways to find $\lim\limits_{n\to\infty} A^n$?

$\endgroup$
  • 1
    $\begingroup$ Just curious, it seems that you are interested in the transition matrix of some nice Markov chain. Is there any reason not relying on the Perron-Froebnius theorem or any related theorem? Certainly it is inconvenient to compute $\lim A^n$ manually every time you encounter this. $\endgroup$ – Sangchul Lee Feb 16 at 4:21
  • $\begingroup$ Yes, that is transition probability matrix of Markov Chain. Thanks for your suggestion. $\endgroup$ – Ongky Denny Wijaya Feb 16 at 4:28
  • 1
    $\begingroup$ Perron-Frobenius theorem implies that if $A$ is an $m\times m$ irreducible nonnegative matrix, then $\lim_{n\to\infty}\left(\frac1{\rho(A)}A\right)^n=\frac{uv^T}{v^Tu}$, where $u$ and $v$ are respectively the right- and left- Perron vectors of $A$. In your case, $A$ is doubly stochastic. Therefore $\rho(A)=1$ and $u=v=(1,1,1,1)^T$. $\endgroup$ – user1551 Feb 16 at 6:23
  • $\begingroup$ Thank you for your information $\endgroup$ – Ongky Denny Wijaya Feb 16 at 6:27
6
$\begingroup$

The matrix $A$ is almost circulant. If the third and fourth rows were swapped, then it would be. So let's consider an alternative matrix: $B=PA$ where $P$ is the permutation matrix $$P=\begin{bmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0 \end{bmatrix}.$$ Then $B$ is circulant.

Since it is circulant, it can be diagonalized with the Discrete Fourier Transform (DFT). The DFT values of $(0.4, 0.3, 0.2, 0.1)$ are $$d = \begin{bmatrix} 1.0000 + 0.0000i \\ 0.2000 - 0.2000i \\ 0.2000 + 0.0000i \\ 0.2000 + 0.2000i \end{bmatrix}$$ Therefore, $B=F^\ast D F$, where $D=\text{diag}(d)$, where $F$ is the DFT matrix.

Note that $B^2=B\cdot B = F^\ast D F \cdot F^\ast D F$. But, since $F$ is unitary, $F F^\ast=I$. Therefore, $B^2=F^\ast D^2 F$. Hopefully you can now see that $B^n = F^\ast D^n F$. (This is a common trick.)

Therefore, $$\lim_{N\rightarrow\infty} B^N = \lim_{N\rightarrow\infty} F^\ast D^N F = F^\ast \text{diag}(1,0,0,0)F.$$

Taking the inverse DFT of $(1,0,0,0)$ yields $(0.25,0.25,0.25,0.25)$. And making a circulant matrix from this vector yields your answer.

(Another way to think about this is to ask, what circulant matrix would diagonalize with eigenvalues $(1,0,0,0)$; and that matrix is the specified matrix.)

So how does this relate to our original $A$?

I didn't figure it out. Luckily, there's another person in this thread that appears to have! https://math.stackexchange.com/a/3114768/24205

$\endgroup$
  • 1
    $\begingroup$ So, you are using diagonalization for finding $A^n$, good idea. Thank you for your answer. $\endgroup$ – Ongky Denny Wijaya Feb 16 at 4:26
  • 2
    $\begingroup$ It's not a circulant. A circulant would have all four diagonal entries equal. $\endgroup$ – jmerry Feb 16 at 5:42
  • $\begingroup$ @jmerry Shoot, you're right! I'll try to fix it. $\endgroup$ – NicNic8 Feb 16 at 15:18
  • $\begingroup$ @jmerry Ok; I hope I fixed it. :) $\endgroup$ – NicNic8 Feb 16 at 15:32
  • $\begingroup$ @OngkyDennyWijaya Be sure to check out the updated answer. $\endgroup$ – NicNic8 Feb 16 at 15:32
2
$\begingroup$

The standard procedure for these sorts of problems is indeed diagonalization. The matrix is almost a circulant; if it were, then it would be diagonalized by the Fourier matrix.

Unfortunately, things don't line up that nicely. We have two of the four diagonal elements equal, not all of them. We would get a circulant matrix if we exchanged the third and fourth rows, but that operation doesn't commute with the 4-cycle that circulants are based on.

That does at least get us one eigenvector. The vector $j$ with all entries $1$ is an eigenvector for all circulants, and it's invariant under exchanging a pair of rows. Here, that eigenvector is associated with the eigenvalue $0.1+0.2+0.3+0.4 = 1$, which is the largest eigenvalue. For the simple question of what the limit of $A^n$ is, that's enough; $$A^n(c_1j+c_2v_2+c_3v_3+c_4v_4) = c_1j+c_2\lambda_2^nv_2+c_3\lambda_3^nv_3+c_4\lambda_4^nv_4\to c_1j$$ where $\lambda_i$ and $v_i$ are the eigenvalues and eigenvectors. That tells us that $\lim_n A^n=ju^T$ for some row vector $u^T$ with the sum of its elements $1$. This $u^T$ is an eigenvector for multiplication by $A$ on the right; $u^TA=u^T$. Checking, we can easily see that $u^T$ will be equal to a multiple of $j^T$, and $\lim_n A^n =\frac14 jj^T$, the matrix with each entry equal to $\frac14$.

So there's the answer. What happens if we try for a full diagonalization? The characteristic polynomial is $(x-1)(x^3 - 0.2 x^2 - 0.04 x + 0.016)$. That cubic factor is irreducible over $\mathbb{Q}$, with approximate roots $-0.24111389$ and $0.22055694\pm 0.13309139i$. We could find eigenvectors for those, but it'll be ugly. For example, an eigenvector for the real eigenvalue is approximately $(0.1414406,0.37608589,-1.5175265,1)^T$. This is just not worth it.

$\endgroup$
  • $\begingroup$ ok, thanks for your answer $\endgroup$ – Ongky Denny Wijaya Feb 17 at 10:08
  • $\begingroup$ How do you know that 1 is the largest eigenvalue? $\endgroup$ – NicNic8 Feb 17 at 18:45
  • 1
    $\begingroup$ Standard theory for positive matrices (positive in all entries). There's a unique positive eigenvector, which corresponds to the largest eigenvalue. $\endgroup$ – jmerry Feb 17 at 19:10
  • $\begingroup$ @jmerry Well that's just as cool as heck! By positive eigenvector, do you mean an eigenvector where all the entries are positive? $\endgroup$ – NicNic8 Feb 25 at 2:52
  • $\begingroup$ Yes, that's what I mean. $\endgroup$ – jmerry Feb 25 at 5:45

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.