Rank is a decision

Rank is a clean idea in the algebra. The rank of a matrix is the dimension of the space its columns span, it is an integer, and it is determined completely by the matrix.

Write that matrix down in floating point and the idea stops being clean. A matrix built to have rank four, stored as doubles, has ten nonzero singular values. Six of them are around 10⁻¹⁶ rather than zero, because the entries were rounded on the way in. Nothing about that matrix is exactly rank four any more, and asking a computer for its rank is asking a question that no longer has an answer.

What can be asked instead is where the spectrum stops being signal. That is a decision, and like any decision it can be well or badly supported.

The figure carries its own verdict, and the slider is where it changes.

Thirteen decades of noise separate that frame from the next one, and the readout’s verdict changes from a fact about the matrix to a fact about whoever picked the tolerance:

Across noise levels from 10⁻¹⁴ to 0.1 the gap reads 8.2·10¹², 8.2·10¹¹, 8.2·10¹⁰, 8.2·10⁹, 8.2·10⁸, 8.2·10⁷, 8.2·10⁶, 8.2·10⁵, 8.2·10⁴, 8,202, 820, 82, 8.1 and 1.1 — one decade of gap for one decade of noise, exactly, over thirteen steps.

And the verdict flips once, between a gap of 8,202 and a gap of 820. Every stop with a gap above about a thousand is decisive; every stop below it is an opinion. That is a threshold this essay can name: a rank decision is a decision about a matrix when the cliff is three orders deep, and a decision about a tolerance when it is not.

Nothing else on the page moves across that boundary. The four large singular values are the same four at every noise level, the construction is unchanged, and the matrix is as low-rank at 10⁻⁴ as it was at 10⁻¹⁴. What changes is whether a number computed from it can be defended.

The gap is the evidence #

The number that supports a rank decision is not the smallest retained singular value, and it is not the cutoff. It is the ratio between the last value kept and the first value discarded.

At a noise level of 10⁻⁸, σ₄/σ₅ is 8.2·10⁶. Six and a half orders of magnitude of clear air between the signal and the noise, and calling the rank four is a statement of fact.

At a noise level of 10⁻¹, that ratio is 1.1. The fourth and fifth singular values are essentially the same size, and any rank between three and ten could be argued for. The computation runs exactly as before, returns ten sorted finite numbers exactly as before, and there is nothing in its output that says the answer has become a matter of taste.

The relationship between them is measured across the whole slider: gap × noise = 0.082, at every one of the fourteen positions, to within a factor of three. That is a stronger statement than “the gap shrinks with noise” and it is the honest quantification of how fast the evidence degrades — one decade of gap for one decade of noise, no threshold, no cliff.

The floor the slider cannot go below #

The figure’s matrix is assembled as UΣVᵀ with Σ carrying four nonzero entries, so before a single unit of noise is added it is a matrix of exact rank four by construction. Its singular values, as computed from the assembled doubles, are 1, 0.316, 0.100, 0.0316 — and then 9.96·10⁻¹⁷, 3.92·10⁻¹⁷, 2.10·10⁻¹⁷, 1.54·10⁻¹⁷, 1.27·10⁻¹⁷ and 5.92·10⁻¹⁸.

Ten nonzero values, on the matrix that was built to have four. Nothing was done to it. The two matrix multiplications that assembled it rounded every entry, and what the rounding left behind is a tail sitting sixteen orders of magnitude below the top of the spectrum.

Three things follow, and the third is the one that matters for the slider.

The textbook definition fails on the easiest possible case. “Count the nonzero singular values” returns ten here. Not on a hard matrix, not on measured data — on a matrix whose rank was chosen first and whose factors were then multiplied together.

A tolerance is not a concession, it is the whole mechanism. numericalRank(clean) returns four, and it returns four because it compares against a cutoff rather than against zero. The assertion at the top of the generator — that the noiseless matrix has the rank it was built with — passes only for that reason.

And the noise slider has a floor. Below about 10⁻¹⁶ the added noise is smaller than the tail already present, so dragging further changes nothing: the gap stops growing because the denominator has stopped shrinking. The proportionality quoted above is measured over the range where the added noise dominates, which is the range the slider covers. Outside it the relationship is not weaker; it is measuring a different quantity, and the figure declines to extend there rather than reporting a constant that has quietly changed meaning.

Why every rank routine has a tolerance #

Every implementation of rank in every numerical library takes a tolerance, usually defaulting to something like max(m,n)·σ₁·u. The default is a guess about how much of the spectrum is attributable to rounding, and it is a good guess when rounding is the only noise present.

It is the wrong guess whenever the matrix came from measurement. If the entries are known to three digits, the meaningful cutoff is around 10⁻³σ₁ and not 10⁻¹⁵σ₁ — twelve orders of magnitude different, and the difference is a great many singular values. A rank computed with the default tolerance on measured data is counting directions that are entirely noise.

So the practical rule is: the tolerance belongs to the data, not to the arithmetic. Set it from what is known about the measurement, look at the resulting gap, and if the gap is not decisive say so rather than reporting an integer.

