es
In 1907, the Baltic German mathematician Erhard Schmidt published a paper in which he introduced an orthogonalization algorithm that has since become known as the classical Gram-Schmidt process. Schmidt claimed that his procedure was essentially the same as an earlier one published by the Danish actuary and mathematician J. P. Gram in 1883. The Schmidt version was the first to become popular and widely used. An algorithm related to a modified version of the process appeared in an 1820 treatise by P. S. Laplace. Although related algorithms have been around for almost 200 years, it is the Schmidt paper that led to the popularization of orthogonalization techniques.

Jørgen Pedersen Gram (1850--1916)
     
Erhard Schmidt (1876--1959)

Gram--Schmidt process

The Gram-Schmidt process is an algorithm to transform an ordered set of vectors into an orthogonal or orthonormal set spanning the same subspace, that is generating the same collection of linear combinations.    
Example 1: This example follows the article A Closed-form Formula of a Particular Gram-Schmidt Process Related to Shifted Legendre Polynomials by Yinuo Huang, Matthew Milunic

For n ∈ ℤ, let ℘≤n⟦x⟧ be a vector space of real-valued polynomials of degree at most n. This space is equipped with the inner product \[ \langle f \mid g \rangle = \int_0^1 f(x)\,g(x)\,{\text d}x , \] making it an inner product space. Let us consider the list 𝓜 = (1, x, x², … , xm) for some m ∈ [0..n] = { 0, 1, … , n }. The Gram-Schmidt Orthogonalization Algorithm produces an orthonormal list of vectors 𝓞 = { ω₀, ω₁, … ,⃗ωm } such that span(𝓞) = span(𝓜). We show that \[ \omega_n (x) = \sqrt{2n+1}\,\sum_{k=0}^n (-1)^{k+n} \binom{n}{k} \binom{n+k}{k} x^k . \]

   ■

End of Example 1

 

Recurrence relation

The Gram–Schmidt process is the canonical constructive method for producing an orthogonal (or orthonormal) sequence from an arbitrary linearly independent list in an inner‑product space. When the initial list consists of polynomials ordered by degree, Gram–Schmidt famously produces the classical orthogonal polynomial families—Legendre, Laguerre, Hermite, and others—each of which satisfies a three‑term recurrence relation.

However, when the initial list is arbitrary and no structural assumptions (such as polynomial degree) are imposed, the Gram–Schmidt process still yields a recurrence, but of a simpler form: a two‑term recurrence expressing each new orthogonal vector as a linear combination of the previous orthogonal vector and the next raw input vector. This recurrence is the algebraic heart of the Gram–Schmidt algorithm and is independent of any special structure of the underlying space.

Let V be an inner‑product space over ℝ or ℂ. Let { vₙ }n≥0 be a linearly independent sequence in V.

Applying Gram–Schmidt produces an orthogonal sequence { ψₙ }n≥0 defined recursively by

\[ \psi_0 =v_0,\qquad \psi_n = v_n -\sum _{k=0}^{n-1}\frac{\langle v_n \mid \psi _k\rangle }{\langle \psi_k \mid \psi_k\rangle }\, \psi_k . \]
If desired, one may normalize to obtain an orthonormal sequence, but normalization plays no role in the recurrence structure, so we work with the unnormalized ψₙ.

We make the Key Observation: Triangularity of the Gram--Schmidt process. The Gram–Schmidt formula shows that ψₙ lies in the span of { v₀, v₁, … ,vₙ }. More importantly, the transformation from the basis { vₙ }n≥0 to the orthogonal basis { ψₙ }n≥0 is upper triangular with nonzero diagonal entries.

This triangularity implies that the inverse transformation is also triangular:

\[ v_n =\psi_n +\sum _{k=0}^{n-1} a_{n,k}\, \psi _k. \]
The coefficients 𝑎n,k are explicitly computable from the Gram–Schmidt projections, but their exact form is not needed for the recurrence.

For derivation of the two‑term recurrence, we start from the Gram–Schmidt definition by writing the Gram–Schmidt step as

\[ \psi_n = v_n -\sum _{k=0}^{n-1}c_{n,k}\, \psi_k,\qquad c_{n,k} =\frac{\langle v_n,\psi _k\rangle }{\langle \psi _k,\psi _k\rangle }. \]
Now isolate the term involving ψn-1:
\[ \psi_n =v_n - c_{n,n-1}\psi _{n-1} -\sum _{k=0}^{n-2} c_{n,k}\psi _k. \]
Using the triangular inverse representation,
\[ v_n =\psi _n +\sum _{k=0}^{n-1}a_{n,k}\psi _k. \]
we substitute this into the previous expression:
\[ \psi_n =\left( \psi_n +\sum_{k=0}^{n-1} a_{n,k}\psi _k\right) - c_{n,n-1}\psi_{n-1} -\sum_{k=0}^{n-2} c_{n,k}\psi_k . \]
Cancel ψₙ from both sides:
\[ 0 =\sum_{k=0}^{n-1} a_{n,k}\psi_k - c_{n,n-1}\psi_{n-1} - \sum _{k=0}^{n-2} c_{n,k}\psi_k . \]
Group the terms involving ψn-1 and the rest:
\[ 0 = \left( a_{n,n-1} - c_{n,n-1}\right) \psi_{n-1} +\sum _{k=0}^{n-2}\left( a_{n,k} - c_{n,k}\right) \psi_k . \]

