Compute Orthonormal Basis for 2D Vectors

Problem

Compute an orthonormal basis for a set of 2D vectors using the Gram-Schmidt process. Given two linearly independent 2D vectors, produce two orthogonal unit vectors that span the same subspace.

Solution

import numpy as np

def gram_schmidt_2d(vectors: list[list[float]]) -> list[list[float]]:
    result = []

    for v in vectors:
        v = np.array(v, dtype=float)

        # Subtract projections onto all previous basis vectors
        for u in result:
            u = np.array(u)
            v = v - np.dot(v, u) * u

        # Normalize
        norm = np.linalg.norm(v)
        if norm < 1e-10:
            continue  # Skip linearly dependent vectors
        v = v / norm
        result.append(v.tolist())

    return [list(map(lambda x: round(x, 4), v)) for v in result]

Explanation

1. Gram-Schmidt process: Iteratively orthogonalize each vector against all previously computed basis vectors.
2. Projection removal: For each new vector v, subtract its projection onto each existing basis vector u: v = v - (v . u) * u. This makes v orthogonal to all previous vectors.
3. Normalization: Divide each orthogonalized vector by its norm to make it unit length.
4. Linear dependence: If a vector becomes near-zero after projection removal, it was linearly dependent on the previous vectors and is skipped.

Complexity

• Time: O(k^2 * d) where k is the number of vectors and d is the dimension
• Space: O(k * d) for storing the orthonormal basis