Gram-Schmidt Orthogonalization

Gram-Schmidt Orthogonalization

Given a set of linearly independent vectors, Gram-Schmidt produces an orthonormal basis — a set of vectors that are mutually perpendicular and each have unit length.

Algorithm

For each vector v in turn:

1. Subtract its projection onto every previously found basis vector
2. Normalize the result

$\mathbf{q}_{1} = \frac{\mathbf{v}_{1}}{\|\mathbf{v}_{1}\|}$

For $i = 2, 3, \ldots$:

$\mathbf{w}_{i} = \mathbf{v}_{i} - \sum_{j < i} (\mathbf{v}_{i} \cdot \mathbf{q}_{j})\, \mathbf{q}_{j}, \qquad \mathbf{q}_{i} = \frac{\mathbf{w}_{i}}{\|\mathbf{w}_{i}\|}$

Since each $\mathbf{q}_{j}$ is already normalized (length 1), the projection coefficient simplifies to just $\mathbf{v}_{i} \cdot \mathbf{q}_{j}$.

Example

Input vectors: [1,1,0], [1,0,1], [0,1,1]

Your Task

Implement gram_schmidt(vecs) that takes a list of linearly independent vectors and returns an orthonormal basis.