Burden & Faires, 9th Ed. - §7.1–7.2
Chapter 13: Vector & Matrix Norms, Eigenvalues
Measuring size and error in $\mathbb{R}^n$ · Condition number · Spectral radius · The Power Method
Every error bound so far has measured error with plain absolute value - fine when the unknown is a single number, but every method in this chapter and the next works with entire vectors and matrices as the basic unit. "How big is the error" needs a genuine generalization of absolute value first - a norm - before any of Chapter 14's convergence theorems for linear-system solvers can even be stated. This chapter builds that machinery and its single most important derived quantity, the condition number, then introduces eigenvalues through the one algorithm this course needs them for: the Power Method.
Section 7.1
Vector Norms
Definition - Vector Norm
A vector norm on $\mathbb R^n$ is a function $\|\cdot\|:\mathbb R^n\to\mathbb R$ satisfying $\|\mathbf x\|\ge0$ (with equality iff $\mathbf x=\mathbf 0$), $\|\alpha\mathbf x\|=|\alpha|\,\|\mathbf x\|$, and the triangle inequality $\|\mathbf x+\mathbf y\|\le\|\mathbf x\|+\|\mathbf y\|$. The three standard choices:
$$\|\mathbf x\|_1 = \sum_{i=1}^n|x_i|, \qquad \|\mathbf x\|_2 = \left(\sum_{i=1}^n x_i^2\right)^{1/2}, \qquad \|\mathbf x\|_\infty = \max_{1\le i\le n}|x_i|$$
📘 Example 13.1 - Computing All Three Norms
Compute $\|\mathbf x\|_1,\,\|\mathbf x\|_2,\,\|\mathbf x\|_\infty$ for $\mathbf x=(3,-4,0,1)$.
Solution
$$\|\mathbf x\|_1 = |3|+|-4|+|0|+|1| = 8$$
$$\|\mathbf x\|_2 = \sqrt{9+16+0+1} = \sqrt{26} \approx 5.099$$
$$\|\mathbf x\|_\infty = \max(3,4,0,1) = 4$$
Notice $\|\mathbf x\|_\infty \le \|\mathbf x\|_2 \le \|\mathbf x\|_1$ always holds - a general fact, not a coincidence of this example.
Section 7.2
Matrix Norms & Condition Number
Definition - Induced Matrix Norm
The matrix norm induced by a vector norm is $\|A\| = \max_{\|\mathbf x\|=1}\|A\mathbf x\|$ - the most an $n\times n$ matrix $A$ can stretch a unit vector. For the $\infty$-norm, this has a simple closed form:
$$\|A\|_\infty = \max_{1\le i\le n}\sum_{j=1}^n |a_{ij}| \qquad \text{(maximum absolute row sum)}$$
Definition - Condition Number
$$\kappa(A) = \|A\|\cdot\|A^{-1}\|$$
For the linear system $A\mathbf x=\mathbf b$, if $\mathbf b$ is perturbed to $\mathbf b+\delta\mathbf b$, the resulting solution perturbation satisfies
$$\frac{\|\delta\mathbf x\|}{\|\mathbf x\|} \le \kappa(A)\,\frac{\|\delta\mathbf b\|}{\|\mathbf b\|}$$
$\kappa(A)\ge1$ always; $\kappa(A)$ near $1$ means $A$ is well-conditioned (small input errors stay small); $\kappa(A)\gg1$ means $A$ is ill-conditioned - even tiny round-off in $\mathbf b$ (inevitable in floating point, Chapter 1) can be amplified into a wildly wrong $\mathbf x$, regardless of which linear-system-solving method from Chapter 14 is used.
📘 Example 13.2 - Well- vs. Ill-Conditioned, Side by Side
Compute $\kappa_\infty(A)$ for $A=\begin{pmatrix}1&2\\3&4\end{pmatrix}$ and $H=\begin{pmatrix}1&0.5\\0.5&0.3333\end{pmatrix}$.
Solution
$\|A\|_\infty=\max(3,7)=7$. $A^{-1}=\begin{pmatrix}-2&1\\1.5&-0.5\end{pmatrix}$, $\|A^{-1}\|_\infty=\max(3,2)=3$. So $\kappa_\infty(A)=7\times3=21$.
$\|H\|_\infty=\max(1.5,0.8333)=1.5$. $H^{-1}=\begin{pmatrix}4&-6\\-6&12\end{pmatrix}$, $\|H^{-1}\|_\infty=\max(10,18)=18$. So $\kappa_\infty(H)=1.5\times18=27$.
Solving $H\mathbf x=\mathbf b$ with $\mathbf b=(1.5,\,0.8333)$ gives $\mathbf x=(1,1)$. Perturbing $\mathbf b$ by just $(0.001,0)$: $\mathbf x$ shifts to $(1.004,\,0.994)$ - a perturbation of size $0.001$ in $\mathbf b$ (relative error $\approx0.0007$) produced a shift of size $0.006$ in $\mathbf x$ (relative error $\approx0.006$), roughly $\kappa(H)\times$ larger, exactly as the bound predicts. $H$ here behaves like a small piece of the notoriously ill-conditioned Hilbert matrix.
$\|H\|_\infty=\max(1.5,0.8333)=1.5$. $H^{-1}=\begin{pmatrix}4&-6\\-6&12\end{pmatrix}$, $\|H^{-1}\|_\infty=\max(10,18)=18$. So $\kappa_\infty(H)=1.5\times18=27$.
Solving $H\mathbf x=\mathbf b$ with $\mathbf b=(1.5,\,0.8333)$ gives $\mathbf x=(1,1)$. Perturbing $\mathbf b$ by just $(0.001,0)$: $\mathbf x$ shifts to $(1.004,\,0.994)$ - a perturbation of size $0.001$ in $\mathbf b$ (relative error $\approx0.0007$) produced a shift of size $0.006$ in $\mathbf x$ (relative error $\approx0.006$), roughly $\kappa(H)\times$ larger, exactly as the bound predicts. $H$ here behaves like a small piece of the notoriously ill-conditioned Hilbert matrix.
Section 7.2 continued
Eigenvalues & Spectral Radius
Definition - Eigenvalue, Eigenvector, Spectral Radius
$\lambda$ is an eigenvalue of $A$ with eigenvector $\mathbf x\neq\mathbf0$ if $A\mathbf x=\lambda\mathbf x$ - equivalently, $\det(A-\lambda I)=0$ (the characteristic equation, Chapter 6's determinant machinery in a new role). The spectral radius is $\rho(A)=\max_i|\lambda_i|$, the largest eigenvalue magnitude.
Spectral Radius Is a Lower Bound for Every Matrix Norm
$$\rho(A) \le \|A\|$$
for any induced matrix norm - this single inequality is the reason $\rho(A)<1$ is exactly the right condition to check for convergence of iterative methods (Chapter 14's Jacobi and Gauss-Seidel methods), generalizing the scalar condition $|g'(p)|<1$ from Chapter 3's Fixed-Point Theorem to matrices.
Section 7.3 preview
The Power Method
Finding the Dominant Eigenvalue by Iteration
If $A$ has a strictly dominant eigenvalue $|\lambda_1|>|\lambda_2|\ge\cdots\ge|\lambda_n|$ with eigenvector $\mathbf v_1$, then for almost any starting vector $\mathbf x_0$ (any vector with a nonzero component along $\mathbf v_1$):
$$\mathbf x_{k+1} = A\mathbf x_k, \qquad \text{normalized each step}$$
converges in direction to $\mathbf v_1$, and the normalizing scale factor converges to $\lambda_1$. Why it works: write $\mathbf x_0 = c_1\mathbf v_1+\cdots+c_n\mathbf v_n$ in the eigenbasis. Then $A^k\mathbf x_0 = c_1\lambda_1^k\mathbf v_1 + \cdots + c_n\lambda_n^k\mathbf v_n = \lambda_1^k\left(c_1\mathbf v_1 + \sum_{i\ge2}c_i(\lambda_i/\lambda_1)^k\mathbf v_i\right)$ - every term but the first shrinks geometrically since $|\lambda_i/\lambda_1|<1$, at a rate governed by the ratio $|\lambda_2/\lambda_1|$ (the closer this ratio is to $1$, the slower the convergence - directly analogous to Chapter 3's asymptotic error constant).
Power Method on $A=\begin{pmatrix}4&1\\2&3\end{pmatrix}$ (true eigenvalues $5$ and $2$, dominant eigenvector along $(1,1)$). Each click applies $A$ and renormalizes - watch the vector (red arrow) swing into alignment with the dominant eigenvector direction (dashed) while the eigenvalue estimate climbs toward $5$.
📘 Example 13.3 - Power Method by Hand
Apply the Power Method to $A=\begin{pmatrix}4&1\\2&3\end{pmatrix}$ from $\mathbf x_0=(1,0)$, normalizing by the largest-magnitude component each step.
Solution
The eigenvalue estimate climbs steadily toward the true dominant eigenvalue $\lambda_1=5$, and the normalized vector approaches $(1,1)$ - the true dominant eigenvector direction - confirming both parts of the theorem simultaneously. The ratio $|\lambda_2/\lambda_1|=2/5=0.4$ here predicts roughly linear convergence with constant $0.4$, visible in how the error shrinks by close to that factor each step.
| $k$ | $A\mathbf x_{k-1}$ | eigenvalue estimate | normalized $\mathbf x_k$ |
|---|---|---|---|
| 1 | $(4,\,2)$ | 4.000000 | $(1,\,0.5)$ |
| 2 | $(4.5,\,3.5)$ | 4.500000 | $(1,\,0.7778)$ |
| 3 | $(4.7778,\,4.3333)$ | 4.777778 | $(1,\,0.9070)$ |
| 4 | $(4.9070,\,4.7209)$ | 4.906977 | $(1,\,0.9621)$ |
| 5 | $(4.9621,\,4.8863)$ | 4.962085 | $(1,\,0.9847)$ |
| 7 | - | 4.993869 | $(1,\,0.9975)$ |
Practice
Practice Problem
Try this problem yourself before expanding the solution below.
✏️ Practice Problem 13.1 - Norms, Condition Number, and the Power Method
For $A=\begin{pmatrix}5&2\\2&2\end{pmatrix}$, compute $\|A\|_\infty$, $\|A\|_1$, and the condition number $\text{cond}_\infty(A)$. Then apply the Power Method starting from $x^{(0)}=(1,0)^T$ for four iterations to estimate the dominant eigenvalue.
Solution
Row sums give $\|A\|_\infty=\max(5+2,\,2+2)=7$; column sums give $\|A\|_1=\max(5+2,\,2+2)=7$ (symmetric, so they agree). The inverse is
$$A^{-1}=\begin{pmatrix}0.333333&-0.333333\\-0.333333&0.833333\end{pmatrix}, \qquad \|A^{-1}\|_\infty = 1.166667,$$
so $\text{cond}_\infty(A) = 7\times1.166667 = 8.166667$ - well-conditioned, not close to singular.
Power Method ($y^{(k)}=Ax^{(k-1)}$, $\mu_k=$ largest-magnitude entry of $y^{(k)}$, $x^{(k)}=y^{(k)}/\mu_k$):
$\text{cond}_\infty(A)=8.166667$; the Power Method estimates $\mu_4=5.994220$, closing in on the true dominant eigenvalue $\lambda_1=6$ with eigenvector direction $(1,\,0.5)$.
Power Method ($y^{(k)}=Ax^{(k-1)}$, $\mu_k=$ largest-magnitude entry of $y^{(k)}$, $x^{(k)}=y^{(k)}/\mu_k$):
| $k$ | $y^{(k)}$ | $\mu_k$ | $x^{(k)}$ |
|---|---|---|---|
| 1 | $(5,\,2)$ | 5.000000 | $(1,\,0.400000)$ |
| 2 | $(5.8,\,2.8)$ | 5.800000 | $(1,\,0.482759)$ |
| 3 | $(5.9655,\,2.9655)$ | 5.965517 | $(1,\,0.497110)$ |
| 4 | $(5.9942,\,2.9942)$ | 5.994220 | $(1,\,0.499518)$ |
Connections Across the Course
- The condition number $\kappa(A)$ explains why some linear systems in Chapter 14 resist accurate solution no matter which method is used - it is a property of $A$ itself, not of the solution algorithm.
- $\rho(A)<1$ is the exact matrix generalization of Chapter 3's scalar convergence condition $|g'(p)|<1$, and is the convergence criterion for Jacobi and Gauss-Seidel in the next chapter.
- The Power Method's geometric-decay argument is structurally the same eigenvalue-ratio reasoning used to analyze convergence rates of the iterative linear-system solvers immediately following it.