AIML Rounds RoadmapMocksJobs
Concept15 minBefore this:Matrices as Transformations

Linear Independence, Basis and Rank

What is the rank of a matrix, and why do correlated features break linear regression?

The situation

Your linear regression has weights in the millions, with opposite signs on height in cm and height in inches. A colleague also one-hot encoded a category with all its columns, and included an intercept. The solver warns about a singular matrix. The interviewer asks:

What is the rank of a matrix, and why do correlated features break linear regression?

Why it matters

Rank explains many practical failures: unstable regression weights, the dummy variable trap, models with more features than rows, and why large embedding matrices can be compressed. See SVD and low rank for how to use this.

The idea

Think of directions to a friend's house. "Two blocks north, then one east" gets you there. Adding "also go 200 metres north" tells you nothing new, and now there are many ways to describe the same trip. Rank is how many directions really add something.

IndependentFull rankUnique, stableNearly dependentFull rank, justUnstable weightsDependentRank is lostNo unique answer
Rank is the number of directions that really add something.

Play

Try to break it. Move the correlation from 0.90 to 0.99, then to exactly 1.00.

Correlate two features

Stable against unstable
rank
–
area XᵀX spans
–
variance inflation
–
weight's error grows by
–

Two standardised features. The area is the determinant of the correlation matrix, 1 − ρ². Figures come from the formula, not a simulation. In practice, rank is judged numerically, so very high correlations behave as if rank were lost.

Move from 0.90 to 0.99. Inflation goes up about ten times, even though the features already looked similar. Then try exactly 1.00: the rank drops, and no unique weights exist.

Now say why: why do weights become unstable before rank is actually lost?

Maths

In one breath

Vectors are independent if none can be built from the others. The rank of a matrix is how many of its columns are truly independent: the real number of dimensions in its data. If a feature is a mix of others, the matrix is rank-deficient, and many different weights fit equally well. Nearly-dependent features aren't quite as bad, but they still make weights unstable. Regularisation and removing features both help.

Building blocks

TermMeaningExample
SpanAll the vectors you can build by mixing a set.Two non-parallel arrows reach anywhere in a plane.
IndependentNone can be built from the others.Height in cm and weight. Not height in cm and height in inches.
BasisThe smallest set that reaches everything in a space.(1, 0) and (0, 1) for a plane, but other pairs work too.
RankThe number of independent columns, which always equals the number of independent rows.A 1,000 × 50 data matrix has rank 50 at most.

Column space and null space

  • Column space: every output Ax can produce. If b isn't in it, Ax = b has no exact solution, which is why regression uses least squares.
  • Null space: every x where Ax = 0. Add one of these to a solution, and you get another solution that fits equally well.
  • Rank-nullity: rank + null space size = number of columns. Each lost column dimension adds a direction you can't measure.

When features break regression

  • Exact dependence: height in cm and in inches. XᵀX can't be inverted, and there's no single answer.
  • Near dependence: strongly correlated features. An answer exists, but small changes in data swing the weights.
  • Dummy variable trap: one-hot columns for all k categories add up to the intercept column. Drop one, or use regularisation.
  • More features than rows: rank can't exceed the number of rows, so there are infinitely many perfect fits.

The maths

    As R² approaches 1, VIF grows without limit. At exactly 1, the matrix has lost rank, and the weight isn’t defined.

    In practice

    In practice

    • Prediction vs explanation: collinearity may not hurt predictions on similar data, as the mix of weights still works. It does hurt when you try to interpret individual weights.
    • Fixes: remove one feature, combine them, use ridge, or use PCA.
    • Check: look at VIF, and at the matrix's singular values. Very small ones mean you're close to losing rank.
    • Numerical rank: real data rarely has exact zeros. Count singular values above a small threshold.
    • Low-rank data is useful: many large matrices have a much smaller true rank, which is why compression, recommenders and LoRA work.

    The answer that sounds right

    "The correlation is only 0.9, so it's fine"

    It sounds right, since the features are still different. But at 0.9, each weight's variance is already over five times higher, and at 0.99 it's about fifty times higher. Weights can flip sign between samples. Whether that matters depends on your goal: predictions may hold, while explanations won't.

    Say it

    What is the rank of a matrix, and why do correlated features break linear regression?

    Say your answer out loud

    Aim for 30 seconds. It feels different from reading it, and that's the point.

    Tick what you covered

    The interviewer pushes further

    Follow-up 1 of 3

    Why do the rows and columns always have the same rank?

    Answer it out loud, then check.

    It's a basic theorem: the number of independent rows always equals the number of independent columns. It's why a 1,000 × 50 matrix can't have rank above 50, and why more features than rows always leaves a non-trivial null space.

    Follow-up 2 of 3

    Does multicollinearity hurt predictions?

    Answer it out loud, then check.

    Not much, if new data has the same correlation, because errors in individual weights cancel out in the combination. It hurts interpretation, and predictions when that correlation changes in production. So it matters most for understanding, and for shifting data.

    Follow-up 3 of 3

    You have 100 rows and 1,000 features. What happens to linear regression?

    Answer it out loud, then check.

    The rank is at most 100, so there are infinitely many weights that fit perfectly, and no unique solution. Use regularisation, such as ridge or lasso, reduce the features, or use a minimum-norm solution through the pseudoinverse. Each of those picks one answer.

    The rank is the number of truly independent columns, which is the real dimension of the data. If a feature is a mix of others, the matrix loses rank, XᵀX can't be inverted, and many sets of weights fit equally well. That's what the null space means: directions you can't determine from the data. With strong but not perfect correlation, a solution exists, but weights are unstable, with variance inflated by one over one minus R squared. I'd drop or combine features, or use ridge. Predictions may be fine, but weights can't be trusted.

    Key terms and sources

    Linear independence, span, basis, rank, column and null space, and how they explain collinearity, the dummy variable trap and low-dimensional embeddings.

    Sources

    Explanations are ours, built from these sources. Lab numbers are illustrative, and worked examples were checked by calculation.