Gram-Schmidt Orthogonalization Calculator

What is the Gram-Schmidt Process?

The Gram-Schmidt process is a fundamental algorithm in linear algebra that takes a finite set of linearly independent vectors and produces an orthonormal set of vectors spanning the same subspace. Named after Jørgen Pedersen Gram and Erhard Schmidt, it is one of the most important constructive procedures in mathematics, providing both a theoretical proof that every finite-dimensional inner product space has an orthonormal basis and a practical algorithm for computing one.

Given vectors {v₁, v₂, …, v_n} in an inner product space, the Gram-Schmidt process produces orthonormal vectors {e₁, e₂, …, e_n} such that for every k, the span of {e₁, …, e_k} equals the span of {v₁, …, v_k}. This incremental spanning property is what makes Gram-Schmidt so useful: the first k orthonormal vectors always span the same subspace as the first k original vectors.

Step-by-Step Algorithm

The Gram-Schmidt process operates in three conceptual stages for each vector: projection, subtraction, and normalization. Here is the complete algorithm:

1. Initialize — Take the first vector v₁. Compute u₁ = v₁, then normalize it to obtain the first orthonormal vector: e₁ = u₁ / ‖u₁‖.
2. Compute projections — For each subsequent vector v_k (k = 2, 3, …, n), calculate its projection onto each previously computed orthonormal vector: proj_ej(v_k) = ⟨v_k, e_j⟩ e_j for j = 1, 2, …, k−1.
3. Subtract projections — Remove all these projection components from v_k to get the orthogonal residual: u_k = v_k − ∑_j=1^k-1 ⟨v_k, e_j⟩ e_j.
4. Normalize — Divide by the norm to obtain the next orthonormal vector: e_k = u_k / ‖u_k‖.
5. Repeat — Continue until all n vectors have been processed.

The key insight is that at each step, subtracting the projections removes exactly the components of v_k that lie in the subspace spanned by the previously computed orthonormal vectors. What remains — the vector u_k — is orthogonal to all of them by construction.

Worked Example with Three Vectors

Let us orthogonalize the vectors v₁ = (1, 1, 0), v₂ = (1, 0, 1), and v₃ = (0, 1, 1) using the Gram-Schmidt process.

Step 1: Process v₁

Set u₁ = v₁ = (1, 1, 0). Compute the norm: ‖u₁‖ = √(1² + 1² + 0²) = √2. Normalize: e₁ = (1/√2, 1/√2, 0).

Step 2: Process v₂

Compute the projection of v₂ onto e₁: ⟨v₂, e₁⟩ = (1)(1/√2) + (0)(1/√2) + (1)(0) = 1/√2. Subtract: u₂ = v₂ − (1/√2) e₁ = (1, 0, 1) − (1/2, 1/2, 0) = (1/2, −1/2, 1). Compute the norm: ‖u₂‖ = √(1/4 + 1/4 + 1) = √(3/2). Normalize: e₂ = (1/√6, −1/√6, 2/√6).

Step 3: Process v₃

Compute projections: ⟨v₃, e₁⟩ = (0)(1/√2) + (1)(1/√2) + (1)(0) = 1/√2 and ⟨v₃, e₂⟩ = (0)(1/√6) + (1)(−1/√6) + (1)(2/√6) = 1/√6. Subtract both projections: u₃ = v₃ − (1/√2) e₁ − (1/√6) e₂ = (0, 1, 1) − (1/2, 1/2, 0) − (1/6, −1/6, 2/6) = (−2/3, 2/3, 2/3). Compute the norm: ‖u₃‖ = √(4/9 + 4/9 + 4/9) = 2/√3. Normalize: e₃ = (−1/√3, 1/√3, 1/√3).

The resulting orthonormal set {e₁, e₂, e₃} forms a basis for R³. You can verify orthonormality by checking that ⟨e_i, e_j⟩ = 0 for i ≠ j and ‖e_i‖ = 1 for all i.

Classical vs. Modified Gram-Schmidt

The algorithm described above is the classical Gram-Schmidt (CGS) process. While mathematically correct, it suffers from numerical instability in floating-point arithmetic. When the input vectors are nearly linearly dependent, rounding errors accumulate and the computed vectors can lose orthogonality dramatically.

The modified Gram-Schmidt (MGS) process addresses this by changing the order of operations. Instead of computing all projections of v_k against the original orthonormal vectors at once, MGS updates v_k sequentially:

