Gram-Schmidt Orthogonalization

Gram-Schmidt Orthogonalization

Given a set of linearly independent vectors, Gram-Schmidt produces an orthonormal basis spanning the same subspace.

Algorithm

For vectors $\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n$:

1. $\mathbf{e}_1 = \mathbf{v}_1 / \|\mathbf{v}_1\|$
2. For each $\mathbf{v}_k$ ($k \geq 2$): subtract projections onto all previous basis vectors, then normalize:

$\mathbf{u}_k = \mathbf{v}_k - \sum_{j=1}^{k-1} (\mathbf{v}_k \cdot \mathbf{e}_j)\,\mathbf{e}_j$ $\mathbf{e}_k = \mathbf{u}_k / \|\mathbf{u}_k\|$

Example

$\mathbf{v}_1 = [1, 1]$, $\mathbf{v}_2 = [0, 1]$:

$\mathbf{e}_1 = \frac{1}{\sqrt{2}}[1, 1] \approx [0.7071, 0.7071]$

$\mathbf{u}_2 = [0,1] - \frac{1}{\sqrt{2}} \cdot \frac{1}{\sqrt{2}}[1,1] = [-0.5, 0.5]$

$\mathbf{e}_2 = \frac{1}{1/\sqrt{2}}[-0.5, 0.5] = [-0.7071, 0.7071]$

Verify: $\mathbf{e}_1 \cdot \mathbf{e}_2 = -0.5 + 0.5 = 0$ ✓

Connection to QR Decomposition

Gram-Schmidt is the algorithm behind QR decomposition: $A = QR$ where $Q$ has the orthonormal vectors as columns and $R$ is upper-triangular.

import math

def gram_schmidt(vecs):
    basis = []
    for v in vecs:
        u = v[:]
        for e in basis:
            proj = sum(v[i]*e[i] for i in range(len(v)))
            u = [u[i] - proj*e[i] for i in range(len(u))]
        norm = math.sqrt(sum(x**2 for x in u))
        basis.append([x/norm for x in u])
    return basis

Your Task

Implement gram_schmidt(vecs) that returns a list of orthonormal basis vectors.