Gram–Schmidt

34. Gram–Schmidt

Given a linearly independent set ${{\vec{𝑣}}_{1}, {\vec{𝑣}}_{2}, \dots, {\vec{𝑣}}_{𝑘}}$ , the Gram–Schmidt process produces an orthonormal set ${{\vec{𝑞}}_{1}, {\vec{𝑞}}_{2}, \dots, {\vec{𝑞}}_{𝑘}}$ that spans the same subspace.

It “straightens out” the basis: removes the parallel components between successive vectors so they become mutually orthogonal, then normalizes each.

34.1. The algorithm

Process the input vectors one at a time. For each new vector, subtract off its projection onto the orthonormal vectors already built, then normalize.

For $𝑗 = 1, 2, \dots, 𝑘$ :

{\vec{𝑢}}_{𝑗} = {\vec{𝑣}}_{𝑗} - \sum_{𝑖 = 1}^{𝑗 - 1} ({\vec{𝑣}}_{𝑗} \cdot {\vec{𝑞}}_{𝑖}) {\vec{𝑞}}_{𝑖} (subtract projections off the already-orthonormal vectors)

{\vec{𝑞}}_{𝑗} = \frac{{\vec{𝑢}}_{𝑗}}{‖} {\vec{𝑢}}_{𝑗} ‖ (normalize)

The first step is just normalization: ${\vec{𝑞}}_{1} = \frac{{\vec{𝑣}}_{1}}{‖} {\vec{𝑣}}_{1} ‖$ .

Example

${\vec{𝑣}}_{1} = [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}]$ , ${\vec{𝑣}}_{2} = [\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}]$ in $ℝ^{3}$ .

Step 1: ${\vec{𝑞}}_{1} = \frac{{\vec{𝑣}}_{1}}{‖} {\vec{𝑣}}_{1} ‖ = \frac{1}{\sqrt{2}} [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}]$ .

Step 2: project ${\vec{𝑣}}_{2}$ onto ${\vec{𝑞}}_{1}$ and subtract:

{\vec{𝑣}}_{2} \cdot {\vec{𝑞}}_{1} = \frac{1}{\sqrt{2}}

{\vec{𝑢}}_{2} = {\vec{𝑣}}_{2} - \frac{1}{\sqrt{2}} {\vec{𝑞}}_{1} = [\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}] - \frac{1}{2} [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}] = [\begin{matrix} - \frac{1}{2} \\ \frac{1}{2} \\ 1 \end{matrix}]

Normalize: $‖ {\vec{𝑢}}_{2} ‖ = \sqrt{\frac{1}{4} + \frac{1}{4} + 1} = \sqrt{\frac{3}{2}}$ .

{\vec{𝑞}}_{2} = \sqrt{\frac{2}{3}} [\begin{matrix} - \frac{1}{2} \\ \frac{1}{2} \\ 1 \end{matrix}] = \frac{1}{\sqrt{6}} [\begin{matrix} - 1 \\ 1 \\ 2 \end{matrix}]

Verify: ${\vec{𝑞}}_{1} \cdot {\vec{𝑞}}_{2} = 0 ✓$ and $‖ {\vec{𝑞}}_{1} ‖ = ‖ {\vec{𝑞}}_{2} ‖ = 1 ✓$ .

34.2. Why it works

After subtracting the projections, ${\vec{𝑢}}_{𝑗}$ is orthogonal to every previously-built ${\vec{𝑞}}_{𝑖}$ . Inductively, after step $𝑗$ , the set ${{\vec{𝑞}}_{1}, \dots, {\vec{𝑞}}_{𝑗}}$ is orthonormal and spans the same subspace as ${{\vec{𝑣}}_{1}, \dots, {\vec{𝑣}}_{𝑗}}$ .

34.3. Numerical instability

Classical Gram–Schmidt (the version above) is unstable in floating point — small rounding errors compound, and the computed ${\vec{𝑞}}_{𝑗}$ ’s drift away from being truly orthogonal.

Better alternatives:

Modified Gram–Schmidt — subtract projections one at a time as you go, instead of all at once; much more stable
Householder reflections — used to compute QR in practice
Givens rotations — for sparse / structured input

For pencil-and-paper or symbolic use, classical Gram–Schmidt is fine. For numerical libraries, Householder is standard.

34.4. Connection to QR

The Gram–Schmidt process is exactly the construction behind the QR decomposition: the orthonormal vectors form $𝑄$ , and the projection coefficients form $𝑅$ .

34. Gram–Schmidt

34.1. The algorithm

34.2. Why it works

34.3. Numerical instability

34.4. Connection to QR

34.5. See also