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=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 b is off by a little, how far off is x? For some matrices, a change in the sixth decimal place of b changes the first digit of x. 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∥.
Quick checkWhich singular value says how much A can stretch a unit vector, at most?
σ1=max∥Ax∥ over unit x (a 3.4 problem). The smallest, σn, is the least stretch, and it controls how much A−1 can stretch.Review: singular values
Quick checkIf A=UΣVT is invertible, what are the singular values of A−1?
A−1=VΣ−1UT, so its stretches are the reciprocals. Its largest stretch is 1/σn.Review: the SVD
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∥. 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 A (with the usual length on vectors) is
∥A∥=x=Omax∥x∥∥Ax∥=σ1.
It satisfies ∥Ax∥≤∥A∥∥x∥ for every x, and ∥AB∥≤∥A∥∥B∥. For invertible A, ∥A−1∥=1/σn.
In one line∥A∥=maxx=O∥x∥∥Ax∥: 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 ∥x∥∥Ax∥ is at least the ratio for this particular x. The second follows by applying the first twice: ∥ABx∥≤∥A∥∥Bx∥≤∥A∥∥B∥∥x∥. The third: if A=UΣVT then A−1=VΣ−1UT, which is an SVD with diagonal entries σi1, and its largest entry is σn1 because σn is the smallest of the σi.
Definition B
Condition number
The condition number of an invertible matrix is κ(A)=∥A∥∥A−1∥=σnσ1. Always κ(A)≥1. A matrix with κ near 1 is well conditioned; a large κ means ill conditioned. A singular matrix has κ=∞.
In one lineκ(A)=∥A∥∥A−1∥=σ1/σ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 BTrefethen–Bau Lecture 12; Strang 9.2
Error amplification bound
Let A be invertible, Ax=b with b=O, and A(x+δx)=b+δb. Then
∥x∥∥δx∥≤κ(A)∥b∥∥δb∥.
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=δb, so δx=A−1δb.
Subtract Ax=b from A(x+δx)=b+δb; linearity.
∥δx∥≤∥A−1∥∥δb∥.
The defining property of the operator norm, applied to A−1.
∥x∥1≤∥b∥∥A∥.
Same property applied to A and x: ∥b∥=∥Ax∥≤∥A∥∥x∥; divide by ∥b∥∥x∥>0.
∥x∥∥δx∥≤∥A∥∥A−1∥∥b∥∥δb∥=κ(A)∥b∥∥δb∥. ■
Multiply the two inequalities (both sides positive).
Why· The picture behind the bound
In SVD coordinates A stretches by σ1 in the best direction and only σn in the worst. The worst case for relative error is when the true b lies along the strongly stretched direction (so x is small compared with b) while the error δb lies along the weakly stretched direction (so A−1 blows it up by 1/σn). The ratio of these extremes is σ1/σn. In the picture above, b=(2,2.0001) lies almost exactly along the strong direction (1,1), and the nudge (0,0.0001) has a large component along the weak direction (1,−1).
Your answerA system has κ(A)=106 and b is known to 8 significant digits (relative error 10−8). At most how large can the relative error in x be? Give it as a power of 10, e.g. 1e-5.
κ×10−8=106×10−8=10−2. You can only trust about 2 significant digits of x, even though b had 8.
Definition B
Machine epsilon
Machine epsilonεmach is the largest relative error from rounding a real number to the nearest floating-point number: 2−53≈1.1×10−16 in the double precision used by Python, NumPy and MATLAB. (NumPy’s np.finfo(float).eps reports 2−52≈2.2×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. By the bound, the answer can then be off by κ×10−16. If κ=10k, expect to lose about k of the 16 digits. A matrix with κ=1016 is, to the computer, singular.
Worked example
How many digits can you trust when solving with the 8×8 Hilbert matrix Hij=i+j−11?
Solution.
Compute the condition number.np.linalg.cond(H) gives κ(H8)≈1.5×1010. The Hilbert matrix’s columns are nearly dependent: its rows look alike.
Apply the rule of thumb.log10(1.5×1010)≈10 digits lost out of 16. Each factor of 10 in κ costs one decimal digit.
Check experimentally. Take x=(1,1,…,1), compute b=Hx, solve Hy=b in double precision: y agrees with x to about 7 digits (largest error about 1.2×10−7). The bound says the relative error is at most about 1.5×1010×1.1×10−16≈1.7×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 H13, κ≈3×1018 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,… 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 npn = 10H = 1 / (np.arange(1, n + 1)[:, None] + np.arange(1, n + 1)[None, :] - 1) # Hilbert matrixx = np.ones(n)b = H @ xy = 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−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−10, 10−7 and then about 0.3 (no correct digits left), while the residual stays near 10−16 every time. A tiny residual does not prove a small error.
Worked example
Show that detA is a bad test for near-singularity.
Solution.
A well-conditioned matrix with tiny determinant.A=0.1I100: detA=10−100, astronomically small. The determinant multiplies 100 eigenvalues of size 0.1.
Its condition number. All singular values are 0.1, so κ(A)=1, the best possible. Solving Ax=b is trivially accurate. κ compares the largest and smallest stretch; uniform shrinking does not hurt.
An ill-conditioned matrix with determinant 1.[101081] has det=1 but κ≈1016. One direction is stretched by 108, the other shrunk by 10−8; the determinant (their product) hides both.
Answer. The determinant measures volume change, not sensitivity. Use κ (or the smallest singular value relative to the largest) to judge near-singularity.
Worked example
Find ∥A∥, ∥A−1∥ and κ(A) for A=diag(5,2,0.01). What is κ of an orthogonal matrix?
Solution.
Singular values of a diagonal matrix.ATA=diag(25,4,0.0001), so the singular values are 5,2,0.01. The square roots of the diagonal entries of ATA. For a positive diagonal matrix they are the diagonal entries themselves.
The norm.∥A∥=σ1=5. The operator norm is the largest singular value.
The inverse.A−1=diag(51,21,100), so ∥A−1∥=100=σ31. The largest entry of the inverse comes from the smallest singular value.
The condition number.κ=5×100=500=0.015. Both formulas of the definition agree.
Orthogonal matrices. All singular values of an orthogonal Q are 1 (since QTQ=I), so κ(Q)=1. No direction is stretched more than another, so no error is magnified.
Answer.∥A∥=5, ∥A−1∥=100, κ(A)=500. Orthogonal matrices have κ=1, the best possible.
Your answerWhat is κ(A) for A=diag(5,2,0.01)?
Largest singular value over smallest.
The singular values are 5,2,0.01, so κ=0.015=500.
Worked example
Find κ for the symmetric matrix [1111.0001] of the opening picture.
Solution.
Use symmetry. For a symmetric positive definite matrix the singular values are the eigenvalues. A=QΛQT is already an SVD when every λi>0 (3.4).
Characteristic polynomial. Trace 2.0001, determinant 1.0001−1=0.0001, so λ2−2.0001λ+0.0001=0. For a 2×2 matrix, sum of eigenvalues is the trace and product is the determinant.
Solve.λ1≈2.00005 and λ2=λ10.0001≈0.00004999. The large root is about the trace. The small root then comes from the product, which avoids subtracting two nearly equal numbers.
Divide.κ=0.000049992.00005≈40002. Definition: largest over smallest singular value.
Answer.κ≈4×104, so a relative error in b can be magnified by up to about 40,000, matching the jump seen in the picture. The determinant here is 0.0001, but as the previous example showed, the determinant alone is not what decides this.
Worked example
You can measure b to relative error 10−3 and need x correct to 1%. How large may κ(A) be? How many digits of a 16-digit computation survive if κ=109?
Solution.
Write the bound.∥x∥∥δx∥≤κ⋅∥b∥∥δb∥. The error amplification theorem.
Insert the data. We need κ⋅10−3≤10−2. 1% is 10−2.
Solve.κ≤10. Divide both sides by 10−3.
Digits. With κ=109 and rounding error 10−16, the relative error in x can be 109×10−16=10−7. Same bound with εmach as the data error.
Answer.κ≤10. With κ=109 about 7 of the 16 digits survive.
Your answerA matrix has κ=109. About how many of the 16 digits of a double-precision solution can you trust?
Subtract log10κ from 16.
The relative error can be about κ×10−16=10−7, which means about 7 correct digits.
Quick checkA solver returns an answer with a tiny residual ∥Ax−b∥, but κ(A)=1012. What can you conclude about the error in x?
The bound ∥x∥∥δx∥≤κ∥b∥∥δb∥ also applies with δb = the residual. With κ=1012 a residual of 10−16 (relative) can still hide an error of 10−4 in x. A small residual is not proof of an accurate x.
Worked example
Prove κ(AB)≤κ(A)κ(B) for invertible A and B.
Solution.
Norm of the product.∥AB∥≤∥A∥∥B∥. Submultiplicativity, shown after the definition.
Inverse of the product.(AB)−1=B−1A−1, so ∥(AB)−1∥≤∥B−1∥∥A−1∥. The inverse of a product reverses the order (2.4), then submultiplicativity again.
Multiply the two bounds.κ(AB)=∥AB∥∥(AB)−1∥≤∥A∥∥B∥∥B−1∥∥A−1∥. All quantities are positive, so multiplying inequalities is allowed.
Regroup. The right side is ∥A∥∥A−1∥⋅∥B∥∥B−1∥=κ(A)κ(B). Numbers commute.
Answer.κ(AB)≤κ(A)κ(B). ■ Equality can fail: if B=A−1 then κ(AB)=κ(I)=1, which can be far below κ(A)2.
Worked example
Prove κ(ATA)=κ(A)2 for invertible square A, and check it for A=[3405].
Solution.
Insert the SVD.ATA=(VΣUT)(UΣVT). A=UΣVT and AT=VΣTUT=VΣUT, since Σ is diagonal.
Cancel UTU.=VΣ2VT. U is orthogonal, so UTU=I.
Read off the singular values. This is an SVD of ATA with singular values σi2. Orthogonal V, diagonal Σ2 with non-negative entries in decreasing order.
Divide.κ(ATA)=σn2σ12=κ(A)2. Definition of κ.
Check. For A=[3405] the singular values are 35 and 5, so κ(A)=3. And ATA has eigenvalues 45 and 5, so κ(ATA)=9=32. Numbers from 3.4.
Answer.κ(ATA)=κ(A)2. ■ 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).
Solution.
Setup. Here U=V=I, σ1=2, σ2=0.01, κ=200. A diagonal matrix with positive entries is its own SVD.
Pick b along the strong direction.b=(2,0)=σ1u1, so x=A−1b=(1,0). The data is large compared with the answer.
Pick the error along the weak direction.δb=(0,η), so δx=A−1δb=(0,100η). A−1 multiplies this direction by σ21=100.
Compare.∥x∥∥δx∥=100η and κ∥b∥∥δb∥=200⋅2η=100η. The two sides of the bound are equal.
Answer. Equality holds, so no smaller number than κ can replace κ in the theorem. In general take b=σ1u1 and δb=ηun. ■
Quick checkYou multiply a matrix A by 1000. What happens to κ(A)?
κ=σ1/σn, and both are scaled by the same factor. This is why the determinant (which scales by 1000n) is a bad guide and κ is a good one.
Quick checkFor least squares, why is solving the normal equations ATAx^=ATb risky on real data?
The singular values of ATA are σi2, so its condition number is squared. With κ(A)=108, the normal equations face 1016 and lose everything; QR (2.10) works with κ(A) itself.
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.
Subtract the two systems; linearity.
Operator norm of A−1.
First express δx in terms of δb.
Operator norm of A applied to b=Ax.
Combine the two bounds; κ=∥A∥∥A−1∥.
You need both bounds before multiplying them.
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 of yours, so its error is about κε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.1I100)=10−100 and κ=1. Judge with κ, never with the determinant.
Watch out· A good algorithm cannot fix a bad problem
If κ(A)=1012, 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∥ and κ(A) for A=diag(5,2,0.01).
Solution
∥A∥=5, ∥A−1∥=100, κ=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 κ for [1111.0001] from the step-through, using the fact that it is symmetric.
Solution
Eigenvalues are roots of λ2−2.0001λ+0.0001=0: about 2.00005 and 0.0000500. Symmetric positive definite, so singular values equal eigenvalues and κ≈2.00005/0.00005≈40002.
use
A measurement vector b has relative error 10−3 and you want x to 1% accuracy. How large may κ(A) be?
Solution
Need κ⋅10−3≤10−2, so κ≤10.
prove
Prove κ(AB)≤κ(A)κ(B) for invertible A,B.
Solution
∥AB∥≤∥A∥∥B∥ and ∥(AB)−1∥=∥B−1A−1∥≤∥B−1∥∥A−1∥. Multiply.
prove
Prove κ(ATA)=κ(A)2 for an invertible square A.
Solution
ATA=VΣTΣVT=VΣ2VT, an SVD with singular values σi2. So κ(ATA)=σ12/σn2.
stretchTrefethen–Bau 12
Show the bound is sharp: find b and δb for which equality holds.
Solution
Take b=σ1u1 (so x=v1, ∥x∥=1, ∥b∥=σ1) and δb=ηun (so δx=σnηvn). Then ∥x∥∥δx∥=σnη and κ∥b∥∥δb∥=σnσ1⋅σ1η=σnη. Equal.
Summary
Operator norm∥A∥=σ1: the largest stretch. ∥Ax∥≤∥A∥∥x∥.
Condition numberκ=σ1/σn: the worst-case magnification of relative error in solving Ax=b.
Relative error in x≤κ × relative error in b, and the bound can be attained.
Floating point rounds everything by about 10−16; expect to lose about log10κ digits.
The determinant is a bad test; κ is the right one. Normal equations square κ; QR and SVD do not.
Watch and read
The same ideas explained by someone else. Use these when an explanation here does not land.
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.