1. Set u_k⁽⁰⁾ = v_k.
2. For j = 1, 2, …, k−1: compute u_k^(j) = u_k^(j-1) − ⟨u_k^(j-1), e_j⟩ e_j.
3. Set u_k = u_k^(k-1) and normalize: e_k = u_k / ‖u_k‖.

In exact arithmetic, CGS and MGS produce identical results. In floating-point arithmetic, MGS is significantly more stable because each subtraction uses the most recently updated (and therefore most orthogonal) intermediate vector. The loss of orthogonality in MGS is proportional to the machine epsilon ε times the condition number of the input matrix, compared to ε times the square of the condition number for CGS.

For applications demanding even greater orthogonality, CGS with re-orthogonalization (CGS2) runs the classical process twice. This achieves orthogonality at the level of machine epsilon regardless of the condition number, at the cost of doubling the work.

Connection to QR Decomposition

The Gram-Schmidt process is intimately connected to QR decomposition. When you apply Gram-Schmidt to the columns of a matrix A, you simultaneously compute two matrices:

• Q — The matrix whose columns are the orthonormal vectors e₁, e₂, …, e_n produced by the process.
• R — The upper triangular matrix whose entries are the projection coefficients: r_jk = ⟨v_k, e_j⟩ for j ≤ k (above and on the diagonal) and r_jk = 0 for j > k (below the diagonal). The diagonal entries r_kk = ‖u_k‖ are the norms of the orthogonal residuals.

This means Gram-Schmidt orthogonalization is not merely related to QR decomposition — it is a QR decomposition algorithm. The orthonormal vectors form Q, and the bookkeeping of projection coefficients and norms forms R. This is why our calculator displays both Q and R: the orthonormal basis you seek is exactly the Q matrix, and R records exactly how each original vector decomposes into the orthonormal basis.

Geometric Interpretation

The Gram-Schmidt process has an elegant geometric interpretation. At each step, you are projecting out the components of a vector that lie along previously established directions, leaving only the component that points in a genuinely new direction.

Consider vectors in R³. The first vector v₁ establishes a line. The second vector v₂ generally points in a different direction; by subtracting its projection onto e₁, you extract the component of v₂ that is perpendicular to the line, establishing a plane. The third vector v₃ is then projected onto that plane, and the perpendicular residual gives the component that extends into the third dimension.

Each orthogonal residual u_k represents the "new information" that v_k brings — the part of v_k that cannot be explained by the previous vectors. If ‖u_k‖ is large, then v_k contributes substantial new directional content. If ‖u_k‖ is very small (or zero), then v_k is nearly (or exactly) a linear combination of the previous vectors.

Applications

The Gram-Schmidt process and the orthonormal bases it produces appear throughout mathematics, science, and engineering:

• Orthonormal bases — Any computation in an inner product space becomes simpler with an orthonormal basis. Coordinates are computed by inner products rather than by solving linear systems, and the change-of-basis matrix is its own inverse (transpose).
• Least squares problems — Given the QR factorization A = QR produced by Gram-Schmidt, the least squares solution to Ax ≈ b is x = R⁻¹ Q^Tb. This avoids forming the normal equations A^TAx = A^Tb, which squares the condition number.
• Signal processing — Orthogonalization is central to matched filtering, OFDM subcarrier design, and decorrelation of signals. The Gram-Schmidt procedure is used to construct orthogonal waveforms from arbitrary basis waveforms.
• Quantum mechanics — Quantum states live in Hilbert spaces (infinite-dimensional inner product spaces). The Gram-Schmidt process is used to construct orthonormal bases for state spaces and to orthogonalize sets of wave functions in computational quantum chemistry (e.g., in Hartree-Fock methods).
• Polynomial approximation — Applying Gram-Schmidt to the monomial basis {1, x, x², …} with an appropriate inner product produces families of orthogonal polynomials such as Legendre, Chebyshev, Hermite, and Laguerre polynomials.
• Krylov subspace methods — Iterative solvers like GMRES and the Lanczos algorithm use Gram-Schmidt (typically modified or with re-orthogonalization) to build orthonormal bases for Krylov subspaces, enabling efficient solution of very large sparse linear systems.
• Computer graphics — Orthonormalization of coordinate frames (tangent, bitangent, normal) is essential for correct lighting and texture mapping. Gram-Schmidt is used to re-orthogonalize frames that have drifted due to interpolation or numerical error.
• Statistics and data science — In linear regression, the Gram-Schmidt process applied to the predictor variables corresponds to sequential residualization, which provides insight into partial correlations and the variance explained by each predictor after accounting for earlier ones.

When Vectors Are Linearly Dependent

