19.4 The Collatz–Wielandt Formula

Section 3 proved that the spectral radius of a non-negative matrix is an eigenvalue, and that for an irreducible matrix it comes with a positive eigenvector. It did not say how to find the number. Finding it through the characteristic polynomial means finding the largest root of a polynomial of degree $n$ , which in general has no formula in radicals once $n \ge 5$ . This section gives a way to trap $\rho(\mathbf{A})$ between two numbers read off from a single test vector, with no eigenvalue computed. Each test vector gives a lower and an upper bound, and the bounds meet exactly at the Perron vector. That turns $\rho(\mathbf{A})$ into a maximum and a minimum over vectors, much as Chapter 17 turned the eigenvalues of a Hermitian matrix into extreme values of the Rayleigh quotient (Definition 17.1.1).

Throughout, matrices have real entries, and $\ge$ , $>$ between matrices or vectors are the entrywise order of Section 1. We use one elementary fact repeatedly. If $\mathbf{A} \ge 0$ and $\mathbf{u} \ge \mathbf{u}'$ , then $\mathbf{A}\mathbf{u} \ge \mathbf{A}\mathbf{u}'$ , because each entry of $\mathbf{A}(\mathbf{u} - \mathbf{u}')$ is a sum of products of non-negative numbers. In words, a non-negative matrix preserves the order.

19.4.1. Bounds from a single test vector

If $\mathbf{v} > \mathbf{0}$ is an eigenvector for $\rho$ , then the ratios $(\mathbf{A}\mathbf{v})_i / v_i$ are all equal to $\rho$ . For a vector that is not an eigenvector, the ratios spread out. The idea of this section is that $\rho$ always lies somewhere in that spread.

Take $\mathbf{x} = \mathbf{1}$ . Then $(\mathbf{A}\mathbf{1})_i$ is the $i$ -th row sum, so the ratios are the row sums. For $\mathbf{A} = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 1 & 2 \\ 1 & 0 & 3 \end{pmatrix}$ they are $2, 3, 4$ . The characteristic polynomial is $t^3 - 4t^2 + 2t - 1$ , and $\rho(\mathbf{A}) \approx 3.51$ , which indeed lies between $2$ and $4$ . Two propositions make “lies in the spread” precise, one for each end. The upper end is the classical one.

Proposition 19.4.1 (Subinvariance)

Let $\mathbf{A} \in M_n(\mathbb{R})$ with $\mathbf{A} \ge 0$ , and let $s \in \mathbb{R}$ .

(a) If $\mathbf{x} > \mathbf{0}$ and $\mathbf{A}\mathbf{x} \le s\mathbf{x}$ , then $\rho(\mathbf{A}) \le s$ .
(b) If $\mathbf{A}$ is irreducible, $\mathbf{x} \ge \mathbf{0}$ , $\mathbf{x} \ne \mathbf{0}$ and $\mathbf{A}\mathbf{x} \le s\mathbf{x}$ , then $\rho(\mathbf{A}) \le s$ . If moreover $\mathbf{A}\mathbf{x} \ne s\mathbf{x}$ , then $\rho(\mathbf{A}) < s$ .

Idea. For (a), rescale the coordinates by the entries of $\mathbf{x}$ . In the new coordinates, $\mathbf{x}$ becomes $\mathbf{1}$ , the hypothesis says that every row sum is at most $s$ , and Chapter 16’s row-sum bound finishes the job. For (b), $\mathbf{x}$ may have zero entries, so no rescaling is possible. Instead, pair the inequality with the left Perron vector $\mathbf{w} > \mathbf{0}$ , which turns $\mathbf{w}^{\top}\mathbf{A}\mathbf{x}$ into $\rho\,\mathbf{w}^{\top}\mathbf{x}$ .

Proof.

(a) Let $\mathbf{D} = \operatorname{diag}(x_1, \dots, x_n)$ , which is invertible because every $x_i > 0$ , and put $\mathbf{C} = \mathbf{D}^{-1}\mathbf{A}\mathbf{D}$ . Its entries are $c_{ij} = a_{ij}x_j/x_i \ge 0$ , and its $i$ -th row sum is $\sum_{j=1}^{n} \frac{a_{ij}x_j}{x_i} = \frac{(\mathbf{A}\mathbf{x})_i}{x_i} \le s ,$ where the inequality divides $(\mathbf{A}\mathbf{x})_i \le s x_i$ by $x_i > 0$ . Since the entries of $\mathbf{C}$ are non-negative, its absolute row sums are its row sums, so $\left\| \mathbf{C} \right\|_{\infty} \le s$ by Theorem 16.3.3 (b). The matrices $\mathbf{A}$ and $\mathbf{C}$ are similar, so they have the same characteristic polynomial (Theorem 7.10.3) and the same spectral radius. Hence $\rho(\mathbf{A}) = \rho(\mathbf{C}) \le \left\| \mathbf{C} \right\|_{\infty} \le s$ by Corollary 16.4.2.
(b) Let $\rho = \rho(\mathbf{A})$ and let $\mathbf{w} > \mathbf{0}$ be a left eigenvector for $\rho$ (Corollary 19.3.3). Since $\mathbf{w} \ge \mathbf{0}$ and $s\mathbf{x} - \mathbf{A}\mathbf{x} \ge \mathbf{0}$ , the number $\mathbf{w}^{\top}(s\mathbf{x} - \mathbf{A}\mathbf{x})$ is $\ge 0$ . But $\mathbf{w}^{\top}\mathbf{A}\mathbf{x} = \rho\,\mathbf{w}^{\top}\mathbf{x}$ , so $\mathbf{w}^{\top}(s\mathbf{x} - \mathbf{A}\mathbf{x}) = (s - \rho)\,\mathbf{w}^{\top}\mathbf{x} .$ Choose $i$ with $x_i > 0$ . Then $\mathbf{w}^{\top}\mathbf{x} \ge w_ix_i > 0$ , so $s - \rho \ge 0$ . If moreover $\mathbf{A}\mathbf{x} \ne s\mathbf{x}$ , then $s\mathbf{x} - \mathbf{A}\mathbf{x}$ has some entry $> 0$ , and pairing with $\mathbf{w} > \mathbf{0}$ gives $\mathbf{w}^{\top}(s\mathbf{x} - \mathbf{A}\mathbf{x}) > 0$ , hence $s - \rho > 0$ . This proves the proposition.

The name comes from the inequality $\mathbf{A}\mathbf{x} \le s\mathbf{x}$ : the vector $\mathbf{x}$ is carried into something no bigger than a multiple of itself, “sub-invariant” up to the factor $s$ .

Warning. In part (a), the test vector must be positive unless $\mathbf{A}$ is irreducible. For $\mathbf{A} = \operatorname{diag}(1, 5)$ and $\mathbf{x} = \mathbf{e}_1$ , we have $\mathbf{A}\mathbf{x} = \mathbf{e}_1 \le 1 \cdot \mathbf{x}$ , yet $\rho(\mathbf{A}) = 5$ . The zero entry of $\mathbf{x}$ hides the second coordinate from the test entirely. Part (b) allows zero entries only because irreducibility guarantees that every coordinate is seen through $\mathbf{w} > \mathbf{0}$ .

The lower end needs no positivity at all, and it holds for every non-negative matrix.

Proposition 19.4.2 (Superinvariance)

Let $\mathbf{A} \in M_n(\mathbb{R})$ with $\mathbf{A} \ge 0$ , let $s \in \mathbb{R}$ , and let $\mathbf{x} \ge \mathbf{0}$ , $\mathbf{x} \ne \mathbf{0}$ , with $\mathbf{A}\mathbf{x} \ge s\mathbf{x}$ .

(a) Then $\rho(\mathbf{A}) \ge s$ .
(b) If $\mathbf{A}$ is irreducible and $\mathbf{A}\mathbf{x} \ne s\mathbf{x}$ , then $\rho(\mathbf{A}) > s$ .

Idea. For (a), the proof cannot use a similarity, because $\mathbf{x}$ may have zero entries. Instead it iterates the inequality to get $\mathbf{A}^k\mathbf{x} \ge s^k\mathbf{x}$ , so the powers of $\mathbf{A}$ grow at least like $s^k$ , and Gelfand’s formula reads $\rho(\mathbf{A})$ off that growth. For (b), pair with the left Perron vector exactly as in Proposition 19.4.1 (b).

Proof.

(a) If $s \le 0$ , then $\rho(\mathbf{A}) \ge 0 \ge s$ . Let $s > 0$ . We claim that $\mathbf{A}^k\mathbf{x} \ge s^k\mathbf{x}$ for every $k \ge 0$ . The case $k = 0$ is an equality. If it holds for $k$ , then $\mathbf{A}^{k+1}\mathbf{x} = \mathbf{A}(\mathbf{A}^k\mathbf{x}) \ge \mathbf{A}(s^k\mathbf{x}) = s^k\mathbf{A}\mathbf{x} \ge s^{k+1}\mathbf{x} ,$ where the first inequality holds because $\mathbf{A} \ge 0$ preserves the order, and the second multiplies $\mathbf{A}\mathbf{x} \ge s\mathbf{x}$ by $s^k > 0$ . This proves the claim.
Choose $i$ with $x_i = \left\| \mathbf{x} \right\|_{\infty}$ , which is positive since $\mathbf{x} \ge \mathbf{0}$ and $\mathbf{x} \ne \mathbf{0}$ . By the claim, and Theorem 16.3.2 (a), $s^k\left\| \mathbf{x} \right\|_{\infty} = s^kx_i \le (\mathbf{A}^k\mathbf{x})_i \le \left\| \mathbf{A}^k\mathbf{x} \right\|_{\infty} \le \left\| \mathbf{A}^k \right\|_{\infty}\left\| \mathbf{x} \right\|_{\infty} .$ Dividing by $\left\| \mathbf{x} \right\|_{\infty} > 0$ and taking $k$ -th roots gives $\left\| \mathbf{A}^k \right\|_{\infty}^{1/k} \ge s$ for every $k \ge 1$ . The operator norm $\left\| \cdot \right\|_{\infty}$ is a matrix norm (Theorem 16.3.2 (d)), so by Gelfand’s formula (Theorem 16.4.4) the left side tends to $\rho(\mathbf{A})$ as $k \to \infty$ . A non-strict inequality survives the limit, so $\rho(\mathbf{A}) \ge s$ .
(b) Let $\mathbf{w} > \mathbf{0}$ be a left eigenvector of $\mathbf{A}$ for $\rho = \rho(\mathbf{A})$ (Corollary 19.3.3). As in the proof of Proposition 19.4.1 (b), $\mathbf{w}^{\top}(\mathbf{A}\mathbf{x} - s\mathbf{x}) = (\rho - s)\,\mathbf{w}^{\top}\mathbf{x}$ with $\mathbf{w}^{\top}\mathbf{x} > 0$ . Now $\mathbf{A}\mathbf{x} - s\mathbf{x} \ge \mathbf{0}$ has a positive entry, so the left side is $> 0$ and $\rho > s$ .

Remark. For an irreducible $\mathbf{A}$ , part (a) also follows from the one-line pairing argument of part (b), exactly as in Proposition 19.4.1 (b). The detour through Gelfand’s formula is what makes (a) hold for every non-negative matrix, where $\mathbf{w}$ may have zero entries and $\mathbf{w}^{\top}\mathbf{x}$ may vanish.

Quick check. Let $\mathbf{A} = \begin{pmatrix} 2 & 3 \\ 1 & 0 \end{pmatrix}$ . Use $\mathbf{x} = \mathbf{1}$ and $\mathbf{x} = (3, 1)$ to bound $\rho(\mathbf{A})$ above and below. What do you conclude?

Solution. $\mathbf{A}\mathbf{1} = (5, 1)$ , so $\mathbf{A}\mathbf{1} \ge 1 \cdot \mathbf{1}$ and $\mathbf{A}\mathbf{1} \le 5 \cdot \mathbf{1}$ ; the two propositions give $1 \le \rho(\mathbf{A}) \le 5$ . Next, $\mathbf{A}(3, 1) = (9, 3) = 3 \cdot (3, 1)$ , so $3 \le \rho(\mathbf{A}) \le 3$ , that is, $\rho(\mathbf{A}) = 3$ . Indeed $p_{\mathbf{A}}(t) = t^2 - 2t - 3 = (t - 3)(t + 1)$ . A test vector that happens to be an eigenvector closes the gap completely.

19.4.2. The two Collatz–Wielandt functions

The propositions ask for a number $s$ with $\mathbf{A}\mathbf{x} \le s\mathbf{x}$ or $\mathbf{A}\mathbf{x} \ge s\mathbf{x}$ . The best such numbers for a given $\mathbf{x}$ deserve names, since they are the bounds a test vector actually delivers.

Definition 19.4.1 (Collatz–Wielandt Functions)

Let $\mathbf{A} \in M_n(\mathbb{R})$ with $\mathbf{A} \ge 0$ .

(a) For $\mathbf{x} \ge \mathbf{0}$ with $\mathbf{x} \ne \mathbf{0}$ , the lower Collatz–Wielandt function is $\underline{r}_{\mathbf{A}}(\mathbf{x}) \mathrel{:=} \min\Bigl\{ \frac{(\mathbf{A}\mathbf{x})_i}{x_i} : 1 \le i \le n,\ x_i > 0 \Bigr\} .$
(b) For $\mathbf{x} > \mathbf{0}$ , the upper Collatz–Wielandt function is $\overline{r}_{\mathbf{A}}(\mathbf{x}) \mathrel{:=} \max\Bigl\{ \frac{(\mathbf{A}\mathbf{x})_i}{x_i} : 1 \le i \le n \Bigr\} .$

In words: $\underline{r}_{\mathbf{A}}(\mathbf{x})$ is the smallest of the ratios, taken only over the coordinates where $\mathbf{x}$ is positive, and $\overline{r}_{\mathbf{A}}(\mathbf{x})$ is the largest of the ratios, for a vector with no zero coordinates. Both are well defined: the first set is non-empty because $\mathbf{x} \ne \mathbf{0}$ , and both are finite sets of real numbers.

The definition is built so that $\mathbf{A}\mathbf{x} \ge \underline{r}_{\mathbf{A}}(\mathbf{x})\,\mathbf{x} \quad (\mathbf{x} \ge \mathbf{0},\ \mathbf{x} \ne \mathbf{0}), \qquad \mathbf{A}\mathbf{x} \le \overline{r}_{\mathbf{A}}(\mathbf{x})\,\mathbf{x} \quad (\mathbf{x} > \mathbf{0}) .$ In the first, the coordinates with $x_i > 0$ satisfy $(\mathbf{A}\mathbf{x})_i \ge \underline{r}_{\mathbf{A}}(\mathbf{x})x_i$ by the choice of the minimum, and the coordinates with $x_i = 0$ satisfy $(\mathbf{A}\mathbf{x})_i \ge 0 = \underline{r}_{\mathbf{A}}(\mathbf{x})x_i$ because $\mathbf{A}\mathbf{x} \ge \mathbf{0}$ . And $\underline{r}_{\mathbf{A}}(\mathbf{x})$ is the largest $s$ with $\mathbf{A}\mathbf{x} \ge s\mathbf{x}$ , since any such $s$ is at most each ratio; likewise $\overline{r}_{\mathbf{A}}(\mathbf{x})$ is the smallest $s$ with $\mathbf{A}\mathbf{x} \le s\mathbf{x}$ .

Some examples, simplest first.

The all-ones vector. $\underline{r}_{\mathbf{A}}(\mathbf{1})$ and $\overline{r}_{\mathbf{A}}(\mathbf{1})$ are the smallest and the largest row sum of $\mathbf{A}$ .
An eigenvector. If $\mathbf{x} > \mathbf{0}$ and $\mathbf{A}\mathbf{x} = \mu\mathbf{x}$ , every ratio equals $\mu$ , so $\underline{r}_{\mathbf{A}}(\mathbf{x}) = \overline{r}_{\mathbf{A}}(\mathbf{x}) = \mu$ .
A standard basis vector. $\underline{r}_{\mathbf{A}}(\mathbf{e}_j) = a_{jj}$ : only the coordinate $j$ counts, and there the ratio is $(\mathbf{A}\mathbf{e}_j)_j/1 = a_{jj}$ .
The $1 \times 1$ case. For $\mathbf{A} = (a)$ , both functions are the constant $a = \rho(\mathbf{A})$ .

Non-example by minimal change. Try to define $\overline{r}_{\mathbf{A}}$ on vectors with zero entries in the same way as $\underline{r}_{\mathbf{A}}$ , as the maximum over the coordinates with $x_i > 0$ . For the swap $\mathbf{A} = \begin{psmallmatrix} 0 & 1 \\ 1 & 0 \end{psmallmatrix}$ and $\mathbf{x} = \mathbf{e}_1$ , we get $\mathbf{A}\mathbf{x} = \mathbf{e}_2$ , and the only ratio is $0/1 = 0$ . But $\rho(\mathbf{A}) = 1$ , so this “upper bound” is $0 < \rho$ . What fails is the inequality $\mathbf{A}\mathbf{x} \le 0 \cdot \mathbf{x}$ : in the ignored coordinate, $(\mathbf{A}\mathbf{x})_2 = 1 > 0$ . The coordinates where $\mathbf{x}$ vanishes are harmless for a lower bound, where they contribute $(\mathbf{A}\mathbf{x})_i \ge 0$ , and fatal for an upper bound.

Warning. The two functions are not mirror images. The lower function accepts every non-zero $\mathbf{x} \ge \mathbf{0}$ ; the upper one accepts only $\mathbf{x} > \mathbf{0}$ . The formula of the next subsection is therefore a maximum over the closed orthant and a minimum over the open one, and letting the minimum range over the closed orthant too would make it false, as the non-example shows.

19.4.3. The formula

With the two functions in hand, the propositions of the first subsection say that $\underline{r}_{\mathbf{A}}(\mathbf{x}) \le \rho(\mathbf{A}) \le \overline{r}_{\mathbf{A}}(\mathbf{x})$ , and the second example shows both bounds attained at a positive eigenvector. For an irreducible matrix, such an eigenvector exists (Theorem 19.3.2), and more is true: nothing else attains either bound.

Theorem 19.4.3 (Collatz–Wielandt Formula)

Let $\mathbf{A} \in M_n(\mathbb{R})$ be non-negative and irreducible, with Perron vector $\mathbf{v}$ (Definition 19.3.1). Then $\rho(\mathbf{A}) = \max_{\substack{\mathbf{x} \ge \mathbf{0} \\ \mathbf{x} \ne \mathbf{0}}} \underline{r}_{\mathbf{A}}(\mathbf{x}) = \min_{\mathbf{x} > \mathbf{0}} \overline{r}_{\mathbf{A}}(\mathbf{x}) ,$ both extreme values are attained at $\mathbf{x} = \mathbf{v}$ , and they are attained only at the positive multiples of $\mathbf{v}$ : if $\mathbf{x} \ge \mathbf{0}$ , $\mathbf{x} \ne \mathbf{0}$ and $\underline{r}_{\mathbf{A}}(\mathbf{x}) = \rho(\mathbf{A})$ , or if $\mathbf{x} > \mathbf{0}$ and $\overline{r}_{\mathbf{A}}(\mathbf{x}) = \rho(\mathbf{A})$ , then $\mathbf{x}$ is a positive multiple of $\mathbf{v}$ .

Idea. The inequalities are the two propositions, applied with the best constants $\underline{r}_{\mathbf{A}}(\mathbf{x})$ and $\overline{r}_{\mathbf{A}}(\mathbf{x})$ . Attainment is the eigenvector example. For the “only” clause, use the strict halves of the propositions: if $\mathbf{x}$ attains a bound without being an eigenvector, the strict inequality would push $\rho$ strictly past itself. The usual proofs of this formula start from the optimization problem and need a compactness argument, which is delicate for a matrix with zero entries: then $\underline{r}_{\mathbf{A}}$ can jump where a coordinate of $\mathbf{x}$ becomes $0$ , whereas for a positive matrix it is continuous. Here the compactness was spent once, in Sections 1 and 3, and it has already produced the maximizer.

Proof. Let $\rho = \rho(\mathbf{A})$ .

The inequalities. Let $\mathbf{x} \ge \mathbf{0}$ , $\mathbf{x} \ne \mathbf{0}$ . Since $\mathbf{A}\mathbf{x} \ge \underline{r}_{\mathbf{A}}(\mathbf{x})\,\mathbf{x}$ , Proposition 19.4.2 (a) gives $\underline{r}_{\mathbf{A}}(\mathbf{x}) \le \rho$ . Let $\mathbf{x} > \mathbf{0}$ . Since $\mathbf{A}\mathbf{x} \le \overline{r}_{\mathbf{A}}(\mathbf{x})\,\mathbf{x}$ , Proposition 19.4.1 (a) gives $\rho \le \overline{r}_{\mathbf{A}}(\mathbf{x})$ .

Attainment. By Theorem 19.3.2 (a) and Definition 19.3.1, $\mathbf{v} > \mathbf{0}$ and $\mathbf{A}\mathbf{v} = \rho\mathbf{v}$ , so every ratio $(\mathbf{A}\mathbf{v})_i/v_i$ equals $\rho$ , and $\underline{r}_{\mathbf{A}}(\mathbf{v}) = \overline{r}_{\mathbf{A}}(\mathbf{v}) = \rho$ . With the inequalities, this shows that $\rho$ is the maximum of $\underline{r}_{\mathbf{A}}$ and the minimum of $\overline{r}_{\mathbf{A}}$ .

Only at multiples of $\mathbf{v}$ . Let $\mathbf{x} \ge \mathbf{0}$ , $\mathbf{x} \ne \mathbf{0}$ , with $\underline{r}_{\mathbf{A}}(\mathbf{x}) = \rho$ , so that $\mathbf{A}\mathbf{x} \ge \rho\mathbf{x}$ . If $\mathbf{A}\mathbf{x} \ne \rho\mathbf{x}$ , then Proposition 19.4.2 (b) with $s = \rho$ gives $\rho > \rho$ , which is absurd. Hence $\mathbf{A}\mathbf{x} = \rho\mathbf{x}$ , and $\mathbf{x}$ is a positive multiple of $\mathbf{v}$ by Theorem 19.3.2 (c). If instead $\mathbf{x} > \mathbf{0}$ and $\overline{r}_{\mathbf{A}}(\mathbf{x}) = \rho$ , then $\mathbf{A}\mathbf{x} \le \rho\mathbf{x}$ , and Proposition 19.4.1 (b) rules out $\mathbf{A}\mathbf{x} \ne \rho\mathbf{x}$ in the same way. Conversely, $\underline{r}_{\mathbf{A}}(c\mathbf{v}) = \overline{r}_{\mathbf{A}}(c\mathbf{v}) = \rho$ for $c > 0$ , since the ratios do not change when $\mathbf{x}$ is scaled. This proves the theorem.

So $\rho(\mathbf{A})$ is characterized without eigenvalues: it is the largest growth factor that $\mathbf{A}$ guarantees in every coordinate of some non-negative vector, and the smallest growth factor that bounds every coordinate of some positive vector.

Remark. Irreducibility is used only for the attainment of the minimum and for the “only” clause. For every $\mathbf{A} \ge 0$ , the inequalities hold by the same two propositions, and the maximum is still attained, at the non-negative eigenvector $\mathbf{x}$ of Theorem 19.3.1: every ratio over a coordinate with $x_i > 0$ equals $\rho$ . The minimum can fail to be attained; Exercise C3 at the end of this section works out an example.

19.4.4. Row sums and column sums

The simplest test vector is $\mathbf{1}$ , and the transpose supplies a second family of bounds for free. For a non-negative matrix, write $r_i = \sum_j a_{ij}$ for the $i$ -th row sum and $c_j = \sum_i a_{ij}$ for the $j$ -th column sum.

Corollary 19.4.4 (Row and Column Sums Bound the Spectral Radius)

Let $\mathbf{A} \in M_n(\mathbb{R})$ with $\mathbf{A} \ge 0$ .

(a) $\min_i r_i \le \rho(\mathbf{A}) \le \max_i r_i$ and $\min_j c_j \le \rho(\mathbf{A}) \le \max_j c_j$ .
(b) If $\mathbf{A}$ is irreducible, then $\rho(\mathbf{A}) = \min_i r_i$ if and only if $\rho(\mathbf{A}) = \max_i r_i$ , if and only if all the row sums are equal. The same holds for the column sums.

Idea. Use the test vector $\mathbf{1}$ , whose ratios are the row sums: the two propositions give (a) for rows, and the “only” clause of Theorem 19.4.3 gives (b), since equality at $\mathbf{1}$ makes $\mathbf{1}$ an eigenvector. For columns, run the same argument on $\mathbf{A}^{\top}$ , which has the same spectral radius.

Proof.

(a) $\mathbf{A}\mathbf{1}$ is the vector of row sums, so $\mathbf{A}\mathbf{1} \ge (\min_i r_i)\mathbf{1}$ and $\mathbf{A}\mathbf{1} \le (\max_i r_i)\mathbf{1}$ , with $\mathbf{1} > \mathbf{0}$ . Proposition 19.4.2 (a) and Proposition 19.4.1 (a) give the row bounds. The column sums of $\mathbf{A}$ are the row sums of $\mathbf{A}^{\top} \ge 0$ , and $\rho(\mathbf{A}^{\top}) = \rho(\mathbf{A})$ because $p_{\mathbf{A}^{\top}} = p_{\mathbf{A}}$ (Proposition 9.10.5 (b)); so the row bounds for $\mathbf{A}^{\top}$ are the column bounds for $\mathbf{A}$ .
(b) If all row sums equal $r$ , then $\min_i r_i = \max_i r_i = r$ , and (a) gives $\rho(\mathbf{A}) = r$ . Conversely, suppose $\rho(\mathbf{A}) = \min_i r_i = \underline{r}_{\mathbf{A}}(\mathbf{1})$ . By the “only” clause of Theorem 19.4.3, $\mathbf{1}$ is a positive multiple of the Perron vector, so $\mathbf{A}\mathbf{1} = \rho(\mathbf{A})\mathbf{1}$ , and every row sum equals $\rho(\mathbf{A})$ . The same argument with $\overline{r}_{\mathbf{A}}(\mathbf{1}) = \max_i r_i$ handles the maximum. For the columns, apply this to $\mathbf{A}^{\top}$ , which is irreducible with $\rho(\mathbf{A}^{\top}) = \rho(\mathbf{A})$ by Corollary 19.3.3 (a).

Compare this with Chapter 16. Corollary 16.4.2 gives $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|_{\infty}$ and $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|_1$ for every complex matrix, and for $\mathbf{A} \ge 0$ these are exactly the upper bounds in (a), since the absolute row and column sums are then the row and column sums. What non-negativity adds is the lower bound. For a matrix with entries of both signs there is none: $\mathbf{M} = \begin{pmatrix} 1 & -1 \\ 1 & -1 \end{pmatrix}$ has absolute row sums $2, 2$ , but $\mathbf{M}^2 = 0$ , so every eigenvalue $\lambda$ satisfies $\lambda^2 = 0$ and $\rho(\mathbf{M}) = 0$ . Nor do the signed row sums help: $\mathbf{M}' = \begin{pmatrix} 7 & -3 \\ 19 & -7 \end{pmatrix}$ has row sums $4$ and $12$ , both larger than $\rho(\mathbf{M}') = 2\sqrt2$ , since $p_{\mathbf{M}'}(t) = t^2 + 8$ .

The equality clause (b) genuinely needs irreducibility. The reducible matrix $\operatorname{diag}(1, 2)$ has $\rho = 2 = \max_i r_i$ with unequal row sums, and $\begin{psmallmatrix} 1 & 0 \\ 1 & 1 \end{psmallmatrix}$ has $\rho = 1 = \min_i r_i$ with row sums $1$ and $2$ .

Example (Four bounds, and which one to keep)

Bound $\rho(\mathbf{A})$ above and below using row and column sums, for $\mathbf{A} = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 1 & 2 \\ 1 & 0 & 3 \end{pmatrix} .$

Solution. The row sums are $2, 3, 4$ and the column sums are $1, 2, 6$ . By Corollary 19.4.4 (a), $2 \le \rho(\mathbf{A}) \le 4$ from the rows and $1 \le \rho(\mathbf{A}) \le 6$ from the columns. Keep the larger lower bound and the smaller upper bound: $2 \le \rho(\mathbf{A}) \le 4$ . Chapter 16’s Corollary 16.4.2 gives only the upper bound $4$ .

The matrix is irreducible: $(\mathbf{I} + \mathbf{A})^2 = \begin{psmallmatrix} 2 & 3 & 7 \\ 2 & 4 & 12 \\ 5 & 1 & 17 \end{psmallmatrix} > 0$ (Theorem 19.2.6). Its row sums are not all equal, so by Corollary 19.4.4 (b) both bounds are strict: $2 < \rho(\mathbf{A}) < 4$ .

19.4.5. Estimating the spectral radius

A bracket of width $2$ is crude. The Collatz–Wielandt formula says that a better test vector gives a better bracket, and a test vector close to the Perron vector gives a very narrow one. There is a cheap way to improve a test vector: multiply it by $\mathbf{A}$ .

The improvement is guaranteed. Let $\mathbf{x} > \mathbf{0}$ , and suppose $\mathbf{A}\mathbf{x} > \mathbf{0}$ too. Since $\mathbf{A}$ preserves the order, $\mathbf{A}(\mathbf{A}\mathbf{x}) \ge \mathbf{A}\bigl(\underline{r}_{\mathbf{A}}(\mathbf{x})\,\mathbf{x}\bigr) = \underline{r}_{\mathbf{A}}(\mathbf{x})\,\mathbf{A}\mathbf{x} ,$ so $\underline{r}_{\mathbf{A}}(\mathbf{A}\mathbf{x}) \ge \underline{r}_{\mathbf{A}}(\mathbf{x})$ , because $\underline{r}_{\mathbf{A}}(\mathbf{A}\mathbf{x})$ is the largest $s$ with $\mathbf{A}(\mathbf{A}\mathbf{x}) \ge s\,\mathbf{A}\mathbf{x}$ . In the same way $\overline{r}_{\mathbf{A}}(\mathbf{A}\mathbf{x}) \le \overline{r}_{\mathbf{A}}(\mathbf{x})$ . So the brackets from $\mathbf{x}, \mathbf{A}\mathbf{x}, \mathbf{A}^2\mathbf{x}, \dots$ are nested, as long as each $\mathbf{A}^k\mathbf{x} > \mathbf{0}$ : each lower bound is at least the previous one, and each upper bound is at most the previous one. The condition holds whenever $\mathbf{x} > \mathbf{0}$ and $\mathbf{A}$ is irreducible with $n \ge 2$ , since no row of $\mathbf{A}$ is then zero (a zero row, moved to the bottom by a permutation, would give the block form of Definition 19.2.3 with $k = n - 1$ ), so every entry of $\mathbf{A}\mathbf{y}$ is positive when $\mathbf{y} > \mathbf{0}$ .

Example (Trapping the spectral radius)

For the matrix $\mathbf{A}$ of Example (Four bounds, and which one to keep), compute the brackets $[\underline{r}_{\mathbf{A}}(\mathbf{x}), \overline{r}_{\mathbf{A}}(\mathbf{x})]$ for $\mathbf{x} = \mathbf{1}, \mathbf{A}\mathbf{1}, \mathbf{A}^2\mathbf{1}, \mathbf{A}^3\mathbf{1}, \mathbf{A}^4\mathbf{1}$ . Hence give $\rho(\mathbf{A})$ to two decimal places, and check the answer against the characteristic polynomial.

Solution. Each step multiplies the previous vector by $\mathbf{A}$ , whose rows are $(0, 1, 1)$ , $(0, 1, 2)$ , $(1, 0, 3)$ . The ratios are taken coordinate by coordinate.

$\mathbf{x}$	$\mathbf{A}\mathbf{x}$	ratios $(\mathbf{A}\mathbf{x})_i/x_i$	bracket
$(1, 1, 1)$	$(2, 3, 4)$	$2,\ 3,\ 4$	$[2,\ 4]$
$(2, 3, 4)$	$(7, 11, 14)$	$\tfrac72,\ \tfrac{11}{3},\ \tfrac72$	$[\tfrac72,\ \tfrac{11}{3}]$
$(7, 11, 14)$	$(25, 39, 49)$	$\tfrac{25}{7},\ \tfrac{39}{11},\ \tfrac72$	$[\tfrac72,\ \tfrac{25}{7}]$
$(25, 39, 49)$	$(88, 137, 172)$	$\tfrac{88}{25},\ \tfrac{137}{39},\ \tfrac{172}{49}$	$[\tfrac{172}{49},\ \tfrac{88}{25}]$
$(88, 137, 172)$	$(309, 481, 604)$	$\tfrac{309}{88},\ \tfrac{481}{137},\ \tfrac{151}{43}$	$[\tfrac{481}{137},\ \tfrac{151}{43}]$

For instance, in the last row $\mathbf{A}(88, 137, 172) = (137 + 172,\ 137 + 344,\ 88 + 516) = (309, 481, 604)$ , and $\tfrac{604}{172} = \tfrac{151}{43}$ . All five test vectors are positive, so each bracket is valid by Theorem 19.4.3, and they are nested, as the argument before the example predicts. The five brackets have widths $2$ , $\tfrac16$ , $\tfrac{1}{14}$ , $\tfrac{12}{1225}$ and $\tfrac{4}{5891}$ . Since $\tfrac{481}{137} = 3.51094\ldots$ and $\tfrac{151}{43} = 3.51162\ldots$ , $3.5109 < \rho(\mathbf{A}) < 3.5117 ,$ and therefore $\rho(\mathbf{A}) = 3.51$ to two decimal places.

Check. Expanding $\det(t\mathbf{I} - \mathbf{A})$ along the first column gives $\begin{aligned} p_{\mathbf{A}}(t) &= t\bigl((t - 1)(t - 3)\bigr) - \bigl((-1)(-2) - (-1)(t - 1)\bigr) \\ &= t^3 - 4t^2 + 2t - 1 . \end{aligned}$ Exactly, $p_{\mathbf{A}}(3.51) = -0.016849 < 0$ and $p_{\mathbf{A}}(3.512) = 0.004937728 > 0$ . A real polynomial that changes sign on an interval has a root there, by the intermediate value theorem, fact (A5) of Chapter 16’s introduction. So $p_{\mathbf{A}}$ has a real root between $3.51$ and $3.512$ , consistent with the bracket.

Two things about this computation deserve a comment. First, every number in it is a certified bound, not an approximation whose error is unknown: $\rho(\mathbf{A}) \ge \tfrac{172}{49}$ is a theorem about this matrix, proved by one multiplication. Second, the iteration $\mathbf{x} \mapsto \mathbf{A}\mathbf{x}$ is the power method, and Chapter 24 studies how fast it converges. Nesting alone does not make the brackets shrink to a point, as the next warning shows.

Warning. The brackets need not close up. For the swap $\mathbf{A} = \begin{psmallmatrix} 0 & 1 \\ 1 & 0 \end{psmallmatrix}$ , which is irreducible with $\rho = 1$ , start from $\mathbf{x} = (1, 2)$ . Then $\mathbf{A}\mathbf{x} = (2, 1)$ , with ratios $2$ and $\tfrac12$ , and $\mathbf{A}^2\mathbf{x} = \mathbf{x}$ . The bracket is $[\tfrac12, 2]$ at every step and never improves. The iteration only swaps the two coordinates, because the eigenvalue $-1$ has the same modulus as $\rho$ . Section 5 studies the irreducible matrices whose other eigenvalues all have modulus strictly less than $\rho$ .

19.4.6. Exercises

A. Check your understanding

Exercise (A1)

(a) Define $\underline{r}_{\mathbf{A}}(\mathbf{x})$ and $\overline{r}_{\mathbf{A}}(\mathbf{x})$ , and state on which vectors each is defined.
(b) For $\mathbf{A} = \begin{psmallmatrix} 1 & 2 \\ 3 & 0 \end{psmallmatrix}$ , compute $\underline{r}_{\mathbf{A}}(\mathbf{1})$ and $\overline{r}_{\mathbf{A}}(\mathbf{1})$ . What do you conclude about $\rho(\mathbf{A})$ ?
(c) True or false: if $\mathbf{A} \ge 0$ , $\mathbf{x} \ge \mathbf{0}$ , $\mathbf{x} \ne \mathbf{0}$ and $\mathbf{A}\mathbf{x} \le 2\mathbf{x}$ , then $\rho(\mathbf{A}) \le 2$ . Justify your answer.
(d) True or false: for every $\mathbf{A} \ge 0$ , $\rho(\mathbf{A})$ is at least the smallest row sum of $\mathbf{A}$ . Justify your answer.
(e) Name the result from Chapter 16 that gives the upper bound in Corollary 19.4.4 (a), and say what that result does not give.

Solution.

(a) See Definition 19.4.1: $\underline{r}_{\mathbf{A}}(\mathbf{x})$ is the minimum of $(\mathbf{A}\mathbf{x})_i/x_i$ over the indices with $x_i > 0$ , defined for $\mathbf{x} \ge \mathbf{0}$ , $\mathbf{x} \ne \mathbf{0}$ ; $\overline{r}_{\mathbf{A}}(\mathbf{x})$ is the maximum of $(\mathbf{A}\mathbf{x})_i/x_i$ over all indices, defined only for $\mathbf{x} > \mathbf{0}$ .
(b) $\mathbf{A}\mathbf{1} = (3, 3)$ , so both equal $3$ , and $\rho(\mathbf{A}) = 3$ by Proposition 19.4.2 (a) and Proposition 19.4.1 (a). Indeed $p_{\mathbf{A}}(t) = t^2 - t - 6 = (t - 3)(t + 2)$ .
(c) False: $\mathbf{A} = \operatorname{diag}(1, 5)$ and $\mathbf{x} = \mathbf{e}_1$ give $\mathbf{A}\mathbf{x} = \mathbf{x} \le 2\mathbf{x}$ , but $\rho(\mathbf{A}) = 5$ . It becomes true if $\mathbf{x} > \mathbf{0}$ (Proposition 19.4.1 (a)) or if $\mathbf{A}$ is irreducible (Proposition 19.4.1 (b)).
(d) True, by Corollary 19.4.4 (a), which rests on Proposition 19.4.2 (a) with $\mathbf{x} = \mathbf{1}$ . No irreducibility is needed.
(e) Corollary 16.4.2, which bounds $\rho$ above by the largest absolute row sum and the largest absolute column sum of any complex matrix. It gives no lower bound, and none exists for matrices with entries of both signs: $\begin{psmallmatrix} 1 & -1 \\ 1 & -1 \end{psmallmatrix}$ has $\rho = 0$ .

B. Practice

Exercise (B1: A certified bracket)

Let $\mathbf{A} = \begin{pmatrix} 1 & 2 & 0 \\ 0 & 1 & 3 \\ 1 & 0 & 2 \end{pmatrix} .$ Show that $\mathbf{A}$ is irreducible. Compute the brackets $[\underline{r}_{\mathbf{A}}(\mathbf{x}), \overline{r}_{\mathbf{A}}(\mathbf{x})]$ for $\mathbf{x} = \mathbf{1}$ and for $\mathbf{x} = (10, 11, 8)$ . Hence show that $3.18 < \rho(\mathbf{A}) \le 3.25$ , and check this against $p_{\mathbf{A}}$ .

Solution. Irreducible. $\mathbf{I} + \mathbf{A} = \begin{psmallmatrix} 2 & 2 & 0 \\ 0 & 2 & 3 \\ 1 & 0 & 3 \end{psmallmatrix}$ , and $(\mathbf{I} + \mathbf{A})^2 = \begin{psmallmatrix} 4 & 8 & 6 \\ 3 & 4 & 15 \\ 5 & 2 & 9 \end{psmallmatrix} > 0$ , so $\mathbf{A}$ is irreducible by Theorem 19.2.6.

Brackets. $\mathbf{A}\mathbf{1} = (3, 4, 3)$ , giving $[3, 4]$ . Next, $\mathbf{A}(10, 11, 8) = (10 + 22,\ 11 + 24,\ 10 + 16) = (32, 35, 26) ,$ with ratios $\tfrac{32}{10} = 3.2$ , $\tfrac{35}{11} = 3.1818\ldots$ , $\tfrac{26}{8} = 3.25$ . The bracket is $[\tfrac{35}{11}, \tfrac{13}{4}]$ . By Theorem 19.4.3, $\tfrac{35}{11} \le \rho(\mathbf{A}) \le \tfrac{13}{4}$ . Since $\tfrac{35}{11} > 3.18$ , this gives $3.18 < \rho(\mathbf{A}) \le 3.25$ .

Check. Expanding along the first row, $\begin{aligned} p_{\mathbf{A}}(t) &= (t - 1)\bigl((t - 1)(t - 2)\bigr) + 2\bigl(0 - 3\bigr) \\ &= t^3 - 4t^2 + 5t - 8 . \end{aligned}$ Then $p_{\mathbf{A}}(\tfrac{35}{11}) = -\tfrac{498}{1331} < 0$ and $p_{\mathbf{A}}(\tfrac{13}{4}) = \tfrac{21}{64} > 0$ , so by the intermediate value theorem (fact (A5) of Chapter 16’s introduction) $p_{\mathbf{A}}$ has a root in the bracket, consistent with the estimate. (In fact $\rho(\mathbf{A}) \approx 3.219$ .)

Exercise (B2: When a sum bound is exact)

For each matrix, give the bounds of Corollary 19.4.4 (a) from rows and from columns, and decide whether they determine $\rho$ . Justify your answers. $\text{(a)}\ \begin{pmatrix} 1 & 2 & 1 \\ 3 & 0 & 1 \\ 0 & 2 & 2 \end{pmatrix} \qquad \text{(b)}\ \begin{pmatrix} 1 & 3 \\ 2 & 0 \end{pmatrix} \qquad \text{(c)}\ \begin{pmatrix} 2 & 0 \\ 5 & 3 \end{pmatrix}$

Solution.

(a) Row sums $4, 4, 4$ ; column sums $4, 4, 4$ . Both bracket $\rho$ in $[4, 4]$ , so $\rho = 4$ , with eigenvector $\mathbf{1}$ .
(b) Row sums $4, 2$ , giving $[2, 4]$ ; column sums $3, 3$ , giving $[3, 3]$ . So $\rho = 3$ , with $\mathbf{1}$ as a left eigenvector: $\mathbf{1}^{\top}\mathbf{A} = (3, 3)$ . Check: $p(t) = t^2 - t - 6 = (t - 3)(t + 2)$ . The matrix is irreducible ( $\mathbf{I} + \mathbf{A} > 0$ ), and the row sums are unequal, so by Corollary 19.4.4 (b) the row bracket is strict, $2 < 3 < 4$ , as it is.
(c) Row sums $2, 8$ , giving $[2, 8]$ ; column sums $7, 3$ , giving $[3, 7]$ . Together, $3 \le \rho \le 7$ . The matrix is lower triangular, so its eigenvalues are $2$ and $3$ and $\rho = 3$ , the smallest column sum, although the column sums are unequal. This does not contradict Corollary 19.4.4 (b): the matrix is reducible, since $\mathbf{I} + \mathbf{A}$ has a zero entry in position $(1, 2)$ and $n - 1 = 1$ .

Exercise (B3: A weighted test vector)

Let $\mathbf{A} = \frac{1}{10}\begin{pmatrix} 5 & 20 \\ 1 & 2 \end{pmatrix} .$ Show that neither the row sums nor the column sums prove $\rho(\mathbf{A}) < 1$ . Then use the test vector $\mathbf{x} = (5, 1)$ to prove $\rho(\mathbf{A}) \le \tfrac{9}{10}$ . Hence deduce that $\mathbf{A}^k \to 0$ as $k \to \infty$ .

Solution. The row sums are $\tfrac{25}{10}$ and $\tfrac{3}{10}$ , and the column sums $\tfrac{6}{10}$ and $\tfrac{22}{10}$ . Each upper bound in Corollary 19.4.4 (a) exceeds $1$ , so neither proves $\rho(\mathbf{A}) < 1$ .

With $\mathbf{x} = (5, 1) > \mathbf{0}$ , $\mathbf{A}\mathbf{x} = \tfrac{1}{10}(25 + 20,\ 5 + 2) = \bigl(\tfrac{45}{10},\ \tfrac{7}{10}\bigr) ,$ and the ratios are $\tfrac{45}{50} = \tfrac{9}{10}$ and $\tfrac{7}{10}$ . So $\mathbf{A}\mathbf{x} \le \tfrac{9}{10}\mathbf{x}$ , and Proposition 19.4.1 (a) gives $\rho(\mathbf{A}) \le \tfrac{9}{10} < 1$ . Hence $\mathbf{A}^k \to 0$ by Corollary 16.4.5 (a).

C. Going deeper

Exercise (C1: Lower bounds from single entries)

Let $\mathbf{A} \in M_n(\mathbb{R})$ with $\mathbf{A} \ge 0$ , not necessarily irreducible.

(a) Prove that $\rho(\mathbf{A}) \ge a_{ii}$ for every $i$ .
(b) Prove that $\rho(\mathbf{A}) \ge \sqrt{a_{ij}a_{ji}}$ for every $i \ne j$ .
(c) Hence show that $\begin{psmallmatrix} 1 & 4 & 0 \\ 9 & 2 & 0 \\ 0 & 0 & 5 \end{psmallmatrix}$ has $\rho \ge 6$ , and check this exactly.

Hint: choose a test vector supported on $\{i\}$ or on $\{i, j\}$ .

Solution.

(a) Take $\mathbf{x} = \mathbf{e}_i$ . Then $(\mathbf{A}\mathbf{e}_i)_i = a_{ii}$ and every other coordinate of $\mathbf{A}\mathbf{e}_i$ is $\ge 0$ , so $\mathbf{A}\mathbf{e}_i \ge a_{ii}\mathbf{e}_i$ , and Proposition 19.4.2 (a) gives $\rho(\mathbf{A}) \ge a_{ii}$ .
(b) If $a_{ij}a_{ji} = 0$ , the claim is $\rho(\mathbf{A}) \ge 0$ , which holds. Otherwise put $s = \sqrt{a_{ij}a_{ji}} > 0$ and $\mathbf{x} = \sqrt{a_{ij}}\,\mathbf{e}_i + \sqrt{a_{ji}}\,\mathbf{e}_j \ge \mathbf{0}$ , $\mathbf{x} \ne \mathbf{0}$ . Dropping non-negative terms, $(\mathbf{A}\mathbf{x})_i \ge a_{ij}\sqrt{a_{ji}} = s\sqrt{a_{ij}} = s x_i , \qquad (\mathbf{A}\mathbf{x})_j \ge a_{ji}\sqrt{a_{ij}} = s\sqrt{a_{ji}} = s x_j ,$ and the other coordinates satisfy $(\mathbf{A}\mathbf{x})_k \ge 0 = s x_k$ . So $\mathbf{A}\mathbf{x} \ge s\mathbf{x}$ , and Proposition 19.4.2 (a) gives $\rho(\mathbf{A}) \ge s$ .
(c) With $i = 1$ , $j = 2$ : $\sqrt{4 \cdot 9} = 6$ , so $\rho \ge 6$ . The diagonal bound of (a) gives only $5$ . Exactly: the matrix is block diagonal, the $2 \times 2$ block has $p(t) = t^2 - 3t - 34$ with roots $\frac{3 \pm \sqrt{145}}{2}$ , and the $1 \times 1$ block contributes $5$ . So $\rho = \frac{3 + \sqrt{145}}{2} \approx 7.52 \ge 6$ .

Exercise (C2: Strict monotonicity)

Let $\mathbf{A}, \mathbf{B} \in M_n(\mathbb{R})$ with $0 \le \mathbf{A} \le \mathbf{B}$ and $\mathbf{A} \ne \mathbf{B}$ .

(a) Prove that if $\mathbf{A}$ is irreducible, then so is $\mathbf{B}$ , and $\rho(\mathbf{A}) < \rho(\mathbf{B})$ .
(b) Show by an example that the strict inequality can fail if $\mathbf{A}$ is reducible.

Solution.

(a) Since $\mathbf{I} + \mathbf{B} \ge \mathbf{I} + \mathbf{A} \ge 0$ and a non-negative matrix preserves the order, induction on $k$ gives $(\mathbf{I} + \mathbf{B})^k \ge (\mathbf{I} + \mathbf{A})^k$ : indeed $(\mathbf{I} + \mathbf{B})^{k+1} = (\mathbf{I} + \mathbf{B})(\mathbf{I} + \mathbf{B})^k \ge (\mathbf{I} + \mathbf{B})(\mathbf{I} + \mathbf{A})^k \ge (\mathbf{I} + \mathbf{A})^{k+1}$ , column by column. With $k = n - 1$ , $(\mathbf{I} + \mathbf{B})^{n-1} \ge (\mathbf{I} + \mathbf{A})^{n-1} > 0$ , so $\mathbf{B}$ is irreducible by Theorem 19.2.6.
Let $\mathbf{v} > \mathbf{0}$ be the Perron vector of $\mathbf{A}$ . Then $\mathbf{B}\mathbf{v} = \mathbf{A}\mathbf{v} + (\mathbf{B} - \mathbf{A})\mathbf{v} \ge \mathbf{A}\mathbf{v} = \rho(\mathbf{A})\mathbf{v}$ . Moreover $\mathbf{B} - \mathbf{A} \ge 0$ has some entry $b_{ij} - a_{ij} > 0$ , and then $\bigl((\mathbf{B} - \mathbf{A})\mathbf{v}\bigr)_i \ge (b_{ij} - a_{ij})v_j > 0$ , so $\mathbf{B}\mathbf{v} \ne \rho(\mathbf{A})\mathbf{v}$ . By Proposition 19.4.2 (b) applied to the irreducible $\mathbf{B}$ , $\rho(\mathbf{B}) > \rho(\mathbf{A})$ .
(b) $\mathbf{A} = \operatorname{diag}(1, 0)$ and $\mathbf{B} = \operatorname{diag}(1, \tfrac12)$ satisfy $0 \le \mathbf{A} \le \mathbf{B}$ , $\mathbf{A} \ne \mathbf{B}$ , and $\rho(\mathbf{A}) = \rho(\mathbf{B}) = 1$ .

Exercise (C3: The minimum need not be attained)

Let $\mathbf{A} = \begin{psmallmatrix} 1 & 1 \\ 0 & 1 \end{psmallmatrix}$ .

(a) Show that $\mathbf{A}$ is reducible and $\rho(\mathbf{A}) = 1$ .
(b) Show that $\overline{r}_{\mathbf{A}}(\mathbf{x}) > 1$ for every $\mathbf{x} > \mathbf{0}$ , so that $\min_{\mathbf{x} > \mathbf{0}}\overline{r}_{\mathbf{A}}(\mathbf{x})$ does not exist.
(c) Show that nevertheless $\overline{r}_{\mathbf{A}}(\mathbf{x})$ takes values as close to $1$ as we like, and that $\max_{\mathbf{x} \ge \mathbf{0}, \mathbf{x} \ne \mathbf{0}}\underline{r}_{\mathbf{A}}(\mathbf{x}) = 1$ is attained.

Solution.

(a) $\mathbf{I} + \mathbf{A} = \begin{psmallmatrix} 2 & 1 \\ 0 & 2 \end{psmallmatrix}$ has a zero entry, so $\mathbf{A}$ is reducible (Theorem 19.2.6 with $n = 2$ ). It is triangular with diagonal $1, 1$ , so $\rho(\mathbf{A}) = 1$ (Theorem 9.7.4 (b)).
(b) For $\mathbf{x} = (x_1, x_2) > \mathbf{0}$ , $\mathbf{A}\mathbf{x} = (x_1 + x_2,\ x_2)$ , with ratios $1 + x_2/x_1$ and $1$ . Hence $\overline{r}_{\mathbf{A}}(\mathbf{x}) = 1 + x_2/x_1 > 1$ . Suppose some $\mathbf{x} > \mathbf{0}$ gave the smallest value $m = 1 + x_2/x_1$ . Then $\mathbf{x}' = (x_1, x_2/2) > \mathbf{0}$ gives $\overline{r}_{\mathbf{A}}(\mathbf{x}') = 1 + x_2/(2x_1) < m$ , a contradiction. So there is no minimum.
(c) For $\mathbf{x} = (1, t)$ with $t > 0$ , $\overline{r}_{\mathbf{A}}(\mathbf{x}) = 1 + t$ , which is as close to $1$ as we like. For the lower function, $\mathbf{x} = \mathbf{e}_1$ gives $\mathbf{A}\mathbf{e}_1 = \mathbf{e}_1$ , so $\underline{r}_{\mathbf{A}}(\mathbf{e}_1) = 1 = \rho(\mathbf{A})$ ; since every value of $\underline{r}_{\mathbf{A}}$ is $\le \rho(\mathbf{A})$ by Proposition 19.4.2 (a), the maximum is attained at $\mathbf{e}_1$ , which is the non-negative eigenvector of Theorem 19.3.1.