Chapter 4 • Theory & Derivations

Unit 4: The Four Fundamental Matrix Subspaces & Rank-Nullity of Matrices

Row space, column space, null space, and left null space of a matrix; basis construction via RREF; proof that row rank equals column rank; the Rank-Nullity Theorem for matrices; orthogonality and the Fundamental Theorem of Linear Algebra; and Sylvester's Rank Inequality.

§4.1 The Four Fundamental Subspaces of a Matrix

1. Definition of the Four Fundamental Subspaces

Let $A \in M_{m \times n}(F)$ be an $m \times n$ matrix over a field $F$. Associated with $A$ are four canonical subspaces:

1. The Row Space $\text{Row}(A) \subseteq F^n$:

The subspace of $F^n$ spanned by the rows of $A$:

\text{Row}(A) = \text{span}\{\vec{r}_1, \vec{r}_2, \dots, \vec{r}_m\} = \text{Col}(A^T)

2. The Column Space (Range / Image) $\text{Col}(A) \subseteq F^m$:

The subspace of $F^m$ spanned by the columns of $A$:

\text{Col}(A) = \text{span}\{\vec{c}_1, \vec{c}_2, \dots, \vec{c}_n\} = \{A\vec{x} : \vec{x} \in F^n\}

3. The Null Space (Kernel) $\text{Null}(A) \subseteq F^n$:

The set of all solutions to the homogeneous linear system $A\vec{x} = \vec{0}$:

\text{Null}(A) = \{\vec{x} \in F^n : A\vec{x} = \vec{0}\}

4. The Left Null Space $\text{Null}(A^T) \subseteq F^m$:

The null space of $A^T$, or the set of row vectors $\vec{y}^T$ satisfying $\vec{y}^T A = \vec{0}^T$:

\text{Null}(A^T) = \{\vec{y} \in F^m : A^T \vec{y} = \vec{0}\}

2. Systematic Basis Construction Algorithms via RREF

Let $R = \text{rref}(A)$.

Basis for $\text{Row}(A)$: Elementary row operations preserve the row space ($\text{Row}(A) = \text{Row}(R)$). The non-zero rows of $R$ form an orthonormal-like, canonical basis for $\text{Row}(A)$.
Basis for $\text{Col}(A)$: EROs do not preserve the column space! However, EROs preserve all linear dependence relations among columns. The original columns of $A$ corresponding to the pivot columns of $R$ form a basis for $\text{Col}(A)$.
Basis for $\text{Null}(A)$: Solve $R\vec{x} = \vec{0}$. Express each pivot variable in terms of free variables $t_1, \dots, t_{n-r}$. Decomposing into vector parametric form $\vec{x} = \sum_{j=1}^{n-r} t_j \vec{v}_j$ yields the special solutions $\{\vec{v}_1, \dots, \vec{v}_{n-r}\}$, which form a basis for $\text{Null}(A)$.

§4.2 Row Rank Equals Column Rank & The Rank-Nullity Theorem

1. Theorem: Row Rank Equals Column Rank

The Row Rank of $A$ is $\dim(\text{Row}(A))$. The Column Rank of $A$ is $\dim(\text{Col}(A))$.

Theorem 4.1 (Row Rank = Column Rank):

For any matrix $A \in M_{m \times n}(F)$:

\dim(\text{Row}(A)) = \dim(\text{Col}(A)) = \text{rank}(A)

Proof: Let $R = \text{rref}(A)$, and let $r$ be the number of pivot entries (leading $1$s) in $R$.

The non-zero rows of $R$ are linearly independent and span $\text{Row}(R) = \text{Row}(A)$. Since there are $r$ non-zero rows, $\dim(\text{Row}(A)) = r$.
The columns of $A$ corresponding to the $r$ pivot columns of $R$ form a basis for $\text{Col}(A)$. Therefore, $\dim(\text{Col}(A)) = r$.

