The Gram-Schmidt Process and QR Factorization

An orthogonal basis makes coordinates and projections trivial, but a subspace usually arrives with an arbitrary basis instead. The Gram–Schmidt process converts one into the other: given any basis for a subspace, it produces an orthogonal basis for the same subspace, one vector at a time. Recording the arithmetic as a matrix product yields the QR factorization, the numerically preferred route to least-squares solutions and eigenvalues.

Subtracting the projection

Start with a basis ${x_{1}, \dots, x_{p}}$ of a subspace $W$ . Keep the first vector, $v_{1} = x_{1}$ . To make the second vector orthogonal to the first, subtract from $x_{2}$ its projection onto the line $W_{1} = Span {v_{1}}$ :

v_{2} = x_{2} - proj_{W_{1}} x_{2} = x_{2} - \frac{x _{2} \cdot v _{1}}{v _{1} \cdot v _{1}} v_{1} .

By the orthogonal decomposition theorem, $v_{2}$ is the component of $x_{2}$ orthogonal to $v_{1}$ , and it stays in $W$ because it is a combination of $x_{2}$ and $x_{1}$ . Each later vector subtracts its projection onto the span of all the orthogonal vectors already built.

One Gram-Schmidt step in R^3: v2 is x2 minus its projection p onto the line through x1, leaving the part of x2 perpendicular to x1 while staying in the plane W.

The general process

The span condition is the point of the construction: the orthogonal set built from the first $k$ inputs spans exactly the same subspace $W_{k}$ as those inputs. The proof is induction. Suppose ${v_{1}, \dots, v_{k}}$ is an orthogonal basis for $W_{k} = Span {x_{1}, \dots, x_{k}}$ . Define $v_{k + 1} = x_{k + 1} - proj_{W_{k}} x_{k + 1}$ . By the orthogonal decomposition theorem it is orthogonal to $W_{k}$ ; it lies in $W_{k + 1}$ ; and it is nonzero because $x_{k + 1}$ is not in $W_{k}$ . So ${v_{1}, \dots, v_{k + 1}}$ is an orthogonal basis of the $(k + 1)$ -dimensional space $W_{k + 1}$ .

Gram-Schmidt builds a nested chain of subspaces: v1 spans a line, v2 completes the plane W2, and v3 rises out of it, each new vector orthogonal to every one already built.

Algorithm:

\textsc{Gram-Schmidt}(\mathbf{x}_1, \dots, \mathbf{x}_p)

— orthogonal basis for the span

1
$\mathbf{v}_1 \gets \mathbf{x}_1$
2
for $k = 2$ to $p$ do
3
$\mathbf{v}_k \gets \mathbf{x}_k$
4
for $j = 1$ to $k-1$ do
5
$\mathbf{v}_k \gets \mathbf{v}_k - \dfrac{\mathbf{x}_k \cdot \mathbf{v}_j}{\mathbf{v}_j \cdot \mathbf{v}_j}\, \mathbf{v}_j$
remove the component along $\mathbf{v}_j$
6
return $\{\mathbf{v}_1, \dots, \mathbf{v}_p\}$

An orthonormal basis follows by normalizing each $v_{k}$ at the end. Doing so only after the orthogonal set is complete avoids writing square roots at every step of a hand calculation.

Orthogonalizing a basis

The QR factorization

Apply Gram–Schmidt with normalization to the columns of a matrix. Each original column $x_{k}$ lies in $Span {u_{1}, \dots, u_{k}}$ , so it is a combination of the first $k$ orthonormal vectors only. Collecting those combinations as columns records the factorization.

Let $Q = [u_{1} \dots u_{n}]$ be the orthonormal basis from Gram–Schmidt. Because $x_{k} \in Span {u_{1}, \dots, u_{k}}$ , there are scalars with

x_{k} = r_{1 k} u_{1} + \dots + r_{k k} u_{k} + 0 u_{k + 1} + \dots + 0 u_{n},

and the entries below the diagonal are zero, making $R = [r_{j k}]$ upper triangular. Choosing $r_{k k} \geq 0$ (flip the sign of $u_{k}$ if needed) makes the diagonal positive. Then $x_{k} = Q r_{k}$ for each $k$ , so $A = QR$ .

A = QR splits an m-by-n matrix with independent columns into an orthonormal Q of the same shape and a small upper-triangular R; the shaded lower part of R is all zeros.

Once $Q$ is known, $R$ is a single product. Since $Q^{⊤} Q = I$ ,

Q^{⊤} A = Q^{⊤} (QR) = R,

so $R = Q^{⊤} A$ .

Numerical stability of QR

The invertibility of $R$ is immediate: if $R x = 0$ , then $A x = QR x = 0$ , and the independent columns of $A$ force $x = 0$ . So $R^{- 1}$ exists, and $A$ and $Q$ share the same column space.

In floating point, the classical Gram–Schmidt recurrence loses orthogonality: rounding makes the computed $u_{j}$ drift out of perpendicularity as $j$ grows. Reordering the subtractions (the modified Gram–Schmidt variant) helps, but production QR routines instead left-multiply $A$ by a sequence of orthogonal reflectors until it becomes upper triangular. That approach parallels the elementary-matrix reduction behind the LU factorization and yields a more accurate $Q$ ; the details belong to the numerical least-squares lesson.

In floating point the classical Gram-Schmidt recurrence loses orthogonality as the step index grows, while the reordered (modified) variant stays far closer to orthonormal.

Method	Output	Cost	Numerical behavior
Classical Gram–Schmidt	${v_{k}}$ then normalize	low	orthogonality degrades for large $j$
Modified Gram–Schmidt	same, reordered updates	low	markedly better, still imperfect
Reflector-based QR	$A = QR$	about twice	most accurate $Q$

Summary

Gram–Schmidt converts a basis into an orthogonal basis by subtracting, from each vector, its projection onto the span of the vectors already orthogonalized, preserving the span at every step.
Normalization at the end gives an orthonormal basis, the columns of $Q$ .
QR factorization $A = QR$ records the process as a matrix product: $Q$ has orthonormal columns spanning $Col A$ , and $R = Q^{⊤} A$ is upper triangular and invertible.

The QR factorization gives a stable route to the least-squares solution $\hat{x} = R^{- 1} Q^{⊤} b$ of an inconsistent system.¹

Lay, §6.4 — The Gram–Schmidt Process: Theorem 11 (orthogonalization with the span property), the orthonormal variant, and Theorem 12 (the QR factorization $A = QR$ with $R = Q^{⊤} A$ ), including the numerical notes on loss of orthogonality. ↩