Gram-Schmidt Process

Precise definition

Given independent vectors $v_1,\ldots,v_k$ in a real inner-product space, Gram–Schmidt constructs orthogonal vectors $u_1=v_1$ and $u_j=v_j-\sum_{i<j}\operatorname{proj}_{u_i}v_j$, where $\operatorname{proj}_{u}v=\langle v,u\rangle u/\langle u,u\rangle$. Normalizing $q_i=u_i/\|u_i\|$ gives an orthonormal basis.

Notation and mathematical language

Each $u_j$ lies in $\operatorname{span}(v_1,\ldots,v_j)$, and the first $j$ new vectors span the same subspace as the first $j$ originals. The input order changes the resulting orthogonal basis but not the final spanned subspace.

Conceptual picture

At each stage, subtract every component in directions already built. The residual is perpendicular to all earlier $u_i$. Orthogonality makes coordinates and projections independent one-dimensional calculations.

Conditions and key results

The input list must be independent for every residual to be nonzero. The displayed formulas use the real convention; in a complex inner-product space, conjugation must follow the chosen inner-product convention and matrix formulas use the conjugate transpose $Q^*$. In finite precision, classical Gram–Schmidt can lose orthogonality when vectors are nearly dependent; modified Gram–Schmidt or Householder QR is more stable.

A reliable strategy

1. Confirm the inner product and input independence, and retain the chosen order.
2. Set $u_1=v_1$; for each later vector subtract projections onto all previous $u_i$.
3. Check each residual is nonzero, then normalize only after orthogonalization if an orthonormal basis is required.
4. Verify pairwise inner products are zero and spans agree.

Fully worked example

Interpretation and application

Gram–Schmidt produces QR factorizations, least-squares coordinates, signal bases, and stable geometric decompositions. Orthogonality depends on the selected inner product, which may incorporate weights or units.

Common mistakes

Verification and reasonableness

• Compute every pairwise dot product in the output.
• Reconstruct each original vector from the generated span.
• For an orthonormal output, check every norm equals 1.

Practice

1. Project $(2,1)$ onto $(1,0)$.
2. What does a zero residual mean?
3. Does changing input order change the output basis?

Further deduction

For a matrix $A$ with independent columns, Gram–Schmidt yields $A=QR$, where columns of $Q$ are orthonormal and $R=Q^TA$ is upper triangular with nonzero diagonal. Then $A^TA=R^TR$, and least squares can be solved as $R\hat x=Q^Tb$ without forming $A^TA$, improving conditioning.

Orthogonalization depends on order, but the projector onto the final span does not. If two different orders produce orthonormal matrices $Q_1,Q_2$ spanning the same subspace, then $Q_1Q_1^T=Q_2Q_2^T$. This invariant projector provides a strong check even when the displayed basis vectors look different.

Related topics

• Orthogonality
• Least Squares
• Orthogonal Projection