Chapter 15: Rank, Null Space & Solvability of Linear Systems

Chapter 15: Rank, Null Space & Solvability of Linear Systems

AI Reading

Quick summary of this article

Preparing the AI summary…

AI Mathematics Masterclass — Chapter 15 of 48

Rank answers one question about a matrix: how much information does it actually use? A rank-deficient matrix has a null space — a set of input directions it erases entirely. That single fact explains why a duplicated feature column breaks a regression, why a ReLU layer can permanently lose a unit, why a low-rank adapter is an approximation rather than a reparameterisation, and why LinAlgError: Singular matrix is a statement about lost dimensionality rather than a software fault.

1. Technical Audit & Core Learning Objectives

Component Common Tutorial Deficiency Engineering Standard Applied Here
Rank Defined as “number of independent rows” and left there. Framed as the dimension of the image, with information loss made explicit.
Null space Omitted or treated as abstract. Presented as the set of directions the matrix cannot see.
Solvability The four cases listed without a decision procedure. Structured as a table keyed on m, n, and rank, each with the right solver.
ML connection Never mentioned. Rank collapse traced through features, dead units, and adapters.

Core learning objectives. After this chapter you should be able to:

  1. Compute rank from the singular value spectrum and from elimination.
  2. Find the null space of a small matrix and verify Av = 0.
  3. State the rank–nullity theorem and use it to count free variables.
  4. Decide solvability from rank(A) versus rank([A|b]).
  5. Predict what a rank-deficient layer destroys.
  6. Detect rank collapse in a trained network.

2. The Four Subspaces

Column space, row space and null space boxes with the rank-nullity identity beneath
Figure 15.1: The subspaces attached to a matrix, and the identity that links their dimensions.
For A ∈ ℝ^(m×n):

column space  C(A) ⊆ ℝ^m     dim = rank
row space     C(Aᵀ) ⊆ ℝ^n    dim = rank
null space    N(A) ⊆ ℝ^n     dim = n − rank
left null     N(Aᵀ) ⊆ ℝ^m    dim = m − rank

Rank–nullity:  rank + nullity = n        (number of columns)
import numpy as np

A = np.array([[1.0, 2.0, 3.0],
              [2.0, 4.0, 6.0],
              [1.0, 1.0, 1.0]])

r = np.linalg.matrix_rank(A)
print("shape:", A.shape, " rank:", r, " nullity:", A.shape[1] - r)
assert r + (A.shape[1] - r) == A.shape[1]

# the null space comes from the smallest right singular vectors
u, s, vt = np.linalg.svd(A)
n = vt[r:].T
print("null space basis:\n", np.round(n, 6))
print("A @ null == 0:", np.allclose(A @ n, 0.0, atol=1e-12))

The last two lines are the practical definition. Any vector v with ‖Av‖ ≈ 0 is in (or nearly in) the null space, and the SVD hands you an orthonormal basis for it as the trailing rows of Vᵀ.

3. The Null Space Is What the Matrix Erases

A line in the plane labelled null space whose vectors all map to zero
Figure 15.2: Every vector on the null-space line maps to zero. Those inputs cannot be recovered from the output.

The consequence is many-to-one behaviour. If An = 0, then for any input x:

A(x + n) = Ax + An = Ax + 0 = Ax

Two distinct inputs, one identical output.
The map cannot be inverted: given Ax you cannot tell
whether the input was x or x + n.
import numpy as np

A = np.array([[1.0, 2.0],
              [2.0, 4.0]])
n = np.array([2.0, -1.0])              # null vector: row2 = 2*row1
print("A @ n =", A @ n)                # [0. 0.]

x = np.array([3.0, 1.0])
print("A x       =", A @ x)
print("A (x + n) =", A @ (x + n))
assert np.allclose(A @ x, A @ (x + n))
print("two different inputs, identical output")

4. Solvability: The Decision Table

Ax equals b solvability conditions with the role of rank and the null space
Figure 15.3: A solution exists exactly when b lies in the column space.
Four cases of linear systems by shape and rank, with the number of solutions and the appropriate method
Figure 15.4: The four cases, and the solver each one calls for.
Case Solutions Use
m = n, full rank Exactly one np.linalg.solve
m > n, full column rank Zero or one lstsq — least squares
m < n, full row rank Infinitely many lstsq — minimum norm
rank < min(m,n) Zero or infinitely many lstsq, or add ridge
import numpy as np

# over-determined: 4 equations, 2 unknowns
X = np.array([[1.0, 0.0], [0.0, 1.0], [1.0, 1.0], [2.0, 1.0]])
y = np.array([1.0, 2.0, 3.0, 4.5])

print("rank(X):", np.linalg.matrix_rank(X), "of", X.shape[1], "columns")
w, *_ = np.linalg.lstsq(X, y, rcond=None)
resid = np.linalg.norm(X @ w - y)
print("least-squares residual:", round(resid, 4))    # not zero: no exact solution

5. Rank Deficiency in a Network

Consequences of a rank-deficient weight matrix and the causes of rank collapse
Figure 15.5: What a rank-deficient layer destroys, and the training conditions that produce one.
import numpy as np

rng = np.random.default_rng(0)
d = 64

healthy = rng.normal(size=(d, d)) / np.sqrt(d)
print("healthy rank:", np.linalg.matrix_rank(healthy))

