Rank, Invertibility & Null Space

What is Matrix Rank?

The Rank of a matrix is the maximum number of linearly independent column vectors (or row vectors) it contains.

Column vectors are linearly independent if no column can be created by scaling and adding other columns together.

  FULL RANK (Rank = 2)                       RANK DEFICIENT (Rank = 1)
  Col 1: [1, 0]^T                            Col 1: [1, 2]^T
  Col 2: [0, 1]^T                            Col 2: [2, 4]^T (Col 2 = 2 * Col 1!)
  (Columns point in distinct directions)     (Col 2 lies on same line as Col 1!)

The Invertibility Equivalences (Square n × n Matrix A)

The following statements are 100% mathematically equivalent. If one is true, all are true:

1. A is Full Rank: $\text{Rank}(A) = n$.
2. A is Invertible (Non-Singular): Matrix inverse $A^{-1}$ exists such that $A A^{-1} = I$.
3. Determinant is Non-Zero: $\det(A) \neq 0$.
4. Null Space is Trivial: $\text{Null}(A) = {0}$ (Only $x = 0$ satisfies $A x = 0$).
5. Eigenvalues are Non-Zero: All eigenvalues $\lambda_i \neq 0$.
6. Unique Solution: System $A x = b$ has a unique single solution $x = A^{-1} b$.

Why This Destroys OLS Linear Regression

The closed-form solution for Ordinary Least Squares (OLS) weights:

w = (X^T X)^-1 X^T y

Suppose your dataset includes two features:

• Feature 1: Weight in pounds ($x_1$).
• Feature 2: Weight in kilograms ($x_2 = 0.453592 \cdot x_1$).

Because $x_2$ is a direct linear multiple of $x_1$, the features are perfectly collinear.

1. Column 2 is linearly dependent on Column 1.
2. Feature matrix $X$ loses full rank ($\text{Rank}(X^T X) < d$).
3. Determinant $\det(X^T X) = 0$ (Matrix is Singular).
4. Matrix inverse $(X^T X)^{-1}$ DOES NOT EXIST. Program crashes with singular matrix error!

Two Fixes for Rank Deficiency in ML

1. Drop Collinear Columns: Use Variance Inflation Factor (VIF) to find and remove redundant columns.
2. L2 Regularization (Ridge Regression): Add $\lambda I$ to $X^T X$:

w = (X^T X + \lambda I)^-1 X^T y

Adding $\lambda I$ shifts all eigenvalues away from 0, guaranteeing that $(X^T X + \lambda I)$ is always full rank and 100% invertible!

Say this out loud

Matrix Rank measures the number of linearly independent columns. A square n x n matrix is full rank if its rank is n, its determinant is non-zero, and its inverse A^-1 exists. If features are linearly dependent (multicollinearity), X^T X loses full rank and becomes non-invertible, breaking OLS regression. We fix this by dropping redundant features or adding L2 Ridge regularization (X^T X + lambda I) to force full rank.

Follow-ups to expect

• What is the Rank-Nullity Theorem? For an m x n matrix A: Rank(A) + Dim(Null(A)) = n. The dimension of column space plus dimension of null space equals total number of columns n.
• What is a Pseudo-Inverse (Moore-Penrose Inverse)? For non-square or rank-deficient matrices where A^-1 does not exist, the pseudo-inverse A^+ provides the minimum-norm least-squares solution.