Since both dimensions equal the number of pivots $r$, we have $\dim(\text{Row}(A)) = \dim(\text{Col}(A)) = r$. $\blacksquare$

2. The Rank-Nullity Theorem for Matrices

Theorem 4.2 (The Matrix Rank-Nullity Theorem):

For any $m \times n$ matrix $A$:

\text{rank}(A) + \text{nullity}(A) = n

where $\text{rank}(A) = \dim(\text{Col}(A))$ and $\text{nullity}(A) = \dim(\text{Null}(A))$.

Proof: Let $r = \text{rank}(A)$ be the number of pivot columns in $\text{rref}(A)$. The total number of columns in $A$ is $n$. Every column of $\text{rref}(A)$ is either a pivot column or a free-variable column. Thus, the number of free variables is $n - r$. The dimension of the null space $\dim(\text{Null}(A))$ is precisely the number of free variables in the homogeneous solution:

\text{nullity}(A) = n - r

Rearranging gives:

r + (n - r) = n \implies \text{rank}(A) + \text{nullity}(A) = n

The proof is complete. $\blacksquare$

§4.3 The Fundamental Theorem of Linear Algebra & Orthogonality

1. Orthogonal Complements in $\mathbb{R}^n$

Let $W$ be a subspace of $\mathbb{R}^n$. The Orthogonal Complement of $W$, denoted by $W^\perp$, is:

W^\perp = \{\vec{x} \in \mathbb{R}^n : \vec{x} \cdot \vec{w} = 0 \quad \forall \vec{w} \in W\}

Properties of orthogonal complements:

$W^\perp$ is a subspace of $\mathbb{R}^n$.
$W \cap W^\perp = \{\vec{0}\}$.
$\mathbb{R}^n = W \oplus W^\perp$, and $\dim(W) + \dim(W^\perp) = n$.
$(W^\perp)^\perp = W$.

2. The Fundamental Theorem of Linear Algebra (Strang's Four Subspaces)

Theorem 4.3 (The Fundamental Theorem of Linear Algebra):

For any real $m \times n$ matrix $A$:

The null space is the orthogonal complement of the row space in $\mathbb{R}^n$:

\text{Null}(A) = (\text{Row}(A))^\perp \quad \iff \quad \mathbb{R}^n = \text{Row}(A) \oplus \text{Null}(A)

The left null space is the orthogonal complement of the column space in $\mathbb{R}^m$:

\text{Null}(A^T) = (\text{Col}(A))^\perp \quad \iff \quad \mathbb{R}^m = \text{Col}(A) \oplus \text{Null}(A^T)

Proof of Part 1: A vector $\vec{x} \in \text{Null}(A)$ if and only if $A\vec{x} = \vec{0}$. In terms of rows $\vec{r}_1, \dots, \vec{r}_m$ of $A$:

A\vec{x} = \begin{pmatrix} \vec{r}_1 \cdot \vec{x} \\ \vec{r}_2 \cdot \vec{x} \\ \vdots \\ \vec{r}_m \cdot \vec{x} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix}

This holds if and only if $\vec{x}$ is orthogonal to every row $\vec{r}_i$ of $A$, which is equivalent to $\vec{x}$ being orthogonal to all linear combinations of rows, i.e., $\vec{x} \in (\text{Row}(A))^\perp$. Applying this to $A^T$ yields Part 2. $\blacksquare$

3. Sylvester's Rank Inequality

