LA-4.5

Available

Matrix Rank

The rank of a matrix is the fundamental dimension that determines solvability of linear systems and invertibility of square matrices.

Learning Objectives

Define the rank of a matrix
Prove that row rank equals column rank
Compute rank using row reduction
Understand rank and solvability of linear systems
Apply rank to determine invertibility
Master rank inequalities
Connect rank to dimension of image and kernel
Understand the equivalent standard form

Prerequisites

Linear independence and span
Dimension of vector spaces
Elementary matrices (LA-4.4)
Gaussian elimination

1. Definition of Matrix Rank

The rank of a matrix captures the "essential dimension" of the linear transformation it represents.

Definition 4.18: Three Equivalent Definitions of Rank

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

Rank: $r(A) = \dim(\text{im } A)$ (dimension of image as a linear map)
Row rank: Dimension of the span of row vectors
Column rank: Dimension of the span of column vectors

Theorem 4.37: Fundamental Rank Theorem

For any matrix $A$ :

\text{rank}(A) = \text{row rank}(A) = \text{column rank}(A)

Remark 4.26: Why This is Remarkable

The row and column vectors of a matrix are completely different sets of vectors, yet they always have the same rank. This is not at all obvious from the definition!

2. Proof of the Rank Theorem

Proof:

Step 1: Show column rank ≤ row rank.

Let the row rank be $r$ , and let $\alpha_1, \ldots, \alpha_r$ be a maximal linearly independent set of rows. Every row is a linear combination of these $r$ rows:

\text{row}_i = \sum_{k=1}^{r} c_{ik} \alpha_k

Looking at the $j$ -th entry of each row, every column is a linear combination of $r$ vectors. Therefore column rank ≤ $r$ = row rank.

Step 2: Apply the same argument to $A^T$ .

Column rank of $A^T$ ≤ row rank of $A^T$ , which means row rank of $A$ ≤ column rank of $A$ .

Together: row rank = column rank.

∎

Corollary 4.12: Transpose Preserves Rank

\text{rank}(A^T) = \text{rank}(A)

Since transpose swaps rows and columns, and row rank = column rank.

3. Computing Rank

Theorem 4.38: Rank = Number of Pivots

The rank of a matrix equals the number of pivot columns in its row echelon form.

\text{rank}(A) = \text{number of pivots in REF of } A

Proof:

Row operations preserve row rank (they don't change the row space). In row echelon form, the non-zero rows are linearly independent, so row rank = number of non-zero rows = number of pivots.

∎

Example 4.15: Finding Rank

Find the rank of $A = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 1 & 3 & 4 \end{pmatrix}$ .

Solution: Row reduce:

\begin{pmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 1 & 3 & 4 \end{pmatrix} \xrightarrow{R_2 - 2R_1, R_3 - R_1} \begin{pmatrix} 1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 1 & 1 \end{pmatrix} \xrightarrow{R_2 \leftrightarrow R_3} \begin{pmatrix} 1 & 2 & 3 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{pmatrix}

There are 2 pivots, so $\text{rank}(A) = 2$ .

Example 4.15b: Rank of a 4×3 Matrix

Find the rank of $B = \begin{pmatrix} 1 & 0 & 2 \\ 0 & 1 & 1 \\ 2 & 1 & 5 \\ 1 & 1 & 3 \end{pmatrix}$ .

Solution: Row reduce:

\begin{pmatrix} 1 & 0 & 2 \\ 0 & 1 & 1 \\ 2 & 1 & 5 \\ 1 & 1 & 3 \end{pmatrix} \xrightarrow{R_3 - 2R_1, R_4 - R_1} \begin{pmatrix} 1 & 0 & 2 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{pmatrix} \xrightarrow{R_3 - R_2, R_4 - R_2} \begin{pmatrix} 1 & 0 & 2 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}

There are 2 pivots, so $\text{rank}(B) = 2$ . Note that despite having 4 rows and 3 columns, the rank is only 2.

Example 4.15c: Full Rank Matrix

Show that $C = \begin{pmatrix} 1 & 2 & 0 \\ 0 & 1 & 3 \\ 1 & 0 & 2 \end{pmatrix}$ has full rank.

Solution: Row reduce:

\begin{pmatrix} 1 & 2 & 0 \\ 0 & 1 & 3 \\ 1 & 0 & 2 \end{pmatrix} \xrightarrow{R_3 - R_1} \begin{pmatrix} 1 & 2 & 0 \\ 0 & 1 & 3 \\ 0 & -2 & 2 \end{pmatrix} \xrightarrow{R_3 + 2R_2} \begin{pmatrix} 1 & 2 & 0 \\ 0 & 1 & 3 \\ 0 & 0 & 8 \end{pmatrix}

3 pivots in a 3×3 matrix means $\text{rank}(C) = 3$ (full rank), so $C$ is invertible.

Remark 4.27: Alternative Rank Computations

Besides counting pivots, rank can be computed by:

Finding the size of the largest non-zero minor (subdeterminant)
Finding a maximal linearly independent set of rows/columns
Using SVD: rank = number of non-zero singular values

4. Rank and Invertibility

Theorem 4.39: Invertibility Criterion

For a square matrix $A \in M_n(F)$ , the following are equivalent:

$A$ is invertible
$\text{rank}(A) = n$
The $n$ rows (columns) are linearly independent
$Ax = 0$ has only the trivial solution

Proof:

(1) ⇒ (2): Invertible means bijective as a linear map, so dim(im) = n.

(2) ⇒ (3): Rank n means row/column rank is n, so rows/columns are independent.

(3) ⇒ (4): Independent columns means ker = {0}.

(4) ⇒ (1): Trivial kernel means injective, and for square matrices, injective implies surjective.

∎

5. Rank and Linear Systems

Theorem 4.40: Solvability via Rank

For the system $Ax = b$ :

Has a solution iff $\text{rank}(A) = \text{rank}([A|b])$
Has a unique solution iff additionally $\text{rank}(A) = n$ (number of unknowns)
Has infinitely many solutions iff $\text{rank}(A) < n$ and consistent

Theorem 4.41: Full Row/Column Rank

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

Full column rank ( $\text{rank} = n$ ): $A$ is injective, ker = {0}, solutions unique if they exist
Full row rank ( $\text{rank} = m$ ): $A$ is surjective, $Ax = b$ always solvable

Example 4.17: Linear System Analysis

Analyze the system $Ax = b$ where $A \in M_{2 \times 4}$ has rank 2:

Full row rank: Since rank = 2 = m, system is always consistent (surjective)
Nullity: $\text{nullity} = 4 - 2 = 2$ (two free parameters)
Solution space: If $x_0$ is a particular solution, general solution is $x_0 + \ker(A)$

Theorem 4.41b: Left/Right Inverse Existence

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

$A$ has a left inverse iff $A$ has full column rank ( $m \geq n$ , $\text{rank} = n$ )
$A$ has a right inverse iff $A$ has full row rank ( $n \geq m$ , $\text{rank} = m$ )
$A$ has both iff $A$ is square and invertible

Proof:

For left inverse: If $\text{rank}(A) = n$ , then $A^T A$ is $n \\times n$ with $\text{rank}(A^T A) = n$ (invertible).

Define $L = (A^T A)^{-1} A^T$ . Then $LA = (A^T A)^{-1} A^T A = I_n$ .

∎

Example 4.17b: Moore-Penrose Pseudoinverse

For a full column rank matrix $A$ , the left inverse is:

A^+ = (A^T A)^{-1} A^T

This gives the least squares solution to $Ax = b$ : $x = A^+ b$ .

6. Rank Inequalities

Theorem 4.42: Basic Rank Bounds

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

0 \leq \text{rank}(A) \leq \min(m, n)

Theorem 4.43: Product Rank Inequality

For matrices $A$ and $B$ where $AB$ is defined:

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

Theorem 4.44: Sum Rank Inequality

\text{rank}(A + B) \leq \text{rank}(A) + \text{rank}(B)

Theorem 4.45: Sylvester's Inequality

For $A \in M_{m \times n}$ and $B \in M_{n \times p}$ :

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

Proof:

Consider the sequence of linear maps:

F^p \xrightarrow{B} F^n \xrightarrow{A} F^m

We have $\text{im}(AB) \subseteq \text{im}(A)$ , so $\text{rank}(AB) \leq \text{rank}(A)$ .

Also, $\ker(A) \cap \text{im}(B)$ has dimension at least $\text{rank}(B) - \text{rank}(AB)$ (columns of $B$ mapped to $\ker(A)$ ).

Since $\ker(A) \subseteq F^n$ has dimension $n - \text{rank}(A)$ , we get the inequality.

∎

Example 4.16b: Applying Sylvester's Inequality

If $A \in M_{3 \times 4}$ has rank 3 and $B \in M_{4 \times 5}$ has rank 4, find bounds on $\text{rank}(AB)$ .

Solution:

Upper bound: $\text{rank}(AB) \leq \min(3, 4) = 3$
Sylvester: $\text{rank}(AB) \geq 3 + 4 - 4 = 3$

Therefore $\text{rank}(AB) = 3$ exactly.

Theorem 4.46: Frobenius Inequality

For matrices $A$ , $B$ , $C$ where $ABC$ is defined:

\text{rank}(AB) + \text{rank}(BC) \leq \text{rank}(B) + \text{rank}(ABC)

Corollary 4.13: Rank Equality under Full Rank

If $P$ is invertible, then $\text{rank}(PA) = \text{rank}(A) = \text{rank}(AQ)$ for invertible $Q$ .

Proof:

By Sylvester: $\text{rank}(P) + \text{rank}(A) - n \leq \text{rank}(PA) \leq \text{rank}(A)$ .

Since $P$ is invertible, $\text{rank}(P) = n$ , so $\text{rank}(A) \leq \text{rank}(PA)$ .

∎

7. Equivalent Standard Form

Theorem 4.46: Equivalent Standard Form

Every $m \times n$ matrix $A$ of rank $r$ can be transformed to:

PAQ = \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix}

