16.4 The Spectral Radius

Every criterion in Chapter 10 §10 began by looking at the largest modulus of an eigenvalue, and that section gave the number a name in passing — the spectral radius — without a numbered definition and without a single norm available to compare it with. It also left a note: “Chapter 16 measures matrices by norms, proves that the spectral radius never exceeds the norm of $\mathbf{A}$ induced by any vector norm, and recovers $\rho(\mathbf{A})$ as a limit built from the norms of the powers $\mathbf{A}^{m}$ .” This section pays that note in full, and is careful about what is new when it does.

Throughout, matrices are complex. A real matrix is read inside $M_n(\mathbb{C})$ , exactly as Chapter 10 §10 read it when it counted eigenvalues; over $\mathbb{R}$ a matrix may have no eigenvalue at all, and then there is nothing to take the largest modulus of.

16.4.1. The number Chapter 10 named

The spectral radius is the radius of the smallest disk about the origin that holds the whole spectrum.

Definition 16.4.1 (Spectral Radius)

Let $\mathbf{A} \in M_n(\mathbb{C})$ with $n \ge 1$ . The spectral radius of $\mathbf{A}$ is

$\rho(\mathbf{A}) \mathrel{:=} \max\{\,\lvert\lambda\rvert : \lambda \in \operatorname{spec}(\mathbf{A})\,\} .$

For an operator $T$ on a non-zero finite-dimensional complex vector space, $\rho(T)$ is defined by the same formula with $\operatorname{spec}(T)$ in place of $\operatorname{spec}(\mathbf{A})$ .

The maximum is over a finite non-empty set, so it exists with no analysis at all: $\operatorname{spec}(\mathbf{A})$ is the root set of the characteristic polynomial $p_{\mathbf{A}}$ , which is non-empty by the Fundamental Theorem of Algebra (Theorem 6.5.1) and has at most $n$ elements. It is the largest modulus of an eigenvalue, not the largest eigenvalue: over $\mathbb{C}$ there is no order to take a largest in, and even for a real spectrum $\rho(\operatorname{diag}(-5, 1)) = 5$ , not $1$ . This is the number Chapter 10 §10 introduced in prose, now with a label so that later sections can cite it.

Some values, simplest first.

Diagonal or triangular. The eigenvalues of a triangular matrix are its diagonal entries (Theorem 9.7.4 (b)), so $\rho$ is the largest modulus on the diagonal. For $\operatorname{diag}(d_1, \dots, d_n)$ it is $\max_i\lvert d_i\rvert$ .
Normal. If $\mathbf{A}$ is normal then $\mathbf{A} = \mathbf{U}\mathbf{D}\mathbf{U}^{*}$ with $\mathbf{D} = \operatorname{diag}(\lambda_1, \dots, \lambda_n)$ (Corollary 12.4.3), so $\mathbf{A}^{*}\mathbf{A} = \mathbf{U}\operatorname{diag}(\lvert\lambda_i\rvert^2)\mathbf{U}^{*}$ and the singular values of $\mathbf{A}$ are the moduli $\lvert\lambda_i\rvert$ . Hence $\rho(\mathbf{A}) = \sigma_1(\mathbf{A}) = \left\| \mathbf{A} \right\|_2$ by Theorem 16.3.3 (c). For a normal matrix the spectral radius is the spectral norm, which is where the second name comes from.
A rotation. $\begin{psmallmatrix} 0 & -1 \\ 1 & 0 \end{psmallmatrix}$ has eigenvalues $\pm i$ , so $\rho = 1$ , although no real vector is left in place.
Nilpotent. $\mathbf{J}_k(0)$ is triangular with zero diagonal, so by the first bullet $\rho(\mathbf{J}_k(0)) = 0$ . The matrix itself is not $0$ when $k \ge 2$ .

The last entry is the degenerate case, and it is the important one: it says at once that $\rho$ is not a norm.

Warning. $\rho$ is not a norm, and it is neither subadditive nor submultiplicative. Take

$\mathbf{A} = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}, \qquad \mathbf{B} = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} .$

Both are nilpotent, so $\rho(\mathbf{A}) = \rho(\mathbf{B}) = 0$ although neither is the zero matrix. Their sum $\begin{psmallmatrix} 0 & 1 \\ 1 & 0\end{psmallmatrix}$ has eigenvalues $\pm 1$ and their product $\mathbf{A}\mathbf{B} = \begin{psmallmatrix} 1 & 0 \\ 0 & 0\end{psmallmatrix}$ has eigenvalues $1$ and $0$ . So $\rho(\mathbf{A} + \mathbf{B}) = 1 > 0 = \rho(\mathbf{A}) + \rho(\mathbf{B})$ and $\rho(\mathbf{A}\mathbf{B}) = 1 > 0 = \rho(\mathbf{A})\rho(\mathbf{B})$ . So positive definiteness and subadditivity both fail, and so does submultiplicativity, all on the same small pair. Only absolute homogeneity survives, since $\rho(c\mathbf{A}) = \lvert c\rvert\rho(\mathbf{A})$ for every scalar $c$ .

So $\rho$ is a genuinely different kind of measurement from the ones of the previous section. The relation between the two is the subject of the rest of this section, and it is one-sided.

16.4.2. Every norm dominates the spectral radius

Theorem 16.4.1 (The Spectral Radius Is a Lower Bound for Every Norm)

Let $\mathbf{A} \in M_n(\mathbb{C})$ .

(a) If $\left\| \cdot \right\|$ is the operator norm on $M_n(\mathbb{C})$ induced by a norm on $\mathbb{C}^n$ (Definition 16.3.2), then $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|$ .
(b) More generally, $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|$ for every matrix norm $\left\| \cdot \right\|$ on $M_n(\mathbb{C})$ (Definition 16.3.1).

