Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 62 · Vector Spaces

Rank

Understand matrix rank as the number of independent directions, use the rank-nullity theorem, and learn why np.linalg.matrix_rank needs a tolerance.

The rank of a matrix is the number of independent directions in it. A 5 x 5 matrix whose rows are all multiples of one row has rank 1, however large it looks. A 5 x 5 matrix with no redundancy has rank 5. Rank is one of the most informative single numbers about a matrix: it tells you whether a system can be solved, whether a matrix can be inverted, and how much information a data table really holds.

You have already met rank twice, as the count of pivots and as the dimension of the column space. This lesson pulls those threads together, states the rank-nullity theorem, and shows why computing rank on a computer is always a judgment call.

Rank in one sentence

Independent columns The most columns you can pick with no redundancy.
Independent rows Always the same number as independent columns.
Pivots One pivot per independent direction after elimination.

Three descriptions, one number.

1 / 2

Definition

The rank of a matrix A is the dimension of its column space. Equivalent descriptions:

  • the number of pivots in an echelon form of A,
  • the maximum number of linearly independent columns,
  • the maximum number of linearly independent rows.

The last two are the same number, which is surprising at first glance: rank(A) = rank(A^T). You saw both dimensions equal to 2 for the same matrix in the previous lesson, and it is always so.

For an m x n matrix, the rank is at most min(m, n). If it reaches that maximum, the matrix has full rank. A square matrix is invertible exactly when it has full rank. A matrix with lower rank is rank deficient.

Python Computing rank with NumPy

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second row of A is twice the first, so the rank is 2, not 3. Its transpose has the same rank. A random integer matrix almost always has full rank, which is why redundancy usually comes from structure in the problem (a duplicated measurement, a formula that combines other columns), not from bad luck.

The rank-nullity theorem

The most useful statement about rank links it to the null space. For any m x n matrix A:

rank(A) + nullity(A) = n

where nullity(A) is the dimension of the null space and n is the number of columns. Every column is either a pivot column (an independent direction that adds to the rank) or a free column (a free variable that adds to the nullity). Pivot columns plus free columns equals all columns.

The consequences are practical.

  • If n > m, there are more unknowns than equations, so the rank is at most m and the nullity is at least n - m > 0. A system A x = b with more unknowns than equations never has a unique solution.
  • A square matrix is invertible exactly when its nullity is 0, which happens when the rank is n.
  • If the nullity is zero, A is one-to-one: different inputs give different outputs.

Two further rules help when you reason about products and sums:

  • rank(A B) <= min(rank(A), rank(B)): multiplying cannot create new independent directions.
  • rank(A + B) <= rank(A) + rank(B).

A matrix built as a product U V with U of shape m x k and V of shape k x n therefore has rank at most k, no matter how large m and n are. Low-rank matrices like this appear everywhere in data science, and they are the subject of Low-Rank Approximation and Image Compression.

Python A product has rank at most the inner size

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The 6 x 5 matrix A has 30 entries, but it is built from two columns and two rows, so its rank is 2. Multiplying by another matrix cannot raise it. Look at the singular values (a preview of the Singular Value Decomposition): two are sizeable and three are around 1e-16, which is rounding noise rather than real signal. Counting the values above a small threshold is exactly how NumPy computes rank.

Rank on a computer is numerical

On paper, a number is zero or it is not. In floating point, rounding errors leave tiny leftovers where an exact zero should be. So np.linalg.matrix_rank does not look for exact zeros. It computes the singular values of the matrix and counts those larger than a tolerance. The default tolerance is

S.max() * max(M, N) * eps

where eps is the machine epsilon of the data type (about 2.2e-16 for float64), which is the quantity printed in the example above.

This is usually the right call, but it has consequences:

  • A matrix that is rank deficient in theory can show up as full rank if rounding noise lifts a zero singular value above the tolerance.
  • A matrix that is technically full rank but extremely close to rank deficient can show up as deficient.
  • You can pass your own tol when you know the scale of your data or noise.
Python Numerical rank depends on the tolerance

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The matrix B has rank 1, but a nudge of size 1e-12 makes the second singular value about 8e-13. With the default tolerance, which is near 1e-15 here, that value counts, so the rank jumps to 2. A tolerance of 1e-6 says "treat anything below a millionth as zero" and gets 1 back. Neither answer is wrong: the question "is this really rank 1?" depends on how much noise your data carries.

