Survey of Mathematics

3.5 Matrix norms, conditioning, and why numerics fail

Some linear systems turn a tiny error in the data into a huge error in the answer. The condition number, the ratio of the largest to the smallest singular value, measures exactly how much, and tells you how many digits a computer can be trusted with.

Beyond the courseTrefethen and Bau, Numerical Linear Algebra, Lectures 3 and 12 to 15Strang, Introduction to Linear Algebra, 9.2CS 532 (Matrix Methods in Machine Learning)

On paper, a square matrix is either invertible or it is not, and Ax=bAx = b has one exact answer. On a computer, every number carries a tiny rounding error, and the data itself usually comes from measurements. The question that matters in practice is: if bb is off by a little, how far off is xx? For some matrices, a change in the sixth decimal place of bb changes the first digit of xx. This chapter measures that sensitivity with one number, explains it with the SVD, and shows why some textbook methods are dangerous on real data.

Before you start

Chapter 3.4: singular values and σ1=max⁡∥x∥=1∥Ax∥\sigma_1 = \max_{\lVert x \rVert = 1}\lVert Ax \rVert.

Quick checkWhich singular value says how much AA can stretch a unit vector, at most?
Quick checkIf A=UΣVTA = U\Sigma V^{\mathsf T} is invertible, what are the singular values of A−1A^{-1}?

The picture: a system that magnifies errors

Where this came from· Turing, von Neumann, and the birth of numerical analysis

When electronic computers arrived in the 1940s, mathematicians had to ask whether Gaussian elimination could be trusted with thousands of rounded numbers. John von Neumann and Herman Goldstine published a rounding-error analysis of matrix inversion in 1947, with worst-case bounds that looked alarming. In 1948 Alan Turing wrote “Rounding-off errors in matrix processes”, the earliest paper known to use the term “condition number” and the formula κ=∥A∥ ∥A−1∥\kappa = \lVert A \rVert\,\lVert A^{-1} \rVert. James Wilkinson’s backward error analysis, developed from about 1961, showed that elimination with pivoting is reliable in practice, and that the real culprit, when answers go wrong, is usually the conditioning of the problem rather than the algorithm.

Definitions and theorems

Definition B

Operator norm

The operator norm of AA (with the usual length on vectors) is

∥A∥=max⁡x≠O∥Ax∥∥x∥=σ1.\lVert A \rVert = \max_{x \ne O} \frac{\lVert Ax \rVert}{\lVert x \rVert} = \sigma_1.

It satisfies ∥Ax∥≤∥A∥ ∥x∥\lVert Ax \rVert \le \lVert A \rVert\,\lVert x \rVert for every xx, and ∥AB∥≤∥A∥ ∥B∥\lVert AB \rVert \le \lVert A \rVert\,\lVert B \rVert. For invertible AA, ∥A−1∥=1/σn\lVert A^{-1} \rVert = 1/\sigma_n.

In one line∥A∥=max⁡x≠O∥Ax∥∥x∥\lVert A \rVert = \max_{x \ne O}\frac{\lVert Ax \rVert}{\lVert x \rVert}: the largest factor by which A stretches any vector; for the usual length it equals σ₁.

Why it existsIt turns 'how big is a matrix' into one number with the property ‖Ax‖ ≤ ‖A‖‖x‖, which is exactly what error estimates need.

Each of those three facts has a short reason. The first is the definition: the largest ratio ∥Ax∥∥x∥\frac{\lVert Ax \rVert}{\lVert x \rVert} is at least the ratio for this particular xx. The second follows by applying the first twice: ∥ABx∥≤∥A∥ ∥Bx∥≤∥A∥ ∥B∥ ∥x∥\lVert ABx \rVert \le \lVert A \rVert\,\lVert Bx \rVert \le \lVert A \rVert\,\lVert B \rVert\,\lVert x \rVert. The third: if A=UΣVTA = U\Sigma V^{\mathsf T} then A−1=VΣ−1UTA^{-1} = V\Sigma^{-1}U^{\mathsf T}, which is an SVD with diagonal entries 1σi\frac1{\sigma_i}, and its largest entry is 1σn\frac1{\sigma_n} because σn\sigma_n is the smallest of the σi\sigma_i.

Definition B

Condition number