Idea. For (a) there is nothing to do but write down the eigenvalue equation: an eigenvector is a vector on which $\mathbf{A}$ acts by multiplication by $\lambda$ , so the stretching factor $\lvert\lambda\rvert$ is one of the factors the maximum in Definition 16.3.2 ranges over. For (b) there is no vector to feed the norm, only matrices — so manufacture one: fill an $n \times n$ matrix with copies of the eigenvector, and the eigenvalue equation becomes a matrix equation that submultiplicativity can be applied to.

Proof.

(a) Let $\lambda \in \operatorname{spec}(\mathbf{A})$ and let $\mathbf{x} \ne \mathbf{0}$ with $\mathbf{A}\mathbf{x} = \lambda\mathbf{x}$ . Then $\left\| \mathbf{A}\mathbf{x} \right\| = \lvert\lambda\rvert\,\left\| \mathbf{x} \right\|$ by homogeneity, while $\left\| \mathbf{A}\mathbf{x} \right\| \le \left\| \mathbf{A} \right\|\left\| \mathbf{x} \right\|$ by Theorem 16.3.2 (a). Since $\mathbf{x} \ne \mathbf{0}$ we have $\left\| \mathbf{x} \right\| > 0$ and may divide, giving $\lvert\lambda\rvert \le \left\| \mathbf{A} \right\|$ . This holds for every eigenvalue, so it holds for the largest modulus.
(b) Let $\lambda$ and $\mathbf{x}$ be as above, and let $\mathbf{X} \in M_n(\mathbb{C})$ be the matrix all of whose $n$ columns equal $\mathbf{x}$ . Then $\mathbf{X} \ne 0$ , so $\left\| \mathbf{X} \right\| > 0$ . Computing column by column, $\mathbf{A}\mathbf{X}$ has every column equal to $\mathbf{A}\mathbf{x} = \lambda\mathbf{x}$ , that is,

$\mathbf{A}\mathbf{X} = \lambda\mathbf{X} .$

Taking norms and using homogeneity on the left and submultiplicativity on the right,

$\lvert\lambda\rvert\,\left\| \mathbf{X} \right\| = \left\| \mathbf{A}\mathbf{X} \right\| \le \left\| \mathbf{A} \right\|\,\left\| \mathbf{X} \right\| .$

Dividing by $\left\| \mathbf{X} \right\| > 0$ gives $\lvert\lambda\rvert \le \left\| \mathbf{A} \right\|$ , and again the largest modulus obeys the same bound. This proves the theorem.

This is the inequality Chapter 10 §10 promised: the spectral radius never exceeds the norm of $\mathbf{A}$ induced by any vector norm. Part (b) says more than was promised, and costs one extra line.

The immediate use is that every computable norm is a computable upper bound for every eigenvalue — and two of the three formulas of Theorem 16.3.3 need no arithmetic beyond adding up moduli.

Corollary 16.4.2 (Cheap Bounds on the Spectrum)

Let $\mathbf{A} \in M_n(\mathbb{C})$ . Then every eigenvalue $\lambda$ of $\mathbf{A}$ satisfies

$\lvert\lambda\rvert \le \rho(\mathbf{A}) \le \min\bigl\{\left\| \mathbf{A} \right\|_1,\ \left\| \mathbf{A} \right\|_{\infty},\ \left\| \mathbf{A} \right\|_F\bigr\} ,$

that is, $\rho(\mathbf{A})$ is at most the largest absolute column sum, at most the largest absolute row sum, and at most $\left\| \mathbf{A} \right\|_F$ .

Proof. The first two are operator norms (Theorem 16.3.3 (a), (b)), so Theorem 16.4.1 (a) applies; $\left\| \cdot \right\|_F$ is a matrix norm (Example (The Frobenius norm is submultiplicative)), so Theorem 16.4.1 (b) applies. A minimum of upper bounds is an upper bound.

Remark. The bound $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|_2 = \sigma_1(\mathbf{A})$ is the same crude inequality $\lvert\lambda\rvert \le \sigma_1$ that Chapter 13 §08 obtained directly from $\mathbf{A}\mathbf{x} = \lambda\mathbf{x}$ . It is now one instance of a general principle rather than an isolated computation, and Theorem 16.4.1 (a) is that computation with the norm left unnamed.

Example (Bounding a spectrum without finding it)

Let $\mathbf{A} = \tfrac{1}{10}\begin{pmatrix} 2 & 5 & 1 \\ 3 & 1 & 4 \\ 1 & 2 & 5 \end{pmatrix}$ . Show that $\rho(\mathbf{A}) \le \tfrac45$ , and hence that $\mathbf{A}^{m} \to 0$ .

Solution. Every row of $\mathbf{A}$ sums to $\tfrac{8}{10} = \tfrac45$ , so $\left\| \mathbf{A} \right\|_{\infty} = \tfrac45$ by Theorem 16.3.3 (b), and $\rho(\mathbf{A}) \le \tfrac45$ by Corollary 16.4.2. Since $\tfrac45 < 1$ , every eigenvalue has modulus less than $1$ and $\mathbf{A}^{m} \to 0$ by Theorem 10.10.2. No characteristic polynomial was computed.

The column sums are $\tfrac{6}{10}$ , $\tfrac{8}{10}$ and $1$ , so $\left\| \mathbf{A} \right\|_1 = 1$ and the column bound gives nothing. It is worth computing both and keeping the smaller. In fact $\rho(\mathbf{A}) = \tfrac45$ exactly, because the constant row sums make $\mathbf{1}$ an eigenvector with eigenvalue $\tfrac45$ , so the row bound here is attained.

