Perron-Frobenius Theory

Let $T$ be a real $n \times n$ matrix with nonnegative entries. $T$ is called primitive if for some $k$ we have $T^k > 0$; $T$ is called irreducible if for all $i,j$ there is a $k$ such that $( T^k )_{ij} > 0$.

(Here, for a matrix (or vector) $A$, $A > 0$ $( \ge 0)$ means that all its entries are positive (nonnegative). The matrix $T = (t_{ij} )$ is irreducible if and only if the directed graph $\Gamma_T$ with vertices $\{1, ... ,n\}$ and edges $(i,j)$ whenever $t_{ij} > 0$ is strongly connected. Note that if $T$ is irreducible, then $I + T$ is primitive.)

The period $d$ of an irreducible matrix $T$ is the greatest common divisor of the integers $k$ for which $(T^k )_{ii} > 0$. It is independent of the $i$ chosen.

Theorem 1.3.1   Let $T \ge 0$ be irreducible. Then there is a (unique) positive real number $\theta_0$ with the following properties:

1. There is a real vector $x_0 > 0$ with $Tx_0 = \theta_0 x_0$.

2. $\theta_0$ has geometric and algebraic multiplicity one.

3. For each eigenvalue $\theta$ of $T$ we have $\vert \theta \vert \le \theta_0$. If $T$ is primitive, then $\vert \theta \vert = \theta_0$ implies $\theta = \theta_0$. In general, if $T$ has period $d$, then $T$ has precisely $d$ eigenvalues $\theta$ with $\vert \theta \vert = \theta_0$, namely $\theta = \theta_0 e^{ 2 \pi i j / d }$ for $j = 0,1, ... ,d-1$. In fact the entire spectrum of $T$ is invariant under rotation of the complex plane over an angle $2 \pi / d$ about the origin.

4. Any (nonzero) nonnegative left or right eigenvector of $T$ has eigenvalue $\theta_0$. More generally, if $x \ge 0$, $x \ne 0$ and $Tx \le \theta x$, then $x > 0$ and $\theta \ge \theta_0$; moreover, $\theta = \theta_0$ if and only if $Tx = \theta x$.

5. If $0 \le S \le T$ or if $S$ is a principal minor of $T$, and $S$ has eigenvalue $\sigma$, then $\vert \sigma \vert \le \theta_0$; if $\vert \sigma \vert = \theta_0$, then $S = T$.

Proof:     (i) Let $P = (I + T)^{n-1}$. Then $P > 0$ and $PT = TP$. Let $B = \{ x \mid x \ge 0 \mbox{~and~} x \ne 0 \}$. Define for $x \in B$:

