Numerical Linear Algebra
where the algebra stops being the arithmetic
Eigenvalues, singular values, rank

Rank is a decision

A floating-point matrix does not have a rank. It has a spectrum of singular values, and somewhere in that spectrum is a place where the values stop being signal and start being noise. Deciding where is a judgement, and the evidence for it is a gap.
14 min read 6 figures Where the algebra stops being the arithmeticMeasured, not assertedWhose fault is itPrecision as the knob

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.

Singular values of a rank-4 matrix with noise of relative size 10⁻⁸Ten singular values on a logarithmic axis. The first four sit near one; the rest sit at the noise level, and the vertical distance between the two groups is the evidence for the rank.1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision
Fig. 1 Ten singular values of a matrix built with four nonzero ones and noise of a stated relative size added. The first four sit near one; the rest sit at the noise level; the cutoff is drawn, and so is the gap. Drag the noise level and watch the evidence run out — the gap and the noise are inversely proportional, with the same constant at every position.

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.

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.

How far the coefficients can move without changing the fit, degree 9Relative increase in the residual against relative change in the coefficients, along the least determined direction. The residual does not move measurably until the coefficients have changed by more than a factor of one.10⁻⁴10⁻³10⁻²10⁻¹110¹10²10³10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹relative change in the coefficients, along the worst directionrelative increase in the residualcoefficients doubled39% change, fit unmoved in the sixth digit308×: the third digit movesκ(A) = 3.6·10⁶. Exact arithmetic would pick one point on this floor. It would not raise it.24 points, degree 9, monomial basisthe data leaves them free
Fig. 2 The same small singular value, in the coefficients. Move along the direction it belongs to and the fit does not change — the coefficients are free to a third of their own size before the residual notices. Rank deficiency and undetermined coefficients are one fact with two names.

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.

How far a perturbation of size ε moves an eigenvalue, 8×8A log–log plot of eigenvalue movement against perturbation size. The symmetric case lies on a line of slope one; the non-symmetric case lies on a line of slope one eighth, and at a perturbation of ten to the minus sixteen it has already moved by a hundredth.10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹size of the perturbation ‖δA‖how far the eigenvalues moveJordan block, ε^(1/8)symmetric, ≤ ‖δA‖rounding error alone moves it to 10⁻²six seeds per symmetric point; Jordan is closed formsymmetry beats precision
Fig. 3 Why the decision cannot be deferred to a better algorithm. For a well-behaved matrix, perturbations move things by their own size and a rank decision degrades gracefully. For a defective one, they move by a fractional power, and the spectrum you are deciding about has already shifted by 10⁻² before any algorithm has run.

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.

Error of the best rank-k approximation to a 10×10 matrixApproximation error against k on a logarithmic axis, with the measured error and the next singular value drawn as separate curves lying exactly on top of one another.12345678910⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1rank k of the approximation‖A − Aₖ‖measured, 2-normσₖ₊₁, from theorymeasured, Frobeniusthe first two agreeto 4.3·10⁻⁹worst |‖A−Aₖ‖₂ − σₖ₊₁| / σₖ₊₁4.3·10⁻⁹worst Frobenius discrepancy4.3·10⁻⁹κ = 10⁹; 30 random rank-3 matrices, none closerthe error is σₖ₊₁
Fig. 4 What the decision is usually feeding. The best rank-k approximation’s error is exactly σₖ₊₁, so choosing k is choosing how much of the matrix to discard, and the spectrum says exactly what that costs. The rank decision and the approximation decision are the same decision.

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.

Backward and forward error against the condition numberA log–log plot over twelve decades of condition number. The backward error is a flat line at ten to the minus sixteen; the forward error rises in proportion to the condition number.110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)relative errorforward errorbackward errorpredicted: κ · u8×8, 20 seeds per κ; dashed is the worstthe problem worsens, not the method
Fig. 5 And the reason the decision matters. A matrix treated as full rank when it is not is a matrix whose condition number is enormous, and the error in anything computed with it rises accordingly. The choice of tolerance is the choice of where on this axis you are working.
Loss of orthogonality against condition number, in binary64A log–log plot of the norm of Q-transpose-Q minus the identity against condition number. Classical Gram–Schmidt rises steeply, modified Gram–Schmidt rises gently, and Householder is flat.110²10⁴10⁶10⁸10¹⁰10¹²10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)‖QᵀQ − I‖classicalmodifiedHouseholderκ²uκu8×8, eight seeds per κ, binary64all three reconstruct A
Fig. 6 And the other quantity that fails at the same place. Loss of orthogonality rises with κ, and κ is large exactly when a singular value is small — so the matrices where a rank decision is hard are the matrices where the factorisation used to make it is least trustworthy. Householder’s flat line is why that does not compound.

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.

Where this goes next

12345678910⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1rank k of the approximation‖A − Aₖ‖measured, 2-normσₖ₊₁, from theorymeasured, Frobeniusthe first two agreeto 4.3·10⁻⁹worst |‖A−Aₖ‖₂ − σₖ₊₁| / σₖ₊₁4.3·10⁻⁹worst Frobenius discrepancy4.3·10⁻⁹κ = 10⁹; 30 random rank-3 matrices, none closerthe error is σₖ₊₁ The best approximation there is The error of the best rank-k approximation is not bounded by the next singular value. It is equal to it. That is an unusually sharp theorem, and it makes the theorem itself usable as an independent check on the computation. 10⁻⁴10⁻³10⁻²10⁻¹110¹10²10³10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹relative change in the coefficients, along the worst directionrelative increase in the residualcoefficients doubled39% change, fit unmoved in the sixth digit308×: the third digit movesκ(A) = 3.6·10⁶. Exact arithmetic would pick one point on this floor. It would not raise it.24 points, degree 9, monomial basisthe data leaves them free The valley with no bottom A degree-nine fit's coefficients can be moved by a third of their own size before the residual changes in the sixth significant figure. The arithmetic did not lose those digits. The data never contained them. 110¹10²10³10⁴10⁵10⁶10⁷00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10·10⁵worst found 7.6·10⁵6×6, 200 directionsmedian reaches 0.29 of κ The condition number is an amplifier κ is usually introduced as a definition and then quoted. It is a measurement: perturb the input by a known amount, look at how much the output moves, and the largest ratio you can find is the number.