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)

The Gram–Schmidt process is a simple algorithm for producing an orthogonal or orthonormal basis for any nonzero subspace of a finite dimensional inner product space (V, ⟨ • , • ⟩).

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:    ■
End of Example 1
   
Example 2:    ■
End of Example 2
   
Example 3:    ■
End of Example 3
Theorem 1 (Gram-Schmidt): Let { v₁, v₂, … vₙ, …} be a (finite or infinite) system of independent vectors in an inner-product space (V, ⟨ • , • ⟩)⟨ ·∣· ⟩ . Then there is an orthogonal system { e₁, e₂, … eₙ, …} having the following property: For each s
\[ \operatorname{span}\left\{ \mathbf{e}_1 , \mathbf{e}_2 , \ldots , \mathbf{e}_{s+1} \right\} = \text{span}\left\{ \mathbf{v}_1 , \mathbf{v}_2 , \ldots , \mathbf{v}_{s+1} \right\} \subset V . \]
Moreover, the vectors eₙ are unique up to multiplication by scalars.
We begin with e₁ = v₁ and proceed by indeterminate coefficients for the next one: e₂ = v₁ + 𝑎₁ v₂ has to be orthogonal to e₁ = v₁. More generally, since the subspaces generated by the { v₁, v₂, … vₛ} and the { e₁, e₂, … eₛ} are the same, we have to take
\[ \mathbf{e}_{s+1} = \mathbf{e}_1 + x_1 \mathbf{e}_2 + \cdots + x_{s-1} \mathbf{e}_{s} + x_s \mathbf{v}_{s+1} \]
with the orthogonality conditions
\[ \left\langle \mathbf{e}_{s+1} \mid \mathbf{e}_j \right\rangle = 0 \qquad j = 1 , 2, \ldots , s . \]
These condition furnish a linear system for the unknown coefficients. The problem is to solve this system at each step. Thanks to the theory of determinants, there is an elegant way to give the result. Consider the symbolic determinant
\[ \begin{vmatrix} \langle \mathbf{v}_1 \mid \mathbf{v}_1 \rangle & \cdots & \langle \mathbf{v}_{s+1} \mid \mathbf{v}_1 \rangle \\ \vdots & \ddots & \vdots \\ \langle \mathbf{v}_s \mid \mathbf{v}_1 \rangle & \cdots & \langle \mathbf{v}_{s+1} \mid \mathbf{v}_s \rangle \\ \mathbf{v}_1 & \cdots & \mathbf{v}_{s+1} \end{vmatrix} , \]
which represents a vector es+1 ∈ V. Expanding it according to its last row, we find
\[ \mathbf{e}_{s+1} = g_s \mathbf{v}_{s+1} = \text{a linear combination of $\mathbf{v}_i$ for $i \le s$} , \]
where gₛ stands for the Gram determinant of the first s vectors { vₗ }. This determ,inant is nonzero because vectors { vₗ } are linearly independent. We also observe that
\[ \operatorname{span}\left\{ \mathbf{v}_1 , \mathbf{v}_2 , \ldots , \mathbf{v}_{s+1} \right\} = \text{span}\left\{ \mathbf{v}_1 , \mathbf{v}_2 , \ldots , \mathbf{v}_s , \mathbf{e}_{s+1} \right\} \subset V . \]
An induction shows that
\[ \operatorname{span}\left\{ \mathbf{v}_1 , \mathbf{v}_2 , \ldots , \mathbf{v}_{s+1} \right\} = \text{span}\left\{ \mathbf{e}_1 , \mathbf{e}_2 , \ldots , \mathbf{e}_{s+1} \right\} \subset V . \]
Furthermore, distributing the inner products in the last row, we see that for i ≤ s, ⟨ei ∣ es+1⟩ is given by a determinant having two equal rows, hence zero: eₛ is orthogonal to the previously constructed ei's.
   
Example 1:    ■
End of Example 1
   
