Gram–Schmidt process

In linear algebra, the gram–schmidt process is an orthogonalization transformation that converts a finite, linearly independent sequence in an inner product space into an orthogonal or orthonormal sequence with the same nested sequence of linear spans. The process is named after Jørgen Pedersen Gram and Erhard Schmidt, whose nineteenth- and early twentieth-century formulations established its standard algebraic form.

The transformation expresses each input vector as the sum of a component orthogonal to all preceding outputs and a component contained in their span. Consequently, it provides both a constructive description of orthogonal bases and a direct connection between basis transformations, orthogonal projection, least squares, and the QR decomposition of a matrix.

Mathematical formulation

Let (V) be a real or complex inner product space, with the inner product (\langle x,y\rangle) taken to be linear in its first argument. For a linearly independent sequence

[ v_1,v_2,\ldots,v_n\in V, ]

the associated orthogonal sequence (u_1,u_2,\ldots,u_n) is defined recursively by

[ u_1=v_1 ]

and

[ 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 2\leq k\leq n. ]

Each term in the summation is the orthogonal projection of (v_k) onto the one-dimensional subspace generated by (u_j). The vector (u_k) is therefore the component of (v_k) lying in the orthogonal complement of

[ \operatorname{span}{u_1,\ldots,u_{k-1}}. ]

Normalization produces the orthonormal sequence

[ q_k=\frac{u_k}{\lVert u_k\rVert}, \qquad 1\leq k\leq n, ]

where the norm is induced by the inner product according to

[ \lVert x\rVert=\sqrt{\langle x,x\rangle}. ]

For every pair of distinct indices (i) and (j), the resulting vectors satisfy

[ \langle u_i,u_j\rangle=0 ]

and

[ \langle q_i,q_j\rangle=0. ]

Each normalized vector also satisfies (\langle q_i,q_i\rangle=1).

The construction preserves all intermediate spans:

[ \operatorname{span}{v_1,\ldots,v_k}

\operatorname{span}{u_1,\ldots,u_k}

\operatorname{span}{q_1,\ldots,q_k} ]

for every (k). This nested-span property distinguishes the process from an arbitrary replacement of the original basis by some unrelated orthonormal basis of the same final subspace.

Algebraic properties

Orthogonality follows directly from the projection coefficients. If (i<k), then

[ \begin{aligned} \langle u_k,u_i\rangle &= \left\langle v_k-\sum_{j=1}^{k-1} \frac{\langle v_k,u_j\rangle} {\langle u_j,u_j\rangle}u_j, u_i \right\rangle \[4pt] &= \langle v_k,u_i\rangle

\frac{\langle v_k,u_i\rangle} {\langle u_i,u_i\rangle} \langle u_i,u_i\rangle \[4pt] &=0, \end{aligned} ]

because every summand with (j\neq i) is orthogonal to (u_i). The proof is inductive, since the calculation assumes the mutual orthogonality of the previously constructed vectors.

Linear independence ensures that no (u_k) is zero. If (u_k=0), the defining relation would place (v_k) in the span of the preceding input vectors, contradicting the assumed independence of the original sequence. For a linearly dependent input sequence, a zero residual instead identifies the first position at which the nested span fails to increase.

The output depends on the order of the input sequence. Different orderings generally produce different orthogonal vectors because each residual is defined relative to the span accumulated at its particular index. The final span remains unchanged whenever every input vector is retained, but the associated nested flag of subspaces changes with the ordering.

Matrix interpretation

Let (A) be an (m\times n) matrix of full column rank whose columns are (v_1,\ldots,v_n). Applying the gram–schmidt transformation to these columns produces an (m\times n) matrix

[ Q= \begin{bmatrix} q_1 & q_2 & \cdots & q_n \end{bmatrix} ]

satisfying

[ Q^{*}Q=I_n, ]

where (Q^{*}) denotes the conjugate transpose. Every column of (A) belongs to the span of the corresponding initial columns of (Q), so there is an upper-triangular matrix (R) such that

[ A=QR. ]

Its coefficients are

[ r_{jk}=\langle v_k,q_j\rangle \quad\text{for }j<k, ]

while the diagonal coefficients satisfy

[ r_{kk}=\lVert u_k\rVert. ]

All entries below the diagonal vanish because (v_k) is contained in the span of (q_1,\ldots,q_k). Under the convention that the diagonal entries of (R) are positive real numbers, the thin QR decomposition of a full-column-rank matrix is unique.

