determin.ant — Linear Algebra from Scratch

Where you'll see this: QR decomposition — used in numerical linear algebra, least squares solvers, and eigenvalue algorithms — is essentially Gram-Schmidt. Every time you call np.linalg.qr, Gram-Schmidt (or a numerically stable version) is running under the hood.

Given any set of linearly independent vectors, Gram-Schmidt produces an orthonormal basis — vectors that are all perpendicular to each other and all have length 1.

Why orthonormal bases are useful

An orthonormal basis is the coordinate system equivalent of a clean desk. Calculations become much simpler:

Coordinates are just dot products: $\alpha_i = \mathbf{v} \cdot \mathbf{e}_i$
Projections are trivial
The inverse of an orthogonal matrix is its transpose: $Q^{-1} = Q^T$

The algorithm

Given two vectors u and v:

Normalize u: $\mathbf{e}_1 = \mathbf{u}/|\mathbf{u}|$
Remove the e₁ component from v: $\mathbf{v}' = \mathbf{v} - (\mathbf{v} \cdot \mathbf{e}_1)\mathbf{e}_1$
Normalize the remainder: $\mathbf{e}_2 = \mathbf{v}'/|\mathbf{v}'|$

Now e₁ and e₂ are unit vectors and e₁ · e₂ = 0. They form an orthonormal basis for the same subspace that u and v spanned.

Step 2 is just projection: you're subtracting the projection of v onto e₁. What's left is automatically perpendicular to e₁.

In higher dimensions

The same process extends to n vectors: at each step, subtract projections onto all previously computed basis vectors, then normalize.

Try it

Drag the input vectors u and v (faint arrows). The solid arrows are the Gram-Schmidt output e₁ and e₂ — always perpendicular, always length 1 (shown scaled up for visibility). The yellow dashed line is the projection that gets subtracted in step 2.

QR decomposition = Gram-Schmidt:

import numpy as np
A = np.array([[3., 1.], [1., 3.]])

# Q has orthonormal columns (Gram-Schmidt result)
# R is upper triangular
Q, R = np.linalg.qr(A)

print(Q)                          # orthonormal columns
print(Q.T @ Q)                    # ≈ identity
print(np.allclose(Q @ R, A))      # True