Quick check. Theorem 16.4.1 says $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|$ for every matrix norm. Why does it not follow that $\rho$ is the smallest matrix norm?

Solution. Because $\rho$ is not a matrix norm at all: $\rho$ vanishes on every non-zero nilpotent matrix, and it fails both subadditivity and submultiplicativity, as the warning above showed. The correct statement is that $\rho(\mathbf{A})$ is a lower bound for the values $\left\| \mathbf{A} \right\|$ , one matrix at a time, and the next theorem shows it is the greatest such lower bound.

16.4.3. A norm as close to the spectral radius as we like

Theorem 16.4.1 leaves open how large the gap can be. It can be enormous for a fixed norm: $\mathbf{J}_2(0)$ has $\rho = 0$ and $\left\| \mathbf{J}_2(0) \right\|_2 = 1$ , and multiplying the corner entry by $10^6$ leaves $\rho = 0$ while the norm becomes $10^6$ . But the norm may be chosen after the matrix, and then the gap can be made as small as we please.

Theorem 16.4.3 (Norms Close to the Spectral Radius)

Let $\mathbf{A} \in M_n(\mathbb{C})$ and let $\varepsilon > 0$ . Then there is a norm $\left\| \cdot \right\|_t$ on $\mathbb{C}^n$ whose induced operator norm satisfies

$\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|_t \le \rho(\mathbf{A}) + \varepsilon .$

Idea. Schur-triangularize and then squash. ① By Corollary 12.1.3, $\mathbf{A} = \mathbf{U}\mathbf{T}\mathbf{U}^{*}$ with $\mathbf{T}$ upper triangular carrying the eigenvalues on its diagonal; the row sums of $\mathbf{T}$ are the diagonal entry plus the off-diagonal junk. ② Conjugating $\mathbf{T}$ by $\mathbf{D}_t = \operatorname{diag}(1, t, \dots, t^{n-1})$ multiplies the entry in position $(i,j)$ by $t^{i-j}$ , which leaves the diagonal alone and, for large $t$ , shrinks everything strictly above it, because $i - j < 0$ there. ③ Choose $t$ so that every off-diagonal row sum is below $\varepsilon$ ; the largest row sum is then below $\rho(\mathbf{A}) + \varepsilon$ , and the largest row sum is a norm we can compute, by Theorem 16.3.3 (b). ④ Transport that norm back to $\mathbb{C}^n$ along the invertible matrix $\mathbf{D}_t\mathbf{U}^{*}$ .

Proof. By Corollary 12.1.3 there are a unitary $\mathbf{U}$ and an upper triangular $\mathbf{T} = (t_{ij})$ with $\mathbf{A} = \mathbf{U}\mathbf{T}\mathbf{U}^{*}$ and $t_{ii} = \lambda_i$ , the eigenvalues of $\mathbf{A}$ . For $t \ge 1$ put $\mathbf{D}_t = \operatorname{diag}(1, t, t^2, \dots, t^{n-1})$ , an invertible matrix, and $\mathbf{T}_t = \mathbf{D}_t\mathbf{T}\mathbf{D}_t^{-1}$ . Multiplying out,

$(\mathbf{T}_t)_{ij} = t^{\,i-1}\,t_{ij}\,t^{-(j-1)} = t^{\,i-j}t_{ij} .$

So $\mathbf{T}_t$ is again upper triangular with the same diagonal $\lambda_1, \dots, \lambda_n$ , while for $i < j$ the entry is scaled by $t^{i-j} \le t^{-1}$ , using $t \ge 1$ and $j - i \ge 1$ . Let $M = \max_{i<j}\lvert t_{ij}\rvert$ if $n \ge 2$ , and $M = 0$ if $n = 1$ . Then the $i$ -th absolute row sum of $\mathbf{T}_t$ is at most

$\lvert\lambda_i\rvert + \sum_{j > i}t^{-1}\lvert t_{ij}\rvert \le \rho(\mathbf{A}) + \frac{(n-1)M}{t} .$

Choose $t = \max\bigl(1,\ (n-1)M/\varepsilon\bigr)$ . Then every absolute row sum of $\mathbf{T}_t$ is at most $\rho(\mathbf{A}) + \varepsilon$ , so $\left\| \mathbf{T}_t \right\|_{\infty} \le \rho(\mathbf{A}) + \varepsilon$ by Theorem 16.3.3 (b).

Now define, for $\mathbf{x} \in \mathbb{C}^n$ ,

$\left\| \mathbf{x} \right\|_t \mathrel{:=} \left\| \mathbf{D}_t\mathbf{U}^{*}\mathbf{x} \right\|_{\infty} .$

This is a norm: it is non-negative, homogeneous and subadditive because $\left\| \cdot \right\|_{\infty}$ is and $\mathbf{x} \mapsto \mathbf{D}_t\mathbf{U}^{*}\mathbf{x}$ is linear, and it vanishes only at $\mathbf{x} = \mathbf{0}$ because $\mathbf{D}_t\mathbf{U}^{*}$ is invertible.

It remains to compute the induced operator norm. Put $\mathbf{Q} = \mathbf{D}_t\mathbf{U}^{*}$ , so $\left\| \mathbf{x} \right\|_t = \left\| \mathbf{Q}\mathbf{x} \right\|_{\infty}$ . As $\mathbf{x}$ runs over $\{\left\| \mathbf{x} \right\|_t = 1\}$ , the vector $\mathbf{y} = \mathbf{Q}\mathbf{x}$ runs over $\{\left\| \mathbf{y} \right\|_{\infty} = 1\}$ , since $\mathbf{Q}$ is a bijection. Moreover $\mathbf{Q}\mathbf{A}\mathbf{Q}^{-1} = \mathbf{D}_t\mathbf{U}^{*}\mathbf{A}\mathbf{U}\mathbf{D}_t^{-1} = \mathbf{D}_t\mathbf{T}\mathbf{D}_t^{-1} = \mathbf{T}_t$ , so