The condition number of an invertible matrix is κ(A)=∥A∥ ∥A−1∥=σ1σn\kappa(A) = \lVert A \rVert\,\lVert A^{-1} \rVert = \dfrac{\sigma_1}{\sigma_n}. Always κ(A)≥1\kappa(A) \ge 1. A matrix with κ\kappa near 1 is well conditioned; a large κ\kappa means ill conditioned. A singular matrix has κ=∞\kappa = \infty.

In one lineκ(A)=∥A∥ ∥A−1∥=σ1/σn\kappa(A) = \lVert A \rVert\,\lVert A^{-1} \rVert = \sigma_1/\sigma_n: the worst-case factor by which A magnifies relative errors in solving Ax = b.

Why it existsIt is the one number that predicts how many correct digits a computed answer can have.

Theorem B Trefethen–Bau Lecture 12; Strang 9.2

Error amplification bound

Let AA be invertible, Ax=bAx = b with b≠Ob \ne O, and A(x+δx)=b+δbA(x + \delta x) = b + \delta b. Then

∥δx∥∥x∥≤κ(A) ∥δb∥∥b∥.\frac{\lVert \delta x \rVert}{\lVert x \rVert} \le \kappa(A)\,\frac{\lVert \delta b \rVert}{\lVert b \rVert}.

In one lineIf Ax = b and A(x + δx) = b + δb, then ‖δx‖/‖x‖ ≤ κ(A) · ‖δb‖/‖b‖.

Why it is trueδx = A⁻¹δb can be up to ‖A⁻¹‖ times δb, while x can be as small as ‖b‖/‖A‖; the ratio of these two worst cases is κ.

ProofStrang 9.2
The idea: Subtract the equations to get A δx = δb, so δx = A⁻¹δb and ‖δx‖ ≤ ‖A⁻¹‖‖δb‖. From b = Ax, ‖b‖ ≤ ‖A‖‖x‖, so 1/‖x‖ ≤ ‖A‖/‖b‖. Multiply the two inequalities.
A δx=δbA\,\delta x = \delta b, so δx=A−1δb\delta x = A^{-1}\delta b.
Subtract Ax=bAx = b from A(x+δx)=b+δbA(x + \delta x) = b + \delta b; linearity.
∥δx∥≤∥A−1∥ ∥δb∥\lVert \delta x \rVert \le \lVert A^{-1} \rVert\,\lVert \delta b \rVert.
The defining property of the operator norm, applied to A−1A^{-1}.
1∥x∥≤∥A∥∥b∥\dfrac{1}{\lVert x \rVert} \le \dfrac{\lVert A \rVert}{\lVert b \rVert}.
Same property applied to AA and xx: ∥b∥=∥Ax∥≤∥A∥ ∥x∥\lVert b \rVert = \lVert Ax \rVert \le \lVert A \rVert\,\lVert x \rVert; divide by ∥b∥ ∥x∥>0\lVert b \rVert\,\lVert x \rVert > 0.
∥δx∥∥x∥≤∥A∥ ∥A−1∥ ∥δb∥∥b∥=κ(A) ∥δb∥∥b∥\dfrac{\lVert \delta x \rVert}{\lVert x \rVert} \le \lVert A \rVert\,\lVert A^{-1} \rVert\,\dfrac{\lVert \delta b \rVert}{\lVert b \rVert} = \kappa(A)\,\dfrac{\lVert \delta b \rVert}{\lVert b \rVert}. ■\blacksquare
Multiply the two inequalities (both sides positive).
Why· The picture behind the bound

In SVD coordinates AA stretches by σ1\sigma_1 in the best direction and only σn\sigma_n in the worst. The worst case for relative error is when the true bb lies along the strongly stretched direction (so xx is small compared with bb) while the error δb\delta b lies along the weakly stretched direction (so A−1A^{-1} blows it up by 1/σn1/\sigma_n). The ratio of these extremes is σ1/σn\sigma_1/\sigma_n. In the picture above, b=(2,2.0001)b = (2, 2.0001) lies almost exactly along the strong direction (1,1)(1, 1), and the nudge (0,0.0001)(0, 0.0001) has a large component along the weak direction (1,−1)(1, -1).

Your answerA system has κ(A)=106\kappa(A) = 10^6 and bb is known to 8 significant digits (relative error 10−810^{-8}). At most how large can the relative error in xx be? Give it as a power of 10, e.g. 1e-5.
Definition B

Machine epsilon

