Matrix Norms and Spectral Radius

Matrix Norms

A norm on $M_n$ is a matrix norm when it is submultiplicative,

$$\|AB\| \le \|A\| \cdot \|B\|$$

Every induced norm $\|A\|_{\|\cdot\|, \|\cdot\|}$ is a matrix norm.

If $\|\cdot\|$ is a matrix norm and $S$ is invertible, $\|A\|_S = \|S^{-1}AS\|$ is a matrix norm.

Spectral Radius and Norms

For all $A \in M_n$ and any matrix norm, $\rho(A) \le \|A\|$.

Proof Let $x$ be an eigenvector of an eigenvalue $\lambda$ of max modulus, and $B := [x | x | \cdots | x] \in M_n$. Then

$$|\lambda| \, \|B\| = \|\lambda B\| = \|[Ax | \cdots | Ax]\| = \|AB\| \le \|A\| \, \|B\|$$

and $\|B\| \neq 0$.

Conversely, for all $\varepsilon > 0$ there is a matrix norm $\|\cdot\|$ on $M_n$ with $\|A\| \le \rho(A) + \varepsilon$.

Proof Let $A = SJS^{-1}$ and $D = \mathrm{diag}(\varepsilon, \varepsilon^2, \ldots, \varepsilon^n)$. $D^{-1}JD$ has the eigenvalues on the diagonal and $\varepsilon$ instead of 1 above it, so its max column sum is at most $\rho(A) + \varepsilon$. Using the matrix norm $\|\cdot\|_{1,1}$ with $SD$,

$$\|A\|_{(1,1), SD} = \|(SD)^{-1}A(SD)\|_{1,1} = \|D^{-1}JD\|_{1,1} \le \rho(A) + \varepsilon$$

Powers of a Matrix

For $A \in M_n$,

$$\lim_{k \to \infty} A^k = 0 \iff \rho(A) < 1$$

Proof

$(\Leftarrow)$ If $\rho(A) < 1$ there is a matrix norm on $M_n$ with $\|A\| < 1$. Then $\|A^k - 0\| \le \|A\|^k \to 0$.

$(\Rightarrow)$ If $A^k \to 0$, then for any eigenpair $\lambda, x$, as $k \to \infty$, $\lambda^k x = A^k x \to 0$, so $|\lambda| < 1$.

Gelfand For any matrix norm $\|\cdot\|$,

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

Proof

1. $\rho(A)^k = \rho(A^k) \le \|A^k\|$, so $\rho(A) \le \|A^k\|^{1/k}$.
2. For $\varepsilon > 0$, $\rho\big(\frac{1}{\rho(A) + \varepsilon} A\big) < 1$, so $\big(\frac{1}{\rho(A) + \varepsilon} A\big)^k \to 0$.
3. So there is $M$ such that for all $k \ge M$, $\big\|\big(\frac{1}{\rho(A) + \varepsilon} A\big)^k\big\| < 1$.
4. So for all such $k$, $\|A^k\| \le (\rho(A) + \varepsilon)^k$, i.e. $\|A^k\|^{1/k} \le \rho(A) + \varepsilon$.

Neumann Series

An NLS is complete iff all absolutely convergent series converge.

If $\|\cdot\|$ is a matrix norm and $\|B\| < 1$, then $I - B$ is invertible and

$$(I - B)^{-1} = \sum_{i=0}^{\infty} B^i$$

Proof The series converges absolutely since $\|B^i\| \le \|B\|^i$, and

$$(I - B)\sum_{i=0}^{N} B^i = I - B^{N+1}, \qquad \|B^{N+1}\| \le \|B\|^{N+1} \to 0$$

Equivalently, if $\|I - A\| < 1$ then

$$A^{-1} = \sum_{i=0}^{\infty} (I - A)^i$$

Condition Number

A vector norm $\|\cdot\|'$ is compatible with a matrix norm $\|\cdot\|$ when $\|Ax\|' \le \|A\| \, \|x\|'$.

$$\kappa_{\|\cdot\|}(A) = \|A\| \cdot \|A^{-1}\|$$

If $Ax = b$ and $A(x + \Delta x) = b + \Delta b$, with compatible norms,

$$\frac{\|\Delta x\|}{\|x\|} \le \kappa(A) \frac{\|\Delta b\|}{\|b\|}$$

since $\|\Delta x\| = \|A^{-1}\Delta b\| \le \|A^{-1}\| \, \|\Delta b\|$ and $\|b\| \le \|A\| \, \|x\|$.