Perron-Frobenius Theory of Nonnegative Matrices

Verify Perron's theorem by computing the eigenvalues and eigenvectors for

Find the right-hand Perron vector $p$ as well as the left-hand Perron vector $q^T$.

Convince yourself that (8.2.2)-(8.2.5) are indeed true.

Statements (8.2.2)-(8.2.5) are properties of the Perron root and Perron vector established in the text for a positive matrix $A_{n\times n} > 0$ with $r = \rho (A)$: (8.2.2) $r > 0$; (8.2.3) $r \in \sigma (A)$ (called the Perron root); (8.2.4) $\text{alg mult}_A(r) = 1$; (8.2.5) there exists an eigenvector $x > 0$ such that $Ax = rx$.

Provide the details that explain why the Perron vector is uniquely defined.

Find the Perron root and the Perron vector for

where $\alpha + \beta = 1$ with $\alpha , \beta > 0$.

Suppose that $A_{n\times n} > 0$ has $\rho (A) = r$.

Prove that if every row (or column) sum of $A_{n\times n} > 0$ is equal to $\rho$, then $\rho (A) = \rho$.

Prove that if $A_{n\times n} > 0$, then

To show the extent to which the hypothesis of positivity cannot be relaxed in Perron's theorem, construct examples of square matrices $A$ such that $A \geq 0$, but $A \not> 0$ (i.e., $A$ has at least one zero entry), with $r = \rho (A) \in \sigma (A)$ that demonstrate the validity of the following statements. Different examples may be used for the different statements.

Establish the min-max version of the Collatz--Wielandt formula that says the Perron root for $A > 0$ is given by $r = \min_{x \in \mathcal{P}} g(x)$, where

Notice that $\mathcal{N} = \left\{ x \mid x \geq 0 \text{ with } x \neq 0\right\}$ is used in the max-min version of the Collatz--Wielandt formula, but $\mathcal{P} = \left\{ x \mid x > 0\right\}$ is used in the min-max version in the previous exercise. Give an example of a matrix $A > 0$ that shows $r \neq \min_{x \in \mathcal{N}} g(x)$ when $g(x)$ is defined as

Let $A = \begin{pmatrix} 0 & 1 & 0 \\ 3 & 0 & 3 \\ 0 & 2 & 0 \end{pmatrix}$.

Suppose that the index of imprimitivity of a $5 \times 5$ nonnegative irreducible matrix $A$ is $h = 3$. Explain why $A$ must be singular with $\text{alg mult}_A(0) = 2$.

Suppose that $A$ is a nonnegative matrix that possesses a positive spectral radius and a corresponding positive eigenvector. Does this force $A$ to be irreducible?

Without computing the eigenvalues or the characteristic polynomial, explain why $\sigma (P_n) = \{ 1, \omega , \omega^2, \ldots , \omega^{n-1}\}$, where $\omega = e^{2\pi i/n}$ for

Determine whether

is reducible or irreducible.

Determine whether the matrix $A$ in Exercise 8.3.5 is primitive or imprimitive.

A matrix $S_{n\times n} \geq 0$ having row sums less than or equal to $1$ with at least one row sum less than $1$ is called a substochastic matrix.

A nonnegative matrix for which each row sum is $1$ is called a stochastic matrix (some say row-stochastic). Prove that if $A_{n\times n}$ is nonnegative and irreducible with $r = \rho (A)$, then $A$ is similar to $rP$ for some irreducible stochastic matrix $P$.

Wielandt constructed the matrix

to show that $W_n^{n^2-2n+2} > 0$, but $[W_n^{n^2-2n+1}]_{11} = 0$. Verify that this is true for $n = 4$.

In the Leslie population model, explain what happens to the vector $f(t)$ as $t \to \infty$ depending on whether $r < 1$, $r = 1$, or $r > 1$.

Use the characteristic equation to show that the Leslie matrix (from the Leslie population model) is primitive even if $b_1 = 0$ (assuming all other $b_k$'s and $s_k$'s are positive).

A matrix $A \in \mathbb {R}^{n \times n}$ is said to be essentially positive if $A$ is irreducible and $a_{ij} \geq 0$ for every $i \neq j$. Prove that each of the following statements is equivalent to saying that $A$ is essentially positive.

Let $A$ be an essentially positive matrix as defined in Exercise 8.3.12. Prove that each of the following statements is true.

Let $A \geq 0$ be an irreducible matrix, and let $a_{ij}^{(k)}$ denote entries in $A^k$. Prove that $A$ is primitive if and only if

Find the stationary distribution for

Does this stationary distribution represent a limiting distribution in the regular sense or only in the Cesaro sense?

A doubly-stochastic matrix is a nonnegative matrix $P_{n\times n}$ having all row sums as well as all column sums equal to $1$. For an irreducible $n$-state Markov chain whose transition matrix is doubly stochastic, what is the long-run proportion of time spent in each state? What form do $\lim_{k\to \infty } (I + P + \cdots + P^{k-1})/k$ and $\lim_{k\to \infty } P^k$ (if it exists) have?

Explain why $\operatorname {rk}\left(I-P\right) = n-1$ for every irreducible stochastic matrix $P_{n\times n}$. Give an example to show that this need not be the case for reducible stochastic matrices.

Prove that the left-hand Perron vector for an irreducible stochastic matrix $P_{n\times n}$ ($n > 1$) is given by

where $P_i$ is the $i$th principal minor determinant of order $n-1$ in $I-P$.

Let $P_{n\times n}$ be an irreducible stochastic matrix, and let $Q_{k\times k}$ be a principal submatrix of $I - P$, where $1 \leq k < n$. Prove that $\rho (Q) < 1$.

Let $P_{n\times n}$ be an irreducible stochastic matrix, and let $Q_{k\times k}$ be a principal submatrix of $I - P$, where $1 \leq k < n$. Explain why $Q$ is an M-matrix.

Let $P_{n\times n}$ ($n > 1$) be an irreducible stochastic matrix. Explain why all principal minors of order $1 \leq k < n$ in $I - P$ are positive.

Use the same assumptions that are used for the fail-safe system described in the worked example on two independent controls (Example 8.4.5), but use three controls, $A$, $B$, and $C$, instead of two. Determine the mean time to failure starting with three proven controls, two proven but one untested control, and three untested controls.

A mouse is placed in one chamber of the box shown in the figure below, and a cat is placed in another chamber. Each minute the doors to the chambers are opened just long enough to allow movement from one chamber to an adjacent chamber. Half of the time when the doors are opened, the cat doesn't leave the chamber it occupies. The same is true for the mouse. When either the cat or mouse moves, a door is chosen at random to pass through.

Figure 8.4.1: the mouse-in-a-box floor plan (chamber # 1 is connected to both # 2 and # 3, and # 2 is connected to # 3).