Machine epsilon εmach\varepsilon_{\text{mach}} is the largest relative error from rounding a real number to the nearest floating-point number: 2−53≈1.1×10−162^{-53} \approx 1.1 \times 10^{-16} in the double precision used by Python, NumPy and MATLAB. (NumPy’s np.finfo(float).eps reports 2−52≈2.2×10−162^{-52} \approx 2.2 \times 10^{-16}, the gap between 1 and the next floating-point number. Rounding to the nearest number is off by at most half a gap, which is why the two differ by a factor of 2. For counting digits the factor does not matter.)

In one lineThe largest relative error from rounding a real number to the nearest floating-point number: about 1.1 × 10⁻¹⁶ in standard double precision.

Why it existsIt is the unavoidable relative error in the data a computer actually works with.

Why· The rule of thumb: you lose log₁₀ κ digits

Even a perfect algorithm must round the input, introducing relative errors about εmach≈10−16\varepsilon_{\text{mach}} \approx 10^{-16}. By the bound, the answer can then be off by κ×10−16\kappa \times 10^{-16}. If κ=10k\kappa = 10^{k}, expect to lose about kk of the 16 digits. A matrix with κ=1016\kappa = 10^{16} is, to the computer, singular.

Worked example
How many digits can you trust when solving with the 8×88 \times 8 Hilbert matrix Hij=1i+j−1H_{ij} = \frac{1}{i + j - 1}?

Solution.

  1. Compute the condition number. np.linalg.cond(H) gives κ(H8)≈1.5×1010\kappa(H_8) \approx 1.5 \times 10^{10}. The Hilbert matrix’s columns are nearly dependent: its rows look alike.
  2. Apply the rule of thumb. log⁡10(1.5×1010)≈10\log_{10}(1.5 \times 10^{10}) \approx 10 digits lost out of 16. Each factor of 10 in κ\kappa costs one decimal digit.
  3. Check experimentally. Take x=(1,1,…,1)x = (1, 1, \dots, 1), compute b=Hxb = Hx, solve Hy=bHy = b in double precision: yy agrees with xx to about 7 digits (largest error about 1.2×10−71.2 \times 10^{-7}). The bound says the relative error is at most about 1.5×1010×1.1×10−16≈1.7×10−61.5 \times 10^{10} \times 1.1 \times 10^{-16} \approx 1.7 \times 10^{-6}, so at least 5 digits survive. The observed error is smaller than this worst case, as usual.

Answer. About 5 to 7 trustworthy digits, from 16. For H13H_{13}, κ≈3×1018\kappa \approx 3 \times 10^{18} and the computed solution is garbage (entries off by about 8 when the true answer is all 1s), although the matrix is mathematically invertible. Fitting high-degree polynomials with the monomial basis 1,t,t2,…1, t, t^2, \dots produces matrices like this, which is why numerical software uses orthogonal polynomials (2.9) instead.

Python labSolve with a Hilbert matrix and watch the error grow
import numpy as np

n = 10
H = 1 / (np.arange(1, n + 1)[:, None] + np.arange(1, n + 1)[None, :] - 1)   # Hilbert matrix
x = np.ones(n)
b = H @ x
y = np.linalg.solve(H, b)

print("condition number:", f"{np.linalg.cond(H):.2e}")
print("relative error in x:", f"{np.linalg.norm(y - x) / np.linalg.norm(x):.2e}")
print("residual |Hy - b|:", f"{np.linalg.norm(H @ y - b):.2e}")
print("digits lost, about:", round(np.log10(np.linalg.cond(H))))

Try this. Run it with n = 10: the residual is about 10−1610^{-16}, yet the answer is wrong in the fifth digit. Now try n = 6, 8 and 12. The error follows the condition number: roughly 10−1010^{-10}, 10−710^{-7} and then about 0.30.3 (no correct digits left), while the residual stays near 10−1610^{-16} every time. A tiny residual does not prove a small error.

Worked example
Show that det⁡A\det A is a bad test for near-singularity.

Solution.

  1. A well-conditioned matrix with tiny determinant. A=0.1 I100A = 0.1\,I_{100}: det⁡A=10−100\det A = 10^{-100}, astronomically small. The determinant multiplies 100 eigenvalues of size 0.1.
  2. Its condition number. All singular values are 0.10.1, so κ(A)=1\kappa(A) = 1, the best possible. Solving Ax=bAx = b is trivially accurate. κ\kappa compares the largest and smallest stretch; uniform shrinking does not hurt.
  3. An ill-conditioned matrix with determinant 1. [110801]\begin{bmatrix}1 & 10^{8}\\ 0 & 1\end{bmatrix} has det⁡=1\det = 1 but κ≈1016\kappa \approx 10^{16}. One direction is stretched by 10810^8, the other shrunk by 10−810^{-8}; the determinant (their product) hides both.