The last example is the Hilbert matrix, a classic in numerical analysis. Mathematically a 12 x 12 Hilbert matrix is invertible, so its rank is 12. Numerically NumPy reports 11, because its smallest singular values drop below the tolerance. Matrices like this are called ill-conditioned, a topic that returns in Numerical Linear Algebra Pitfalls.

Do not compare a computed rank against a hand calculation without thinking about noise. For data from measurements, choose a tolerance from the noise level, and inspect the singular values to see whether there is a clear gap between "signal" and "noise".

Why the rank-nullity theorem is true

The pivot-column argument above is enough for matrices, but the proof for linear maps is short and instructive. Let A be m × n, and let v₁, ..., v_k be a basis of the null space, so k = nullity(A).

  1. Extend the basis. Any independent set in R^n can be extended to a basis of R^n. Add vectors w₁, ..., w_r so that v₁, ..., v_k, w₁, ..., w_r is a basis of R^n. Then k + r = n.
  2. The images of the w's span the column space. Every x in R^n is Σ aᵢvᵢ + Σ bⱼwⱼ. Applying A kills the v terms (they are in the null space), so Ax = Σ bⱼ A wⱼ. Hence the column space, the set of all Ax, is spanned by A w₁, ..., A w_r.
  3. The images are independent. Suppose Σ bⱼ A wⱼ = 0. Then A(Σ bⱼwⱼ) = 0, so Σ bⱼwⱼ lies in the null space and equals Σ cᵢvᵢ for some cᵢ. Rearranged, that is a linear combination of the whole basis of R^n equal to zero, which forces every bⱼ (and cᵢ) to be 0.
  4. So A w₁, ..., A w_r is a basis of the column space: rank(A) = r = n - k. ∎

The proof shows what the theorem means: the null space is the part of the input that A crushes to zero, and everything that survives is exactly the rank. Input dimension = dimension crushed + dimension that survives. It holds for any linear transformation between finite-dimensional spaces, with "kernel" for the null space and "image" for the column space.

Consequences worth remembering

  • Injective versus surjective for square maps: if m = n, then A is one-to-one (nullity = 0) exactly when rank = n, which is exactly when it is onto. For non-square matrices you can have one without the other.
  • A wide matrix (n > m) always has a nontrivial null space, since rank ≤ m < n.
  • rank(AᵀA) = rank(A): AᵀAx = 0 implies xᵀAᵀAx = ‖Ax‖² = 0, so Ax = 0. The two matrices have the same null space and the same number of columns, so the theorem gives equal ranks. That is why the normal equations in least squares are solvable whenever A has independent columns.
  • Dimension counting: the solutions of Ax = b, when they exist, form a "flat" of dimension nullity(A).
Python Following the proof numerically

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why rank matters

  • Solving A x = b: a solution exists exactly when rank(A) = rank([A | b]). It is unique when the rank equals the number of columns.
  • Invertibility: a square matrix is invertible exactly when its rank is n.
  • Data: the rank of a data matrix is the number of truly independent features. A column that is a sum of others adds nothing.
  • Compression: a matrix of rank k can be stored with far fewer numbers than its entries.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A 4 by 6 matrix has rank 3. What is its nullity?

    Rank-nullity says rank + nullity = number of columns. With 6 columns and rank 3, the nullity is 3.
  2. 2. What is the largest possible rank of a 5 by 8 matrix?

    The rank cannot exceed the number of rows or the number of columns, so it is at most min(5, 8) = 5.
  3. 3. A is 100 by 3 and B is 3 by 100. What can you say about the rank of A B, a 100 by 100 matrix?

    rank(A B) is at most min(rank(A), rank(B)), and both are at most 3. It could be lower than 3, so only the upper bound is guaranteed.
  4. 4. Why can np.linalg.matrix_rank report rank 2 for a matrix that is exactly rank 1 on paper?

    matrix_rank counts singular values above a tolerance. Small rounding or measurement errors can leave a value that should be zero just above it.

Summary

  • Rank is the dimension of the column space: the number of pivots, independent columns or independent rows.
  • rank(A) = rank(A^T), and rank(A) <= min(m, n); equality means full rank.
  • Rank-nullity: rank + nullity = number of columns.
  • rank(A B) <= min(rank(A), rank(B)), so a product U V with inner size k has rank at most k.
  • np.linalg.matrix_rank counts singular values above a tolerance, so near-singular matrices can be misclassified; pass tol when you know the noise scale.

Now put these ideas to work by studying matrices as functions in Linear Transformations.