← back

Find the column space of a matrix

#68 · Linear Algebra · Medium

⊣ Solve on deep-ml.com

Problem

Find the column space of a matrix. The column space is the set of all possible linear combinations of the column vectors, represented by the linearly independent columns. Return the basis vectors for the column 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
import numpy as np

def column_space(A):
    A = np.array(A, dtype=float)
    m, n = A.shape

    # Use row echelon form to find pivot columns
    mat = A.copy()
    pivot_cols = []
    row = 0

    for col in range(n):
        # Find pivot in current column
        max_row = row
        for r in range(row + 1, m):
            if abs(mat[r, col]) > abs(mat[max_row, col]):
                max_row = r

        if abs(mat[max_row, col]) < 1e-10:
            continue

        mat[[row, max_row]] = mat[[max_row, row]]
        pivot_cols.append(col)

        for r in range(row + 1, m):
            factor = mat[r, col] / mat[row, col]
            mat[r, col:] -= factor * mat[row, col:]

        row += 1

    # Return original columns at pivot positions
    basis = A[:, pivot_cols]
    return basis.tolist()

Explanation

  1. Perform Gaussian elimination (row echelon form) on the matrix to identify pivot columns.
  2. A pivot column is one that contains a leading 1 (or leading non-zero) after elimination.
  3. The corresponding columns from the original matrix form a basis for the column space.
  4. Partial pivoting is used for numerical stability.
  5. The number of pivot columns equals the rank of the matrix.

Complexity

  • Time: O(m n min(m, n)) for Gaussian elimination
  • Space: O(m * n) for the matrix copy
← #67#69 →