Answer. The determinant measures volume change, not sensitivity. Use κ\kappa (or the smallest singular value relative to the largest) to judge near-singularity.

Worked example
Find ∥A∥\lVert A \rVert, ∥A−1∥\lVert A^{-1} \rVert and κ(A)\kappa(A) for A=diag⁡(5,2,0.01)A = \operatorname{diag}(5, 2, 0.01). What is κ\kappa of an orthogonal matrix?

Solution.

  1. Singular values of a diagonal matrix. ATA=diag⁡(25,4,0.0001)A^{\mathsf T}A = \operatorname{diag}(25, 4, 0.0001), so the singular values are 5,2,0.015, 2, 0.01. The square roots of the diagonal entries of ATAA^{\mathsf T}A. For a positive diagonal matrix they are the diagonal entries themselves.
  2. The norm. ∥A∥=σ1=5\lVert A \rVert = \sigma_1 = 5. The operator norm is the largest singular value.
  3. The inverse. A−1=diag⁡(15,12,100)A^{-1} = \operatorname{diag}(\frac15, \frac12, 100), so ∥A−1∥=100=1σ3\lVert A^{-1} \rVert = 100 = \frac1{\sigma_3}. The largest entry of the inverse comes from the smallest singular value.
  4. The condition number. κ=5×100=500=50.01\kappa = 5 \times 100 = 500 = \frac{5}{0.01}. Both formulas of the definition agree.
  5. Orthogonal matrices. All singular values of an orthogonal QQ are 1 (since QTQ=IQ^{\mathsf T}Q = I), so κ(Q)=1\kappa(Q) = 1. No direction is stretched more than another, so no error is magnified.

Answer. ∥A∥=5\lVert A \rVert = 5, ∥A−1∥=100\lVert A^{-1} \rVert = 100, κ(A)=500\kappa(A) = 500. Orthogonal matrices have κ=1\kappa = 1, the best possible.

Your answerWhat is κ(A)\kappa(A) for A=diag⁡(5,2,0.01)A = \operatorname{diag}(5, 2, 0.01)?
Worked example
Find κ\kappa for the symmetric matrix [1111.0001]\begin{bmatrix}1&1\\1&1.0001\end{bmatrix} of the opening picture.

Solution.

  1. Use symmetry. For a symmetric positive definite matrix the singular values are the eigenvalues. A=QΛQTA = Q\Lambda Q^{\mathsf T} is already an SVD when every λi>0\lambda_i > 0 (3.4).
  2. Characteristic polynomial. Trace 2.00012.0001, determinant 1.0001−1=0.00011.0001 - 1 = 0.0001, so λ2−2.0001λ+0.0001=0\lambda^2 - 2.0001\lambda + 0.0001 = 0. For a 2×22 \times 2 matrix, sum of eigenvalues is the trace and product is the determinant.
  3. Solve. λ1≈2.00005\lambda_1 \approx 2.00005 and λ2=0.0001λ1≈0.00004999\lambda_2 = \frac{0.0001}{\lambda_1} \approx 0.00004999. The large root is about the trace. The small root then comes from the product, which avoids subtracting two nearly equal numbers.
  4. Divide. κ=2.000050.00004999≈40002\kappa = \frac{2.00005}{0.00004999} \approx 40002. Definition: largest over smallest singular value.

Answer. κ≈4×104\kappa \approx 4 \times 10^4, so a relative error in bb can be magnified by up to about 40,000, matching the jump seen in the picture. The determinant here is 0.00010.0001, but as the previous example showed, the determinant alone is not what decides this.

Worked example
You can measure bb to relative error 10−310^{-3} and need xx correct to 1%. How large may κ(A)\kappa(A) be? How many digits of a 16-digit computation survive if κ=109\kappa = 10^{9}?