Now orthogonality forces all coefficients to vanish because { ψₖ } is an orthogonal basis, the only way the above linear combination can vanish is if each coefficient is zero:

\[ a_{n,k} =c_{n,k}\quad (0\leq k\leq n-1). \]
Thus, the Gram–Schmidt step simplifies to
\[ \psi_n = v_n - a_{n,n-1}\psi_{n-1}. \]
This is the final two‑term recurrence, so we have shown that each orthogonal vector ψₙ satisfies
\begin{equation} \label{EqRecurrence} \psi_n =v_n-\frac{\langle v_n ,\psi_{n-1}\rangle }{\langle \psi_{n-1},\psi_{n-1}\rangle }\psi_{n-1}. \end{equation}
with the initial condition ψ₀ = v₀. It expresses each new orthogonal vector ψₙ using only:
  • the new input vector vₙ, and
  • the immediately preceding orthogonal vector ψn-1.
Nothing else appears explicitly in recurrence \eqref{EqRecurrence}. This is in contrast to the full-history Gram–Schmidt formula, which subtracts projections onto all previous ψₖ.

This recurrence is universal: it holds for any linearly independent sequence { v₀, v₁, … ,vₙ, … } in any inner‑product space. It is the minimal recurrence compatible with orthogonality and triangularity.

The two‑term recurrence \eqref{EqRecurrence} expresses a simple geometric fact: to make vₙ orthogonal to all previous ψₖ, it suffices to remove only its component along ψn-1.

Why? Because the triangular structure ensures that vₙ is already orthogonal to ψ₀, ψ₁, … , ψn-2 after subtracting the ψn-1-component. The Gram–Schmidt projections onto earlier vectors are implicitly encoded in the triangular change‑of‑basis coefficients. Thus, the recurrence is not merely an algebraic convenience; it reflects the geometry of nested subspaces:

\[ \mbox{span} \{ v_0,\dots ,v_{n-1}\} =\mbox{span} \{ \psi _0,\dots ,\psi _{n-1}\} . \]
The new vector ψₙ must be orthogonal to this subspace, and the only direction in which vₙ can fail to be orthogonal is the direction of ψn-1.

The Gram–Schmidt process, when viewed through the lens of triangularity and orthogonality, naturally yields a two‑term recurrence for the orthogonal sequence \{ \psi _n\} . This recurrence is the minimal algebraic structure required to enforce orthogonality at each step and is independent of any special properties of the initial list. In contexts where the initial list has additional structure—such as monomials ordered by degree—the two‑term recurrence expands into the familiar three‑term recurrence of orthogonal polynomials. But at its core, Gram–Schmidt always operates through the same geometric mechanism: subtracting the projection onto the most recently constructed orthogonal direction.

Below is a compact, reusable Mathematica snippet that:

  • takes a list of linearly independent vectors vList = { v₀, v₁, … },
  • an inner product function ip[.,.],
  • and returns the orthogonal sequence { ψ₀, ψ₁, … } using only the two‑term recurrence.
    (* ip[f, g] should implement the inner product ⟨f, g⟩ *) Clear[GramSchmidtTwoTerm]; GramSchmidtTwoTerm[v_List, ip_] := Module[{psi}, psi[0] = v[[1]]; Do[ psi[n] = v[[n + 1]] - (ip[v[[n + 1]], psi[n - 1]]/ip[psi[n - 1], psi[n - 1]]) psi[n - 1] , {n, 1, Length[v] - 1} ]; Table[psi[n], {n, 0, Length[v] - 1}] ]; (* ip[f, g] should implement the inner product ⟨f, g⟩ *) Clear[GramSchmidtTwoTerm]; GramSchmidtTwoTerm[v_List, ip_] := Module[{psi}, psi[0] = v[[1]]; Do[ psi[n] = v[[n + 1]] - (ip[v[[n + 1]], psi[n - 1]]/ip[psi[n - 1], psi[n - 1]]) psi[n - 1] , {n, 1, Length[v] - 1} ]; Table[psi[n], {n, 0, Length[v] - 1}] ];
    For polynomials with weight w(x) on [𝑎,b], you might define
    ip[f_, g_] := Integrate[f[x] g[x] w[x], {x, a, b}]; vList = Table[x^n, {n, 0, N}]; psiList = GramSchmidtTwoTerm[vList, ip];
    This directly realizes the two‑term recurrence in a form you can adapt, extend, or wrap into a package.    
    Example 1:    ■
    End of Example 1