# simulate collapse: 40 of 64 rows driven to zero (dead units)
collapsed = rng.normal(size=(d, d)) / np.sqrt(d)
collapsed[:40] = 0.0
print("collapsed rank:", np.linalg.matrix_rank(collapsed))    # 24, not 64

s_h = np.linalg.svd(healthy, compute_uv=False)
s_c = np.linalg.svd(collapsed, compute_uv=False)
print("healthy  smin/smax:", f"{s_h[-1]/s_h[0]:.4f}")
print("collapsed smin/smax:", f"{s_c[-1]/s_c[0]:.2e}")

The ratio σmin/σmax is the reciprocal condition number, and it is the practical collapse detector. A value falling by many orders of magnitude during training means the layer is progressively ignoring input directions — which is what “dead units” look like in matrix form.

6. Worked Examples

6.1 Rank from inspection

A = [[1,2],[2,4]]
row₂ = 2·row₁  →  rank 1
nullity = 2 − 1 = 1
null vector (2,−1) since 1·2 + 2·(−1) = 0

6.2 Rank of a rank-one outer product

u vᵀ for u ∈ ℝ^m, v ∈ ℝⁿ has rank exactly 1.
Every column is a multiple of u.

6.3 Inconsistent system

x + y = 1
x + y = 2
rank([[1,1],[1,1]]) = 1
rank([[1,1,1],[1,1,2]]) = 2
Extended rank exceeds coefficient rank → no solution.

6.4 Under-determined system

x + y = 3      (1 equation, 2 unknowns)
rank = 1, nullity = 1, infinitely many solutions
Solver returns the minimum-norm one: (1.5, 1.5).

6.5 Rank bound of a product

rank(AB) ≤ min(rank A, rank B)
So a rank-4 LoRA adapter ΔW = BA is at most rank 4,
no matter how large A and B are.

7. Verify It in Python

import numpy as np

# --- 1. rank-nullity identity -------------------------------------
A = np.array([[1., 2., 3.], [2., 4., 6.], [1., 1., 1.]])
r = np.linalg.matrix_rank(A)
assert r + (A.shape[1] - r) == A.shape[1]
print("rank:", r, " nullity:", A.shape[1] - r)

# --- 2. null space from SVD ---------------------------------------
u, s, vt = np.linalg.svd(A)
null = vt[r:].T
assert np.allclose(A @ null, 0.0, atol=1e-12)
print("null basis has", null.shape[1], "vector(s)")

# --- 3. many-to-one mapping ---------------------------------------
D = np.array([[1., 2.], [2., 4.]])
n = np.array([2., -1.])
assert np.allclose(D @ n, 0.0)
x = np.array([3., 1.])
assert np.allclose(D @ x, D @ (x + n))
print("null vector causes identical outputs")

# --- 4. inconsistent system detection -----------------------------
M = np.array([[1., 1.], [1., 1.]])
b = np.array([1., 2.])
aug = np.column_stack([M, b])
assert np.linalg.matrix_rank(M) < np.linalg.matrix_rank(aug)
print("rank(A):", np.linalg.matrix_rank(M),
      " rank([A|b]):", np.linalg.matrix_rank(aug), "-> inconsistent")

# --- 5. under-determined returns minimum norm ---------------------
row = np.array([[1., 1.]])
sol, *_ = np.linalg.lstsq(row, np.array([3.]), rcond=None)
print("min-norm solution:", sol)
assert np.allclose(sol, [1.5, 1.5])
assert np.isclose(sol @ sol, 4.5)                 # 1.5^2 + 1.5^2

# --- 6. rank of an outer product is 1 -----------------------------
u = np.arange(1., 5.); v = np.array([2., 3., 5.])
assert np.linalg.matrix_rank(np.outer(u, v)) == 1
print("outer product rank:", np.linalg.matrix_rank(np.outer(u, v)))

# --- 7. rank of a product is bounded -------------------------------
rng = np.random.default_rng(0)
Bmat = rng.normal(size=(64, 4))
Amat = rng.normal(size=(4, 64))
dW = Bmat @ Amat
assert np.linalg.matrix_rank(dW) <= 4
print("rank(BA) <= 4:", np.linalg.matrix_rank(dW))

# --- 8. collapse detector -----------------------------------------
W = rng.normal(size=(32, 32)) / np.sqrt(32)
sv = np.linalg.svd(W, compute_uv=False)
ratio = sv[-1] / sv[0]
print("sigma_min/sigma_max:", f"{ratio:.4f}")
assert ratio > 1e-6                                # healthy: not collapsed
print("all assertions passed")

8. Practice Questions

  1. Find the rank and nullity of [[1,2,3],[2,4,6]].
  2. Give a null vector for [[1,2],[2,4]] and verify Av = 0.
  3. State the rank–nullity theorem and apply it to a (3×5) full-rank matrix.
  4. When is Ax = b inconsistent, in terms of ranks?
  5. Show that a rank-one outer product has rank exactly one.
  6. Prove rank(AB) ≤ min(rank A, rank B) and give an example where it is strictly smaller.
  7. Explain why a rank-deficient layer cannot be inverted.
  8. What does σmin/σmax approaching zero indicate during training?
  9. Why does lstsq succeed where solve raises LinAlgError?
  10. For a LoRA adapter with r = 8 on a 4096×4096 weight, what is the maximum rank of the update?

Leave a Reply

Your email address will not be published. Required fields are marked *