Solution.

  1. Write the bound. ∥δx∥∥x∥≤κ⋅∥δb∥∥b∥\frac{\lVert \delta x \rVert}{\lVert x \rVert} \le \kappa\cdot\frac{\lVert \delta b \rVert}{\lVert b \rVert}. The error amplification theorem.
  2. Insert the data. We need κ⋅10−3≤10−2\kappa\cdot10^{-3} \le 10^{-2}. 1% is 10−210^{-2}.
  3. Solve. κ≤10\kappa \le 10. Divide both sides by 10−310^{-3}.
  4. Digits. With κ=109\kappa = 10^9 and rounding error 10−1610^{-16}, the relative error in xx can be 109×10−16=10−710^{9}\times10^{-16} = 10^{-7}. Same bound with εmach\varepsilon_{\text{mach}} as the data error.

Answer. κ≤10\kappa \le 10. With κ=109\kappa = 10^9 about 7 of the 16 digits survive.

Your answerA matrix has κ=109\kappa = 10^9. About how many of the 16 digits of a double-precision solution can you trust?
Quick checkA solver returns an answer with a tiny residual ∥Ax−b∥\lVert Ax - b \rVert, but κ(A)=1012\kappa(A) = 10^{12}. What can you conclude about the error in xx?
Worked example
Prove κ(AB)≤κ(A)κ(B)\kappa(AB) \le \kappa(A)\kappa(B) for invertible AA and BB.

Solution.

  1. Norm of the product. ∥AB∥≤∥A∥ ∥B∥\lVert AB \rVert \le \lVert A \rVert\,\lVert B \rVert. Submultiplicativity, shown after the definition.
  2. Inverse of the product. (AB)−1=B−1A−1(AB)^{-1} = B^{-1}A^{-1}, so ∥(AB)−1∥≤∥B−1∥ ∥A−1∥\lVert (AB)^{-1} \rVert \le \lVert B^{-1} \rVert\,\lVert A^{-1} \rVert. The inverse of a product reverses the order (2.4), then submultiplicativity again.
  3. Multiply the two bounds. κ(AB)=∥AB∥ ∥(AB)−1∥≤∥A∥∥B∥∥B−1∥∥A−1∥\kappa(AB) = \lVert AB \rVert\,\lVert (AB)^{-1} \rVert \le \lVert A \rVert\lVert B \rVert\lVert B^{-1} \rVert\lVert A^{-1} \rVert. All quantities are positive, so multiplying inequalities is allowed.
  4. Regroup. The right side is ∥A∥∥A−1∥⋅∥B∥∥B−1∥=κ(A)κ(B)\lVert A \rVert\lVert A^{-1} \rVert\cdot\lVert B \rVert\lVert B^{-1} \rVert = \kappa(A)\kappa(B). Numbers commute.

Answer. κ(AB)≤κ(A)κ(B)\kappa(AB) \le \kappa(A)\kappa(B). ■\blacksquare Equality can fail: if B=A−1B = A^{-1} then κ(AB)=κ(I)=1\kappa(AB) = \kappa(I) = 1, which can be far below κ(A)2\kappa(A)^2.

Worked example
Prove κ(ATA)=κ(A)2\kappa(A^{\mathsf T}A) = \kappa(A)^2 for invertible square AA, and check it for A=[3045]A = \begin{bmatrix}3&0\\4&5\end{bmatrix}.

Solution.

  1. Insert the SVD. ATA=(VΣUT)(UΣVT)A^{\mathsf T}A = (V\Sigma U^{\mathsf T})(U\Sigma V^{\mathsf T}). A=UΣVTA = U\Sigma V^{\mathsf T} and AT=VΣTUT=VΣUTA^{\mathsf T} = V\Sigma^{\mathsf T}U^{\mathsf T} = V\Sigma U^{\mathsf T}, since Σ\Sigma is diagonal.
  2. Cancel UTUU^{\mathsf T}U. =VΣ2VT= V\Sigma^2V^{\mathsf T}. UU is orthogonal, so UTU=IU^{\mathsf T}U = I.
  3. Read off the singular values. This is an SVD of ATAA^{\mathsf T}A with singular values σi2\sigma_i^2. Orthogonal VV, diagonal Σ2\Sigma^2 with non-negative entries in decreasing order.
  4. Divide. κ(ATA)=σ12σn2=κ(A)2\kappa(A^{\mathsf T}A) = \frac{\sigma_1^2}{\sigma_n^2} = \kappa(A)^2. Definition of κ\kappa.
  5. Check. For A=[3045]A = \begin{bmatrix}3&0\\4&5\end{bmatrix} the singular values are 353\sqrt5 and 5\sqrt5, so κ(A)=3\kappa(A) = 3. And ATAA^{\mathsf T}A has eigenvalues 4545 and 55, so κ(ATA)=9=32\kappa(A^{\mathsf T}A) = 9 = 3^2. Numbers from 3.4.

