Gram-Schmidt Process

Gram-Schmidt Process is an algorithm that converts any linearly independent set of vectors into an orthonormal set spanning the same subspace. Key result: given

{v_{1}, \dots, v_{n}}

, it produces

{e_{1}, \dots, e_{n}}

with

⟨ e_{i}, e_{j} ⟩ = δ_{ij}

and

span (e_{1}, \dots, e_{k}) = span (v_{1}, \dots, v_{k})

for every

k

. Applies in: any inner product space (Euclidean spaces, function spaces,

L^{2}

). Who/when: named for Jørgen Pedersen Gram (1883) and Erhard Schmidt (1907), though Laplace and Cauchy used the idea earlier.

The Gram-Schmidt process is a constructive procedure that takes a list of linearly independent vectors in an inner product space and orthogonalizes them one at a time by subtracting off the components along previously processed directions. Each new vector is made orthogonal to all those before it, then normalized to unit length, yielding an orthonormal basis for the same span. It matters because orthonormal bases dramatically simplify computation: coordinates become inner products, projections become sums, and matrices become orthogonal. A surprising fact is that the process is mathematically equivalent to the QR factorization of a matrix — the orthonormal vectors form $Q$ and the bookkeeping coefficients form an upper-triangular $R$ — so a 19th-century geometric idea underlies a workhorse of modern numerical linear algebra.

The Core Insight

To make a vector orthogonal to a subspace, subtract its orthogonal projection onto that subspace. Doing this sequentially — projecting each new vector onto the span of all already-orthogonalized vectors and removing that component — guarantees the leftover is orthogonal to everything before it. Normalizing then fixes the length. The whole algorithm is just "project, subtract, normalize," repeated.

Formal Statement

Inner Product Space Setup

Let $V$ be a real or complex vector space equipped with an inner product $⟨ \cdot, \cdot ⟩$ , which induces the norm $∥ v ∥ = ⟨ v, v ⟩$ . A set ${e_{1}, \dots, e_{n}}$ is orthonormal if

