Perron–Frobenius theorem

Today I attended a lecture given by Vaughn Climenhaga. He presented a proof of the following version of Perron–Frobenius theorem:

Let \Delta\subset \mathbb{R}^d be the set of probability vectors, P be a stochastic matrix with positive entries. Then
–there is a positive probability \pi\in \Delta fixed by P
–the eigenspace E_1=\mathbb{R}\pi
–the spectra \Sigma(P)\subset B(0,r)\cup\{1\} for some r<1
–for all v\in\Delta, P^n v\to \pi exponentially as n\to \infty.

Proof. (1) Let v\in\Delta. Then \sum_i v_i=1, and
\sum_i (Pv)_i=\sum_i \sum_j p_{ij}v_j=\sum_j v_j=1. So Pv\in \Delta. Moreover, Pv is positive and P(\Delta)\subset \text{Int}(\Delta). Therefore there exists some point \pi\in\text{Int}(\Delta) fixed by P.

(2). Suppose on the contrary that there exists v\notin \mathbb{R}\pi that is also fixed by P. Then P fixes every vector in the plane \Pi:=\mathbb{R}v\oplus\mathbb{R}\pi, in particular the points on \Pi\cap \partial \Delta. This contradicts (1).

(3). We use the norm |v|=\sum|v_i|. Note that |Pv|=\sum_i |(Pv)_i|\le \sum_{ij}p_{ij}|v_j|=|v|. So \Sigma(P)\subset D(0,1). It suffices to show \Sigma(P)\backslash\{1\}\cap S^1=\emptyset. If not, pick one ,say \lambda, and n\ge 1 such that \text{Re}(\lambda^n)1 for any \epsilon>0.

Consider the matrix A=P^n-\epsilon I, which is positive if \epsilon is small enough. Then we have |A|\le |P_n| and hence \Sigma(A)\subset D(0,1). This contradicts the fact \lambda^n-\epsilon is an eigenvalue of A.

(4). Let W\subset \mathbb{R}^d be the subset of vectors with zero mean: \sum v_i=0, and consider the decomposition \mathbb{R}^d=\mathbb{R}\pi\oplus W. Note that PW\subset W and hence \Sigma(P|_{W})\subset D(0,r). For any v\in\Delta, we have v=\pi+w for some w\in W. Then |P^nv-\pi|=|P^n(v-\pi)|=|P^nw|\le Cr^n|w|.

Only light calculations are used in his lecture. As pointed by Vaughn, this approach does not give precise information of the r.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com 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

%d bloggers like this: