Linear Algebra: Gram-Schmidt Process

In many areas of engineering, physics, and data science, working with vectors becomes dramatically simpler when they are perpendicular and of unit length. The Gram-Schmidt process is the fundamental algorithm that transforms any set of linearly independent vectors into such a clean, organized basis. Mastering this process is not just an algebraic exercise; it unlocks efficient computations for everything from solving least-squares problems in control systems to compressing signals and performing Fourier analysis.

The Power of an Orthonormal Basis

Before constructing something, you must understand why it's valuable. An orthonormal basis for a vector space is a set of vectors that are all unit length (normalized) and mutually perpendicular (orthogonal). Formally, a set ${\mathbf{q}}_1,{\mathbf{q}}_2,...,{\mathbf{q}}_k$ is orthonormal if ${\mathbf{q}}_i\cdot {\mathbf{q}}_j=0$ for $i\ne j$ (orthogonality) and ${\mathbf{q}}_i\cdot {\mathbf{q}}_i=1$ for all $i$ (normality).

Why is this so powerful? Computations simplify immensely. Projecting a vector onto a subspace spanned by an orthonormal basis involves simple dot products, not messy matrix inversions. Coefficients in linear combinations are easily found. More abstractly, it provides the ideal coordinate system for a subspace, where geometry and algebra align perfectly. The Gram-Schmidt process is your tool for building this ideal system from any admissible starting point.

The Classical Gram-Schmidt Algorithm: Step-by-Step

The Gram-Schmidt algorithm takes a linearly independent set ${\mathbf{v}}_1,{\mathbf{v}}_2,...,{\mathbf{v}}_n$ and produces an orthonormal set ${\mathbf{q}}_1,{\mathbf{q}}_2,...,{\mathbf{q}}_n$ that spans the same subspace. The process works sequentially, ensuring each new ${\mathbf{q}}_k$ is orthogonal to all previously created ones.

Here is the algorithm in its classical form:

1. Start with the first vector: Simply normalize it.

$${\mathbf{u}}_1={\mathbf{v}}_1,{\mathbf{q}}_1=\frac{{\mathbf{u}}_1}{\Vert {\mathbf{u}}_1\Vert }$$ The notation $\Vert {\mathbf{u}}_1\Vert$ denotes the norm (length) of ${\mathbf{u}}_1$, calculated as $\sqrt{{\mathbf{u}}_1\cdot {\mathbf{u}}_1}$.

1. For each subsequent vector ${\mathbf{v}}_k$: Remove its projection onto the span of all previous orthonormal vectors.

$${\mathbf{u}}_k={\mathbf{v}}_k-{\text{proj}}_{\text{span}({\mathbf{q}}_1,...,{\mathbf{q}}_{k-1})}({\mathbf{v}}_k)$$ This subtraction step is the heart of the process. The projection of ${\mathbf{v}}_k$ onto the established subspace is the sum of its projections onto each individual ${\mathbf{q}}_i$: $${\mathbf{u}}_k={\mathbf{v}}_k-({\mathbf{v}}_k\cdot {\mathbf{q}}_1){\mathbf{q}}_1-({\mathbf{v}}_k\cdot {\mathbf{q}}_2){\mathbf{q}}_2-\cdots -({\mathbf{v}}_k\cdot {\mathbf{q}}_{k-1}){\mathbf{q}}_{k-1}$$ The vector ${\mathbf{u}}_k$ is now orthogonal to ${\mathbf{q}}_1,...,{\mathbf{q}}_{k-1}$.

1. Normalize the result: Finally, make ${\mathbf{u}}_k$ into a unit vector to complete the step.

$${\mathbf{q}}_k=\frac{{\mathbf{u}}_k}{\Vert {\mathbf{u}}_k\Vert }$$

You repeat step 2 for $k=2,3,...,n$. The set ${\mathbf{q}}_1,...,{\mathbf{q}}_n$ is your new orthonormal basis.

Worked Example in ${\mathbb{R}}^3$

Let ${\mathbf{v}}_1=[1,1,0{]}^T$, ${\mathbf{v}}_2=[1,0,1{]}^T$, ${\mathbf{v}}_3=[0,1,1{]}^T$.

• Step 1: ${\mathbf{u}}_1={\mathbf{v}}_1$, $\Vert {\mathbf{u}}_1\Vert =\sqrt{2}$, so ${\mathbf{q}}_1=[1/\sqrt{2},1/\sqrt{2},0{]}^T$.
• Step 2 for ${\mathbf{v}}_2$: Compute ${\mathbf{v}}_2\cdot {\mathbf{q}}_1=1/\sqrt{2}$. Then:

$${\mathbf{u}}_2=[1,0,1{]}^T-(1/\sqrt{2})[1/\sqrt{2},1/\sqrt{2},0{]}^T=[1/2,-1/2,1{]}^T$$ Normalize: $\Vert {\mathbf{u}}_2\Vert =\sqrt{3/2}$, so ${\mathbf{q}}_2=[1/\sqrt{6},-1/\sqrt{6},2/\sqrt{6}{]}^T$.

• Step 3 for ${\mathbf{v}}_3$: Compute ${\mathbf{v}}_3\cdot {\mathbf{q}}_1=1/\sqrt{2}$ and ${\mathbf{v}}_3\cdot {\mathbf{q}}_2=1/\sqrt{6}$. Then:

$${\mathbf{u}}_3=[0,1,1{]}^T-(1/\sqrt{2}){\mathbf{q}}_1-(1/\sqrt{6}){\mathbf{q}}_2=[-2/3,2/3,2/3{]}^T$$ Normalize: $\Vert {\mathbf{u}}_3\Vert =2/\sqrt{3}$, so ${\mathbf{q}}_3=[-1/\sqrt{3},1/\sqrt{3},1/\sqrt{3}{]}^T$.

Applying the Process to Function Spaces

The power of Gram-Schmidt extends far beyond geometric vectors. In engineering, you often work in spaces where the "vectors" are functions. Consider the space of polynomials of degree $\le 2$ on the interval $[-1,1]$, with an inner product defined as $⟨f,g⟩={\int }_{-1}^{1}f(x)g(x)dx$.

You can start with the linearly independent set $1,x,x^2$ and apply Gram-Schmidt to construct an orthonormal basis of polynomials.

1. Let $p_0(x)=1$. Its norm is $\sqrt{{\int }_{-1}^{1}1\cdot 1dx}=\sqrt{2}$. So $q_0(x)=1/\sqrt{2}$.
2. Take $v_1(x)=x$. Compute $⟨x,q_0⟩={\int }_{-1}^1(x)(1/\sqrt{2})dx=0$. So $u_1(x)=x-0\cdot q_0=x$. Its norm is $\sqrt{{\int }_{-1}^1{x}^{2}dx}=\sqrt{2/3}$. Thus, $q_1(x)=\sqrt{3/2}x$.
3. Take $v_2(x)=x^2$. Compute $⟨x^2,q_0⟩=\sqrt{2}/3$ and $⟨x^2,q_1⟩=0$. Then $u_2(x)=x^2-(\sqrt{2}/3)q_0=x^2-1/3$. Normalizing gives $q_2(x)=\sqrt{45/8}(x^2-1/3)$.

This exact process yields the Legendre polynomials (up to normalization), which are crucial for numerical integration and solving differential equations in spherical coordinates.

Numerical Stability and the Modified Gram-Schmidt

When implemented on a computer with finite precision, the classical Gram-Schmidt (CGS) algorithm described above suffers from numerical instability. Small rounding errors in the computation of projections can accumulate, causing the final vectors to lose orthogonality. The subtraction ${\mathbf{u}}_k={\mathbf{v}}_k-\sum ({\mathbf{v}}_k\cdot {\mathbf{q}}_i){\mathbf{q}}_i$ can lead to a catastrophic loss of significant digits if ${\mathbf{v}}_k$ is nearly parallel to the span of the previous vectors.

The solution is the modified Gram-Schmidt (MGS) algorithm. Mathematically, it is equivalent to CGS, but it organizes the calculations differently to dramatically improve stability. Instead of projecting ${\mathbf{v}}_k$ onto all previous ${\mathbf{q}}_i$ at once and then subtracting, MGS performs the subtraction sequentially.

Modified Gram-Schmidt Process:

1. Set ${\mathbf{u}}_1={\mathbf{v}}_1$, then ${\mathbf{q}}_1={\mathbf{u}}_1/\Vert {\mathbf{u}}_1\Vert$.
2. For $k=2,...,n$:

• Start with a working vector: ${\mathbf{u}}_k^{(1)}={\mathbf{v}}_k$.
• For $i=1$ to $k-1$:

$${\mathbf{u}}_k^{(i+1)}={\mathbf{u}}_k^{(i)}-({\mathbf{u}}_k^{(i)}\cdot {\mathbf{q}}_i){\mathbf{q}}_i$$

• After this loop, ${\mathbf{u}}_k^{(k)}$ is the orthogonal vector. Set ${\mathbf{q}}_k={\mathbf{u}}_k^{(k)}/\Vert {\mathbf{u}}_k^{(k)}\Vert$.

By orthogonalizing against each ${\mathbf{q}}_i$ one at a time and using the updated working vector, MGS ensures that the subtraction uses the best available approximation of the component left in the direction of ${\mathbf{q}}_i$. This subtle change makes it the preferred algorithm for serious numerical work, such as in the QR factorization used by computational software.

Common Pitfalls

1. Starting with a linearly dependent set: The Gram-Schmidt process requires linear independence. If your input vectors are linearly dependent, at some step you will get ${\mathbf{u}}_k=0$ (a zero vector), which cannot be normalized. This is not a failure of the algorithm but a signal that your original set did not form a basis. The solution is to simply discard that ${\mathbf{v}}_k$ and proceed with the next vector; the algorithm will produce an orthonormal basis for the span of the original set.
2. Confusing orthogonalization with normalization: These are two distinct steps. First, you subtract projections to make the vector orthogonal (the ${\mathbf{u}}_k$ step). Second, you scale it to unit length (the ${\mathbf{q}}_k$ step). Performing them out of order or skipping normalization will not yield an orthonormal basis.
3. Misapplying the projection formula: When computing the projection component $({\mathbf{v}}_k\cdot {\mathbf{q}}_i){\mathbf{q}}_i$, remember that the coefficient must be the dot product of ${\mathbf{v}}_k$ with the already normalized vector ${\mathbf{q}}_i$. Using a non-normalized vector here is a common algebraic mistake.
4. Ignoring numerical stability for computational tasks: For hand calculations or small, well-conditioned problems, classical Gram-Schmidt is fine. However, for any significant implementation in code, especially in engineering applications, you must default to using the Modified Gram-Schmidt algorithm to ensure reliable, accurate results.

Summary

• The Gram-Schmidt process is a systematic method for converting any set of linearly independent vectors into an orthonormal basis (mutually perpendicular unit vectors) for the same subspace.
• Its core operation is sequential projection subtraction: for each new vector, subtract away its components that lie in the direction of all previously orthonormalized vectors, then normalize the result.
• The algorithm's utility extends to abstract vector spaces like polynomial and function spaces, where it constructs orthogonal families of functions essential for approximation and signal analysis.
• For reliable computer implementation, the modified Gram-Schmidt algorithm is superior due to its improved numerical stability, which preserves orthogonality in the presence of rounding errors.
• Mastering this process is foundational because orthonormal bases simplify critical computations like finding projections, solving least-squares problems, and performing eigenvalue decompositions, which are ubiquitous in engineering and scientific computing.