Reporting the gap alongside the rank #

This site’s rankByGap returns four things: the count, the cutoff, the gap, and a flag saying whether the gap exceeds a thousand. That last field is the one worth stealing.

An integer alone is a claim with its evidence stripped off. rank = 4 reads identically whether the gap behind it was 10⁷ or 1.1, and the two situations warrant completely different downstream behaviour. Returning the gap makes the difference visible at no cost, and it makes the eventual argument about it a short one.

The function has one subtlety worth mentioning because the first version got it wrong. When every singular value clears the cutoff, there is no discarded value to compare the last retained one against, and the naive implementation reported an infinite gap — full rank, maximum confidence. But a smallest singular value that only just clears the threshold is a rank decision that could easily have gone the other way. The gap in that case is measured against the cutoff itself, which is the only honest denominator available, and the check that caught this is in verify-kit’s own self-test: a spectrum whose smallest value beats the cutoff by a factor of 1.5 must be reported as not decisive.

What rank deficiency does to everything else #

Near rank deficiency is not one phenomenon among several. It is the same phenomenon as ill-conditioning, and as the flat valley, and as amplified perturbations, seen from four directions.

κ(A) = σ₁/σₙ, so a matrix with a nearly zero smallest singular value has a nearly infinite condition number. The right singular vector belonging to it is the direction in which coefficients are undetermined, which is the valley with no bottom. It is also the direction in which perturbations are amplified worst, which is the condition number is an amplifier. And it is the direction the best rank-(n−1) approximation discards, which is the best approximation there is.

One small singular value, four essays. That is not repetition; it is the reason the singular value decomposition is the central object of the subject.

Computing the spectrum well enough to decide #

A rank decision is only as good as the singular values it rests on, and there is a route that destroys exactly the ones the decision depends on.

The tempting route is to form AᵀA and take square roots of its eigenvalues, which is correct mathematics and squares the condition number. On a matrix with κ = 10¹², the three smallest singular values computed that way have relative error 1.0 — they are wrong by their own size, which is to say entirely lost. Computed by one-sided Jacobi on A directly, the worst relative error across the whole spectrum is 4.4·10⁻⁶.

The difference matters precisely at the bottom of the spectrum, which is where the rank decision lives. A method that gets the large singular values right and the small ones wrong is a method that answers a question nobody asked.

This is the road that squares the problem again, in a different guise: forming a cross-product matrix is convenient and it costs the small end of the spectrum.

What to do when the gap is not decisive #

Three honest options and one dishonest one.

Report the ambiguity. “Rank is 4 or 5; the gap between σ₄ and σ₅ is a factor of 1.3” is a useful sentence and it takes one line. Anything downstream can then decide.

Regularise explicitly. Truncate at a stated tolerance and say what was discarded. The truncated SVD is exactly this decision made visible, and it is often the right one.

Get better data. The gap is proportional to the inverse of the noise, so a tenfold improvement in measurement buys a tenfold improvement in the evidence. Since the relationship is exact and measurable, the required improvement can be computed in advance rather than guessed.

The dishonest option is to accept whatever integer the default tolerance produces and carry it forward, which is what happens by default, because the default returns an integer and integers look like facts.

What is asserted here #

The noiseless matrix has the rank it was built with. Checked before any noise is added — if the construction did not produce a rank-four matrix, the rest of the figure would be about something else.

The added noise is the size stated. Measured as ‖A − A_clean‖/‖A_clean‖ and required to match the caption’s number, because a figure whose axis label is wrong is a figure that measures nothing.

The gap is inversely proportional to the noise, with the product between 0.04 and 0.25 at every position of the slider. That assertion replaced an earlier one — “at low noise the gap is decisive” — which failed at one position for a reason that was about the threshold rather than about the phenomenon. The proportionality is both stronger and true everywhere.

And the rank routine must be able to report indecision. Fed a spectrum whose smallest value beats the cutoff by 1.5, it must return decisive: false. Without that, a rank routine that always claimed confidence would produce identical figures and nothing would say so.

Rank-revealing factorisations #

Computing the full SVD to make a rank decision is the reliable route and it is not always the affordable one. The alternative is a factorisation that reveals the rank without computing every singular value.

QR with column pivoting reorders the columns so that the diagonal of R decreases in magnitude, and the point where it drops sharply indicates the numerical rank. It costs about the same as an ordinary QR and is what dgeqp3 does. The catch is that it can fail: the Kahan matrix is the standard counterexample, a matrix whose R diagonal decays smoothly while its smallest singular value is far smaller than the last diagonal entry suggests. The failure is rare and it is real.

Strong rank-revealing QR adds a post-processing step that swaps columns until a guaranteed bound holds, at a cost that is usually small. It removes the counterexample and is what a careful implementation uses when the decision matters.

Randomised methods sketch the matrix down to a small number of columns and factorise the sketch, which for a matrix with a rapid spectral decay gives an excellent estimate at a fraction of the cost. The bound is probabilistic rather than certain, which is a genuinely different kind of guarantee and is the reason randomised numerical linear algebra is a field rather than a trick.

