Exercises Notebook

Converted from exercises.ipynb for web reading.

Matrix Rank - Exercises

10 graded exercises covering the full linear algebra basics arc, from computation to ML-facing matrix workflows.

Difficulty: straightforward -> moderate -> challenging.

Code cell 2

import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl

try:
    import seaborn as sns
    sns.set_theme(style="whitegrid", palette="colorblind")
    HAS_SNS = True
except ImportError:
    plt.style.use("seaborn-v0_8-whitegrid")
    HAS_SNS = False

mpl.rcParams.update({
    "figure.figsize":    (10, 6),
    "figure.dpi":         120,
    "font.size":           13,
    "axes.titlesize":      15,
    "axes.labelsize":      13,
    "xtick.labelsize":     11,
    "ytick.labelsize":     11,
    "legend.fontsize":     11,
    "legend.framealpha":   0.85,
    "lines.linewidth":      2.0,
    "axes.spines.top":     False,
    "axes.spines.right":   False,
    "savefig.bbox":       "tight",
    "savefig.dpi":         150,
})
np.random.seed(42)
print("Plot setup complete.")

Code cell 3

import numpy as np
import numpy.linalg as la
import scipy.linalg as sla
from scipy import stats

COLORS = {
    "primary": "#0077BB",
    "secondary": "#EE7733",
    "tertiary": "#009988",
    "error": "#CC3311",
    "neutral": "#555555",
    "highlight": "#EE3377",
}
HAS_MPL = True
np.set_printoptions(precision=8, suppress=True)
np.random.seed(42)

def header(title):
    print("\n" + "=" * len(title))
    print(title)
    print("=" * len(title))

def check_true(name, cond):
    ok = bool(cond)
    print(f"{'PASS' if ok else 'FAIL'} - {name}")
    return ok

def check_close(name, got, expected, tol=1e-8):
    ok = np.allclose(got, expected, atol=tol, rtol=tol)
    print(f"{'PASS' if ok else 'FAIL'} - {name}: got {got}, expected {expected}")
    return ok

def check(name, got, expected, tol=1e-8):
    return check_close(name, got, expected, tol=tol)

def softmax(z, axis=-1, tau=1.0):
    z = np.asarray(z, dtype=float) / float(tau)
    z = z - np.max(z, axis=axis, keepdims=True)
    e = np.exp(z)
    return e / np.sum(e, axis=axis, keepdims=True)

def cosine_similarity(a, b):
    a = np.asarray(a, dtype=float); b = np.asarray(b, dtype=float)
    return float(a @ b / (la.norm(a) * la.norm(b) + 1e-12))

def numerical_rank(A, tol=1e-10):
    return int(np.sum(la.svd(A, compute_uv=False) > tol))

def orthonormal_basis(A, tol=1e-10):
    Q, R = la.qr(A)
    keep = np.abs(np.diag(R)) > tol
    return Q[:, keep]

def null_space(A, tol=1e-10):
    U, S, Vt = la.svd(A)
    return Vt[S.size:,:].T if S.size < Vt.shape[0] else Vt[S <= tol,:].T



# Compatibility helpers used by the Chapter 02 theory and exercise cells.
def null_space(A, tol=1e-10):
    A = np.asarray(A, dtype=float)
    U, S, Vt = la.svd(A, full_matrices=True)
    rank = int(np.sum(S > tol))
    return Vt[rank:].T

svd_null_space = null_space

def gram_schmidt(vectors, tol=1e-10):
    A = np.asarray(vectors, dtype=float)
    if A.ndim == 1:
        A = A.reshape(1, -1)
    basis = []
    for v in A:
        w = v.astype(float).copy()
        for q in basis:
            w = w - np.dot(w, q) * q
        norm = la.norm(w)
        if norm > tol:
            basis.append(w / norm)
    return np.array(basis)

def projection_matrix_from_columns(A, tol=1e-10):
    Q = orthonormal_basis(np.asarray(A, dtype=float), tol=tol)
    return Q @ Q.T


def random_unit_vectors(n, d):
    X = np.random.randn(n, d)
    return X / np.maximum(la.norm(X, axis=1, keepdims=True), 1e-12)

def pairwise_distances(X):
    X = np.asarray(X, dtype=float)
    diff = X[:, None, :] - X[None, :, :]
    return la.norm(diff, axis=-1)


def normalize(x, axis=None, tol=1e-12):
    x = np.asarray(x, dtype=float)
    norm = la.norm(x, axis=axis, keepdims=True)
    return x / np.maximum(norm, tol)

def frobenius_inner(A, B):
    return float(np.sum(np.asarray(A, dtype=float) * np.asarray(B, dtype=float)))