⟨ e_{i}, e_{j} ⟩ = δ_{ij} = {10 i = j i \neq = j

⟳

δ_{ij}

is the Kronecker delta; orthogonality is the off-diagonal condition, unit length the diagonal condition.

The orthogonal projection of a vector $u$ onto a nonzero vector $w$ is

proj_{w} (u) = \frac{⟨ u , w ⟩}{⟨ w , w ⟩} w

⟳seek scalar

c

so that

u - c w ⊥ w

; impose

⟨ u - c w, w ⟩ = 0

and solve for

c = ⟨ u, w ⟩ / ⟨ w, w ⟩

The Gram-Schmidt Algorithm

Given linearly independent vectors $v_{1}, \dots, v_{n}$ , define orthogonal vectors $u_{1}, \dots, u_{n}$ and orthonormal vectors $e_{1}, \dots, e_{n}$ recursively:

u_{1} = v_{1}, e_{1} = \frac{u _{1}}{∥ u _{1} ∥}

⟳the first vector needs no orthogonalization; only normalization.

u_{k} = v_{k} - j = 1 \sum k - 1 \frac{⟨ v _{k} , u _{j} ⟩}{⟨ u _{j} , u _{j} ⟩} u_{j}, e_{k} = \frac{u _{k}}{∥ u _{k} ∥}

⟳subtract from

v_{k}

its projections onto each previously found orthogonal direction

u_{j}

; the remainder is orthogonal to all of them.

Equivalently, using the already-normalized $e_{j}$ (cleaner since $⟨ e_{j}, e_{j} ⟩ = 1$ ):

u_{k} = v_{k} - j = 1 \sum k - 1 ⟨ v_{k}, e_{j} ⟩ e_{j}

⟳substitute

u_{j} = ∥ u_{j} ∥ e_{j}

into [4]; the

∥ u_{j} ∥^{2}

in the denominator cancels, leaving inner products against unit vectors.

Correctness of Gram-Schmidt

If $v_{1}, \dots, v_{n}$ are linearly independent, then the vectors $e_{1}, \dots, e_{n}$ produced by [3]–[5] are orthonormal and satisfy

span (e_{1}, \dots, e_{k}) = span (v_{1}, \dots, v_{k}) for all 1 \leq k \leq n .

⟳prove span-preservation by induction; linear independence guarantees each

u_{k} \neq = 0

so normalization is valid.

Why It Holds / Derivation

Orthogonality and Span Preservation

We prove by induction on $k$ that ${e_{1}, \dots, e_{k}}$ is orthonormal and spans the same space as ${v_{1}, \dots, v_{k}}$ .

Step 1 (Base case).

u_{1} = v_{1} \neq = 0

since the

v_{i}

are independent, so

e_{1} = v_{1} /∥ v_{1} ∥

is well-defined and

⟨ e_{1}, e_{1} ⟩ = 1

. Clearly

span (e_{1}) = span (v_{1})

. Step 2 (Inductive hypothesis). Assume

{e_{1}, \dots, e_{k - 1}}

is orthonormal and spans

span (v_{1}, \dots, v_{k - 1})

. Step 3 ( $u_{k}$ is orthogonal to each earlier $e_{i}$ ). For

i < k

, take the inner product of [5] with

e_{i}

⟨ u_{k}, e_{i} ⟩ = ⟨ v_{k}, e_{i} ⟩ - j = 1 \sum k - 1 ⟨ v_{k}, e_{j} ⟩ ⟨ e_{j}, e_{i} ⟩ = ⟨ v_{k}, e_{i} ⟩ - ⟨ v_{k}, e_{i} ⟩ = 0.

⟳by orthonormality

⟨ e_{j}, e_{i} ⟩ = δ_{j i}

, so the sum collapses to the single

j = i

term.

Step 4 ( $u_{k} \neq = 0$ ). If

u_{k} = 0

, then [5] would express

v_{k}

as a linear combination of

e_{1}, \dots, e_{k - 1}

, hence of

v_{1}, \dots, v_{k - 1}

(inductive hypothesis), contradicting linear independence. So

∥ u_{k} ∥ > 0

and

e_{k} = u_{k} /∥ u_{k} ∥

is well-defined with

∥ e_{k} ∥ = 1

. Step 5 (Span preservation). From [5],

v_{k} = ∥ u_{k} ∥ e_{k} + \sum_{j < k} ⟨ v_{k}, e_{j} ⟩ e_{j}

, so

v_{k} \in span (e_{1}, \dots, e_{k})

and conversely

e_{k} \in span (v_{1}, \dots, v_{k})

. Combined with the inductive hypothesis,

span (e_{1}, \dots, e_{k}) = span (v_{1}, \dots, v_{k})

. This closes the induction.

■

Erhard Schmidt | 1876–1959

A German mathematician and student of David Hilbert, Schmidt is a founding figure of functional analysis. In his 1907 work on integral equations he introduced the orthogonalization procedure now bearing his name, applying it to function spaces — the setting that became Hilbert space theory. The "Gram" in the name credits Jørgen Pedersen Gram, a Danish actuary and mathematician whose 1883 paper on least-squares series expansions used the same construction. Historically, the underlying idea appears even earlier in the work of Laplace and Cauchy. Schmidt also co-founded the Berlin school of applied mathematics and contributed to the spectral theory of compact operators.

Building Intuition

Picture standing at the origin holding several arrows pointing in generic directions. You want to replace them with a clean set of mutually perpendicular unit arrows covering exactly the same flat region. Take the first arrow and just shrink it to length one — that's your first axis. For the second arrow, its shadow (projection) onto the first axis is the part you don't want; cut it off, keep the perpendicular leftover, shrink to length one. For the third arrow, remove its shadows on both established axes; the remainder points straight out of the plane they span. Each step strips away everything that "leans" toward earlier directions, leaving a fresh perpendicular component. The order matters: $e_{1}$ always points exactly along $v_{1}$ , and the process never looks ahead — it only cleans up against what came before.

Gram-Schmidt in the plane: projecting v₂ onto u₁ and keeping the perpendicular remainder

Worked Examples

Orthonormalizing Vectors in ℝ³

Given the linearly independent vectors

v_{1} = (1, 1, 0), v_{2} = (1, 0, 1), v_{3} = (0, 1, 1),

using the standard dot product. Step 1.

u_{1} = v_{1} = (1, 1, 0)

, with

∥ u_{1} ∥ = 2

, so

e_{1} = \frac{1}{2} (1, 1, 0) .

Step 2.

⟨ v_{2}, u_{1} ⟩ = 1 \cdot 1 + 0 \cdot 1 + 1 \cdot 0 = 1

, and

⟨ u_{1}, u_{1} ⟩ = 2

u_{2} = v_{2} - \frac{1}{2} u_{1} = (1, 0, 1) - \frac{1}{2} (1, 1, 0) = (\frac{1}{2}, - \frac{1}{2}, 1) .

∥ u_{2} ∥ = \frac{1}{4} + \frac{1}{4} + 1 = 3/2

, so

e_{2} = \frac{1}{3/2} (\frac{1}{2}, - \frac{1}{2}, 1) = \frac{1}{6} (1, - 1, 2) .

Step 3.

⟨ v_{3}, u_{1} ⟩ = 0 + 1 + 0 = 1

and

⟨ v_{3}, u_{2} ⟩ = 0 \cdot \frac{1}{2} + 1 \cdot (- \frac{1}{2}) + 1 \cdot 1 = \frac{1}{2}

u_{3} = v_{3} - \frac{1}{2} u_{1} - \frac{1/2}{3/2} u_{2} = v_{3} - \frac{1}{2} u_{1} - \frac{1}{3} u_{2} .

Compute:

\frac{1}{2} u_{1} = (\frac{1}{2}, \frac{1}{2}, 0)

\frac{1}{3} u_{2} = (\frac{1}{6}, - \frac{1}{6}, \frac{1}{3})

u_{3} = (0, 1, 1) - (\frac{1}{2}, \frac{1}{2}, 0) - (\frac{1}{6}, - \frac{1}{6}, \frac{1}{3}) = (- \frac{2}{3}, \frac{2}{3}, \frac{2}{3}) .

∥ u_{3} ∥ = \frac{2}{3} 3

, so

e_{3} = \frac{1}{3} (- 1, 1, 1)

. Boxed answer (orthonormal basis):

e_{1} = \frac{1}{2} (1, 1, 0), e_{2} = \frac{1}{6} (1, - 1, 2), e_{3} = \frac{1}{3} (- 1, 1, 1)

(Check: each has unit length and pairwise dot products vanish, e.g.

e_{1} \cdot e_{2} = \frac{1}{12} (1 - 1 + 0) = 0

Legendre Polynomials from Monomials

Given the functions

1, x, x^{2}

[- 1, 1]

with the inner product

⟨ f, g ⟩ = \int_{- 1}^{1} f (x) g (x) d x .

We orthogonalize (without normalizing, to match standard Legendre conventions). Step 1.

u_{0} = 1

, with

⟨ u_{0}, u_{0} ⟩ = \int_{- 1}^{1} 1 d x = 2

. Step 2.

⟨ x, u_{0} ⟩ = \int_{- 1}^{1} x d x = 0

, so no subtraction:

u_{1} = x - 0 = x .

Here

⟨ u_{1}, u_{1} ⟩ = \int_{- 1}^{1} x^{2} d x = \frac{2}{3}

. Step 3.

⟨ x^{2}, u_{0} ⟩ = \int_{- 1}^{1} x^{2} d x = \frac{2}{3}

and

⟨ x^{2}, u_{1} ⟩ = \int_{- 1}^{1} x^{3} d x = 0

u_{2} = x^{2} - \frac{2/3}{2} \cdot 1 - 0 = x^{2} - \frac{1}{3} .

Boxed answer:

u_{0} = 1, u_{1} = x, u_{2} = x^{2} - \frac{1}{3}

These are proportional to the Legendre polynomials

P_{0}, P_{1}, P_{2}

(up to the normalization

P_{n} (1) = 1

, giving

P_{2} = \frac{1}{2} (3 x^{2} - 1)

). Gram-Schmidt on

{1, x, x^{2}, \dots}

with this inner product generates the entire Legendre family.

Common Misconceptions

Classical Gram-Schmidt is Numerically Unstable

The textbook recursion [4] — called Classical Gram-Schmidt (CGS) — suffers severe loss of orthogonality in floating-point arithmetic when the input vectors are nearly linearly dependent. Rounding errors accumulate, and the computed $e_{i}$ can fail to be orthogonal. The fix is Modified Gram-Schmidt (MGS), which subtracts projections sequentially and re-orthogonalizes against each $u_{j}$ as it is computed rather than all at once. MGS is mathematically identical to CGS in exact arithmetic but vastly more stable numerically. For maximum robustness, Householder reflections or Givens rotations are preferred for QR factorization. Never use CGS for ill-conditioned problems.

Order Dependence and Normalization Pitfalls

The output depends on the ordering of the input vectors: permuting $v_{1}, \dots, v_{n}$ generally gives a different orthonormal basis. Also, a common slip is dividing by $⟨ u_{j}, u_{j} ⟩$ when using the normalized $e_{j}$ in the formula — if you use unnormalized $u_{j}$ you must keep the $∥ u_{j} ∥^{2}$ denominator [4]; if you use $e_{j}$ the denominator is $1$ [5]. Mixing the two leads to wrong projections.

Linearly Dependent Input Breaks the Process

If the input vectors are not linearly independent, Gram-Schmidt fails. Take $v_{1} = (1, 0)$ , $v_{2} = (2, 0)$ in $R^{2}$ . Then

u_{2} = v_{2} - \frac{⟨ v _{2} , u _{1} ⟩}{⟨ u _{1} , u _{1} ⟩} u_{1} = (2, 0) - \frac{2}{1} (1, 0) = (0, 0) .

Here

u_{2} = 0

, so

e_{2} = u_{2} /∥ u_{2} ∥

involves division by zero. This is exactly the situation Step 4 of the proof rules out under independence. In practice, encountering a (near-)zero

u_{k}

is how one detects linear dependence — the process doubles as a rank test.

Connections

Gram-Schmidt is woven through linear algebra and analysis:

QR Decomposition: applying Gram-Schmidt to the columns of a matrix $A$ yields $A = QR$ , where $Q$ has the orthonormal $e_{i}$ as columns and $R$ is upper triangular with entries $R_{j k} = ⟨ v_{k}, e_{j} ⟩$ and $R_{k k} = ∥ u_{k} ∥$ .
Orthogonal Projection: each step is literally subtracting an orthogonal projection onto a subspace; the algorithm is projection applied repeatedly.
Inner Product Space: the whole construction lives in any space with an inner product, real or complex (with conjugation in the Hermitian case).
Orthogonal Polynomials: Gram-Schmidt on monomials with a weighted inner product generates Legendre, Chebyshev, Hermite, and Laguerre families.
Least Squares Approximation: an orthonormal basis turns the normal equations into trivial coordinate computations.
Spectral Theorem: the existence of orthonormal eigenbases for symmetric/Hermitian operators is often established via Gram-Schmidt on eigenspaces.

Real-World Applications

Numerical linear algebra / QR algorithm: Gram-Schmidt (via MGS or Householder QR) underlies solving least-squares problems and the QR eigenvalue algorithm used in virtually every scientific computing library (LAPACK).
Signal processing: orthogonalizing basis functions for transforms; the Gram-Schmidt orthogonalization step in adaptive filtering and decorrelation of signals.
Quantum mechanics: constructing orthonormal sets of states; degenerate eigenstates of a Hamiltonian are orthogonalized via Gram-Schmidt to form a usable basis.
Statistics / regression: orthogonalizing predictor variables (related to the QR approach to ordinary least squares) reduces multicollinearity effects and stabilizes coefficient estimation.
Computer graphics: re-orthonormalizing rotation matrices and camera/coordinate frames that have drifted due to accumulated floating-point error keeps transformations rigid.
Wireless communications (MIMO): V-BLAST detection and lattice-reduction algorithms use Gram-Schmidt to orthogonalize channel matrices.
Function approximation: generating orthonormal polynomial and wavelet bases for spectral methods in solving PDEs.

Historical Development

c. 1795–1810 — Pierre-Simon Laplace, in work on least squares and planetary motion, implicitly employs sequential orthogonalization of functions.
1830s — Augustin-Louis Cauchy uses related orthogonalization ideas in his studies of determinants and quadratic forms.
1883 — Jørgen Pedersen Gram publishes Über die Entwickelung reeller Functionen in Reihen, applying orthogonalization to least-squares series expansions of real functions.
1907 — Erhard Schmidt, in his foundational paper on integral equations (Hilbert's program), gives the explicit recursive procedure in function spaces, establishing it as a basic tool of the emerging functional analysis.
1920s — The method becomes standard in Hilbert space theory and quantum mechanics following the work of Hilbert, von Neumann, and others.
1960s — Numerical analysts (notably John Rice and Åke Björck) identify the instability of Classical Gram-Schmidt and formalize Modified Gram-Schmidt, analyzing its superior error behavior.
1965 — Householder's reflection-based QR factorization is established as the gold standard for stability, contextualizing where Gram-Schmidt should and shouldn't be used.
1971 — Björck's detailed roundoff-error analysis of MGS clarifies its loss-of-orthogonality bounds in terms of the condition number.
1990s–present — Reorthogonalization schemes ("twice is enough") and block Gram-Schmidt variants developed for large-scale and high-performance computing.

Subtleties & Limits

Several refinements remain active in numerical linear algebra. The precise conditions under which a single reorthogonalization step suffices ("Kahan–Parlett twice-is-enough") are understood for well-separated cases but become delicate near breakdown. Block Gram-Schmidt variants for tall-skinny matrices on parallel/GPU architectures face a tension between communication efficiency and orthogonality quality, an area of ongoing algorithm design. In infinite-dimensional Hilbert spaces, Gram-Schmidt always terminates on countable independent sets but the resulting orthonormal sequence's completeness (whether it spans the whole space) is a separate analytic question tied to density. Finally, generalizing stable orthogonalization to non-standard or indefinite inner products (e.g., Minkowski/Lorentzian "inner products" in relativity, where $⟨ v, v ⟩$ can be negative or zero) requires modified algorithms, since vectors can be null or "imaginary-length," and the classical normalization step breaks down.

Gram-Schmidt Process

The Core Insight

Formal Statement

Inner Product Space Setup

The Gram-Schmidt Algorithm

Correctness of Gram-Schmidt

Why It Holds / Derivation

Orthogonality and Span Preservation

Erhard Schmidt | 1876–1959

Building Intuition

Gram-Schmidt in the plane: projecting v₂ onto u₁ and keeping the perpendicular remainder

Worked Examples

Orthonormalizing Vectors in ℝ³

Legendre Polynomials from Monomials

Common Misconceptions

Classical Gram-Schmidt is Numerically Unstable

Order Dependence and Normalization Pitfalls

Linearly Dependent Input Breaks the Process

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also

Before this

Where this leads