$\left\| \mathbf{A}\mathbf{x} \right\|_t = \left\| \mathbf{Q}\mathbf{A}\mathbf{x} \right\|_{\infty} = \left\| \mathbf{T}_t\,\mathbf{y} \right\|_{\infty} .$

Taking maxima over the two matching sets gives $\left\| \mathbf{A} \right\|_t = \left\| \mathbf{T}_t \right\|_{\infty} \le \rho(\mathbf{A}) + \varepsilon$ . The lower bound $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|_t$ is Theorem 16.4.1 (a). This proves the theorem.

Read together, the last two theorems say

$\rho(\mathbf{A}) = \inf\{\left\| \mathbf{A} \right\| : \left\| \cdot \right\| \text{ an induced matrix norm}\} .$

Remark. The infimum need not be attained. If $\mathbf{A} \ne 0$ is nilpotent then $\rho(\mathbf{A}) = 0$ while $\left\| \mathbf{A} \right\| > 0$ for every norm, so no norm achieves the value. At the other extreme, for a normal $\mathbf{A}$ the spectral norm achieves it exactly: $\left\| \mathbf{A} \right\|_2 = \rho(\mathbf{A})$ , as computed at the start of this section. The gap between $\rho$ and the norms is a measure of how far $\mathbf{A}$ is from being normal, which is the theme Chapter 12 §11 opened with the departure from normality.

16.4.4. Gelfand’s formula

The infimum above is over norms, and to use it we must choose one. There is a second description of $\rho(\mathbf{A})$ that needs no choice: fix any norm at all, and let the powers of $\mathbf{A}$ tell you the answer.

Theorem 16.4.4 (Gelfand’s Formula)

Let $\mathbf{A} \in M_n(\mathbb{C})$ and let $\left\| \cdot \right\|$ be any matrix norm on $M_n(\mathbb{C})$ . Then

$\lim_{k \to \infty}\ \left\| \mathbf{A}^{k} \right\|^{1/k} = \rho(\mathbf{A}) .$

In particular the limit exists and does not depend on which matrix norm is used.

Idea. Two inequalities, one for each direction, and they come from opposite ends of the chapter. ① The lower bound $\rho(\mathbf{A}) \le \left\| \mathbf{A}^k \right\|^{1/k}$ is Theorem 16.4.1 applied to $\mathbf{A}^{k}$ , once we know $\rho(\mathbf{A}^{k}) = \rho(\mathbf{A})^{k}$ — which is the Spectral Mapping Theorem. This holds for every $k$ , with no limit taken. ② For the upper bound, scale $\mathbf{A}$ down by a whisker more than $\rho(\mathbf{A})$ . The scaled matrix has spectral radius below $1$ , so Chapter 10 §10’s criterion makes its powers tend to $0$ , and once they are below $1$ in norm the inequality we want has been written down. Theorem 16.4.3 says the same decay is geometric, which is what the corollary below extracts.

Proof. Lower bound. Fix $k \ge 1$ . By Theorem 9.10.1 applied to $q(x) = x^{k}$ , $\operatorname{spec}(\mathbf{A}^{k}) = \{\lambda^{k} : \lambda \in \operatorname{spec}(\mathbf{A})\}$ , so

$\rho(\mathbf{A}^{k}) = \max_{\lambda \in \operatorname{spec}(\mathbf{A})}\lvert\lambda\rvert^{k} = \rho(\mathbf{A})^{k} .$

By Theorem 16.4.1 (b) applied to $\mathbf{A}^{k}$ , $\rho(\mathbf{A})^{k} = \rho(\mathbf{A}^{k}) \le \left\| \mathbf{A}^{k} \right\|$ . Taking $k$ -th roots of these non-negative reals,

$\rho(\mathbf{A}) \le \left\| \mathbf{A}^{k} \right\|^{1/k} \qquad \text{for every } k \ge 1 .$

Upper bound. Let $\varepsilon > 0$ , put $s = \rho(\mathbf{A}) + \varepsilon > 0$ and $\mathbf{B} = s^{-1}\mathbf{A}$ . Every eigenvalue of $\mathbf{B}$ is $\lambda/s$ for some $\lambda \in \operatorname{spec}(\mathbf{A})$ (Theorem 9.10.1 with $q(x) = x/s$ ), so

$\rho(\mathbf{B}) = \frac{\rho(\mathbf{A})}{\rho(\mathbf{A}) + \varepsilon} < 1 .$

By Theorem 10.10.2, $\mathbf{B}^{k} \to 0$ entrywise. Entrywise convergence of matrices is convergence in every norm on $M_n(\mathbb{C})$ , by Corollary 16.2.4, so $\left\| \mathbf{B}^{k} \right\| \to 0$ . A real sequence tending to $0$ is eventually below $1$ : there is $K$ with $\left\| \mathbf{B}^{k} \right\| \le 1$ for all $k \ge K$ . Since $\mathbf{B}^{k} = s^{-k}\mathbf{A}^{k}$ , homogeneity gives $\left\| \mathbf{A}^{k} \right\| \le s^{k}$ , that is,

$\left\| \mathbf{A}^{k} \right\|^{1/k} \le \rho(\mathbf{A}) + \varepsilon \qquad (k \ge K) .$

Conclusion. Combining, for every $\varepsilon > 0$ there is $K$ with

$\rho(\mathbf{A}) \le \left\| \mathbf{A}^{k} \right\|^{1/k} \le \rho(\mathbf{A}) + \varepsilon \qquad (k \ge K),$