Theorem 4.4 (Sylvester's Rank Inequality):

Let $A \in M_{m \times n}(F)$ and $B \in M_{n \times p}(F)$. Then:

\text{rank}(A) + \text{rank}(B) - n \le \text{rank}(AB) \le \min(\text{rank}(A), \text{rank}(B))

TIERED UNIVERSITY HONORS PROBLEMS

Step-by-Step Solved Examination Problems

Comprehensive analytical derivations, multi-tier solutions (Foundational, Intermediate Exam, and Honors/Proof Challenge) with complete line-by-line verification.

Tier 1: Foundational Example 4.1: Systematic Derivation of the Four Fundamental Subspaces

Given the matrix $A \in M_{3 \times 4}(\mathbb{R})$:

A = \begin{pmatrix} 1 & -1 & 2 & 3 \\ 2 & 2 & 0 & 2 \\ 4 & 0 & 4 & 8 \end{pmatrix}

(a) Compute the Reduced Row Echelon Form $\text{rref}(A)$. (b) Find the rank and nullity of $A$. (c) Construct explicit bases for all four fundamental subspaces: $\text{Row}(A), \text{Col}(A), \text{Null}(A)$, and $\text{Null}(A^T)$. (d) Explicitly verify that every basis vector of $\text{Null}(A)$ is orthogonal to every basis vector of $\text{Row}(A)$.

Step 1: Compute RREF of $A$:

A = \begin{pmatrix} 1 & -1 & 2 & 3 \\ 2 & 2 & 0 & 2 \\ 4 & 0 & 4 & 8 \end{pmatrix}

Apply row operations:

$R_2 \to R_2 - 2R_1$: $(0, \; 2 - 2(-1) = 4, \; 0 - 4 = -4, \; 2 - 6 = -4)$
$R_3 \to R_3 - 4R_1$: $(0, \; 0 - 4(-1) = 4, \; 4 - 8 = -4, \; 8 - 12 = -4)$

Row 2 divided by 4: $R_2 \to \frac{1}{4}R_2 = (0, 1, -1, -1)$. Row 3 minus Row 2: $R_3 \to R_3 - 4R_2 = (0, 0, 0, 0)$. Clear Row 1 above pivot: $R_1 \to R_1 + R_2 = (1, 0, \; 2 - 1 = 1, \; 3 - 1 = 2)$.

The RREF is:

\text{rref}(A) = \begin{pmatrix} 1 & 0 & 1 & 2 \\ 0 & 1 & -1 & -1 \\ 0 & 0 & 0 & 0 \end{pmatrix}

Step 2: Rank and Nullity:

Number of pivots = 2 $\implies \text{rank}(A) = 2$.
Number of columns $n = 4 \implies \text{nullity}(A) = 4 - 2 = 2$.

Step 3: Bases for the Four Subspaces:

1. Row Space $\text{Row}(A) \subseteq \mathbb{R}^4$:

\mathcal{B}_{\text{Row}} = \left\{ \begin{pmatrix} 1 \\ 0 \\ 1 \\ 2 \end{pmatrix}, \; \begin{pmatrix} 0 \\ 1 \\ -1 \\ -1 \end{pmatrix} \right\}

2. Column Space $\text{Col}(A) \subseteq \mathbb{R}^3$:

Pivots are in columns 1 and 2:

\mathcal{B}_{\text{Col}} = \left\{ \begin{pmatrix} 1 \\ 2 \\ 4 \end{pmatrix}, \; \begin{pmatrix} -1 \\ 2 \\ 0 \end{pmatrix} \right\}

3. Null Space $\text{Null}(A) \subseteq \mathbb{R}^4$:

From RREF: $x_1 + x_3 + 2x_4 = 0 \implies x_1 = -x_3 - 2x_4$; $x_2 - x_3 - x_4 = 0 \implies x_2 = x_3 + x_4$. Free variables $x_3 = s, x_4 = t$:

\vec{x} = s \begin{pmatrix} -1 \\ 1 \\ 1 \\ 0 \end{pmatrix} + t \begin{pmatrix} -2 \\ 1 \\ 0 \\ 1 \end{pmatrix} \implies \mathcal{B}_{\text{Null}} = \left\{ \begin{pmatrix} -1 \\ 1 \\ 1 \\ 0 \end{pmatrix}, \; \begin{pmatrix} -2 \\ 1 \\ 0 \\ 1 \end{pmatrix} \right\}

4. Left Null Space $\text{Null}(A^T) \subseteq \mathbb{R}^3$:

Solve $A^T \vec{y} = \vec{0}$:

A^T = \begin{pmatrix} 1 & 2 & 4 \\ -1 & 2 & 0 \\ 2 & 0 & 4 \\ 3 & 2 & 8 \end{pmatrix} \to \text{rref}(A^T) = \begin{pmatrix} 1 & 0 & 2 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}