where $P$ and $Q$ are products of elementary matrices.

Proof:

Use row and column operations (elementary matrices) to create pivots and clear all other entries. The result has $I_r$ in the upper-left and zeros elsewhere.

∎

Definition 4.19: Matrix Equivalence

Matrices $A$ and $B$ are equivalent if $B = PAQ$ for invertible $P$ , $Q$ . Two matrices are equivalent iff they have the same rank.

8. Worked Examples

Example: Rank and Solutions

Problem: For which values of $k$ does $\begin{pmatrix} 1 & 2 \\ 3 & k \end{pmatrix}x = \begin{pmatrix} 1 \\ 3 \end{pmatrix}$ have a unique solution?

Solution: Unique solution requires rank = 2 (full rank).

\text{rank} < 2 \iff \det = 0 \iff k - 6 = 0 \iff k = 6

So unique solution for all $k \neq 6$ .

Example: Using Sylvester

Problem: If $A \in M_{3 \times 4}$ has rank 3 and $B \in M_{4 \times 2}$ has rank 2, what are bounds on rank(AB)?

Solution:

\text{Upper bound: } \min(3, 2) = 2

\text{Lower bound (Sylvester): } 3 + 2 - 4 = 1

So $1 \leq \text{rank}(AB) \leq 2$ .

9. Common Mistakes

Mistake 1: Confusing Row and Column Space

Row operations preserve row space but can change column space. However, they preserve column RANK.

Mistake 2: Rank of Sum

$\text{rank}(A + B) \neq \text{rank}(A) + \text{rank}(B)$ in general. The inequality is ≤, and it can be strict.

Mistake 3: Solvability Criterion

$Ax = b$ solvable requires $\text{rank}(A) = \text{rank}([A|b])$ , not just that $A$ has high rank.

10. Key Takeaways

Row = Column

Row rank = column rank for ANY matrix.

Count Pivots

Rank = number of pivots in row echelon form.

Invertibility

Square matrix invertible ⟺ full rank.

Standard Form

Every matrix equivalent to $[I_r, 0; 0, 0]$ .

11. Additional Practice Problems

Problem 1

Find the rank of $\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 6 & 8 \\ 1 & 1 & 1 & 1 \end{pmatrix}$ .

Problem 2

If $\text{rank}(A) = 3$ and $A$ is $5 \times 7$ , what is dim(ker A)?

Problem 3

Prove that $\text{rank}(AA^T) = \text{rank}(A)$ .

Problem 4

For which values of $k$ is $\text{rank}\begin{pmatrix} 1 & k & 1 \\ k & 1 & 1 \\ 1 & 1 & k \end{pmatrix} < 3$ ?

Problem 5

If $AB = 0$ , prove that $\text{rank}(A) + \text{rank}(B) \leq n$ where $A$ is $m \times n$ .

12. Connections to Other Topics

Linear Maps

The rank of a matrix $A$ equals the dimension of the image of the linear map $x \mapsto Ax$ :

\text{rank}(A) = \dim(\text{im}(T_A))

Determinants

For square matrices, rank is related to the determinant:

\text{rank}(A) = n \iff \det(A) \neq 0

Eigenvalues

The rank relates to eigenvalues: $A$ has rank $n$ iff 0 is NOT an eigenvalue. Equivalently:

\text{rank}(A) < n \iff \lambda = 0 \text{ is an eigenvalue}

13. Study Tips

Count Pivots

The fastest way to find rank: row reduce and count pivots (leading 1s in REF).

Check Both Ways

Sometimes it's easier to count independent rows, sometimes columns. Use whichever is easier.

Use Upper Bounds

Remember rank ≤ min(m,n). If you need rank 5 but the matrix is 3×7, it's at most 3.

