This section asks what rank information survives a stated matrix perturbation, a different question from the residual and sensitivity analysis of the previous unit. It uses real finite matrices with and the spectral norm throughout.
An exact integer can be sensitive
Let have singular values , . Its exact rank is the number of strictly positive singular values. This statement concerns an exact matrix. A measurement or stored approximation may be close to without having the same exact rank: has rank one, while has rank two for every , however small.
The preceding low-rank approximation chapter proves that when the smallest spectral-norm perturbation that reduces rank below has size . Indeed a perturbation smaller than cannot produce rank at most ; the perturbation attains that distance. In the other direction, if , the perturbation increases rank by one for every ; the new singular values may need reordering. If , choose any unit vectors and : has rank one for every . Thus exact rank can rise under arbitrarily small perturbations whenever it is not maximal. A matrix with cannot gain rank and retains rank under perturbations of norm less than .
A threshold is a declared decision
Definition 6.2.1
(Threshold rank)
For a chosen tolerance , define the threshold rank . The strict inequality is a convention that decides the boundary explicitly. It need not equal exact rank: positive values at or below are deliberately treated as unresolved. The tolerance should reflect the problem's measurement and computational error scales; a number cannot be declared universally correct without that context. Multiplying the data matrix by a scalar multiplies all singular values by , so an absolute threshold carries units.
Theorem 6.2.2
(Stability of singular values)
Suppose exact matrices have the same shape and satisfy . The singular-value stability inequality is
Proof
(A max–min formula and the triangle inequality)
For completeness, its proof uses the variational characterization
Use a full SVD with right singular basis ; for , . The span of the first right singular vectors attains at least . Every -dimensional intersects the span of nontrivially, by dimension counting; a unit vector in that intersection has . This proves the characterization. For each unit , the triangle inequality gives . Taking the minimum on each , then the maximum over , gives ; exchanging proves (1).
Proof X-ray
Where the dimension count and the triangle inequality enter
The max–min formula is chosen because it describes without singular vectors, so and can be compared on the same subspaces . The key move is that holds uniformly over unit vectors (it comes from ), and taking a minimum and then a maximum preserves such a uniform inequality. The dimension count is used only to prove the formula: an -dimensional and the -dimensional span of have dimensions adding to , so they meet in a nonzero vector. The argument closes by exchanging and , which turns a one-sided bound into an absolute value. Only the common shape and are assumed; nothing is said about the ranks themselves, which is why exact rank can jump while every moves by at most .
Corollary 6.2.3
(Rank bounds from an uncertainty band)
With as in the stability theorem and any ,
Proof
(Counting indices on both sides of the threshold)
If , then (1) gives , so the index is counted by ; distinct indices stay distinct, which gives the left inequality. If , then , so is counted by the right-hand side; this gives the right inequality.
The lower bound counts values certainly above threshold; the upper bound includes every value that could be above it. These bounds remain valid if . Values in the uncertainty band need not have a determined classification. Here are treated as exact; if an algorithm reports approximations to them, its certified computational error must also be included in the uncertainty before applying this reasoning.
Worked examples
Worked example 6.2.4
(Exact rank changes while threshold rank is stable)
Let and . Compare their exact ranks and bound using and .
Solution. has two positive singular values and rank two; has three and rank three. The difference is , of spectral norm . For , exactly two singular values exceed , and exactly two exceed . Both bounds in (2) equal two, so . The threshold conclusion is stable here despite the differing exact ranks.
Worked example 6.2.5
(An uncertainty band can prevent a decision)
A known matrix is ; the unknown true matrix satisfies . What does this tell us about ?
Solution. For , one singular value exceeds and two exceed . Thus (2) gives . Both possibilities really occur: and are each at distance from . Under the strict threshold rule their ranks at tolerance are respectively one and two. The uncertainty cannot be resolved without more information; reporting either answer as certain would overstate the data.
Worked example 6.2.6
(The distance to rank loss and the strict threshold)
Let , so , and the exact rank is two. The perturbation has , and has rank one: rank can drop at distance . For any with , inequality (1) gives , so the rank stays two. At the tolerance the singular value is not strictly larger than , so although the exact rank is two. This boundary case shows that the strict inequality is a convention that must be stated.
Counterexample mode
Nearby matrices need not have the same exact rank
Claim: if is tiny, then . This is false. Take and . Then has spectral norm , yet and . What survives is the pair of bounds (2): with and , only exceeds and only exceeds (), so is pinned down. A declared tolerance larger than the uncertainty gives a stable answer; exact rank does not.
Common mistakes and subtle points
Common mistake
(Reading the rank of the measured matrix as the rank of the true one)
In the second worked example has , but a matrix within the stated distance has . Applying the threshold to the measured matrix alone ignores the uncertainty band; the honest answer is the interval from (2).
Common mistake
(Forgetting that the threshold carries units)
Scaling a data matrix by scales every singular value by . With , the matrix has threshold rank one, while has threshold rank two. A tolerance has to be chosen relative to the units and error scale of the data.
Exercises
Quick check
(For , find the exact rank and the threshold rank .)
Count strictly positive singular values, then those exceeding .
Solution · Answer
The singular values are , so the exact rank is two. Only exceeds , so .
Quick check
(Let , and . What does (2) say about when ?)
Compare the singular values of with .
Solution · Answer
Only exceeds , while both and exceed . Hence . Both values occur: gives one, and , at distance from , gives two.
Quick check
(If and , what range does the stability inequality give for ?)
Apply (1) with .
Solution · Answer
, so . In particular , and has at least three positive singular values.