Orthonormal basis (Gram-Schmidt)

Background

Gram-Schmidt turns any set of vectors into an orthonormal basis for the space they span — a set of mutually perpendicular unit vectors. Orthonormal bases make projections, least-squares, and QR factorization simple, and they underpin numerical stability throughout linear algebra.

Problem statement

Implement orthonormal_basis(vectors, tol) using the Gram-Schmidt process. Process the input vectors in order; for each $v$, subtract its projection onto every basis vector already collected, then normalise and keep it only if its remaining norm exceeds tol:

$$u = v - \sum_{b \,\in\, \text{basis}} (v \cdot b)\, b, \qquad \text{if } \lVert u\rVert > \text{tol}: \;\; \text{append } \frac{u}{\lVert u\rVert}$$

Input

• vectors — list[list[float]]: the input vectors (all the same dimension).
• tol — float (default 1e-10): a vector whose residual norm falls below this is treated as linearly dependent and dropped.

Output

Returns a list[np.ndarray]: an orthonormal basis for the span of the inputs (its length equals the rank).

Examples

Example 1

Input:  orthonormal_basis([[1, 0], [1, 1]])
Output: [array([1., 0.]), array([0., 1.])]

Explanation: $[1, 0]$ normalises to itself; for $[1, 1]$, subtract its projection $[1, 0]$ onto the first basis vector, leaving $[0, 1]$, which normalises to $[0, 1]$.

Constraints

• Subtract projections onto all previously accepted basis vectors before normalising (classical Gram-Schmidt).
• Drop any vector whose residual norm is $\le$ tol (linearly dependent).
• The returned vectors are mutually orthogonal and of unit length.

Notes

• The number of returned vectors equals the rank of the input set; dependent vectors collapse to near-zero residuals and are skipped.
• Classical Gram-Schmidt can lose orthogonality under floating-point error for ill-conditioned inputs; the modified Gram-Schmidt variant is more numerically stable.