def outer_sum_product(A, B):
    A = np.asarray(A, dtype=float)
    B = np.asarray(B, dtype=float)
    return sum(np.outer(A[:, k], B[k, :]) for k in range(A.shape[1]))

def softmax_rows(X):
    return softmax(X, axis=1)

def col_space(A, tol=1e-10):
    return orthonormal_basis(np.asarray(A, dtype=float), tol=tol)

def row_space(A, tol=1e-10):
    return orthonormal_basis(np.asarray(A, dtype=float).T, tol=tol).T

def rref(A, tol=1e-10):
    R = np.array(A, dtype=float, copy=True)
    m, n = R.shape
    pivots = []
    row = 0
    for col in range(n):
        pivot = row + int(np.argmax(np.abs(R[row:, col]))) if row < m else row
        if row >= m or abs(R[pivot, col]) <= tol:
            continue
        if pivot != row:
            R[[row, pivot]] = R[[pivot, row]]
        R[row] = R[row] / R[row, col]
        for r in range(m):
            if r != row:
                R[r] = R[r] - R[r, col] * R[row]
        pivots.append(col)
        row += 1
        if row == m:
            break
    R[np.abs(R) < tol] = 0.0
    return R, pivots

def nullspace_basis(A, tol=1e-10):
    A = np.asarray(A, dtype=float)
    U, S, Vt = la.svd(A, full_matrices=True)
    rank = int(np.sum(S > tol))
    return Vt[rank:].T, rank

print("Chapter helper setup complete.")

Exercise 1: Rank from Pivots *

Use row reduction to determine the rank of a matrix. This is the algebraic starting point for the chapter.

Task:

• Implement a small rref(M) routine
• Return the reduced matrix and pivot columns
• Use it to compute the rank of a sample matrix

Code cell 5

# Your Solution
# Exercise 1 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 1.")

Code cell 6

# Solution
# Exercise 1 - reference solution

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

def rref(M, tol=1e-12):
    M = np.array(M, dtype=float).copy()
    rows, cols = M.shape
    pivots = []
    r = 0

    for c in range(cols):
        if r >= rows:
            break
        pivot = r + np.argmax(np.abs(M[r:, c]))
        if abs(M[pivot, c]) < tol:
            continue
        if pivot != r:
            M[[r, pivot]] = M[[pivot, r]]
        M[r] /= M[r, c]
        for i in range(rows):
            if i != r and abs(M[i, c]) > tol:
                M[i] -= M[i, c] * M[r]
        M[np.abs(M) < tol] = 0.0
        pivots.append(c)
        r += 1
    return M, pivots


R, pivots = rref(A)

header('Exercise 1 checks')
print('RREF(A) =\n', R)
print('pivots =', pivots)
check_true('rank is 2', len(pivots) == 2)
print('\nTakeaway: in exact algebra, rank is the number of pivot columns.')

print("Exercise 1 solution complete.")

Exercise 2: Null Space and Rank-Nullity *

Rank tells you how many directions survive. Nullity tells you how many are killed.

Task:

• Compute a basis for the null space using SVD
• Verify rank-nullity for a rectangular matrix

Code cell 8

# Your Solution
# Exercise 2 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 2.")

Code cell 9

# Solution
# Exercise 2 - reference solution

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

def nullspace(A, tol=1e-10):
    U, s, Vt = np.linalg.svd(A)
    rank = np.sum(s > tol)
    return Vt[rank:].T, rank


N, rank_B = nullspace(B)
nullity_B = B.shape[1] - rank_B

header('Exercise 2 checks')
print('rank(B) =', rank_B)
print('nullity(B) =', nullity_B)
print('nullspace basis =\n', N)
check_true('rank-nullity holds', rank_B + nullity_B == B.shape[1])
check_close('B @ N = 0', B @ N, np.zeros((B.shape[0], N.shape[1])))
print('\nTakeaway: rank counts surviving directions, nullity counts annihilated directions.')

print("Exercise 2 solution complete.")

Exercise 3: Row Space and Column Space Dimensions *

The theorem row rank = column rank says two very different-looking spaces have the same dimension.

Task:

• Find a basis for the row space from the non-zero rows of RREF
• Find a basis for the column space from the pivot columns of the original matrix
• Verify that the dimensions agree

Code cell 11

# Your Solution
# Exercise 3 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 3.")

Code cell 12

# Solution
# Exercise 3 - reference solution

C = np.array([[1.0, 2.0, 3.0], [2.0, 4.0, 6.0], [1.0, 1.0, 2.0]])
R, pivots = rref(C)

row_basis = R[~np.all(np.isclose(R, 0.0), axis=1)]
col_basis = C[:, pivots]