which is the definition of $\left\| \mathbf{A}^{k} \right\|^{1/k} \to \rho(\mathbf{A})$ . The independence of the norm is automatic, since the limit equals $\rho(\mathbf{A})$ whichever matrix norm was fixed at the start. This proves the theorem.

Remark. Which analysis was used. The lower bound used none. The upper bound used Theorem 10.10.2, which is a theorem of this book, and Corollary 16.2.4, likewise; the only analysis is that a real sequence tending to $0$ is eventually less than $1$ , and that a sequence trapped between $\rho(\mathbf{A})$ and $\rho(\mathbf{A}) + \varepsilon$ for every $\varepsilon > 0$ converges to $\rho(\mathbf{A})$ . Neither is an extra import: both are the definition of a limit of a real sequence, read forwards and backwards. Nothing from the list (A1)–(A4) of the chapter introduction is needed here, and nothing outside it is used.

The formula is a genuine computation rule as well as a theorem. For a fixed $k$ the number $\left\| \mathbf{A}^{k} \right\|^{1/k}$ is an upper estimate of $\rho(\mathbf{A})$ — that is the lower bound above, read the other way — and the estimates improve as $k$ grows.

Example (Watching the limit converge)

Let $\mathbf{A} = \begin{pmatrix} 1/2 & 10 \\ 0 & 1/3 \end{pmatrix}$ . Compute $\left\| \mathbf{A}^{k} \right\|_{\infty}$ exactly and confirm Gelfand’s formula.

Solution. $\mathbf{A}$ is upper triangular, so $\rho(\mathbf{A}) = \max(\tfrac12, \tfrac13) = \tfrac12$ and the powers are upper triangular with diagonal $2^{-k}, 3^{-k}$ . For the corner entry, induction on $k$ gives

$(\mathbf{A}^{k})_{12} = 10\sum_{j=0}^{k-1}2^{-j}3^{-(k-1-j)} = 60\bigl(2^{-k} - 3^{-k}\bigr),$

the last step by summing the geometric series with ratio $3/2$ . The two absolute row sums are $2^{-k} + 60(2^{-k} - 3^{-k})$ and $3^{-k}$ , the first being the larger, so by Theorem 16.3.3 (b)

$\left\| \mathbf{A}^{k} \right\|_{\infty} = 61\cdot 2^{-k} - 60\cdot 3^{-k} .$

At $k = 1$ this is $10.5$ , which overestimates $\rho(\mathbf{A}) = \tfrac12$ by a factor of $21$ ; the $k$ -th roots run $10.5,\ 2.93,\ 1.75,\ 1.32,\ 1.11,\ 0.98, \dots$ and settle toward $\tfrac12$ , which is what Theorem 16.4.4 guarantees. The convergence is slow, and it has to be: the single number $\left\| \mathbf{A} \right\|_{\infty}$ cannot know that the entry $10$ sits above the diagonal rather than on it.

16.4.5. What is new, and what is not

Corollary 16.4.5 (Powers Tending to Zero, with a Rate)

Let $\mathbf{A} \in M_n(\mathbb{C})$ and let $\left\| \cdot \right\|$ be any matrix norm on $M_n(\mathbb{C})$ .

(a) $\mathbf{A}^{k} \to 0$ if and only if $\rho(\mathbf{A}) < 1$ , and this holds if and only if $\left\| \mathbf{A}^{k} \right\| \to 0$ .
(b) If $\rho(\mathbf{A}) < 1$ , then for every $q$ with $\rho(\mathbf{A}) < q < 1$ there is a constant $C \ge 1$ , depending on $\mathbf{A}$ , on $q$ and on the norm, such that $\left\| \mathbf{A}^{k} \right\| \le C\,q^{k}$ for every $k \ge 0$ .

Idea. Part (a) is Theorem 10.10.2 translated into norms by Corollary 16.2.4; nothing is proved that was not proved in Chapter 10. Part (b) is the new content, and it is Theorem 16.4.3 doing what it was built for: choose a norm in which $\mathbf{A}$ itself is already smaller than $q$ , take powers there, and pay one fixed constant to return to the norm we were given.

Proof.

(a) The first equivalence is Theorem 10.10.2, since $\rho(\mathbf{A}) < 1$ says exactly that every eigenvalue has modulus less than $1$ . The second is Corollary 16.2.4: entrywise convergence of matrices and convergence in the norm $\left\| \cdot \right\|$ are the same thing.
(b) Let $\varepsilon = q - \rho(\mathbf{A}) > 0$ . By Theorem 16.4.3 there is an induced matrix norm $\left\| \cdot \right\|_t$ on $M_n(\mathbb{C})$ with $\left\| \mathbf{A} \right\|_t \le \rho(\mathbf{A}) + \varepsilon = q$ . Submultiplicativity (Theorem 16.3.2 (d)) gives $\left\| \mathbf{A}^{k} \right\|_t \le \left\| \mathbf{A} \right\|_t^{k} \le q^{k}$ for every $k \ge 0$ . By Theorem 16.2.2, applied to the two norms $\left\| \cdot \right\|$ and $\left\| \cdot \right\|_t$ on the finite-dimensional space $M_n(\mathbb{C})$ , there is $C_0 > 0$ with $\left\| \mathbf{M} \right\| \le C_0\left\| \mathbf{M} \right\|_t$ for every $\mathbf{M}$ . Taking $C = \max(C_0, 1)$ ,

$\left\| \mathbf{A}^{k} \right\| \le C_0\left\| \mathbf{A}^{k} \right\|_t \le C\,q^{k} .$

This proves the corollary.