Answer. κ(ATA)=κ(A)2\kappa(A^{\mathsf T}A) = \kappa(A)^2. ■\blacksquare This is why the normal equations lose twice as many digits.

Worked example Trefethen–Bau Lecture 12
Show the error bound can be attained, for A=diag⁡(2,0.01)A = \operatorname{diag}(2, 0.01).

Solution.

  1. Setup. Here U=V=IU = V = I, σ1=2\sigma_1 = 2, σ2=0.01\sigma_2 = 0.01, κ=200\kappa = 200. A diagonal matrix with positive entries is its own SVD.
  2. Pick bb along the strong direction. b=(2,0)=σ1u1b = (2, 0) = \sigma_1u_1, so x=A−1b=(1,0)x = A^{-1}b = (1, 0). The data is large compared with the answer.
  3. Pick the error along the weak direction. δb=(0,η)\delta b = (0, \eta), so δx=A−1δb=(0,100η)\delta x = A^{-1}\delta b = (0, 100\eta). A−1A^{-1} multiplies this direction by 1σ2=100\frac1{\sigma_2} = 100.
  4. Compare. ∥δx∥∥x∥=100η\frac{\lVert \delta x \rVert}{\lVert x \rVert} = 100\eta and κ∥δb∥∥b∥=200⋅η2=100η\kappa\frac{\lVert \delta b \rVert}{\lVert b \rVert} = 200\cdot\frac\eta2 = 100\eta. The two sides of the bound are equal.

Answer. Equality holds, so no smaller number than κ\kappa can replace κ\kappa in the theorem. In general take b=σ1u1b = \sigma_1u_1 and δb=ηun\delta b = \eta u_n. ■\blacksquare