header('Exercise 3 checks')
print('pivot columns =', pivots)
print('\nrow-space basis =\n', row_basis)
print('\ncolumn-space basis =\n', col_basis)
check_true('row-space dimension equals column-space dimension', row_basis.shape[0] == col_basis.shape[1])
print('\nTakeaway: row rank and column rank coincide even though the spaces live in different ambient dimensions.')

print("Exercise 3 solution complete.")

Exercise 4: Rank Inequalities *

Rank obeys useful upper and lower bounds under addition and multiplication.

Task:

• Build small matrices showing that product rank can collapse dramatically
• Verify the inequalities numerically

Code cell 14

# Your Solution
# Exercise 4 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 4.")

Code cell 15

# Solution
# Exercise 4 - reference solution

A = np.array([[1.0, 0.0], [0.0, 0.0]])
B = np.array([[0.0, 0.0], [0.0, 1.0]])
C = np.array([[1.0, 0.0], [0.0, 0.0]])
D = np.array([[0.0, 0.0], [0.0, 1.0]])

rank_A = np.linalg.matrix_rank(A)
rank_B = np.linalg.matrix_rank(B)
rank_AB = np.linalg.matrix_rank(A @ B)
rank_C = np.linalg.matrix_rank(C)
rank_D = np.linalg.matrix_rank(D)
rank_C_plus_D = np.linalg.matrix_rank(C + D)

header('Exercise 4 checks')
print('rank(A), rank(B), rank(AB) =', rank_A, rank_B, rank_AB)
print('rank(C), rank(D), rank(C + D) =', rank_C, rank_D, rank_C_plus_D)
check_true('product rank can drop to zero', rank_AB == 0)
check_true('subadditivity holds', rank_C_plus_D <= rank_C + rank_D)
print('\nTakeaway: multiplication never creates new independent directions, and addition is only subadditive.')

print("Exercise 4 solution complete.")

Exercise 5: Numerical Rank and Thresholds **

Exact rank is discrete. Numerical rank depends on what you treat as negligible.

Task:

• Build a diagonal matrix with singular values (10, 1, 1e-2, 1e-6)
• Study how the detected rank changes as the threshold changes

Code cell 17

# Your Solution
# Exercise 5 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 5.")

Code cell 18

# Solution
# Exercise 5 - reference solution

S = np.diag([5.0, 1e-2, 1e-6, 1e-10])
thresholds = [1e-12, 1e-8, 1e-4, 1e-1]

singular_values = np.linalg.svd(S, compute_uv=False)

header('Exercise 5 checks')
print('singular values =', singular_values)
for eps in thresholds:
    rank_eps = np.sum(singular_values > eps)
    print(f'threshold {eps:>7.1e} -> numerical rank {rank_eps}')
check_true('exact rank is 4', np.linalg.matrix_rank(S) == 4)
print('\nTakeaway: numerical rank is threshold-sensitive, which is exactly why SVD-based diagnostics are needed in practice.')

print("Exercise 5 solution complete.")

Exercise 6: Rank Factorization **

A rank-r matrix factors through an r-dimensional latent space.

Task:

• Construct a rank factorization A = B @ C using the SVD
• Verify that the inner dimension equals the rank

Code cell 20

# Your Solution
# Exercise 6 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 6.")

Code cell 21

# Solution
# Exercise 6 - reference solution

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

U, s, Vt = np.linalg.svd(A, full_matrices=False)
r = np.linalg.matrix_rank(A)
B = U[:, :r] @ np.diag(s[:r])
C = Vt[:r, :]

header('Exercise 6 checks')
print('rank(A) =', r)
print('B shape =', B.shape)
print('C shape =', C.shape)
check_close('A reconstructed from factors', B @ C, A)
check_true('inner dimension equals rank', B.shape[1] == r and C.shape[0] == r)
print('\nTakeaway: rank factorization makes the latent bottleneck explicit.')

print("Exercise 6 solution complete.")

Exercise 7: Best Rank-1 Approximation **

Use truncated SVD to compute the best rank-1 approximation and measure how much of the matrix energy it captures.

Code cell 23

# Your Solution
# Exercise 7 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 7.")

Code cell 24

# Solution
# Exercise 7 - reference solution

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

U, s, Vt = np.linalg.svd(A, full_matrices=False)
A1 = s[0] * np.outer(U[:, 0], Vt[0, :])
fro_error = np.linalg.norm(A - A1, ord='fro')
variance_fraction = (s[0] ** 2) / np.sum(s**2)

header('Exercise 7 checks')
print('singular values =', s)
print('\nA1 =\n', A1)
print('\nFrobenius error =', fro_error)
print('variance fraction =', variance_fraction)
check_true('Eckart-Young Frobenius error matches discarded singular value', np.isclose(fro_error, s[1]))
print('\nTakeaway: low-rank approximation quality is governed by singular value decay, not by matrix size alone.')