It is worth being exact about the accounting. Part (a) is not new. Chapter 10 §10 proved that $\mathbf{A}^{m} \to 0$ if and only if every eigenvalue has modulus less than $1$ , and it proved it with the Jordan form and no norms whatsoever; all that has happened here is that the conclusion has been restated in a language where “small” is a number. What is new is part (b): a rate. Chapter 10 could say that the powers die; it could not say how fast, because it had nothing to measure a matrix with. Now every decaying matrix comes with a geometric envelope $Cq^{k}$ for every $q$ above its spectral radius, and that envelope is what later sections integrate, sum and differentiate.

Two honest limitations of the envelope deserve saying out loud.

Warning. $\rho(\mathbf{A}) < 1$ promises eventual decay, not immediate decay. The constant $C$ in Corollary 16.4.5 (b) is generally larger than $1$ and grows as $q$ approaches $\rho(\mathbf{A})$ . For

$\mathbf{A} = \begin{pmatrix} 9/10 & 10 \\ 0 & 9/10 \end{pmatrix}, \qquad \mathbf{A}^{k} = \begin{pmatrix} (9/10)^{k} & 10k(9/10)^{k-1} \\ 0 & (9/10)^{k} \end{pmatrix},$

we have $\rho(\mathbf{A}) = 9/10 < 1$ , yet $\left\| \mathbf{A}^{k} \right\|_{\infty} = (9/10)^{k-1}(9/10 + 10k)$ rises from $10.9$ at $k = 1$ to about $39.13$ at $k = 9$ before beginning its decay, and does not fall below $1$ until $k = 63$ . A transient hump of this kind is invisible to the spectral radius and is exactly what the constant $C$ is paying for.

Quick check. For which matrices can one take $C = 1$ and $q = \rho(\mathbf{A})$ in the bound of Corollary 16.4.5 (b), with the spectral norm?

Solution. For normal $\mathbf{A}$ , among others. If $\mathbf{A}$ is normal then so is $\mathbf{A}^{k}$ (its adjoint is $(\mathbf{A}^{*})^{k}$ , and powers of commuting matrices commute), so $\left\| \mathbf{A}^{k} \right\|_2 = \rho(\mathbf{A}^{k}) = \rho(\mathbf{A})^{k}$ by the computation at the start of this section together with Theorem 9.10.1. There is then no transient at all: the norm of the powers is exactly geometric. The hump in the warning is possible only because that matrix is far from normal, with departure from normality $10$ in the sense of Definition 12.11.1.

16.4.6. Exercises

A. Check your understanding

Exercise (A1)

(a) Define the spectral radius, and say why the maximum in the definition exists.
(b) State Theorem 16.4.1 and Theorem 16.4.4.
(c) Determine whether the following statement is correct, and justify your answer: $\rho$ is a matrix norm on $M_n(\mathbb{C})$ .
(d) Determine whether the following statement is correct, and justify your answer: if $\rho(\mathbf{A}) < 1$ then $\left\| \mathbf{A} \right\|_2 < 1$ .
(e) Chapter 10 §10 already proved that $\mathbf{A}^{m} \to 0$ exactly when $\rho(\mathbf{A}) < 1$ . What does Corollary 16.4.5 add to that?

Solution.

(a) $\rho(\mathbf{A}) = \max\{\lvert\lambda\rvert : \lambda \in \operatorname{spec}(\mathbf{A})\}$ (Definition 16.4.1). The set $\operatorname{spec}(\mathbf{A})$ is finite and non-empty — it is the root set of $p_{\mathbf{A}}$ , non-empty by Theorem 6.5.1 — so the maximum of the finitely many moduli exists.
(b) For every matrix norm on $M_n(\mathbb{C})$ , $\rho(\mathbf{A}) \le \left\| \mathbf{A} \right\|$ ; and for every matrix norm, $\left\| \mathbf{A}^{k} \right\|^{1/k} \to \rho(\mathbf{A})$ as $k \to \infty$ .
(c) Incorrect. $\rho$ vanishes on non-zero nilpotent matrices, so it is not even a norm, and it is neither subadditive nor submultiplicative: see the warning after Definition 16.4.1.
(d) Incorrect. $\mathbf{A} = \begin{psmallmatrix} 0 & 10 \\ 0 & 0\end{psmallmatrix}$ has $\rho(\mathbf{A}) = 0$ and $\left\| \mathbf{A} \right\|_2 = 10$ . The correct statement is that some norm has $\left\| \mathbf{A} \right\| < 1$ , by Theorem 16.4.3.
(e) Nothing about the criterion, which is Theorem 10.10.2 restated; what it adds is the quantitative envelope $\left\| \mathbf{A}^{k} \right\| \le Cq^{k}$ for every $q \in (\rho(\mathbf{A}), 1)$ , a rate of decay rather than the bare fact of it.

B. Practice

Exercise (B1: Four numbers again)

Let $\mathbf{A} = \begin{pmatrix} 0 & 2 \\ 1/4 & 0 \end{pmatrix}$ . Compute $\rho(\mathbf{A})$ , $\left\| \mathbf{A} \right\|_1$ , $\left\| \mathbf{A} \right\|_{\infty}$ and $\left\| \mathbf{A} \right\|_2$ , and verify Theorem 16.4.1 in each case.

Solution. $p_{\mathbf{A}}(x) = x^2 - \tfrac12$ , so $\operatorname{spec}(\mathbf{A}) = \{\pm 1/\sqrt2\}$ and $\rho(\mathbf{A}) = 1/\sqrt2 \approx 0.707$ .