Think Linear Maps

Rank = dim(image). This connects to rank-nullity: n = rank + nullity.

14. Historical Notes

Ferdinand Georg Frobenius: Developed much of the theory of matrix rank in the late 19th century, including the rank-nullity theorem for matrices.

James Joseph Sylvester: Proved the inequality that bears his name: rank(A) + rank(B) - n ≤ rank(AB). This connects products to their factors.

Row Rank = Column Rank: This surprising theorem was established as matrices became understood as representations of linear maps, not just arrays of numbers.

Modern Applications: Matrix rank is fundamental in data science (PCA uses low-rank approximations), control theory, and signal processing.

15. Quick Reference Summary

Property	Formula
Basic bound	$\text{rank}(A) \leq \min(m, n)$
Transpose	$\text{rank}(A^T) = \text{rank}(A)$
Product upper bound	$\text{rank}(AB) \leq \min(\text{rank}(A), \text{rank}(B))$
Sylvester's inequality	$\text{rank}(A) + \text{rank}(B) - n \leq \text{rank}(AB)$
Sum inequality	$\text{rank}(A+B) \leq \text{rank}(A) + \text{rank}(B)$
Invertibility	$A \text{ invertible} \iff \text{rank}(A) = n$

16. Applications of Rank

Data Compression (Low-Rank Approximation)

SVD approximates a matrix with lower rank, compressing images and data while preserving essential information.

Control Theory

The rank of controllability and observability matrices determines whether a system can be controlled or observed.

Statistics (Least Squares)

Rank determines the existence and uniqueness of least squares solutions. Full column rank guarantees uniqueness.

Recommender Systems

Matrix factorization techniques (Netflix, Amazon) assume user-item matrices are approximately low-rank.

Computer Vision

Rank constraints appear in epipolar geometry, structure from motion, and background subtraction.

Network Analysis

The rank of incidence and adjacency matrices reveals connectivity properties of graphs.

17. Advanced Topics

Theorem 4.47: Rank and Determinant

For an $n \\times n$ matrix $A$ :

$\text{rank}(A) = n \iff \det(A) \neq 0$
$\text{rank}(A) < n \iff \det(A) = 0$

Theorem 4.48: Rank via Minors

The rank of $A$ equals the size of the largest non-zero minor (subdeterminant).

$\text{rank}(A) = r$ iff there exists an $r \\times r$ non-zero minor, but all $(r+1) \times (r+1)$ minors are zero.

Example 4.18: Rank via Minors

For $A = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 0 & 1 & 1 \end{pmatrix}$ :

$\det(A) = 0$ (row 2 = 2 × row 1)
Check 2×2 minors: $\det\begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix} = 1 \neq 0$
Therefore $\text{rank}(A) = 2$

Theorem 4.49: Rank of A^T A

For any real matrix $A$ :

\text{rank}(A^T A) = \text{rank}(A A^T) = \text{rank}(A)

Proof:

Show $\ker(A) = \ker(A^T A)$ :

$Ax = 0 \Rightarrow A^T A x = 0$ (clearly)
$A^T A x = 0 \Rightarrow x^T A^T A x = 0 \Rightarrow \|Ax\|^2 = 0 \Rightarrow Ax = 0$

So nullity( $A$ ) = nullity( $A^T A$ ), and by rank-nullity, rank( $A$ ) = rank( $A^T A$ ).

∎

Remark 4.28: Numerical Rank

In numerical computations, the "numerical rank" may differ from theoretical rank due to floating-point errors. Small singular values are often treated as zero based on a tolerance threshold.

Theorem 4.50: Rank of Idempotent Matrix

If $P^2 = P$ (idempotent), then $\text{rank}(P) = \text{tr}(P)$ .

Proof:

Eigenvalues of $P$ are 0 or 1 only. Say $P$ has $r$ eigenvalues equal to 1.

Then $\text{rank}(P) = r$ and $\text{tr}(P) = 1 + 1 + \cdots + 1 = r$ .

∎

18. Computational Aspects

Complexity of Rank Computation

Method	Complexity	Notes
Gaussian Elimination	$O(mn \cdot \min(m,n))$	Standard method
SVD	$O(mn^2)$ for $m \geq n$	More numerically stable
QR Decomposition	$O(mn^2)$	Good stability
Rank-revealing LU	$O(mn \cdot r)$	$r$ = rank, efficient for low rank

Remark 4.29: Rank Determination in Practice

When computing rank numerically:

Use SVD and count singular values above a threshold
Threshold ≈ $\epsilon \cdot \|A\| \cdot \max(m,n)$ where $\epsilon$ is machine epsilon
Pivoting strategies in LU/QR help reveal numerical rank