print("Exercise 7 solution complete.")

Exercise 8: Stable Rank vs Exact Rank **

Two matrices can have the same exact rank but very different effective structure.

Task:

• Compute exact rank, stable rank, and condition number for several examples

Code cell 26

# Your Solution
# Exercise 8 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 8.")

Code cell 27

# Solution
# Exercise 8 - reference solution

W1 = np.diag([5.0, 4.0, 3.0, 2.0])
W2 = np.diag([5.0, 0.5, 0.05, 0.005])
W3 = np.outer(np.array([1.0, 2.0, -1.0]), np.array([2.0, 0.5, 1.0]))

def stable_rank(A):
    s = np.linalg.svd(A, compute_uv=False)
    return np.sum(s**2) / (s[0]**2)


header('Exercise 8 checks')
for name, W in [('W1', W1), ('W2', W2), ('W3', W3)]:
    rank = np.linalg.matrix_rank(W)
    sr = stable_rank(W)
    cond = np.linalg.cond(W) if rank == min(W.shape) else np.inf
    print(f'{name}: rank = {rank}, stable rank = {sr:.6f}, cond = {cond}')
check_true('W3 is rank 1', np.linalg.matrix_rank(W3) == 1)
check_true('stable rank never exceeds exact rank', stable_rank(W1) <= np.linalg.matrix_rank(W1))
print('\nTakeaway: stable rank measures how spread the spectrum is, not just how many singular values are non-zero.')

print("Exercise 8 solution complete.")

Exercise 9 (★★★): Rank Bound for Products

Show numerically that

$$\operatorname{rank}(AB)\le \min(\operatorname{rank}(A),\operatorname{rank}(B)).$$

Connect this to low-rank adapters and bottleneck layers.

Code cell 29

# Your Solution
# Exercise 9 - learner workspace
# Compare ranks of A, B, and AB.
print("Learner workspace ready for Exercise 9.")

Code cell 30

# Solution
# Exercise 9 - rank of a product
header("Exercise 9: rank product bound")

rng = np.random.default_rng(7)
A = rng.normal(size=(6, 2)) @ rng.normal(size=(2, 5))
B = rng.normal(size=(5, 3)) @ rng.normal(size=(3, 4))
AB = A @ B
rA, rB, rAB = la.matrix_rank(A), la.matrix_rank(B), la.matrix_rank(AB)
print("rank(A), rank(B), rank(AB):", rA, rB, rAB)
check_true("product rank bound", rAB <= min(rA, rB))
print("Takeaway: bottleneck dimensions cap the expressive rank of a linear map.")

Exercise 10 (★★★): Numerical Rank Under Noise

A matrix may be exactly low rank but appear full rank after small noise. Inspect singular values and estimate rank using a tolerance.

Code cell 32

# Your Solution
# Exercise 10 - learner workspace
# Add noise to a low-rank matrix and inspect singular values.
print("Learner workspace ready for Exercise 10.")

Code cell 33

# Solution
# Exercise 10 - numerical rank under noise
header("Exercise 10: numerical rank")

rng = np.random.default_rng(42)
M_low = rng.normal(size=(8, 2)) @ rng.normal(size=(2, 6))
M_noisy = M_low + 1e-6 * rng.normal(size=M_low.shape)
s = la.svd(M_noisy, compute_uv=False)
print("singular values:", s)
print("rank tol=1e-10:", numerical_rank(M_noisy, tol=1e-10))
print("rank tol=1e-4:", numerical_rank(M_noisy, tol=1e-4))
check_true("strict rank sees noise", numerical_rank(M_noisy, tol=1e-10) > 2)
check_true("practical rank recovers signal", numerical_rank(M_noisy, tol=1e-4) == 2)
print("Takeaway: numerical rank is a modeling decision tied to tolerance and noise scale.")

What to Review After Finishing

• Can you compute rank from pivots, from null space dimension, and from singular values?
• Can you explain why row rank and column rank are the same number even though the spaces differ?
• Can you use SVD to reason about numerical rank and low-rank approximation?
• Can you explain LoRA and attention bottlenecks directly in rank language?
• Do you know when exact rank is the wrong practical concept and numerical rank is the right one?

References used in the chapter and notebook design:

• notes.md
• theory.ipynb
• MIT 18.06 Linear Algebra
• Stanford EE263
• LoRA
• DeepSeek-V2 Technical Report
• DeepSeek-V3 Technical Report
• Aghajanyan et al. (2020)
• Halko, Martinsson, and Tropp (2011)
• Gavish and Donoho (2014)