Quick checkYou multiply a matrix AA by 1000. What happens to κ(A)\kappa(A)?
Quick checkFor least squares, why is solving the normal equations ATAx^=ATbA^{\mathsf T}A\hat x = A^{\mathsf T}b risky on real data?
Proof workshopRebuild the error amplification boundStrang 9.2

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

    Where it is used

    Used inside maths· Inside maths: stability of algorithms

    Conditioning belongs to the problem; stability belongs to the algorithm. A backward-stable algorithm (QR, SVD, elimination with partial pivoting in practice) gives the exact answer to a problem within εmach\varepsilon_{\text{mach}} of yours, so its error is about κ εmach\kappa\,\varepsilon_{\text{mach}}, the best possible. An unstable algorithm (the normal equations, or elimination without pivoting) can do much worse even on a well-conditioned problem.

    Used in the real world· Engineering and AI: when results cannot be trusted

    GPS receivers solve least squares problems whose conditioning depends on where the satellites are in the sky: satellites bunched together give nearly parallel equations and a large “dilution of precision”, which receivers report so the position’s error bar widens. In deep learning, multiplying through many layers whose weight matrices have singular values above or below 1 makes gradients explode or vanish exponentially; orthogonal initialisation and normalisation layers keep the product’s condition number under control.

    Traps

    Watch out· Small determinant does not mean ill conditioned

    det⁡(0.1 I100)=10−100\det(0.1\,I_{100}) = 10^{-100} and κ=1\kappa = 1. Judge with κ\kappa, never with the determinant.

    Watch out· A good algorithm cannot fix a bad problem

    If κ(A)=1012\kappa(A) = 10^{12}, even a perfect algorithm loses about 12 digits, because the input was rounded. Reformulate the problem (a better basis, regularisation, more data) instead of blaming the solver.

    Problems

    check

    Find ∥A∥\lVert A \rVert and κ(A)\kappa(A) for A=diag⁡(5,2,0.01)A = \operatorname{diag}(5, 2, 0.01).

    Solution

    ∥A∥=5\lVert A \rVert = 5, ∥A−1∥=100\lVert A^{-1} \rVert = 100, κ=500\kappa = 500.

    check

    What is the condition number of an orthogonal matrix?

    Solution

    1: all singular values are 1. Orthogonal matrices are perfectly conditioned (3.3).

    use

    Compute κ\kappa for [1111.0001]\begin{bmatrix}1&1\\1&1.0001\end{bmatrix} from the step-through, using the fact that it is symmetric.

    Solution

    Eigenvalues are roots of λ2−2.0001λ+0.0001=0\lambda^2 - 2.0001\lambda + 0.0001 = 0: about 2.000052.00005 and 0.00005000.0000500. Symmetric positive definite, so singular values equal eigenvalues and κ≈2.00005/0.00005≈40002\kappa \approx 2.00005/0.00005 \approx 40002.

    use

    A measurement vector bb has relative error 10−310^{-3} and you want xx to 1% accuracy. How large may κ(A)\kappa(A) be?

    Solution

    Need κ⋅10−3≤10−2\kappa \cdot 10^{-3} \le 10^{-2}, so κ≤10\kappa \le 10.

    prove

    Prove κ(AB)≤κ(A)κ(B)\kappa(AB) \le \kappa(A)\kappa(B) for invertible A,BA, B.

    Solution

    ∥AB∥≤∥A∥∥B∥\lVert AB \rVert \le \lVert A \rVert\lVert B \rVert and ∥(AB)−1∥=∥B−1A−1∥≤∥B−1∥∥A−1∥\lVert (AB)^{-1} \rVert = \lVert B^{-1}A^{-1} \rVert \le \lVert B^{-1} \rVert\lVert A^{-1} \rVert. Multiply.

    prove

    Prove κ(ATA)=κ(A)2\kappa(A^{\mathsf T}A) = \kappa(A)^2 for an invertible square AA.

    Solution

    ATA=VΣTΣVT=VΣ2VTA^{\mathsf T}A = V\Sigma^{\mathsf T}\Sigma V^{\mathsf T} = V\Sigma^2V^{\mathsf T}, an SVD with singular values σi2\sigma_i^2. So κ(ATA)=σ12/σn2\kappa(A^{\mathsf T}A) = \sigma_1^2/\sigma_n^2.

    stretchTrefethen–Bau 12

    Show the bound is sharp: find bb and δb\delta b for which equality holds.

    Solution

    Take b=σ1u1b = \sigma_1 u_1 (so x=v1x = v_1, ∥x∥=1\lVert x \rVert = 1, ∥b∥=σ1\lVert b \rVert = \sigma_1) and δb=ηun\delta b = \eta u_n (so δx=ησnvn\delta x = \frac{\eta}{\sigma_n}v_n). Then ∥δx∥∥x∥=ησn\frac{\lVert \delta x \rVert}{\lVert x \rVert} = \frac{\eta}{\sigma_n} and κ∥δb∥∥b∥=σ1σn⋅ησ1=ησn\kappa\frac{\lVert \delta b \rVert}{\lVert b \rVert} = \frac{\sigma_1}{\sigma_n}\cdot\frac{\eta}{\sigma_1} = \frac{\eta}{\sigma_n}. Equal.

    Summary

    • Operator norm ∥A∥=σ1\lVert A \rVert = \sigma_1: the largest stretch. ∥Ax∥≤∥A∥∥x∥\lVert Ax \rVert \le \lVert A \rVert\lVert x \rVert.
    • Condition number κ=σ1/σn\kappa = \sigma_1/\sigma_n: the worst-case magnification of relative error in solving Ax=bAx = b.
    • Relative error in xx ≤\le κ\kappa × relative error in bb, and the bound can be attained.
    • Floating point rounds everything by about 10−1610^{-16}; expect to lose about log⁡10κ\log_{10}\kappa digits.
    • The determinant is a bad test; κ\kappa is the right one. Normal equations square κ\kappa; QR and SVD do not.

    Watch and read

    The same ideas explained by someone else. Use these when an explanation here does not land.

    Where this sits

    Comes from
    3.4 The singular value decomposition and PCA
    Leads to
    3.8 Matrix calculus and backpropagation
    Same idea elsewhere
    CS 240 / CS 400: Floating-point numbers store about 16 significant decimal digits. This chapter says how many of them survive solving a linear system.
    MATH 375: Exam answers came out exact because the matrices were small integers. Real data never is, and a determinant near 0 does NOT mean what you think (2.7's trap).
    AI: Exploding and vanishing gradients in deep networks are products of many matrices with large or small singular values; conditioning is the same phenomenon.