The decision between them is the usual one: how much does it cost to be wrong. A rank decision inside an exploratory analysis and one inside a control system warrant different answers.

The condition number is the same information #

It is worth making the identity explicit, because the two quantities are usually taught in different chapters.

κ(A) = σ₁/σₙ. Numerical rank deficiency means σₙ is below a tolerance relative to σ₁. Those are the same statement: a matrix is numerically rank deficient exactly when its condition number exceeds the reciprocal of the tolerance.

So every rank decision is a conditioning decision wearing different clothes, and every conditioning threshold is a rank threshold. When the condition number is an amplifier says κ = 10¹⁶ leaves nothing in double precision, it is saying the matrix is numerically singular at the tolerance u — the same sentence.

The reason both vocabularies survive is that they answer different questions about the same fact. Conditioning asks how much accuracy is lost; rank asks how many directions are resolved. The first is a continuous quantity and the second is an integer, and the integer is the one people over-trust.

A worked decision #

To make the procedure concrete, here is the whole thing on the figure’s matrix at a noise level of 10⁻⁶.

Compute the singular values: they run 1, 0.32, 0.10, 0.032, then 3.9·10⁻⁷ and below. Choose a tolerance from what is known about the data — here the noise was 10⁻⁶ relative, so anything below about 10⁻⁶·σ₁ is not distinguishable from noise. That cuts after the fourth. The gap between σ₄ and σ₅ is 8.2·10⁴.

Report: rank 4, gap 8.2·10⁴, tolerance set from a stated noise level of 10⁻⁶. Three numbers and a provenance, in place of one integer.

Anyone reading that can second-guess it, which is the point. Someone who knows the noise is really 10⁻⁴ can see immediately that the decision would change; someone who needs rank 5 for a downstream reason can see how much evidence stands against them. An integer alone permits neither conversation.

The three essays of this field share one object. Symmetry is worth more than precision is about the spectrum’s stability, this one about where it stops being signal, and the best approximation there is about what discarding the tail costs — which is exactly σₖ₊₁, and therefore exactly the number this essay’s cutoff is drawn at.

The word “numerical” is doing real work #

It is worth being clear about the vocabulary, because “rank” and “numerical rank” are used interchangeably in a way that hides the whole difficulty.

Rank is the dimension of the column space, an exact integer, defined for a matrix of real numbers and computable in exact arithmetic. The rank of a matrix of rationals can be determined with certainty by fraction-free elimination, and the answer is not a judgement.

Numerical rank is the number of singular values above a tolerance. It depends on the tolerance, which depends on what is known about the data, which is outside the matrix. Two people with the same matrix and different knowledge of where it came from can correctly report different numerical ranks.

That second sentence is the one people resist, and it is the point. The matrix does not contain the information needed to answer the question, because the question is about which parts of it are signal, and the matrix cannot say. The gap is the closest thing to an answer that the matrix has, and reporting it is how the missing information is made visible rather than assumed.

The same structure appears elsewhere on this site. Whether a residual is small enough depends on the uncertainty in the data; whether a coefficient is determined depends on how many digits are needed. In every case the arithmetic supplies a quantity and something outside it supplies a threshold, and the mistake is always the same one: taking the default threshold as though it came from the problem.

Three quantities that cannot make it #

A rank verdict is a decision about a gap in the singular values. Three quantities are commonly offered instead — the determinant, its scale-free nth root, and the smallest singular value — and none of them can make the decision.

The reason usually given is that they average over the whole spectrum and so cannot see a gap. That is true of the first two and false of the third: σ_min is not an average of anything, it is the gap’s lower lip. The property all three actually lack is scale invariance. Under A → cA the determinant goes as cⁿ, its nth root as c, and σ_min as c, while σ_min/σ₁ does not move at all. So each of the three can be sent anywhere by a multiplication that changes no rank and no conditioning, and a threshold on any of them is a threshold on the matrix’s units.

That distinction sounds like pedantry until it is made to bite. Two 12×12 matrices, each an ordinary spectrum multiplied by a scalar:

Every one of the three orders the pair the wrong way round. The numerically rank-deficient matrix has the larger determinant — by forty-eight orders of magnitude — the larger nth root by four, and the larger smallest singular value by a factor of ten. The quantity that answers the question puts them nine orders apart in the other direction.

This is worth separating from bluntness, because the two failures call for different responses. A blunt instrument orders a pair correctly and fails to separate them, and the response is a finer instrument or a wider margin. These order them backwards, which means no threshold on any of the three classifies both matrices correctly, at any value, chosen with any care. There is no setting to tune. And the counterexample took nothing exotic: both matrices have an unremarkable spectrum, and then one was multiplied by a number.

The same reasoning is why the condition number is an amplifier is stated as a ratio and why a rank that is a number of digits counts digits rather than measuring a size: a quantity that answers a question about proportions has to be a proportion.

assertTheSubstitutesOrderThePairBackwards builds both matrices, requires each of the three to be larger for the deficient one, and checks the scaling law that explains it — that σ_min/σ₁ is exactly unmoved by a scalar while the other three move with it.