Chapter 14 Exercises — Row Space, Left Null Space, and Rank-Nullity

How to use these. Work the ⭐ problems first to lock in the four-subspaces vocabulary (no computation needed). The ⭐⭐ problems are by-hand calculations — find all four subspaces, count dimensions, apply rank-nullity. The ⭐⭐⭐ problems split into proofs (the A track) and coding with numpy (the C track); do the ones that match your path, but the strongest students do both. The ⭐⭐⭐⭐ problems are applied: find the four-subspaces structure hiding in a real system. Tags: [hand] = pencil only, [code] = needs numpy, [proof] = rigorous argument, [essay] = written explanation.

For several problems, use the running matrix from the chapter, $$A = \begin{bmatrix} 1 & 2 & 1 & 3 \\ 2 & 4 & 0 & 4 \\ 3 & 6 & 1 & 7 \end{bmatrix}, \qquad \operatorname{RREF}(A) = \begin{bmatrix} 1 & 2 & 0 & 2 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

Tier ⭐ — Conceptual (what is / why)

14.1 [hand] Name the four fundamental subspaces of an $m \times n$ matrix $A$, give the symbol for each, and state which ambient space ($\mathbb{R}^m$ or $\mathbb{R}^n$) each one lives in. Which two share the input space, and which two share the output space?

14.2 [hand] Why is the row space of $A$ written $C(A^{\mathsf{T}})$ rather than with a new symbol of its own? Answer in one sentence that names what the columns of $A^{\mathsf{T}}$ are.

14.3 [hand] State the rank-nullity theorem, including its conditions, for an $m \times n$ matrix. What is on the right-hand side — $m$, $n$, or $r$ — and why is it a common error to write the wrong one?

14.4 [hand] In one or two sentences each, explain the geometric meaning of (a) the column space, (b) the null space, (c) the row space, (d) the left null space, in terms of "reaches," "destroys," and "cannot reach."

14.5 [hand] A basis for the row space comes from the RREF rows, but a basis for the column space must come from the original columns of $A$. Explain the asymmetry: which space does row reduction preserve, and which does it change?

14.6 [hand] Define rank, and state two different things it equals (one about columns, one about rows). Why is it surprising that these two counts always agree, and what single quantity explains the agreement?

14.7 [hand] Give the dimensions of all four fundamental subspaces of an $m \times n$ matrix of rank $r$, in terms of $m$, $n$, and $r$. Check that the input-space pair sums to $n$ and the output-space pair sums to $m$.

14.8 [hand] A matrix is said to have full column rank when $r = n$ and full row rank when $r = m$. For each, say which fundamental subspace becomes the zero subspace, and what that implies about solutions of $A\mathbf{x} = \mathbf{b}$ (existence, uniqueness).

Tier ⭐⭐ — Computation by hand

14.9 [hand] For the running matrix $A$ above, write down a basis for the row space $C(A^{\mathsf{T}})$ and state its dimension. (Read the nonzero RREF rows.)

14.10 [hand] For $A$ above, write down a basis for the column space $C(A)$ and state its dimension. (Use the pivot columns of $A$ itself — be careful not to use the RREF columns.)

14.11 [hand] For $A$ above, find a basis for the null space $N(A)$ by setting each free variable to $1$ in turn. Confirm $\dim N(A) = n - r$.

14.12 [hand] For $A$ above, find a basis for the left null space $N(A^{\mathsf{T}})$ by spotting the dependence among the rows of $A$. Confirm $\dim N(A^{\mathsf{T}}) = m - r$ and that your vector $\mathbf{y}$ satisfies $\mathbf{y}^{\mathsf{T}}A = \mathbf{0}$.

14.13 [hand] Verify rank-nullity for $A$ by adding $\operatorname{rank}(A)$ and $\dim N(A)$; confirm the sum is $n = 4$. Then verify the output-space version: $\operatorname{rank}(A) + \dim N(A^{\mathsf{T}}) = m = 3$.