$$\theta ( x ) = \max_{ \theta \in {\mathbb{R}}} \{ \theta \mi... ...\min_{{1 \le i \le n} \atop {x_i \ne 0}} { (Tx)_i \over x_i }.$$

Now $\theta ( \alpha x ) = \theta ( x )$ for $\alpha \in {\mathbb{R}}$, $\alpha > 0$, and ($x \le y$, $x \ne y$ implies $Px < Py$, so) $\theta ( Px ) \ge \theta ( x )$; in fact $\theta ( Px ) > \theta (x)$ unless $x$ is an eigenvector of $T$. Put $C = \{ x \mid x \ge 0$ and $\Vert x \Vert= 1 \}$. Then since $C$ is compact and $\theta ( . )$ is continuous on $P[C]$ (but not in general on $C$ !), there is an $x_0 \in P[C]$ such that

$$\theta_0 := \sup_{ x \in B } \theta (x) = \sup_{ x \in C } \theta (x) = \sup_{ x \in P[C] } \theta (x) = \theta ( x_0 ).$$

Now $x_0 > 0$ and $x_0$ is an eigenvector of $T$, so $Tx_0 = \theta_0 x_0$, and $\theta_0 > 0$.

(ii) For a vector $x = (x_1 , ... , x_n )^\top$, write $x_{+} = ( \vert x_1 \vert , ... , \vert x_n \vert )^\top$. If $Tx = \theta x$, then by the triangle inequality we have $T x_{+} \ge \vert \theta \vert x_{+}$. For nonzero $x$ this means $\vert \theta \vert \le \theta (x_{+} ) \le \theta_0$. If, for some vector $z \in B$, we have $Tz \ge \theta_0 z$, then $z$ is eigenvector of $T$ (otherwise $\theta ( Pz ) > \theta_0$), and since $0 < Pz = (1 + \theta_0 )^{n-1} z$ we have $z > 0$. Now if $x$ is any eigenvector of $T$ with eigenvalue $\theta_0$, then if $x$ is real consider $y = x_0 + \varepsilon x$, where $\varepsilon$ is chosen such that $y \ge 0$ but not $y > 0$; now $y \not\in B$, i.e., $y = 0$, so $x$ is a multiple of $x_0$. In the general case, both the real and imaginary parts of $x$ are multiples of $x_0$. This shows that the eigenspace of $\theta_0$ has dimension 1, i.e., that the geometric multiplicity of $\theta_0$ is 1. We shall look at the algebraic multiplicity later.

(iii) We have seen $\vert \theta \vert \le \theta_0$. If $\vert \theta \vert = \theta_0$ and $Tx = \theta x$, then $Tx_{+} = \theta_0 x_{+}$ and we had equality in the triangle inequality $\vert \sum_j t_{ij} x_j \vert \le \sum_j t_{ij} \vert x_j \vert$; this means that all numbers $t_{ij} x_j$ ($1 \le j \le n$) have the same angular part (argument). If $T$ is primitive, then we can apply this reasoning with $T^k$ instead of $T$, where $T^k > 0$, and conclude that all $x_j$ have the same angular part. Consequently, in this case $x$ is a multiple of a real vector and may be taken real, nonnegative. Now $Tx = \theta x$ shows that $\theta$ is real, and $\vert \theta \vert = \theta_0$ that $\theta = \theta_0$. In the general case, $T^d$ is a direct sum of primitive matrices $T^{(0)} , ... , T^{(d-1)}$, and if $x = ( x^{(0)} , ... , x^{(d-1)} )$ is the corresponding decomposition of an eigenvector of $T$ (with eigenvalue $\theta$), then $( x^{(0)} , \zeta x^{(1)} , ... , \zeta^{d-1} x^{(d-1)} )$ also is an eigenvector of $T$, with eigenvalue $\zeta \theta$, for any $d$-th root of unity $\zeta$. (Here we assume that the $T^{(i)}$ are ordered in such a way that in $\Gamma_T$ the arrows point from the subset corresponding to $T^{(i)}$ to the subset corresponding to $T^{(i+1)}$.) Since $T^d$ has a unique eigenvalue of maximum modulus (let $T_{(i)}^{(i+1)}$ be the (nonsquare) submatrix of $T$ describing the arrows in $G_T$ between the subset corresponding to $T^{(i)}$ to the subset corresponding to $T^{(i+1)}$; then $T^{(i)} = \prod_{j=0}^{d-1} T_{(i+j)}^{(i+j+1)}$ and if $T^{(i)} z = \gamma z$, $z > 0$ then $T^{(i-1)} z' = \gamma z'$ where $z' = T_{(i-1)}^{(i)} z \ne 0$, so that all $T^{(i)}$ have the same eigenvalue of maximum modulus), it follows that $T$ has precisely $d$ such eigenvalues.

(iv) Doing the above for left eigenvectors instead of right ones, we find $y_0 > 0$ with $y_0^\top T = \eta_0 y_0^\top$. If $Tx = \theta x$ and $y^\top T = \eta y^\top$, then $\eta y^\top x = y^\top T x = \theta y^\top x$. It follows that either $\theta = \eta$ or $y^\top x = 0$. Taking $y \in B$, $x = x_0$ or $x \in B$, $y = y_0$ we see that $\theta = \eta$ ( $= \theta_0 = \eta_0$). Similarly, if $Tx \le \theta x$, $x \in B$ then $\theta_0 y_0^\top x = y_0^\top Tx \le \theta y_0^\top x$ so that $\theta_0 \le \theta$; also $0 < Px \le (1 + \theta )^{n-1} x$, so $x > 0$. If $\theta = \theta_0$, then $y_0^\top (Tx - \theta x) = 0$ so $Tx = \theta x$.

(v) If $s \ne 0$, $Ss = \sigma s$, then $Ts_{+} \ge Ss_{+} \ge \vert \sigma \vert s_{+}$, so $\vert \sigma \vert \le \theta_0$. But if $\vert \sigma \vert = \theta_0$ then $s_{+}$ is eigenvector of $T$ and $s_{+} > 0$ and $(T - S)s_{+} = 0$, so $S = T$.

(vi) Finally, in order to prove that $\theta_0$ is a simple root of $\chi_T$, the characteristic polynomial of $T$, we have to show that ${d \over { d \theta }} \chi_T ( \theta )$ is nonzero for $\theta = \theta_0$. But $\chi_T ( \theta ) = \det ( \theta I - T)$ and ${d \over { d \theta }} \chi_T ( \theta ) = \sum_i \det ( \theta I - T_{ii} )$, and by (v) we have $\det ( \theta I - T_{ii} ) > 0$ for $\theta = \theta_0$. $\Box$

Remark In case $T \ge 0$ but $T$ not necessarily irreducible, we can say the following.

(i) The spectral radius $\theta_0$ of $T$ is an eigenvalue, and there are nonnegative left and right eigenvectors corresponding to it.

(ii) If $0 \le S \le T$ and $S$ has eigenvalue $\sigma$, then $\vert \sigma \vert \le \theta_0$.

( Proof:    (i) Use continuity arguments; (ii) the old proof still applies.)

For more details, see the exposition of the Perron-Frobenius theory in Gantmacher [12], Chapter XIII; cf. also Varga [33], Marcus & Minc [27], Berman & Plemmons [2], Seneta [29], Chapter 1.