The absolute column sums are $\tfrac14$ and $2$ , so $\left\| \mathbf{A} \right\|_1 = 2$ ; the absolute row sums are $2$ and $\tfrac14$ , so $\left\| \mathbf{A} \right\|_{\infty} = 2$ . For the spectral norm, $\mathbf{A}^{\top}\mathbf{A} = \operatorname{diag}(\tfrac1{16}, 4)$ , whose eigenvalues are $\tfrac1{16}$ and $4$ ; hence $\sigma_1 = 2$ and $\left\| \mathbf{A} \right\|_2 = 2$ by Theorem 16.3.3 (c).

So $\rho(\mathbf{A}) = 0.707\dots \le 2$ in all three cases, and the gap is a factor of nearly $3$ even though $\mathbf{A}$ is a very small matrix. The reason is the mismatch between the two off-diagonal entries: $\mathbf{A}$ is far from normal.

Exercise (B2: Gelfand exactly)

With $\mathbf{A}$ as in Exercise (B1: Four numbers again), compute $\mathbf{A}^{k}$ for every $k$ and evaluate $\lim_k\left\| \mathbf{A}^{k} \right\|_{\infty}^{1/k}$ directly.

Solution. $\mathbf{A}^2 = \tfrac12\mathbf{I}$ , so by induction $\mathbf{A}^{2l} = 2^{-l}\mathbf{I}$ and $\mathbf{A}^{2l+1} = 2^{-l}\mathbf{A}$ . Hence

$\left\| \mathbf{A}^{2l} \right\|_{\infty} = 2^{-l}, \qquad \left\| \mathbf{A}^{2l+1} \right\|_{\infty} = 2^{-l}\cdot 2 = 2^{1-l} .$

For even $k = 2l$ , $\left\| \mathbf{A}^{k} \right\|_{\infty}^{1/k} = (2^{-l})^{1/(2l)} = 2^{-1/2}$ , exactly $\rho(\mathbf{A})$ for every $l$ . For odd $k = 2l+1$ , $\left\| \mathbf{A}^{k} \right\|_{\infty}^{1/k} = 2^{(1-l)/(2l+1)}$ , and $(1-l)/(2l+1) \to -\tfrac12$ , so this too tends to $2^{-1/2}$ . Both subsequences converge to $1/\sqrt2 = \rho(\mathbf{A})$ , confirming Theorem 16.4.4.

Exercise (B3: Deciding convergence without eigenvalues)

For each matrix, decide whether $\mathbf{A}^{m} \to 0$ , using only Corollary 16.4.2 and Theorem 10.10.2.

(a) $\mathbf{A} = \tfrac{1}{4}\begin{pmatrix} 1 & 2 & 0 \\ 0 & 1 & 1 \\ 2 & 0 & 1 \end{pmatrix}$ .
(b) $\mathbf{A} = \begin{pmatrix} 1/2 & 3 \\ 0 & 2 \end{pmatrix}$ .

Solution.

(a) The absolute row sums are $\tfrac34$ , $\tfrac12$ and $\tfrac34$ , so $\left\| \mathbf{A} \right\|_{\infty} = \tfrac34$ and $\rho(\mathbf{A}) \le \tfrac34 < 1$ . By Theorem 10.10.2, $\mathbf{A}^{m} \to 0$ .
(b) Here the row sums are $\tfrac72$ and $2$ and the column sums are $\tfrac12$ and $5$ , so the bounds give only $\rho(\mathbf{A}) \le \tfrac72$ and decide nothing. But the bound is an upper bound, and here the matrix is triangular, so the eigenvalues are visible: $\tfrac12$ and $2$ , giving $\rho(\mathbf{A}) = 2 > 1$ . By Theorem 10.10.2 the powers do not tend to $0$ . The moral is that Corollary 16.4.2 can only ever certify convergence, never rule it out.

C. Going deeper

Exercise (C1: A norm that sees the decay)

Let $\mathbf{A} \in M_n(\mathbb{C})$ .

(a) Prove that if $\left\| \mathbf{A} \right\| < 1$ for some matrix norm, then $\mathbf{A}^{k} \to 0$ .
(b) Give a matrix with $\mathbf{A}^{k} \to 0$ and $\left\| \mathbf{A} \right\|_2 > 1$ , so that the converse of (a) fails for a fixed norm.
(c) Prove that the converse of (a) nevertheless holds if the norm is allowed to depend on $\mathbf{A}$ .

Solution.

(a) Submultiplicativity gives $\left\| \mathbf{A}^{k} \right\| \le \left\| \mathbf{A} \right\|^{k}$ by induction on $k$ . With $r = \left\| \mathbf{A} \right\| < 1$ the right-hand side tends to $0$ , so $\left\| \mathbf{A}^{k} \right\| \to 0$ , and by Corollary 16.2.4 this is the same as $\mathbf{A}^{k} \to 0$ entrywise.
(b) $\mathbf{A} = \begin{psmallmatrix} 0 & 10 \\ 0 & 0\end{psmallmatrix}$ satisfies $\mathbf{A}^2 = 0$ , so certainly $\mathbf{A}^{k} \to 0$ ; but $\left\| \mathbf{A} \right\|_2 = 10 > 1$ . The same happens for $\begin{psmallmatrix} 1/2 & 10 \\ 0 & 1/2\end{psmallmatrix}$ , which is not even nilpotent.
(c) Suppose $\mathbf{A}^{k} \to 0$ . By Theorem 10.10.2, $\rho(\mathbf{A}) < 1$ . Apply Theorem 16.4.3 with $\varepsilon = \tfrac12(1 - \rho(\mathbf{A})) > 0$ : it produces an induced matrix norm $\left\| \cdot \right\|_t$ with

$\left\| \mathbf{A} \right\|_t \le \rho(\mathbf{A}) + \varepsilon = \tfrac12\bigl(1 + \rho(\mathbf{A})\bigr) < 1 .$