$y_1 = -2y_3, y_2 = -y_3$. Letting $y_3 = 1$:

\mathcal{B}_{\text{LeftNull}} = \left\{ \begin{pmatrix} -2 \\ -1 \\ 1 \end{pmatrix} \right\}

Step 4: Verify Orthogonality $\text{Row}(A) \perp \text{Null}(A)$:

$\vec{r}_1 \cdot \vec{n}_1 = 1(-1) + 0(1) + 1(1) + 2(0) = -1 + 1 = 0$.
$\vec{r}_1 \cdot \vec{n}_2 = 1(-2) + 0(1) + 1(0) + 2(1) = -2 + 2 = 0$.
$\vec{r}_2 \cdot \vec{n}_1 = 0(-1) + 1(1) + (-1)(1) + (-1)(0) = 1 - 1 = 0$.
$\vec{r}_2 \cdot \vec{n}_2 = 0(-2) + 1(1) + (-1)(0) + (-1)(1) = 1 - 1 = 0$.

Orthogonality strictly verified!

Final Answer & Physical Insight

$\text{rank}(A) = 2, \text{nullity}(A) = 2$. $\mathcal{B}_{\text{Row}} = \{(1, 0, 1, 2)^T, (0, 1, -1, -1)^T\}$, $\mathcal{B}_{\text{Col}} = \{(1, 2, 4)^T, (-1, 2, 0)^T\}$, $\mathcal{B}_{\text{Null}} = \{(-1, 1, 1, 0)^T, (-2, 1, 0, 1)^T\}$, $\mathcal{B}_{\text{LeftNull}} = \{(-2, -1, 1)^T\}$. Orthogonality verified.

Tier 2: Intermediate Exam Example 4.2: Rank Analysis of Matrix Products & Invariance Under Multiplication

(a) Prove that for any two matrices $A \in M_{m \times n}(F)$ and $B \in M_{n \times p}(F)$:

\text{rank}(AB) \le \min(\text{rank}(A), \text{rank}(B))

(b) If $P \in M_{m \times m}(F)$ is an invertible matrix, prove that $\text{rank}(PA) = \text{rank}(A)$. (c) If $Q \in M_{n \times n}(F)$ is an invertible matrix, prove that $\text{rank}(AQ) = \text{rank}(A)$. (d) Find a concrete counterexample showing that $\text{rank}(AB)$ can be strictly less than $\min(\text{rank}(A), \text{rank}(B))$. Under what necessary and sufficient condition on the fundamental subspaces does equality $\text{rank}(AB) = \text{rank}(B)$ hold?

Part (a): Proof of $\text{rank}(AB) \le \min(\text{rank}(A), \text{rank}(B))$:

Column space containment: Each column of $AB$ is a linear combination of the columns of $A$:

(AB)_{*j} = A (B_{*j}) \in \text{Col}(A)

Therefore, $\text{Col}(AB) \subseteq \text{Col}(A)$. Since a subspace cannot have a larger dimension than its parent space:

\text{rank}(AB) = \dim(\text{Col}(AB)) \le \dim(\text{Col}(A)) = \text{rank}(A)

Row space containment: Similarly, each row of $AB$ is a linear combination of the rows of $B$:

(AB)_{i*} = (A_{i*}) B \in \text{Row}(B)

Therefore, $\text{Row}(AB) \subseteq \text{Row}(B)$, implying:

\text{rank}(AB) = \dim(\text{Row}(AB)) \le \dim(\text{Row}(B)) = \text{rank}(B)