Example 7: Gram--Schmidt orthogonalization is a method that takes a non-orthogonal set of linearly independent function and literally constructs an orthogonal set over an arbitrary interval and with respect to an arbitrary weighting function. Here for convenience, all functions are assumed to be real.

The Hermite polynomial Hₙ(x) can be derived from the orthogonalization of the polynomials

\[ u_n (x) = x^n , \qquad n = 0,1,2, \ldots ; \]
with weight function
\[ w(x) = e^{-x^2} . \]
   ■
End of Example 7
   
Example 8: 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 . \tag{L.1} \]

By the binomial theorem, we have

\[ f_n (x) = x^n \left( 1- x \right)^n = \sum_{k=0}^n \,(-1)^k\,\binom{n}{k} x^{n+k} . \]
Taking n-th derivative, we get
\begin{align*} f_n^{(n)} (x) &= \frac{{\text d}^n}{{\text d}x^n}\, f_n (x) = \frac{{\text d}^n}{{\text d}x^n}\, \sum_{k=0}^n \,(-1)^k\,\binom{n}{k} x^{n+k} \\ &= \sum_{k=0}^n \,(-1)^k\,\binom{n}{k} \cdot \frac{(n+k) !}{k!} \cdot x^k \\ &= \sum_{k=0}^n \,(-1)^k\,\binom{n}{k} \binom{n+k}{k} \cdot n! \cdot x^k \\ &= n! \cdot \sum_{k=0}^n \,(-1)^k\,\binom{n}{k} \binom{n+k}{k} \cdot x^k . \end{align*}
Rearranging terms in the sum above, we obtain
\[ \frac{1}{n!}\, \frac{{\text d}^n}{{\text d}x^n}\, f_n (x) = \sum_{k=0}^n \,(-1)^k\,\binom{n}{k} \binom{n+k}{k} \cdot x^k . \]
For some positive integer n, we consider the polynomial
\[ p_n (x) = \frac{1}{\binom{2n}{n}}\,\sum_{k=0}^n \,(-1)^{n+k} \,\binom{n}{k}\binom{n+k}{k}\, x^k . \]
We are going to show that pₙ is a monic polynomial, that is orthogonal to the subspace of all real polynomials of degree at most n − 1.

The coefficient of xⁿ is equal to 1, as Mathematica confirms

p[n_ , x_] = 1/Binomial[2*n, n] * Sum[(-1)^(n + k) * Binomial[n, k] * Binomial[n + k, k] * x^k , {k, 0, n}]; With[{n = 5}, Coefficient[p[n, x], x, Exponent[p[n, x], x]] ]
1
If W ⊂ V is the subspace of all polynomials of degree at most n − 1, then pₙ ⊥ q for all q ∈ W. Indeed, since
\[ p_n (x) = \frac{(-1)^n}{\binom{2n}{n}\, n!}\, f_n^{(n)} (x) , \]
we have
\[ \langle p_n , q \rangle = \int_0^1 \,f_n^{(n)} \,q(x)\,{\text d}x . \]
Integration by parts yields
\[ \langle p_n , q \rangle = \left. \sum_{j=0}^{n-1} \,(-1)^j \,f_n^{(n-j-1)} (x) \,q^{(j)} (x) \right\vert_{x=0}^1 + (-1)^n \,\int_0^1 \,f_n (x)\,q^{(n)} (x)\,{\text d}x . \]
For any integer r < n, we have \( \displaystyle \quad f_n^{(r)} (0) = f_n^{(r)} (1) = 0 . \quad \) Substituting back r = n − j − 1, we have
\[ \left. \sum_{j=0}^{n-1} \,(-1)^j \,f_n^{(n-j-1)} (x) \,q^{(j)} (x) \right\vert_{x=0}^1 = 0 . \]
Furthermore, because q has degree at most n − 1, its n-th derivative vanishes, so pₙ ⊥ q for all q ∈ W.

Now we prove formula (L.1) using mathematical indusction. Since the initial step is easily verifiable, we go directly to the inductive step.