So a norm witnessing the decay always exists, though it must be chosen after $\mathbf{A}$ .

Exercise (C2: Spectral radius zero)

Let $\mathbf{A} \in M_n(\mathbb{C})$ .

(a) Prove that $\rho(\mathbf{A}) = 0$ if and only if $\mathbf{A}$ is nilpotent.
(b) Deduce that for a nilpotent $\mathbf{A}$ and any matrix norm, $\left\| \mathbf{A}^{k} \right\|^{1/k} \to 0$ , and verify this directly for $\mathbf{A} = \mathbf{J}_n(0)$ .
(c) Explain why (a) shows that no inequality of the form $\left\| \mathbf{A} \right\| \le c\,\rho(\mathbf{A})$ , with $c$ depending only on $n$ , can hold.

Solution.

(a) $(\Rightarrow)$ If $\rho(\mathbf{A}) = 0$ then every eigenvalue is $0$ , so $p_{\mathbf{A}}(x) = x^{n}$ because $p_{\mathbf{A}}$ is monic of degree $n$ and splits over $\mathbb{C}$ with all roots $0$ (Theorem 6.5.1). By the Cayley–Hamilton theorem (Theorem 9.6.1), $\mathbf{A}^{n} = p_{\mathbf{A}}(\mathbf{A}) = 0$ , so $\mathbf{A}$ is nilpotent (Definition 10.2.1).
$(\Leftarrow)$ If $\mathbf{A}^{d} = 0$ and $\mathbf{A}\mathbf{x} = \lambda\mathbf{x}$ with $\mathbf{x} \ne \mathbf{0}$ , then $\mathbf{0} = \mathbf{A}^{d}\mathbf{x} = \lambda^{d}\mathbf{x}$ , so $\lambda^{d} = 0$ and $\lambda = 0$ . Hence $\operatorname{spec}(\mathbf{A}) = \{0\}$ and $\rho(\mathbf{A}) = 0$ .
(b) By Theorem 16.4.4 the limit is $\rho(\mathbf{A}) = 0$ . Directly for $\mathbf{A} = \mathbf{J}_n(0)$ : $\mathbf{A}^{k} = 0$ for $k \ge n$ , so $\left\| \mathbf{A}^{k} \right\|^{1/k} = 0$ for all $k \ge n$ , and the sequence is eventually constant at $0$ .
(c) Such an inequality would force $\left\| \mathbf{A} \right\| = 0$ , hence $\mathbf{A} = 0$ , for every nilpotent $\mathbf{A}$ . But $\mathbf{J}_2(0) \ne 0$ is nilpotent. So the two quantities cannot be compared in that direction at all; Theorem 16.4.3 is the best available substitute, and it buys its conclusion by changing the norm.

Exercise (C3: When the infimum is attained)

Call $\mathbf{A} \in M_n(\mathbb{C})$ radius-attaining if $\left\| \mathbf{A} \right\| = \rho(\mathbf{A})$ for some matrix norm.

(a) Prove that every normal $\mathbf{A}$ is radius-attaining.
(b) Prove that a non-zero nilpotent $\mathbf{A}$ is not.
(c) Deduce that $\begin{psmallmatrix} 1 & 1 \\ 0 & 1 \end{psmallmatrix}$ is not radius-attaining, even though it is invertible.

Hint for (c): consider $\mathbf{A} - \mathbf{I}$ .

Solution.

(a) Let $\mathbf{A}$ be normal, so $\mathbf{A} = \mathbf{U}\mathbf{D}\mathbf{U}^{*}$ with $\mathbf{U}$ unitary and $\mathbf{D} = \operatorname{diag}(\lambda_1, \dots, \lambda_n)$ (Corollary 12.4.3). Then $\mathbf{A}^{*}\mathbf{A} = \mathbf{U}\operatorname{diag}(\lvert\lambda_i\rvert^2)\mathbf{U}^{*}$ , so the singular values of $\mathbf{A}$ are the $\lvert\lambda_i\rvert$ in decreasing order and $\left\| \mathbf{A} \right\|_2 = \sigma_1 = \max_i\lvert\lambda_i\rvert = \rho(\mathbf{A})$ by Theorem 16.3.3 (c).
(b) If $\mathbf{A} \ne 0$ is nilpotent then $\rho(\mathbf{A}) = 0$ by Exercise (C2: Spectral radius zero) (a), while $\left\| \mathbf{A} \right\| > 0$ for every norm, since a norm vanishes only at $0$ (Definition 16.1.1). So no norm can give $\left\| \mathbf{A} \right\| = \rho(\mathbf{A})$ .
(c) Put $\mathbf{A} = \begin{psmallmatrix} 1 & 1 \\ 0 & 1\end{psmallmatrix}$ , whose only eigenvalue is $1$ , so $\rho(\mathbf{A}) = 1$ . Suppose some matrix norm had $\left\| \mathbf{A} \right\| = 1$ . Then $\left\| \mathbf{A}^{k} \right\| \le \left\| \mathbf{A} \right\|^{k} = 1$ for every $k$ , so the sequence $(\mathbf{A}^{k})$ is bounded in that norm, hence bounded entrywise by Corollary 16.2.4, whose second sentence covers boundedness. But $\mathbf{A}^{k} = \begin{psmallmatrix} 1 & k \\ 0 & 1\end{psmallmatrix}$ , whose $(1,2)$ -entry is unbounded. Contradiction. (The hint points at the same phenomenon: $\mathbf{A} - \mathbf{I}$ is a non-zero nilpotent, so $\mathbf{A}$ is a unipotent matrix, and it is the nilpotent part that the spectral radius cannot see.)