14.14 [hand] A matrix $B$ is $6 \times 4$ with rank $3$. Without seeing $B$, give the dimensions of all four fundamental subspaces and identify which space each lives in. Is $B\mathbf{x} = \mathbf{b}$ solvable for every $\mathbf{b}$? When it is solvable, how many free parameters does the solution have?

14.15 [hand] Find all four subspaces (bases and dimensions) of the tall matrix $$B = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}.$$ Which subspace is the zero subspace, and what does that say about solving $B\mathbf{x} = \mathbf{b}$?

14.16 [hand] For the matrix $\begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \end{bmatrix}$ (rank $1$), give bases for all four fundamental subspaces and verify both forms of rank-nullity. (Note how small the rank is and how large the two null spaces become.)

14.17 [hand] Verify the orthogonality relationships for the running matrix $A$ by hand: take one row-space basis vector and dot it with each null-space basis vector (should be $0$), then take one column-space basis vector and dot it with the left-null vector $(1, 1, -1)$ (should be $0$).

14.18 [hand] A square matrix $A$ is $4 \times 4$ with $\dim N(A) = 0$. Use rank-nullity to find $\operatorname{rank}(A)$, then state the dimensions of the other three subspaces and explain why $A$ must be invertible.

Tier ⭐⭐⭐ — Proofs (A track)

14.19 [proof] Prove that adding a multiple of one row to another does not change the row space. (Show new-span $\subseteq$ old-span using that the new row is a combination of old rows, then use reversibility for the other inclusion.)

14.20 [proof] Prove that $\operatorname{rank}(A) = \operatorname{rank}(A^{\mathsf{T}})$ using the rank factorization $A = CR$, where $C$ is $m \times r$ with columns a basis for $C(A)$ and $R$ is $r \times n$. (Read $A = CR$ by rows to bound the row rank by $r$, then apply the same argument to $A^{\mathsf{T}}$.)

14.21 [proof] Prove that $N(A)$ is orthogonal to $C(A^{\mathsf{T}})$: show that if $\mathbf{x} \in N(A)$ then $\mathbf{x}$ is perpendicular to every row of $A$, and conclude it is perpendicular to every linear combination of the rows.

14.22 [proof] Prove that for any $m \times n$ matrix, $\operatorname{rank}(A) \le \min(m, n)$. (Use that the rank is the dimension of a subspace of $\mathbb{R}^m$ and also of a subspace of $\mathbb{R}^n$.)

