5.412 min read

The Row Rank Theorem: Proof via Factoring

The proof of the Row Rank Theorem uses a clever intermediate idea: matrix factoring. A $q$ -factoring of $C$ is a way to write $C = AB$ where $A$ is $m \times q$ and $B$ is $q \times n$ . The number $q$ is like a bottleneck: information must pass through a $q$ -dimensional space.

The key lemmas are: (1) if $C$ has a $q$ -factoring, then $\text{Rank}(C) \leq q$ ; (2) if $\text{Rank}(C) = r$ , then $C$ has an $r$ -factoring (take $A$ to be any matrix whose columns form a basis for $\text{Col}(C)$ ). Together, these let us bound the rank of a matrix by looking at any factoring.

The proof then works by a symmetric sandwich argument. Using factoring, we can show $\text{Rank}(C^t) \leq \text{Rank}(C)$ . Applying this same inequality to $C^t$ gives $\text{Rank}(C) = \text{Rank}((C^t)^t) \leq \text{Rank}(C^t)$ . Combining both directions forces equality.

Formal View

Definition 5.5 — Matrix Factoring

Let

C

be an

m \times n

matrix. We say

C = AB

is a $q$-factoring if

A

m \times q

and

B

q \times n

Lemma 5.6

C

has a

q

-factoring

C = AB

, then

\text{Rank}(C) \leq q

Proof: $\text{Col}(C) = \text{Col}(AB) \subseteq \text{Col}(A)$ , and $\dim(\text{Col}(A)) \leq q$ .

Lemma 5.7

\text{Rank}(C) = r

, then

C

has an

r

-factoring.

Proof: let $A$ be the $m \times r$ matrix whose columns form a basis for $\text{Col}(C)$ . Then each column of $C$ is a linear combination of the columns of $A$ , giving the needed $r \times n$ matrix $B$ .

Theorem 5.8 — Row Rank Theorem (Proof)

For any matrix

C

\text{Rank}(C^t) \leq \text{Rank}(C)

(from the

r

-factoring of

C

applied to

C^t = B^t A^t

). Applying this to

C^t

gives

\text{Rank}(C) \leq \text{Rank}(C^t)

. Together:

\text{Rank}(C) = \text{Rank}(C^t)

Why This Matters

The factoring argument is a template for bounding rank that appears throughout advanced linear algebra.

Low-rank approximations in data compression (JPEG, Netflix recommendation) exploit the idea that $C \approx AB$ with small $q$
The rank inequality $\text{Rank}(AB) \leq \min(\text{Rank}(A), \text{Rank}(B))$ follows directly from the same factoring argument
In quantum information, factoring rank bounds the complexity of entangled states

Learning Resources

Rank-nullity theorem and proofs

MIT OpenCourseWare

Strang on the fundamental theorem of linear algebra connecting row and column spaces.

48 min

Low rank approximations

Mutual Information

Why the rank of a matrix controls how compressible the data it encodes really is.

14 min

Quiz

Question 1

If $C = AB$ where $A$ is $5 \times 2$ and $B$ is $2 \times 7$ , what can you conclude about $\text{Rank}(C)$ ?

Question 2

$\text{Rank}(AB) \leq \min(\text{Rank}(A), \text{Rank}(B))$ for all matrices $A, B$ with compatible dimensions.

Common Mistakes

Assuming a $q$ -factoring implies $\text{Rank}(C) = q$ — the lemma only gives an upper bound.
Forgetting to reverse the order when transposing a product: $(AB)^t = B^t A^t$ , not $A^t B^t$ .