Combining both inequalities gives $\text{rank}(AB) \le \min(\text{rank}(A), \text{rank}(B))$. $\blacksquare$

Part (b): Invariance under invertible pre-multiplication: Since $P$ is invertible, $A = P^{-1}(PA)$. Applying Part (a):

\text{rank}(PA) \le \text{rank}(A) \quad \text{and} \quad \text{rank}(A) = \text{rank}(P^{-1}(PA)) \le \text{rank}(PA)

Thus $\text{rank}(PA) = \text{rank}(A)$.

Part (c): Invariance under invertible post-multiplication: Since $Q$ is invertible, $A = (AQ) Q^{-1}$. Applying Part (a):

\text{rank}(AQ) \le \text{rank}(A) \quad \text{and} \quad \text{rank}(A) = \text{rank}((AQ)Q^{-1}) \le \text{rank}(AQ)

Thus $\text{rank}(AQ) = \text{rank}(A)$.

Part (d): Counterexample and Condition for Equality: Let $A = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$ and $B = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$. Here $\text{rank}(A) = 1$ and $\text{rank}(B) = 1$. However:

AB = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix} \implies \text{rank}(AB) = 0 < \min(1, 1)

Condition for $\text{rank}(AB) = \text{rank}(B)$: Consider the linear transformation $T_A: \text{Col}(B) \to F^m$ defined by $T_A(\vec{v}) = A\vec{v}$. By the Rank-Nullity Theorem applied to $T_A|_{\text{Col}(B)}$:

\dim(\text{Col}(B)) = \dim(\ker(T_A|_{\text{Col}(B)})) + \dim(\text{im}(T_A|_{\text{Col}(B)})) = \dim(\text{Col}(B) \cap \text{Null}(A)) + \text{rank}(AB)

Therefore, $\text{rank}(AB) = \text{rank}(B)$ if and only if $\dim(\text{Col}(B) \cap \text{Null}(A)) = 0$, i.e.:

\text{Col}(B) \cap \text{Null}(A) = \{\vec{0}\}

Final Answer & Physical Insight

$\text{rank}(AB) \le \min(\text{rank}(A), \text{rank}(B))$. Invertible multiplication preserves rank. Strictly smaller rank occurs when $\text{Col}(B)$ intersects $\text{Null}(A)$ non-trivially (e.g. nilpotents $A=B=\begin{pmatrix}0&1\\0&0\end{pmatrix} \implies AB = O$). Equality $\text{rank}(AB) = \text{rank}(B)$ holds $\iff \text{Col}(B) \cap \text{Null}(A) = \{\vec{0}\}$.

Tier 3: Honors / Proof Challenge Example 4.3: Rigorous Proof of Sylvester's Rank Inequality

Let $A \in M_{m \times n}(F)$ and $B \in M_{n \times p}(F)$ be matrices over field $F$.

(a) Prove rigorously Sylvester's Rank Inequality:

\text{rank}(A) + \text{rank}(B) - n \le \text{rank}(AB)

(b) Give an alternative geometric proof using the restriction of the linear map $T_A$ to the subspace $\text{Col}(B)$. (c) Deduce that if $n = p$ and $AB = O$, then $\text{rank}(A) + \text{rank}(B) \le n$. Provide an example achieving equality.

Part (a): Formal Proof via Rank-Nullity: Consider the linear transformation $T_A: F^n \to F^m$ defined by $T_A(\vec{x}) = A\vec{x}$. Restrict $T_A$ to the subspace $W = \text{Col}(B) \subseteq F^n$. The image of this restriction is:

T_A(W) = T_A(\text{Col}(B)) = \{A(B\vec{y}) : \vec{y} \in F^p\} = \text{Col}(AB)

The kernel of this restriction is:

\ker(T_A|_{W}) = \{\vec{w} \in W : A\vec{w} = \vec{0}\} = W \cap \ker(T_A) = \text{Col}(B) \cap \text{Null}(A)

By the Rank-Nullity Theorem applied to $T_A|_W$:

\dim(W) = \dim(\ker(T_A|_W)) + \dim(T_A(W))

\text{rank}(B) = \dim(\text{Col}(B) \cap \text{Null}(A)) + \text{rank}(AB)

Rearranging for $\text{rank}(AB)$:

\text{rank}(AB) = \text{rank}(B) - \dim(\text{Col}(B) \cap \text{Null}(A))

Since $\text{Col}(B) \cap \text{Null}(A) \subseteq \text{Null}(A)$:

\dim(\text{Col}(B) \cap \text{Null}(A)) \le \dim(\text{Null}(A)) = \text{nullity}(A)

By the Rank-Nullity Theorem for matrix $A$:

\text{nullity}(A) = n - \text{rank}(A)

Therefore:

\dim(\text{Col}(B) \cap \text{Null}(A)) \le n - \text{rank}(A)

Substituting this bound into our expression for $\text{rank}(AB)$:

\text{rank}(AB) = \text{rank}(B) - \dim(\text{Col}(B) \cap \text{Null}(A)) \ge \text{rank}(B) - (n - \text{rank}(A))

\text{rank}(AB) \ge \text{rank}(A) + \text{rank}(B) - n

This establishes Sylvester's Rank Inequality. $\blacksquare$

Part (b): Alternative Proof via Grassmann's Formula: In $F^n$, consider the two subspaces $W_1 = \text{Null}(A)$ and $W_2 = \text{Col}(B)$. By Grassmann's dimension formula:

\dim(W_1 + W_2) = \dim(W_1) + \dim(W_2) - \dim(W_1 \cap W_2)

Since $W_1 + W_2 \subseteq F^n$, we have $\dim(W_1 + W_2) \le n$. Thus:

\dim(W_1 \cap W_2) = \dim(W_1) + \dim(W_2) - \dim(W_1 + W_2) \ge \dim(\text{Null}(A)) + \dim(\text{Col}(B)) - n

Substituting $\dim(\text{Null}(A)) = n - \text{rank}(A)$ and $\dim(\text{Col}(B)) = \text{rank}(B)$:

\dim(W_1 \cap W_2) \ge (n - \text{rank}(A)) + \text{rank}(B) - n = \text{rank}(B) - \text{rank}(A)

From $\text{rank}(AB) = \text{rank}(B) - \dim(W_1 \cap W_2)$:

\text{rank}(AB) \ge \text{rank}(B) - \dim(W_1 \cap W_2)

Substituting $\dim(W_1 \cap W_2) \le \dim(\text{Null}(A)) = n - \text{rank}(A)$ yields $\text{rank}(AB) \ge \text{rank}(A) + \text{rank}(B) - n$. $\blacksquare$

Part (c): Consequence for $AB = O$: If $AB = O$, then $\text{rank}(AB) = 0$. Applying Sylvester's inequality:

0 \ge \text{rank}(A) + \text{rank}(B) - n \implies \text{rank}(A) + \text{rank}(B) \le n

Alternatively, $AB = O \implies \text{Col}(B) \subseteq \text{Null}(A) \implies \text{rank}(B) \le \text{nullity}(A) = n - \text{rank}(A)$.

Equality Example for $n = 4$: Let $A = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}$ and $B = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$. $\text{rank}(A) = 2, \text{rank}(B) = 2$. $AB = O$, and $\text{rank}(A) + \text{rank}(B) = 2 + 2 = 4 = n$. Equality achieved!

Final Answer & Physical Insight

$\text{rank}(AB) \ge \text{rank}(A) + \text{rank}(B) - n$ proved via Rank-Nullity on $T_A|_{\text{Col}(B)}$. If $AB = O$, $\text{rank}(A) + \text{rank}(B) \le n$. Equality holds when $\text{Col}(B) = \text{Null}(A)$ (e.g. complementary projection matrices $A = \text{diag}(1,1,0,0)$ and $B = \text{diag}(0,0,1,1)$).