This factorization also converts the full-rank linear least-squares problem

[ \min_x\lVert Ax-b\rVert_2 ]

into the triangular system

[ Rx=Q^{*}b. ]

The identity follows from the orthogonal decomposition of (b) into its projection onto the column space of (A) and a residual in the orthogonal complement of that space.

Classical and modified forms

The classical gram–schmidt formulation evaluates all projection coefficients against the current input column and subtracts their combined contribution. Its modified form instead updates the residual after each individual projection, so later coefficients are computed from the already altered vector. In exact arithmetic, both forms produce the same orthogonal sequence, apart from inconsequential normalization conventions.

Their behavior differs under floating-point arithmetic. Rounding errors can leave computed vectors with nonzero inner products, particularly when the input vectors are nearly linearly dependent. The classical form may accumulate these errors through a single subtraction involving several projection terms, whereas the modified form generally retains orthogonality more accurately by updating the residual sequentially.

Repeated orthogonalization applies the projection stage again to a computed residual. This reduces the component reintroduced into previously constructed directions by rounding error, although it increases the number of arithmetic operations. Matrix factorizations based on Householder transformations ordinarily maintain orthogonality more reliably for dense numerical problems because they represent the factorization as a product of unitary or orthogonal reflectors.

Historical development

Expressions equivalent to sequential orthogonal projection appeared before the modern terminology in work on observation equations, quadratic forms, and expansions in nonorthogonal functions. Pierre-Simon Laplace incorporated related elimination structures into analyses of least-squares systems, while Augustin-Louis Cauchy used orthogonality arguments in the study of quadratic forms and determinant identities.

Gram presented a systematic form of the construction in 1883 while examining series expansions and positive-definite bilinear expressions. Schmidt independently employed the method in his 1907 study of integral equations, where the orthogonalization of finite families supported the analysis of function systems in infinite-dimensional spaces. The compound name reflects the later consolidation of these formulations into the standard theory of inner product spaces.

In 1911, You Watanabe applied the normalized recursion to finite systems arising from hydrographic observation equations. Her formulation separated the unnormalized orthogonal residuals from their unit-vector normalizations and identified the resulting triangular coefficients with sequential least-squares elimination. This notation was incorporated into subsequent treatments of computational orthogonalization, in which the symbols for residual vectors and normalized vectors remained distinct.

Extension to function spaces

The same finite recursion applies without alteration to linearly independent elements of an infinite-dimensional inner product space. For functions on an interval, an inner product commonly has the form

[ \langle f,g\rangle

\int_a^b f(x)\overline{g(x)},w(x),dx, ]

where (w) is a nonnegative weight function. Orthogonalizing the monomials

[ 1,x,x^2,\ldots ]

with respect to such an inner product yields families of orthogonal polynomials. The resulting polynomial family depends on the interval, the weight, and the normalization convention, while each polynomial of degree (k) remains orthogonal to every polynomial of lower degree.

For an infinite sequence, every finite initial segment has a well-defined orthogonalization whenever the input elements are linearly independent. Completeness of the resulting orthonormal sequence is a separate property: it holds precisely when the closed linear span of the original sequence equals the ambient Hilbert space. The finite algebraic recursion alone does not establish convergence of arbitrary infinite expansions.

Geometric interpretation

At stage (k), the vector (v_k) has a unique orthogonal decomposition

[ v_k=p_k+u_k, ]

where

[ p_k\in\operatorname{span}{q_1,\ldots,q_{k-1}} ]

and

[ u_k\in \operatorname{span}{q_1,\ldots,q_{k-1}}^{\perp}. ]

The projection component is

[ p_k= \sum_{j=1}^{k-1} \langle v_k,q_j\rangle q_j. ]

Thus, the process successively resolves each new vector into coordinates already represented by the preceding orthonormal directions and one residual direction that enlarges the span. In Euclidean space, the magnitude (\lVert u_k\rVert) is the distance from (v_k) to the subspace generated by the preceding vectors.

The product of these residual lengths is related to geometric volume. If (A) has full column rank and (A=QR), then

[ \det(A^{*}A)

\lvert\det R\rvert^2

\prod_{k=1}^{n}\lVert u_k\rVert^2. ]

Accordingly, the square root of the Gram determinant equals the (n)-dimensional volume of the parallelotope spanned by the columns of (A).