Gram-Schmidt Process

⚡ Key Takeaways

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 $\langle e_i,e_j\rangle=\delta_{ij}$ and $\operatorname{span}(e_1,\dots,e_k)=\operatorname{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 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.

DefinitionInner Product Space Setup

Let $V$ be a real or complex vector space equipped with an inner product $\langle\cdot,\cdot\rangle$ , which induces the norm $\|v\|=\sqrt{\langle v,v\rangle}$ . A set $\{e_1,\dots,e_n\}$ is orthonormal if

1

\quad \langle e_i, e_j\rangle = \delta_{ij} = \begin{cases}1 & i=j\\ 0 & i\neq j\end{cases}

Derivation hint: $\delta_{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

2

\quad \operatorname{proj}_w(u) = \frac{\langle u, w\rangle}{\langle w, w\rangle}\, w

Derivation hint: seek scalar $c$ so that $u - cw \perp w$ ; impose $\langle u-cw, w\rangle = 0$ and solve for $c=\langle u,w\rangle/\langle w,w\rangle$ .

DefinitionThe 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:

3

\quad u_1 = v_1, \qquad e_1 = \frac{u_1}{\|u_1\|}

Derivation hint: the first vector needs no orthogonalization; only normalization.

4

\quad u_k = v_k - \sum_{j=1}^{k-1} \frac{\langle v_k, u_j\rangle}{\langle u_j, u_j\rangle}\, u_j, \qquad e_k = \frac{u_k}{\|u_k\|}

Derivation hint: 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 $\langle e_j,e_j\rangle=1$ ):

5

\quad u_k = v_k - \sum_{j=1}^{k-1}\langle v_k, e_j\rangle\, e_j

Derivation hint: substitute $u_j = \|u_j\| e_j$ into [4]; the $\|u_j\|^2$ in the denominator cancels, leaving inner products against unit vectors.

TheoremCorrectness 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

6

\quad \operatorname{span}(e_1,\dots,e_k) = \operatorname{span}(v_1,\dots,v_k) \quad\text{for all } 1\le k\le n.

Derivation hint: prove span-preservation by induction; linear independence guarantees each $u_k\neq 0$ so normalization is valid.

ProofOrthogonality 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 $\langle e_1,e_1\rangle = 1$ . Clearly $\operatorname{span}(e_1)=\operatorname{span}(v_1)$ .

Step 2 (Inductive hypothesis). Assume $\{e_1,\dots,e_{k-1}\}$ is orthonormal and spans $\operatorname{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$ :

7

\quad \langle u_k, e_i\rangle = \langle v_k, e_i\rangle - \sum_{j=1}^{k-1}\langle v_k, e_j\rangle\langle e_j, e_i\rangle = \langle v_k, e_i\rangle - \langle v_k, e_i\rangle = 0.

Derivation hint: by orthonormality $\langle e_j,e_i\rangle=\delta_{ji}$ , 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}\langle v_k,e_j\rangle e_j$ , so $v_k\in\operatorname{span}(e_1,\dots,e_k)$ and conversely $e_k\in\operatorname{span}(v_1,\dots,v_k)$ . Combined with the inductive hypothesis, $\operatorname{span}(e_1,\dots,e_k)=\operatorname{span}(v_1,\dots,v_k)$ . This closes the induction. $\blacksquare$

∎

mathematician · 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.

🧠 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.

Figure

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

ExampleOrthonormalizing Vectors in ℝ³

Given the linearly independent vectors

v_1=(1,1,0),\quad v_2=(1,0,1),\quad v_3=(0,1,1),

using the standard dot product.

Step 1. $u_1=v_1=(1,1,0)$ , with $\|u_1\|=\sqrt 2$ , so

e_1=\tfrac{1}{\sqrt2}(1,1,0).

Step 2. $\langle v_2,u_1\rangle = 1\cdot1+0\cdot1+1\cdot0=1$ , and $\langle u_1,u_1\rangle=2$ .

u_2 = v_2-\tfrac12 u_1 = (1,0,1)-\tfrac12(1,1,0)=(\tfrac12,-\tfrac12,1).

$\|u_2\|=\sqrt{\tfrac14+\tfrac14+1}=\sqrt{3/2}$ , so

e_2=\tfrac{1}{\sqrt{3/2}}(\tfrac12,-\tfrac12,1)=\tfrac{1}{\sqrt6}(1,-1,2).

Step 3. $\langle v_3,u_1\rangle=0+1+0=1$ and $\langle v_3,u_2\rangle=0\cdot\tfrac12+1\cdot(-\tfrac12)+1\cdot1=\tfrac12$ .

u_3 = v_3-\tfrac{1}{2}u_1-\frac{1/2}{3/2}u_2 = v_3-\tfrac12 u_1-\tfrac13 u_2.

Compute: $\tfrac12 u_1=(\tfrac12,\tfrac12,0)$ , $\tfrac13 u_2=(\tfrac16,-\tfrac16,\tfrac13)$ .

u_3=(0,1,1)-(\tfrac12,\tfrac12,0)-(\tfrac16,-\tfrac16,\tfrac13)=(-\tfrac23,\tfrac23,\tfrac23).

$\|u_3\|=\tfrac23\sqrt3$ , so $e_3=\tfrac{1}{\sqrt3}(-1,1,1)$ .

Boxed answer (orthonormal basis):

\boxed{\;e_1=\tfrac{1}{\sqrt2}(1,1,0),\quad e_2=\tfrac{1}{\sqrt6}(1,-1,2),\quad e_3=\tfrac{1}{\sqrt3}(-1,1,1)\;}

(Check: each has unit length and pairwise dot products vanish, e.g. $e_1\cdot e_2=\tfrac{1}{\sqrt{12}}(1-1+0)=0$ .)

ExampleLegendre Polynomials from Monomials

Given the functions $1, x, x^2$ on $[-1,1]$ with the inner product

\langle f,g\rangle=\int_{-1}^{1} f(x)g(x)\,dx.

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

Step 1. $u_0=1$ , with $\langle u_0,u_0\rangle=\int_{-1}^1 1\,dx=2$ .

Step 2. $\langle x, u_0\rangle=\int_{-1}^1 x\,dx=0$ , so no subtraction:

u_1 = x - 0 = x.

Here $\langle u_1,u_1\rangle=\int_{-1}^1 x^2\,dx=\tfrac23$ .

Step 3. $\langle x^2,u_0\rangle=\int_{-1}^1 x^2\,dx=\tfrac23$ and $\langle x^2,u_1\rangle=\int_{-1}^1 x^3\,dx=0$ .

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

Boxed answer:

\boxed{\;u_0=1,\quad u_1=x,\quad u_2=x^2-\tfrac13\;}

These are proportional to the Legendre polynomials $P_0,P_1,P_2$ (up to the normalization $P_n(1)=1$ , giving $P_2=\tfrac12(3x^2-1)$ ). Gram-Schmidt on $\{1,x,x^2,\dots\}$ with this inner product generates the entire Legendre family.

⚠️ 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 $\langle u_j,u_j\rangle$ 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.

CounterexampleLinearly 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 $\mathbb R^2$ . Then

u_2 = v_2 - \frac{\langle v_2,u_1\rangle}{\langle u_1,u_1\rangle}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.

connection

Gram-Schmidt is woven through linear algebra and analysis:

<a class="wiki-link" href="/wiki/qr-decomposition">QR Decomposition</a>: 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_{jk}=\langle v_k,e_j\rangle$ and $R_{kk}=\|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.

🔬 Where this appears

⏳ History

- 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.

open-problem

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 $\langle v,v\rangle$ can be negative or zero) requires modified algorithms, since vectors can be null or "imaginary-length," and the classical normalization step breaks down.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also