Linear Systems, Inverse & Rank

Ax = b has a unique solution exactly when A is square with full rank; rank counts the independent directions A can reach.

6 min read465 wordscore3 viewsupdated 2026-10-03

Definition

A linear system Ax=bAx=b asks for the weights xx that combine the columns of AA into bb. The rank of AA is its number of linearly independent columns (equivalently, rows) — the dimension of everything AA can reach. A square matrix of full rank has an inverse A−1A^{-1} with A−1A=IA^{-1}A=I, and then x=A−1bx=A^{-1}b is the only solution, for every bb.

At a glance

Notation
A∈Rm×nA\in\mathbb{R}^{m\times n}, x∈Rnx\in\mathbb{R}^n, b∈Rmb\in\mathbb{R}^m; rank⁡A\operatorname{rank}A; A−1A^{-1}
Solvable iff
bb lies in the column space of AA
Unique iff
also rank⁡A=n\operatorname{rank}A=n — no nonzero xx with Ax=0Ax=0
Invertible iff
square and full rank ⇔ det⁡A≠0\det A\ne0
Cost
Gaussian elimination (LU), O(n3)O(n^3)
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: Ax=x1a1+x2a2Ax=x_1a_1+x_2a_2, so solving means finding how much of each column to mix to land exactly on bb.

Trouble starts when columns are redundant. If a2a_2 is a multiple of a1a_1, mixing them reaches only one line. A bb off that line is unreachable — no solution. A bb on it is reachable in infinitely many ways, by trading some a1a_1 for some a2a_2. Rank counts how many genuinely different directions the columns provide.

The math

The column space C(A)C(A) is every vector of the form AxAx; the null space N(A)N(A) is every xx with Ax=0Ax=0. The rank–nullity theorem links them:

rank⁡A+dim⁡N(A)=n\operatorname{rank}A+\dim N(A)=n
nn
number of columns (unknowns)
N(A)N(A)
directions xx that AA sends to 00

So the solution set is either empty (b∉C(A)b\notin C(A)) or one particular solution plus the whole null space, x=xp+N(A)x=x_p+N(A). It is a single point exactly when N(A)={0}N(A)=\{0\}, i.e. rank⁡A=n\operatorname{rank}A=n. A tall matrix can satisfy this but reaches only some bb; a square full-rank matrix reaches every bb. For square matrices, full rank, det⁡A≠0\det A\ne0 and invertibility are the same condition.

(abcd)−1=1ad−bc(d−b−ca)\begin{pmatrix}a&b\\c&d\end{pmatrix}^{-1}=\frac{1}{ad-bc}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}
ad−bcad-bc
det⁡A\det A — the inverse exists only if it is nonzero

The 1/det⁡A1/\det A factor hints at the real danger: near-singular matrices. The condition number κ(A)=σmax⁡/σmin⁡\kappa(A)=\sigma_{\max}/\sigma_{\min}, the ratio of the largest to the smallest singular value, bounds how much relative error in bb is amplified in xx. Float64 carries about 16 digits, so κ=1010\kappa=10^{10} leaves roughly 6 trustworthy digits.

Gaussian elimination

  1. 1Subtract multiples of the first row to zero the first column below the pivot.
  2. 2Repeat on the remaining rows and columns until the matrix is upper-triangular.
  3. 3Back-substitute from the last equation upward.
  4. 4The number of nonzero pivots is the rank.

See it

row picture · axes x₁, x₂2x₁ + 1x₂ = 31x₁ + 3x₂ = 5a₁a₂bcolumn picture · b = x₁a₁ + x₂a₂
det A = 5rank = 2x = (0.8, 1.4)
drag a₁, a₂, b · presets
fig.Left: each equation is a line; the solution is where they cross. Right: b = x₁a₁ + x₂a₂ drawn head to tail. Starting at a₁ = (2, 1), a₂ = (1, 3), b = (3, 5): det = 5 and x = (0.8, 1.4). Make the columns parallel and rank drops to 1 — the lines become parallel (no solution) or identical (infinitely many).

Worked example

2x1+x2=32x_1+x_2=3 and x1+3x2=5x_1+3x_2=5. Here det⁡A=2⋅3−1⋅1=5\det A=2\cdot3-1\cdot1=5, A−1=15(3−1−12)A^{-1}=\tfrac15\begin{pmatrix}3&-1\\-1&2\end{pmatrix}, so x=15(9−5, −3+10)=(0.8, 1.4)x=\tfrac15(9-5,\,-3+10)=(0.8,\,1.4). Check: 2(0.8)+1.4=32(0.8)+1.4=3 and 0.8+3(1.4)=50.8+3(1.4)=5.

Now x1+2x2=3x_1+2x_2=3 and 2x1+4x2=62x_1+4x_2=6: the second row is twice the first, so det⁡A=0\det A=0 and rank is 1. Every point x=(3,0)+t(−2,1)x=(3,0)+t(-2,1) solves it. Change the right side to (3,7)(3,7) and the rows contradict each other (2⋅3≠72\cdot3\ne7): no solution.

In code

python
1import numpy as np
2
3A = 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 formed
5np.linalg.matrix_rank(A), np.linalg.cond(A) # (2, ≈ 2.618)
6
7S = np.array([[1.0, 2.0], [2.0, 4.0]]) # parallel columns
8np.linalg.matrix_rank(S) # 1
9np.linalg.lstsq(S, np.array([3.0, 6.0]), rcond=None)[0] # ≈ [0.6, 1.2] (min-norm)
Solve, inspect rank and conditioning, and handle the singular case.

Where it's used

Least squares

The normal equations X⊤Xw=X⊤yX^\top Xw=X^\top y are a linear system; collinear features make XX rank-deficient and ww non-unique.

Second-order optimization

Each Newton step solves H Δ=−∇fH\,\Delta=-\nabla f for the step Δ\Delta.

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

AA is 3×33\times3 with rank 2, and bb is in its column space. How many solutions does Ax=bAx=b have?

Check yourself

What is det⁡(1234)\det\begin{pmatrix}1&2\\3&4\end{pmatrix}, and is the matrix invertible?

Remember

  • ✓Solvable iff b∈C(A)b\in C(A); unique iff also rank⁡A=n\operatorname{rank}A=n.
  • ✓Rank = independent columns; rank⁡A+dim⁡N(A)=n\operatorname{rank}A+\dim N(A)=n.
  • ✓Square: full rank ⇔ det⁡A≠0\det A\ne0 ⇔ invertible.
  • ✓Solve with solve or lstsq, never inv; judge stability by the condition number.
← back to Mathematics roadmap