Rank and Linear Independence

Ways of saying the same thing

For a square matrix, all of these are one statement:

• the columns are linearly dependent;
• the determinant is zero;
• the rank is less than the number of columns;
• the matrix has no inverse;
• Ax = 0 has a solution other than x = 0;
• at least one eigenvalue is zero.

Column rank always equals row rank, which is a genuinely surprising theorem: the number of independent columns and the number of independent rows are the same number, whatever shape the matrix is.

How many directions actually survive

The rank of a matrix is the number of genuinely independent directions in it — how many dimensions of information it carries, as opposed to how many columns it has.

Take three columns: [1, 2], [2, 4] and [0, 1]. The second is exactly twice the first, so it adds nothing. There are three columns and only two independent directions, so the rank is 2.

A set of vectors is linearly independent when none of them can be written as a combination of the others. Independent vectors each point somewhere new; dependent ones are redundant.

The consequences are immediate:

• A matrix with rank equal to its smaller dimension is full rank, and is as informative as its shape allows.
• Anything less is rank deficient: some columns are redundant, and the matrix collapses space.
• A square matrix is invertible exactly when it is full rank.

Finding it, and what it costs when it is low

import numpy as np

A = np.array([[1, 2, 0],
              [2, 4, 1]])
np.linalg.matrix_rank(A)      # 2 - the second column is twice the first

Under the hood, matrix_rank counts singular values above a tolerance rather than doing exact arithmetic, which is the right approach in floating point: real data is never exactly dependent, only nearly so.

Where rank deficiency bites:

Linear regression. The normal equation needs XᵀX to be invertible, which requires X to have full column rank. Perfectly correlated features — or a one-hot encoding that kept every level alongside an intercept — make it singular, and the fit either fails or returns arbitrary coefficients.

Any distance or covariance calculation. Redundant columns count the same information several times, distorting distances and inflating the apparent dimensionality.

PCA. The number of non-zero eigenvalues is the rank. If your 50-column dataset has rank 12, you can drop to 12 components with no loss at all.

Independence in practice: the dummy variable trap

The most common rank problem in applied work is not exotic. One-hot encode a three-category column into three indicator columns and they always sum to 1 — which is exactly what the intercept column already is. Four columns, three independent directions, rank deficient.

The fix is to drop one level as a reference, which is why OneHotEncoder(drop="first") exists and why it matters for linear models with an intercept.

Other everyday sources:

• A feature and the same feature in different units (metres and centimetres).
• Sub-scores plus their total in the same feature set.
• A percentage column alongside its numerator and denominator.
• More features than samples, which guarantees rank deficiency regardless of content.

That last case — wide, short data, common in genomics and text — is why regularisation is not optional there. Ridge and elastic net remain solvable when ordinary least squares cannot be.

Count the real directions

Three matrices, and rank counting what is genuinely independent rather than how many rows were written down.

import numpy as np

independent = np.array([[1.0, 0.0], [0.0, 1.0]])
dependent = np.array([[1.0, 2.0], [2.0, 4.0]])
tall = np.array([[1.0, 2.0], [2.0, 4.0], [3.0, 6.0]])

for name, M in [("independent rows", independent),
                ("row 2 = 2 x row 1", dependent),
                ("three rows, all multiples", tall)]:
    print("%-26s shape %s  rank %d"
          % (name, M.shape, np.linalg.matrix_rank(M)))
print()
print("rank counts genuinely different directions, not rows.")
print("three rows spanning one direction still has rank 1.")
print()
print("rank <= min(rows, columns), always.")

Try it yourself

1. Start independent. c₁ = (2, 1), c₂ = (1, 2). The determinant is 3, the rank is 2, and the reachable dots fill the plane in a lattice.
2. Collapse it. Press Make Column 2 A Multiple Of Column 1. c₂ becomes 1.5×c₁ = (3.0, 1.5), the determinant goes to exactly 0 and every dot falls onto one line. Adding a second column bought you nothing.
3. Nudge it back. Move Column 2 y by a single notch. The rank jumps straight back to 2 — rank is a count, so it does not degrade gradually, it steps. That is also why "nearly dependent" needs a different measure entirely.
4. Try the near-miss. Set c₂ to (3.0, 1.6) instead: the determinant is 0.20, technically rank 2, and the lattice is stretched into a nearly-flat sliver. This is what collinear features look like, and why a fit on them is unstable.
5. Zero a column. Set both of c₂'s components to 0. Rank 1 again: a zero column contributes no direction at all.
6. Zero both. Rank 0, and the only reachable point is the origin.

