Matrix norms and condition numbers · Linear Algebra

§20.0 gave vectors a notion of length. This lesson gives matrices one too — not to measure the matrix's entries directly, but to measure how much it can stretch a vector — and uses it to build the single number that answers a question this course has sidestepped until now: when is solving A\vec x=\vec b numerically trustworthy?

The induced (operator) norm

The induced 2-norm of a matrix A is

$\|A\|_2=\max_{\vec x\neq\vec0}\frac{\|A\vec x\|}{\|\vec x\|}$

Properties, all inherited from the vector norm it's built on (§20.0): \|A\|_2\ge0, \|cA\|_2=|c|\|A\|_2, and submultiplicativity \|AB\|_2\le\|A\|_2\|B\|_2 (stretching twice is bounded by the product of the individual stretch factors).

The condition number

$\kappa(A)=\|A\|_2\,\|A^{-1}\|_2=\frac{\sigma_1}{\sigma_n}$

(largest singular value over smallest, using \|A^{-1}\|_2=1/\sigma_n — A^{-1}'s singular values are the reciprocals of A's, since inverting undoes each stretch factor). \kappa(A)\ge1 always (Cauchy-Schwarz-style argument: 1=\|I\|_2=\|AA^{-1}\|_2\le\|A\|_2\|A^{-1}\|_2).

What it measures: how much a relative error in \vec b can be amplified in the solution \vec x of A\vec x=\vec b. If \vec b is perturbed by a small relative amount \varepsilon, the solution \vec x can change by up to \kappa(A)\cdot\varepsilon — the condition number is the error amplification factor, and it depends only on A, never on which solver or algorithm is used.

\kappa(A) near 1: well-conditioned — errors don't grow much.
\kappa(A) large: ill-conditioned — small input errors (rounding, measurement noise) can produce large, unreliable output errors, even with a mathematically exact algorithm.
\kappa(A)=\infty (singular A, \sigma_n=0): no finite bound at all — the system is on the edge of having no unique solution.

The number this lesson has been building toward

§20.5's normal equations use A^TA, and \kappa(A^TA)=\kappa(A)^2 — squaring the condition number. This is the precise, numerical version of §20.6's informal warning: forming A^TA doesn't just cost more computationally, it makes an already-marginal problem quadratically worse. §20.6's QR route works directly with A (and its orthogonal Q factor, which has \kappa(Q)=1 exactly — orthogonal matrices are perfectly conditioned, since they preserve length in every direction equally, §20.4), avoiding the squaring entirely — this is the concrete numerical justification for every "QR avoids forming A^TA" claim made since §20.5.

Doing it in Python

import numpy as np

A_good = np.array([[2., 0.], [0., 1.]])
A_bad = np.array([[1., 1.], [1., 1.0001]])   # columns nearly parallel

for name, A in [("A_good", A_good), ("A_bad", A_bad)]:
    kappa = np.linalg.cond(A)
    print(f"{name}: singular values={[round(v,6) for v in np.linalg.svd(A, compute_uv=False)]}, "
          f"condition number={round(kappa, 4)}")

A_good: singular values=[2.0, 1.0], condition number=2.0
A_bad: singular values=[2.00005, 5e-05], condition number=40002.0001

Watching a large condition number amplify a tiny perturbation in \vec b:

import numpy as np

A = np.array([[1., 1.], [1., 1.0001]])
b = np.array([2., 2.0001])
b_perturbed = b + np.array([0., 0.0001])   # a tiny relative change in b

x = np.linalg.solve(A, b)
x_perturbed = np.linalg.solve(A, b_perturbed)

rel_change_b = np.linalg.norm(b_perturbed - b) / np.linalg.norm(b)
rel_change_x = np.linalg.norm(x_perturbed - x) / np.linalg.norm(x)

print("relative change in b:", round(float(rel_change_b), 8))
print("relative change in x:", round(float(rel_change_x), 6))
print("amplification factor:", round(float(rel_change_x / rel_change_b), 2))
print("condition number:", round(float(np.linalg.cond(A)), 2))

