Matrix Rank

#329 · Linear Algebra · Medium

Problem

Compute the rank of a matrix. The rank is the number of linearly independent rows (or equivalently columns), which equals the number of non-zero rows after row echelon reduction.

Solution

from typing import List

def matrix_rank(matrix: List[List[float]], tol: float = 1e-9) -> int:
    if not matrix or not matrix[0]:
        return 0

    # Work on a copy
    m = len(matrix)
    n = len(matrix[0])
    mat = [row[:] for row in matrix]

    rank = 0
    for col in range(n):
        # Find pivot row
        pivot = -1
        for row in range(rank, m):
            if abs(mat[row][col]) > tol:
                if pivot == -1 or abs(mat[row][col]) > abs(mat[pivot][col]):
                    pivot = row
                break

        if pivot == -1:
            continue

        # Swap pivot row into position
        mat[rank], mat[pivot] = mat[pivot], mat[rank]

        # Eliminate below
        for row in range(rank + 1, m):
            if abs(mat[row][col]) > tol:
                factor = mat[row][col] / mat[rank][col]
                for j in range(col, n):
                    mat[row][j] -= factor * mat[rank][j]

        rank += 1

    return rank

Explanation

Perform Gaussian elimination to reduce the matrix to row echelon form.
For each column, find the best pivot (first non-zero entry below the current rank row).
Swap the pivot row into position and eliminate all entries below it in that column.
Each successful pivot increases the rank by 1. The final rank equals the number of non-zero rows.

Complexity

Time: O(m n min(m, n)) for Gaussian elimination
Space: O(m * n) for the matrix copy

← #328 #330 →