Example 4.19: Numerical Rank

Consider $A = \begin{pmatrix} 1 & 2 \\ 1.00001 & 2.00001 \end{pmatrix}$

Theoretically rank = 2, but numerically the rows are nearly dependent.

SVD gives singular values ≈ 3.16 and 0.00001. With tolerance $10^{-4}$ , numerical rank = 1.

Remark 4.30: Low-Rank Approximation

The Eckart-Young theorem states that the best rank- $k$ approximation to $A$ (in Frobenius or spectral norm) is obtained by keeping only the top $k$ singular values in the SVD:

A_k = \sum_{i=1}^{k} \sigma_i u_i v_i^T

This is fundamental in data compression, noise reduction, and dimensionality reduction.

Theorem 4.51: Rank and Linear Independence

A set of $k$ vectors $\{v_1, \ldots, v_k\}$ in $F^n$ is linearly independent if and only if the matrix with these vectors as columns has rank $k$ .

Corollary 4.14: Maximum Independent Vectors

The maximum number of linearly independent vectors that can be chosen from the rows (or columns) of a matrix $A$ equals $\text{rank}(A)$ .

Remark 4.31: Summary: Multiple Views of Rank

Matrix rank can be understood from several equivalent perspectives:

Row space: Dimension of span of rows
Column space: Dimension of span of columns
Pivot count: Number of pivots in REF
Linear map: Dimension of image
Minors: Size of largest non-zero minor
SVD: Number of non-zero singular values

Key Takeaways

• Row rank = Column rank for any matrix
• rank(A) = # pivots in row echelon form
• rank + nullity = n (number of columns)
• Ax = b solvable iff rank(A) = rank([A|b])
• Unique solution iff rank(A) = n (full column rank)
• Sylvester inequality: rank(A) + rank(B) - n ≤ rank(AB) ≤ min(rank A, rank B)
• Full rank ⟺ invertible for square matrices

💡 Remember

Matrix rank is the unifying concept connecting row space, column space, solvability, and invertibility.

Rank determines: solvability of systems, invertibility, and dimension of null space.

rank(A) + nullity(A) = number of columns

What's Next?

Now that you understand matrix rank, you're ready for the next major topics:

Special Matrices: Diagonal, triangular, symmetric, orthogonal matrices with special properties
Determinants: A scalar invariant that detects invertibility
Eigenvalues: The values that reveal matrix structure
Diagonalization: Finding the simplest form of a matrix

Matrix Rank Practice

Questions

Correct

Accuracy

The rank of a matrix equals:

Easy

Not attempted

Row rank equals column rank:

Medium

Not attempted

For an

m \times n

matrix, rank is at most:

Easy

Not attempted

A square matrix is invertible iff its rank equals:

Easy

Not attempted

A

3 \times 5

with rank 2, then

\dim(\ker A) =

Medium

Not attempted

Row operations preserve:

Medium

Not attempted

\text{rank}(A^T) =

Easy

Not attempted

A

has full column rank, then

Ax = b

has:

Medium

Not attempted

A

has full row rank, then

Ax = b

has:

Medium

Not attempted

\text{rank}(AB) \leq

Hard

Not attempted

\text{rank}(A^T A)

equals:

Medium

Not attempted

P

is idempotent (

P^2=P

\text{rank}(P)

equals:

Hard

Not attempted

The rank of the zero matrix is:

Easy

Not attempted

A

has full column rank,

A^T A

is:

Medium

Not attempted

Sylvester's inequality gives a _____ bound on

\text{rank}(AB)

Medium

Not attempted

Matrix Rank

1. Definition of Matrix Rank

2. Proof of the Rank Theorem

3. Computing Rank

4. Rank and Invertibility

5. Rank and Linear Systems

6. Rank Inequalities

7. Equivalent Standard Form

8. Worked Examples

9. Common Mistakes

Mistake 1: Confusing Row and Column Space

Mistake 2: Rank of Sum

Mistake 3: Solvability Criterion

10. Key Takeaways

Row = Column

Count Pivots

Invertibility

Standard Form

11. Additional Practice Problems

12. Connections to Other Topics

13. Study Tips

Count Pivots

Check Both Ways

Use Upper Bounds

Think Linear Maps

14. Historical Notes

15. Quick Reference Summary

16. Applications of Rank

Data Compression (Low-Rank Approximation)

Control Theory

Statistics (Least Squares)

Recommender Systems

Computer Vision

Network Analysis

17. Advanced Topics

18. Computational Aspects

Complexity of Rank Computation

Key Takeaways

Related Topics

💡 Remember

What's Next?