Gram–Schmidt Orthogonalization

What Gram–Schmidt does

Given a list of linearly independent vectors $\{\mathbf{v}_1, \ldots, \mathbf{v}_k\}$, the Gram–Schmidt process produces an orthogonal list $\{\mathbf{u}_1, \ldots, \mathbf{u}_k\}$ spanning the same subspace. Dividing each $\mathbf{u}_i$ by its length gives an orthonormal basis $\{\mathbf{q}_1, \ldots, \mathbf{q}_k\}$.

The formulas

$\mathbf{u}_1 = \mathbf{v}_1$ $\mathbf{u}_k = \mathbf{v}_k - \sum_{i=1}^{k-1} \dfrac{\mathbf{v}_k \cdot \mathbf{u}_i}{\mathbf{u}_i \cdot \mathbf{u}_i} \, \mathbf{u}_i$

The formula subtracts the projection of $\mathbf{v}_k$ onto every previously-computed $\mathbf{u}_i$. What's left is orthogonal to all of them.

Normalize: $\mathbf{q}_i = \mathbf{u}_i / \|\mathbf{u}_i\|$.

Step-by-step

$\mathbf{v}_1 = (1, 1, 0), \quad \mathbf{v}_2 = (1, 0, 1)$.

Step 1 — $\mathbf{u}_1 = \mathbf{v}_1 = (1, 1, 0)$.

Length: $\|\mathbf{u}_1\| = \sqrt{1 + 1 + 0} = \sqrt{2}$.

Step 2 — Project $\mathbf{v}_2$ onto $\mathbf{u}_1$. $\mathbf{v}_2 \cdot \mathbf{u}_1 = (1)(1) + (0)(1) + (1)(0) = 1$ $\mathbf{u}_1 \cdot \mathbf{u}_1 = 2$

Projection coefficient: $1/2$.

Projection vector: $\dfrac{1}{2} (1, 1, 0) = (\tfrac{1}{2}, \tfrac{1}{2}, 0)$.

Step 3 — Subtract to get $\mathbf{u}_2$. $\mathbf{u}_2 = \mathbf{v}_2 - \text{proj} = (1, 0, 1) - (\tfrac{1}{2}, \tfrac{1}{2}, 0) = (\tfrac{1}{2}, -\tfrac{1}{2}, 1)$

Check orthogonality: $\mathbf{u}_2 \cdot \mathbf{u}_1 = (\tfrac{1}{2})(1) + (-\tfrac{1}{2})(1) + (1)(0) = \tfrac{1}{2} - \tfrac{1}{2} + 0 = 0$ ✓

Step 4 — Normalize. $\|\mathbf{u}_2\| = \sqrt{\tfrac{1}{4} + \tfrac{1}{4} + 1} = \sqrt{\tfrac{3}{2}} = \dfrac{\sqrt{6}}{2}$

$\mathbf{q}_1 = \dfrac{\mathbf{u}_1}{\|\mathbf{u}_1\|} = \dfrac{1}{\sqrt{2}} (1, 1, 0) = \left(\tfrac{\sqrt{2}}{2}, \tfrac{\sqrt{2}}{2}, 0\right)$

$\mathbf{q}_2 = \dfrac{\mathbf{u}_2}{\|\mathbf{u}_2\|} = \dfrac{2}{\sqrt{6}} \left(\tfrac{1}{2}, -\tfrac{1}{2}, 1\right) = \left(\tfrac{\sqrt{6}}{6}, -\tfrac{\sqrt{6}}{6}, \tfrac{\sqrt{6}}{3}\right)$

Verification

• $\|\mathbf{q}_1\|^2 = 1/2 + 1/2 + 0 = 1$ ✓
• $\|\mathbf{q}_2\|^2 = 1/6 + 1/6 + 4/6 = 1$ ✓
• $\mathbf{q}_1 \cdot \mathbf{q}_2 = \tfrac{\sqrt{12}}{12} - \tfrac{\sqrt{12}}{12} + 0 = 0$ ✓

Why Gram–Schmidt matters

• QR decomposition: any full-column-rank matrix $A$ factors as $A = QR$ where $Q$'s columns are the Gram–Schmidt orthonormalization of $A$'s columns and $R$ is upper triangular.
• Least squares: QR makes least-squares problems numerically stable.
• Orthonormal bases: critical for projections, coordinate changes, and Fourier-like expansions.
• Numerical linear algebra: modified Gram–Schmidt (a slight variation) is used inside many iterative solvers.

Geometric picture

Each step builds the next vector by removing any component of the new vector that's already covered by earlier ones. You end up with vectors that span the same subspace but form a set of perpendicular "axes" — the natural coordinate system for that subspace.

The modified Gram–Schmidt (stability note)

The formulas above are "classical" Gram–Schmidt. In finite-precision arithmetic, it can lose orthogonality fast. The modified Gram–Schmidt subtracts projections one at a time during each step, which is more numerically stable and what most libraries actually implement.

Common mistakes

• Normalizing before subtracting projections. You need the unnormalized $\mathbf{u}_i$ inside the projection formula. Normalize only at the end (or after each step if you also divide by $\mathbf{q}_i \cdot \mathbf{q}_i = 1$, which simplifies).
• Using the original $\mathbf{v}_i$ in later projections instead of the new $\mathbf{u}_i$. Classical Gram–Schmidt uses the $\mathbf{u}$'s; that's essential.
• Applying to linearly dependent vectors. If a $\mathbf{v}_k$ is a combination of earlier vectors, you'll get $\mathbf{u}_k = \mathbf{0}$ (the projection covers everything).

Try it in the visualization

Two input vectors are drawn in 3D. The first stays put; the second shrinks down to its component orthogonal to the first as the projection is subtracted. Both are then normalized to unit length, ending with perpendicular blue arrows of equal length.