14.23 [proof] Prove the rank-nullity theorem in the form $\dim(\operatorname{im} T) + \dim(\ker T) = \dim V$ for a linear map $T : V \to W$ with $\dim V$ finite, by extending a basis of $\ker T$ to a basis of $V$ and showing the images of the added vectors form a basis of $\operatorname{im} T$. (This is the coordinate-free proof of §14.9's sidebar; you may assume the basis-extension lemma.)

14.24 [proof] Prove that $\operatorname{rank}(A + B) \le \operatorname{rank}(A) + \operatorname{rank}(B)$. (Hint: the column space of $A + B$ is contained in the sum of the column spaces $C(A) + C(B)$, and $\dim(U + W) \le \dim U + \dim W$.)

Tier ⭐⭐⭐ — Coding (C track)

Use numpy and, where helpful, sympy (for exact RREF) and scipy.linalg.null_space. Where a problem says "from scratch," do not call matrix_rank in the body — implement the logic and use matrix_rank only to check.

14.25 [code] Write a function four_subspace_dims(A) that returns the four dimensions $(\dim C(A),\ \dim N(A),\ \dim C(A^{\mathsf{T}}),\ \dim N(A^{\mathsf{T}}))$ using np.linalg.matrix_rank and the shape of A. Test it on the running matrix (expect $(2, 2, 2, 1)$) and on the tall matrix $B$ of 14.15 (expect $(2, 0, 2, 2)$).

14.26 [code] Implement rank(A) from scratch (no numpy in the body) following the Build-Your-Toolkit recipe in §14.12: row reduce to RREF and count the nonzero rows, using a tolerance of 1e-9 to decide whether a row is zero. Verify it against np.linalg.matrix_rank(np.array(A)) on at least five matrices, including the running matrix (rank $2$), a full-rank square matrix, the zero matrix (rank $0$), and a tall rank-deficient matrix.

14.27 [code] Write check_rank_nullity(A) that returns the triple $(r,\ \dim N(A),\ n)$ and asserts $r + \dim N(A) = n$. Use your rank from 14.26 for $r$ and np.array(A).shape[1] for $n$. Confirm the assertion holds for the running matrix, the tall matrix $B$, and a random $4 \times 7$ integer matrix.

14.28 [code] Verify the two orthogonality relationships numerically. For the running matrix $A$, get a row-space basis (nonzero sympy RREF rows), a null-space basis (scipy.linalg.null_space(A)), a column-space basis (pivot columns of A), and a left-null basis (null_space(A.T)). Print the matrix of dot products between the row-space and null-space bases (should be all $\approx 0$) and between the column-space and left-null bases (all $\approx 0$).

14.29 [code] Confirm row rank equals column rank empirically: generate 1000 random integer matrices of assorted shapes (tall, wide, square) and assert np.linalg.matrix_rank(M) == np.linalg.matrix_rank(M.T) for every one. Report that all passed and explain in a comment why numpy's SVD-based rank gives an independent confirmation of the pivot-counting argument.

14.30 [code] Build the $4 \times 4$ incidence matrix of the graph with edges $1\!\to\!2$, $2\!\to\!3$, $1\!\to\!3$, $3\!\to\!4$ ($-1$ at tail, $+1$ at head). Compute its rank and the dimensions of all four subspaces. Confirm the null space is spanned by the all-ones vector $(1,1,1,1)$ and that the left-null vector $(1, 1, -1, 0)$ (the triangle loop) satisfies $\mathbf{y}^{\mathsf{T}}A = \mathbf{0}$. Relate $\dim N(A^{\mathsf{T}})$ to the number of independent loops.

Tier ⭐⭐⭐⭐ — Application / short essay

14.31 [essay] Degrees of freedom in regression (statistics). A linear regression with $n$ data points and $p$ predictors (including the intercept) builds an $n \times p$ design matrix $X$ of full column rank $p$. In 150–250 words, explain how the residual degrees of freedom $n - p$ is exactly the dimension of a fundamental subspace of $X$ (which one?), and connect this to the chapter's rank-nullity reading. Tie your answer to the idea of degrees of freedom as the count of independent directions left after fitting.

14.32 [essay] Rank and compression (data science). A grayscale image is an $m \times n$ matrix of pixel values. In 150–250 words, explain why a matrix of rank $r$ can be stored using $r(m + n)$ numbers instead of $mn$ (use the rank factorization $A = CR$ of §14.5), and why an image whose rows are nearly dependent compresses well. Connect this to dimensionality reduction and forward-reference the SVD chapters.

14.33 [essay] A statically determinate truss (structural engineering). A 2D pin-jointed truss has $b$ bars and $j$ joints (with some joints pinned to the ground). Its equilibrium equations form a matrix $A$ relating bar forces to joint loads. In 150–250 words, explain how the rank of $A$ decides whether the structure is statically determinate (a unique set of bar forces balances any load — full rank, trivial null space) or indeterminate / a mechanism (a nonzero null space means the bars admit a self-stress, or the truss can move without stretching any bar). Name which fundamental subspace corresponds to "mechanisms" and which to "self-stress states."

14.34 [essay] Observability of a sensor network (engineering). A network of $m$ linear sensors measures an $n$-parameter state, giving $A\mathbf{x} = \mathbf{b}$. In 150–250 words, explain why the unobservable directions of the state form the null space $N(A)$ and have dimension $n - r$, why adding a sensor whose reading is a linear combination of existing ones does not improve observability, and how a rank check on $A$ tells an engineer how many independent parameters the network can actually determine. Which form of rank-nullity ($= n$ or $= m$) governs the count of unobservable directions, and why?