The Gram--Schmidt orthogonalization algorithm when is applied to an orthonormal list gives us a (not necessarily normalized) vector

\[ v_n = x^n - \sum_{k=0}^{n-1} \, \left\langle \omega_k \mid x^n \right\rangle \, \omega_k , \qquad \omega_n = \frac{v_n}{\| v_n \|} . \]
Note that vₙ is a monic polynomial of degree n (that is, it is a polynomial in which the leading coefficient (the coefficient of the highest degree term) is exactly equal to 1).

Furthermore, a known property of the algorithm is that vₙ is orthogonal to W.

Polynomial pₙ is of degree n and is monic. For q ∈ W, we have ⟨pₙ , q⟩ = 0. Hence,

\[ \langle v_n - p_n , q \rangle = \langle v_n , q \rangle - \langle p_n , q \rangle = 0-0 = 0 . \]
So vₙ − pₙ is orthogonal to W. Because vₙ and pₙ are both monic polynomials of degree n, their difference vₙ − pₙ is a polynomials of degree at most n − 1, so vₙ − pₙ ∈ W. The only vector in W that is orthogonal to W is the zero vector, so vₙ = pₙ.

Thus, we have shown that

\[ v_n = x^n - \sum_{k=0}^{n-1} \, \left\langle \omega_k \mid x^n \right\rangle \, w \omega_k = \frac{1}{\binom{2n}{n}} \,\sum_{k=0}^n (-1)^{n+k} \binom{n}{k}\binom{n+k}{k} \,x^k . \]
The norm of it is
\begin{align*} \| v_n \|^2 &= \frac{1}{\binom{2n}{n}^2}\,\int_0^1 \left( \sum_{k=0}^n \,(-1)^{n+k} \binom{n}{k} \binom{n+k}{k}\, x^k \right)^2 {\text d} x \\ &= \frac{1}{\binom{2n}{n}^2 \left( n! \right)^2}\,\int_0^1 \left( f_n^{(n)} (x) \right)^2 {\text d}x . \end{align*}
Using integration by parts repeatedly, and by similar logic as before, the boundary terms all vanisj; so we get
\begin{align*} \| v_n \|^2 &= (-1)^n \int_0^1 \,f_n (x) \cdot f_n^{(2n)} \,{\text d}x \\ &= (-1)^n \int_0^1 \,f_n (x) \cdot (2n)! \,(-1)^n \,{\text d}x \\ &= (2n)! \,\int_0^1 \, x^n \,(1-x)^n \,{\text d} x \\ &= (2n)! \, B(n+1 , n+1 ) = (2n)! \cdot \frac{n!\, n!}{(2n+1)!} \\ &= \frac{\left( n! \right)^2}{2n+1} . \end{align*}
Therefore, we have
\[ \| v_n \|^2 = \frac{1}{\binom{2n}{n}^2 \,(n! )^2} \cdot \frac{(n!)^2}{2n+1} . \]
This means that
\[ \| v_n \| = \frac{1}{\binom{2n}{n}\,\sqrt{2n+1}} , \]
so
\begin{align*} \omega_n &= \frac{v_n}{\| v_n \|} \\ &= \frac{1}{\binom{2n}{n}}\,\sum_{k=1}^n \, (-1)^{n+k} \binom{n}{k} \binom{n+k}{k}\,x^k \cdot \binom{2n}{n}\,\sqrt{2n+1} \\ &= \sqrt{2n+1} \,\sum_{k=1}^n \, (-1)^{n+k} \binom{n}{k} \binom{n+k}{k}\,x^k \end{align*}
as desired.

We have constructed and proved a closed-form formula for outputs of the Gram--Schmidt orthogonalization algorithm for our inner product space and the choice of elementary basis vectors in this vector space given by Eq.(L.1). It should be noted that this expression is closely related to the shifted Legendre polynomials \( \displaystyle \quad \tilde{P}_n (x) = P_n (2x+1) . \)    ■

End of Example 8

 

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