Definition
A linear system asks for the weights that combine the columns of into . The rank of is its number of linearly independent columns (equivalently, rows) — the dimension of everything can reach. A square matrix of full rank has an inverse with , and then is the only solution, for every .
At a glance
- Notation
- , , ; ;
- Solvable iff
- lies in the column space of
- Unique iff
- also — no nonzero with
- Invertible iff
- square and full rank ⇔
- Cost
- Gaussian elimination (LU),
- Prerequisites
- matrix multiplication
- Used in
- least squares, Newton's method, Gaussian processes, Kalman filters
The intuition
The same equations have two pictures. Row picture: each equation is a line (a hyperplane in higher dimensions), and a solution is a point lying on all of them. Column picture: , so solving means finding how much of each column to mix to land exactly on .
Trouble starts when columns are redundant. If is a multiple of , mixing them reaches only one line. A off that line is unreachable — no solution. A on it is reachable in infinitely many ways, by trading some for some . Rank counts how many genuinely different directions the columns provide.
The math
The column space is every vector of the form ; the null space is every with . The rank–nullity theorem links them:
- number of columns (unknowns)
- directions that sends to
So the solution set is either empty () or one particular solution plus the whole null space, . It is a single point exactly when , i.e. . A tall matrix can satisfy this but reaches only some ; a square full-rank matrix reaches every . For square matrices, full rank, and invertibility are the same condition.
- — the inverse exists only if it is nonzero
The factor hints at the real danger: near-singular matrices. The condition number , the ratio of the largest to the smallest singular value, bounds how much relative error in is amplified in . Float64 carries about 16 digits, so leaves roughly 6 trustworthy digits.
Gaussian elimination
- 1Subtract multiples of the first row to zero the first column below the pivot.
- 2Repeat on the remaining rows and columns until the matrix is upper-triangular.
- 3Back-substitute from the last equation upward.
- 4The number of nonzero pivots is the rank.
See it
Worked example
and . Here , , so . Check: and .
Now and : the second row is twice the first, so and rank is 1. Every point solves it. Change the right side to and the rows contradict each other (): no solution.
In code
1import numpy as np23A = np.array([[2.0, 1.0], [1.0, 3.0]]); b = np.array([3.0, 5.0])4np.linalg.solve(A, b) # array([0.8, 1.4]) — LU, no inverse formed5np.linalg.matrix_rank(A), np.linalg.cond(A) # (2, ≈ 2.618)67S = np.array([[1.0, 2.0], [2.0, 4.0]]) # parallel columns8np.linalg.matrix_rank(S) # 19np.linalg.lstsq(S, np.array([3.0, 6.0]), rcond=None)[0] # ≈ [0.6, 1.2] (min-norm)Where it's used
Least squares
The normal equations are a linear system; collinear features make rank-deficient and non-unique.
Second-order optimization
Each Newton step solves for the step .
Gaussian processes & Kalman filters
Predictions require solving with covariance matrices, usually via a Cholesky factorization.
Feature engineering
One-hot encoding every category plus an intercept is rank-deficient — the dummy-variable trap.
Check yourself
is with rank 2, and is in its column space. How many solutions does have?
Check yourself
What is , and is the matrix invertible?
Remember
- ✓Solvable iff ; unique iff also .
- ✓Rank = independent columns; .
- ✓Square: full rank ⇔ ⇔ invertible.
- ✓Solve with
solveorlstsq, neverinv; judge stability by the condition number.