Markov Chains – Problem (32/365)

Let M be a stochastic matrix (i.e. M_{ij} > 0 and \sum_j M_{ij} = 0 for all i). Show that 1 is an eigenvalue of this matrix and all its eigenvalues \lambda satisfy | \lambda | \le 1.

Since, M is a stochastic matrix we can apply the Ergodic theorem which tells us that there exists \pi = \langle \pi_1, \dots, \pi_n \rangle with \sum_i p_i = 1 such that M^n v \rightarrow p as n \rightarrow \infty. Thus, we see that Mp = (1)p.

To show that all eigenvalues of M have a magnitude less than 1, note that

\displaystyle  \text{for all vectors } v \\ \min \{v_i \} \le \sum_j M_{ij} v_j \le \max \{ v_i \} \\ \text{because } M_i \text{ is a convex combination}

As a result, if an eigenvalue \lambda > 1 for an eigenvector v, then \lambda \max \{ v_i \} > \max \{ v_i \}. Similarly, if \lambda < -1, then \lambda \min \{ v_i \} < \min \{ v_i \}. Therefore, all eigenvalues must satisfy | \lambda | \le 1.

This entry was posted in Uncategorized and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s