Where this bites in practice

• The dummy variable trap. One-hot encode a category into k columns and keep an intercept, and the k dummies sum to the intercept column exactly. The design matrix is rank deficient, XᵀX is singular, and ordinary least squares has no unique solution. Dropping one dummy fixes it.
• Duplicated features. Height in cm and height in inches are one direction written twice. The rank does not go up; the instability does.
• More features than rows. With p > n the rank is at most n, so the columns are guaranteed dependent and the model can fit the training data perfectly for reasons that have nothing to do with the data. Regularisation is the standard answer.
• Low-rank approximation. Keeping only the strongest few directions of a matrix is what PCA does, and what the "low rank" in LoRA refers to: a big weight update approximated by the product of two thin matrices, because the update did not need every direction.

Worth remembering

Rank counts the independent directions a matrix's columns actually provide, which is the dimension of everything they can reach. Full rank means the span is as large as it could be and the matrix is invertible; a drop in rank means one column was a combination of the others, the determinant is zero, and both the inverse and the unique solution to Ax = b disappear together. Rank is a count and therefore steps rather than slides, so "nearly dependent" is a separate and more practical concern — it is what collinear features, duplicated columns and the dummy variable trap all produce, and why low-rank structure is something worth exploiting on purpose.

Rank, span, and basis

Three related ideas complete the picture.

The span of a set of vectors is everything you can reach by scaling and adding them. Two independent vectors in 3-D span a plane; three span the whole space.

A basis is a minimal set that spans the space — independent, with nothing redundant. Any vector in the space is one unique combination of them.

The rank is the dimension of the span of the columns. So rank, span and basis are three views of the same fact: how much room the vectors actually cover.

The rank-nullity theorem ties it together: for an m×n matrix, rank + nullity = n, where the nullity is the dimension of the space that gets collapsed to zero. Every dimension either survives or is destroyed, and the two counts add up to the input's dimension.

Low-rank approximation, the useful side of rank deficiency

Being rank deficient is not always a problem — sometimes it is the goal.

SVD lets you take a large matrix and keep only the strongest k directions, producing the best possible rank-k approximation. That single idea underlies several familiar applications:

• Image compression. A 1000×1000 image kept at rank 50 stores 5% of the numbers and often looks nearly identical, because natural images are dominated by a few strong directions.
• Recommender systems. A user-item ratings matrix is assumed to be approximately low rank — a few latent taste factors explain most preferences — and the missing entries are filled by reconstructing from those factors.
• Noise reduction. Signal usually lives in the strong directions and noise is spread across the weak ones, so truncating the small singular values cleans the data.
• LoRA fine-tuning. Large language models are adapted by learning a low-rank update to the weight matrices, training a tiny fraction of the parameters. The whole method is named after this property.

Questions people ask

How do I check for redundant features? Compare matrix_rank(X) with the number of columns. A correlation matrix and variance inflation factors give a more interpretable per-feature view.

What is the maximum possible rank? The smaller of the number of rows and columns. A 100×5 matrix cannot have rank above 5.

Does rank deficiency always break a model? It breaks anything requiring a matrix inverse. Trees, forests and regularised linear models cope; ordinary least squares does not.

What is the difference between rank and dimension? Dimension describes a space; rank describes how much of a space a particular matrix reaches.

Why do libraries use a tolerance? Because floating-point data is never exactly dependent. Values below the tolerance are treated as zero, which is the only sensible convention.

Is high rank always better? For information, yes. For compression, no — low rank is precisely what makes approximation and factorisation work.

Recap in one screen

• Rank counts the genuinely independent directions in a matrix, which may be fewer than its columns.
• Linearly dependent vectors are redundant; independent ones each add a new direction.
• Full rank means invertible for a square matrix, and a solvable least-squares problem for a tall one.
• The dummy variable trap, duplicated features and wide short data are the everyday causes of rank deficiency.
• Deliberate low-rank approximation powers compression, recommenders, denoising and LoRA fine-tuning.