← back

Compute the Null Space (Kernel) of a Matrix

#330 · Linear Algebra · Medium

⊣ Solve on deep-ml.com

Problem

Compute the null space (kernel) of a matrix A. The null space is the set of all vectors x such that Ax = 0. Return a basis for the null space.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from typing import List

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

    m = len(matrix)
    n = len(matrix[0])
    # Augmented copy for RREF
    mat = [row[:] for row in matrix]

    pivot_cols = []
    row_idx = 0

    for col in range(n):
        # Find pivot
        pivot = -1
        for r in range(row_idx, m):
            if abs(mat[r][col]) > tol:
                pivot = r
                break
        if pivot == -1:
            continue

        mat[row_idx], mat[pivot] = mat[pivot], mat[row_idx]

        # Scale pivot row
        scale = mat[row_idx][col]
        for j in range(n):
            mat[row_idx][j] /= scale

        # Eliminate all other rows
        for r in range(m):
            if r != row_idx and abs(mat[r][col]) > tol:
                factor = mat[r][col]
                for j in range(n):
                    mat[r][j] -= factor * mat[row_idx][j]

        pivot_cols.append(col)
        row_idx += 1

    # Free variables are non-pivot columns
    free_cols = [c for c in range(n) if c not in pivot_cols]
    basis = []

    for fc in free_cols:
        vec = [0.0] * n
        vec[fc] = 1.0
        for i, pc in enumerate(pivot_cols):
            vec[pc] = -mat[i][fc]
        basis.append(vec)

    return basis

Explanation

  1. Reduce the matrix to reduced row echelon form (RREF) using Gaussian elimination with full pivoting.
  2. Identify pivot columns and free (non-pivot) columns. Each free column contributes one basis vector to the null space.
  3. For each free variable, set it to 1 and all other free variables to 0, then read off the pivot variable values from the RREF rows (negated).
  4. The resulting set of vectors forms a basis for the null space.

Complexity

  • Time: O(m n min(m, n)) for RREF computation
  • Space: O(m n + n f) where f is the number of free variables
← #329#331 →