Linear Systems, Rank, and Null Spaces

A house-price model includes floor area in square meters and the same area converted to square feet. The dependence is exact and deliberate, which makes the arithmetic easy to watch. The matrices later in this lesson are real ones — a certified economic regression, an age-period-cohort design, a rank-4 update to a 175B-parameter model. In those, the same failure arrives without anyone constructing it.

The equation Ax = b asks whether the observed target b can be produced by combining the columns of A. If it can, the coefficients x describe one such combination. The deeper question is whether the available equations carry enough independent information to determine x. More rows do not guarantee more information, because rows can repeat the same relationship. Rank measures independent directions. Null spaces describe changes the observations cannot detect. Together they explain identifiability, multicollinearity, and why some inverse problems need regularization.

That question has documented answers, and this lesson works through three of them. A 16-row economic regression that a US standards agency certifies to 16 significant digits, because ordinary software disagrees about it. An age-period-cohort design whose null space is exactly one-dimensional by construction, so no amount of further data closes it. And a rank-4 update that adapts GPT-3 175B while training 18M parameters instead of 175,255.8M.

The column space of A contains every output Ax that the system can generate, and in regression it is the set of prediction vectors available to the linear model. The null space contains every direction z for which Az = 0. If x is a solution, then x + z produces the same output for any null-space vector z. A nontrivial null space therefore means parameters are not uniquely identified by the observations.

The standing example of this is not a toy. In age-period-cohort analysis the three predictors satisfy an exact identity — cohort = period - age — so the design matrix is singular and X'X cannot be inverted. The ordinary least squares estimator does not exist here at all: “the design matrix X is singular with one less than full rank”, as Yang Yang and Kenneth C. Land put it in 2008, leaving an infinite number of possible solutions. Columbia University's Mailman School of Public Health states the consequence for the science: “The presence of perfectly collinear predictors (age, period and cohort) in a regression model will produce a singular non-identifiable design matrix, from which it is statistically impossible to estimate unique estimates for the three effects.”

The null space is one-dimensional, and it is a property of the design rather than of the sample. Every new respondent has an age, a survey year and a birth cohort that satisfy the same identity, so more data adds rows without adding a direction. Liying Luo and James S. Hodges write of “APC models that are unidentified because the predictors are exactly linearly dependent”, and show that the random-effects version carries “greater -- not less -- rank deficiency than the traditional fixed-effects model”. Every published fix is an admission of an arbitrary external constraint. Predictions from such a model can still be stable while the individual coefficients remain ambiguous. A good fit is never evidence that the three effects have been separated.

The geometry depends on where b lies and how many directions A can express. Two of these four outcomes are quietly resolved for you before you ever see a number.

When the columns are dependent, the solution set is not narrow. The LAPACK Users' Guide says of an underdetermined system of full row rank that “there are an infinite number of solutions x which exactly satisfy b-Ax=0.” The guide then nominates one of them as the answer — “finding a minimum norm solution to an underdetermined system of linear equations” — and for a rank-deficient A it seeks “the minimum norm least squares solution”.

NumPy implements exactly that choice. Its numpy.linalg.lstsq documentation states that “If there are multiple minimizing solutions, the one with the smallest 2-norm ||x|| is returned”, and that “singular values are treated as zero if they are smaller than rcond times the largest singular value of a”. SciPy's scipy.linalg.lstsq, whose default LAPACK driver is 'gelsd', exposes the same cutoff as its cond parameter — the “Cutoff for 'small' singular values; used to determine effective rank of a”, where “Singular values smaller than cond * largest_singular_value are considered zero”.

So the coefficient vector printed for a rank-deficient problem is not the solution. It is the shortest member of an infinite set, selected by a documented convention and a tolerance you are free to change.

Follow the evidence from geometry to a stable modeling response. Step two is not a refinement of step one. It is the step where the honest answer lives, because in floating point the tools themselves decline to report a rank without first being given a threshold.

MATLAB documents the rule in the Algorithms section of its rank function: “The rank of a matrix A is computed as the number of singular values that are larger than a tolerance. By default, the tolerance is max(size(A))*eps(norm(A)).” NumPy uses the same construction. Its numpy.linalg.matrix_rank documentation states that “Rank of the array is the number of singular values of the array that are greater than tol”, with a default where “tol is set to S.max() * max(M, N) * eps” — a threshold the Notes describe as “designed to detect rank deficiency accounting for the numerical errors of the SVD computation”.

With eps about 2.22e-16 in IEEE double precision, both defaults sit just above the noise floor of the SVD itself. The reported rank is a decision, not a fact retrieved from the matrix. Change the tolerance and the rank changes with it. That is why the diagnosis continues past step two: read the singular values as a spectrum, find the parameter combinations that leave predictions unchanged, perturb the data, and only then decide between removing redundancy, collecting new information, and imposing a preference you are willing to defend in writing.

Rank is one algebraic property with several practical interpretations, and each one has been measured rather than merely asserted.

From the data side, the claim that real matrices carry far fewer independent directions than their dimensions suggest is a measurement. Armen Aghajanyan and two colleagues reported it at ACL in 2021, in an outstanding paper: “For example, by optimizing only 200 trainable parameters randomly projected back into the full space, we can tune a RoBERTa model to achieve 90% of the full parameter performance levels on MRPC.” Two hundred numbers, ninety per cent of the task.

From the model side, capping rank on purpose is now production practice. LoRA freezes the pretrained weights and trains only a rank-r update; it was presented at ICLR in 2022. The abstract states the result: “Compared to GPT-3 175B fine-tuned with Adam, LoRA can reduce the number of trainable parameters by 10,000 times and the GPU memory requirement by 3 times.” Concretely, adapting only the query and value projections with r = 4 across all 96 layers costs 18M trainable parameters and takes the per-task checkpoint from 350GB to 35MB, roughly 10,000x. Accuracy does not pay for it. At r_q = r_v = 1, 4.7M trainable parameters score WikiSQL 73.4% and MNLI-m 91.7%, against 73.8% and 89.5% for a 175,255.8M-parameter full fine-tune. The authors reach the same conclusion the intrinsic-dimensionality work reached on a different model: “To our surprise, a rank as small as one suffices for adapting both Wq and Wv on these datasets while training Wq alone needs a larger r”. Hugging Face reports the effect from outside the paper, with a T0_3B LoRA adapter file “being just 19MB”.

From the numerical side, none of this escapes the tolerance problem. A bottleneck of r = 4 is a rank chosen by an engineer. The rank of the Longley matrix is full, and useless as a warning. And the rank a library prints for either of them depends on the cutoff described in the diagnosis above. Rank as design, rank as algebra and rank as a threshold decision are three different quantities that share one word.