If the input vectors {v₁, …, v_n} are linearly dependent, then at some step k the orthogonal residual u_k will be the zero vector. This happens because v_k lies entirely in the span of the previous vectors, so subtracting all projections removes everything.

When u_k = 0, normalization is undefined (division by zero). In practice, the algorithm detects that ‖u_k‖ is below some threshold and either:

• Skips the vector — Simply discards v_k and moves to the next input vector. This produces an orthonormal basis for the subspace spanned by the input vectors, with dimension equal to the rank.
• Reports rank deficiency — Signals that the input set is not linearly independent. In the context of QR decomposition, this means the matrix does not have full column rank, and the corresponding diagonal entry of R is zero.

In floating-point arithmetic, u_k will rarely be exactly zero even for linearly dependent vectors. Instead, ‖u_k‖ will be very small (on the order of machine epsilon times the norms of the input vectors), and the resulting "orthonormal" vector will be dominated by rounding errors and point in an essentially random direction. Robust implementations use a tolerance to detect this situation.

Computational Complexity

The Gram-Schmidt process applied to n vectors in R^m (or equivalently, to an m×n matrix) has the following costs:

• Classical Gram-Schmidt (CGS) — Requires approximately 2mn² floating-point operations (flops). Each of the n vectors requires projections against up to n−1 orthonormal vectors, and each projection involves an inner product (2m flops) and a vector subtraction (m flops).
• Modified Gram-Schmidt (MGS) — Has the same flop count as CGS, approximately 2mn², but with different memory access patterns that can affect cache performance.
• CGS with re-orthogonalization (CGS2) — Doubles the cost to approximately 4mn² flops but achieves machine-precision orthogonality.

For a square n×n matrix, the overall complexity is O(n³). This is the same asymptotic complexity as Householder-based QR decomposition, though the constant factors and numerical stability differ.

Gram-Schmidt in General Inner Product Spaces

One of the most powerful aspects of the Gram-Schmidt process is that it works in any inner product space, not just Rⁿ with the standard dot product. The algorithm only requires the ability to compute inner products ⟨·, ·⟩ and norms ‖·‖ = √⟨·, ·⟩.

This generality means Gram-Schmidt applies to:

• Function spaces — For the space of square-integrable functions L²[a, b] with inner product ⟨f, g⟩ = ∫_a^b f(x)g(x) dx, Gram-Schmidt orthogonalizes function families. Applying it to {1, x, x², …} on [−1, 1] yields the Legendre polynomials.
• Complex vector spaces — In Cⁿ with the inner product ⟨u, v⟩ = u^*v (conjugate transpose), Gram-Schmidt produces unitary bases used extensively in quantum computing and signal processing.
• Weighted inner products — With ⟨u, v⟩_W = u^TWv for a positive definite weight matrix W, Gram-Schmidt produces vectors that are W-orthonormal. This arises in finite element methods and generalized least squares.

Comparison with Householder Reflections and Givens Rotations

While Gram-Schmidt is the most intuitive orthogonalization algorithm, it is not the only one. Two other methods are commonly used to achieve the same QR factorization:

Householder reflections apply a sequence of orthogonal reflections H_k = I − 2v_kv_k^T that zero out all sub-diagonal entries in one column at a time. Compared to Gram-Schmidt:

• Householder is backward stable, meaning the computed Q and R satisfy (Q + δQ)(R + δR) = A with perturbations at machine epsilon level. Modified Gram-Schmidt achieves only forward stability for R.
• Householder costs roughly 2mn² − (2/3)n³ flops, slightly less than Gram-Schmidt for square matrices.
• Householder does not explicitly form Q during the factorization; Q is stored implicitly as a product of reflectors. This is more memory-efficient but requires additional work if you need Q explicitly.
• Householder is the algorithm used by LAPACK, NumPy, MATLAB, and virtually all production linear algebra libraries.

Givens rotations zero out individual sub-diagonal entries using 2×2 orthogonal rotations. Compared to Gram-Schmidt:

• Givens rotations are ideal for sparse matrices because each rotation modifies only two rows, preserving the sparsity of the remaining matrix.
• They are naturally suited to parallel and hardware implementations, including FPGAs and systolic arrays.
• Givens rotations are the method of choice for updating an existing QR factorization when rows or columns are added or removed.
• The cost is approximately 3mn² − n³ flops, higher than both Gram-Schmidt and Householder for dense matrices.

In summary: use Gram-Schmidt when you need an intuitive, easily implemented algorithm or when working in abstract inner product spaces; use Householder reflections for production-quality dense matrix computations; and use Givens rotations for sparse or streaming problems that require incremental updates.