relative change in b: 3.535e-05
relative change in x: 1.0
amplification factor: 28284.98
condition number: 40002.0

Worked example

Compute \kappa(A) for A=\begin{pmatrix}3&0\\0&12\end{pmatrix} without computing an SVD (it's already diagonal).

For a diagonal matrix, singular values are the absolute diagonal entries (§21.4's connection between eigenvalues and singular values for symmetric — here diagonal, a special case — matrices): \sigma_1=12, \sigma_2=3.

$\kappa(A)=\frac{\sigma_1}{\sigma_2}=\frac{12}3=4$

$\boxed{\kappa(A)=4}$

Sanity check. A^{-1}=\begin{pmatrix}1/3&0\\0&1/12\end{pmatrix}, so \|A\|_2=12 (the larger stretch) and \|A^{-1}\|_2=1/3 (the larger inverse stretch, coming from A's smaller original entry, 3): \kappa(A)=12\times\tfrac13=4 ✓ — matches exactly, and illustrates the general pattern directly: a diagonal matrix's condition number is simply the ratio of its largest to smallest scaling factor, geometrically how "unevenly" it stretches different directions.

Your turn

1. A matrix has \kappa(A)=1. What can you conclude about its singular values, and about A^TA's effect on conditioning?

2. Why is \kappa(A)=\infty exactly when A is singular?

3. True or false: a matrix with a very small determinant is always ill-conditioned.

Solutions

1. \kappa(A)=1 forces \sigma_1=\sigma_n — since singular values are ordered \sigma_1\ge\cdots\ge\sigma_n\ge0 and the ratio of the extremes is 1, every singular value must be equal (they're squeezed between the largest and smallest, which now coincide). Such a matrix is a scalar multiple of an orthogonal matrix — perfectly conditioned, and \kappa(A^TA)=\kappa(A)^2=1 too, so squaring changes nothing in this best case.

2. \kappa(A)=\sigma_1/\sigma_n, and singular A means \sigma_n=0 (§21.4's rank test: a zero singular value exactly signals a rank deficiency) — dividing by zero gives \infty, matching the intuition that a singular system has no well-defined "amplification factor" at all, since it doesn't have a unique solution to amplify errors around in the first place.

3. False. Determinant and condition number measure different things: \det A=\prod\sigma_i (all singular values multiplied) while \kappa(A)=\sigma_1/\sigma_n (just the extremes, ratioed) — a matrix like 0.001\times I_{100} has a tiny determinant (0.001^{100}) but \kappa=1 (perfectly conditioned, every singular value equal). A small determinant signals overall shrinkage, not uneven stretching, and only the latter is what makes a system ill-conditioned.

Check yourself in code

Compute the condition number of A=\begin{pmatrix}4&0\\0&1\end{pmatrix} via its singular values, and classify it as well- or ill-conditioned using the threshold \kappa<100.

Print exactly this:

singular values: [4.0, 1.0]
condition number: 4.0
well-conditioned: True

import numpy as np

A = np.array([[4., 0.], [0., 1.]])
s = np.linalg.svd(A, compute_uv=False)
print("singular values:", [round(v, 4) for v in s.tolist()])
# print the condition number (s[0]/s[-1]) and whether it's < 100

import numpy as np

A = np.array([[4., 0.], [0., 1.]])
s = np.linalg.svd(A, compute_uv=False)
print("singular values:", [round(v, 4) for v in s.tolist()])

kappa = s[0] / s[-1]
print("condition number:", round(float(kappa), 4))
print("well-conditioned:", bool(kappa < 100))

The induced matrix norm \|A\|_2=\sigma_1 measures A's maximum stretch; the condition number \kappa(A)=\sigma_1/\sigma_n\ge1 measures how unevenly it stretches different directions, and bounds how much relative error in \vec b gets amplified when solving A\vec x=\vec b. Forming A^TA squares the condition number — the precise numerical reason §20.6's QR-based least squares is preferred over §20.5's normal equations.

Next: a completely different route to an eigenvalue — power iteration, which finds only the dominant one, but does it using nothing more than repeated matrix-vector multiplication.

40. Matrix norms and condition numbers