Chapter 50. Gram-Schmidt Orthogonalization

The Gram-Schmidt process converts a linearly independent list of vectors into an orthogonal or orthonormal list spanning the same subspace. It is one of the standard constructions in inner product spaces and is the basic theoretical source of the QR factorization used in numerical linear algebra. The process repeatedly subtracts projections onto previously constructed directions, leaving a residual vector orthogonal to all earlier ones.

50.1 The Problem

Let

be linearly independent vectors in an inner product space $V$. We want to construct vectors

such that:

The output is an orthonormal basis for the same subspace spanned by the original vectors.

The key idea is simple. Keep the part of each new vector that points in a new direction. Remove all parts that already lie in the directions constructed earlier.

50.2 Projection onto a Unit Vector

Suppose $q$ is a unit vector. The projection of $v$ onto the line spanned by $q$ is

This formula is simple because $\|q\|=1$. For a non-unit vector $u$, the projection would be

Gram-Schmidt uses these projections to remove the parts of a vector that lie in old directions.

50.3 First Step

Start with the first vector $v_1$. Since the list is linearly independent, $v_1\ne 0$.

Define

Normalize it:

Then $q_1$ is a unit vector and

The first direction is unchanged except for scaling.

50.4 Second Step

The second vector $v_2$ may have a component in the direction of $q_1$. Remove that component:

Then $u_2$ is orthogonal to $q_1$. Indeed,

Using linearity,

Since $q_1$ is a unit vector,

Therefore

Normalize:

Now $q_1,q_2$ are orthonormal and span the same subspace as $v_1,v_2$.

50.5 General Step

Assume that

have already been constructed and are orthonormal.

To construct the next vector, subtract from $v_j$ its projections onto all previous $q_i$:

Then normalize:

The vector $u_j$ is orthogonal to every earlier $q_i$. For $m<j$,

By linearity,

Since the $q_i$ are orthonormal,

Thus only one term remains:

So $u_j$ is orthogonal to all previous directions.

50.6 Why $u_j$ Is Nonzero

The vector $u_j$ must be nonzero. If

then

This would imply

But

Thus $v_j$ would lie in the span of the earlier $v_i$, contradicting linear independence.

Therefore $u_j\ne 0$, so normalization is valid.

50.7 The Algorithm

Given linearly independent vectors

the Gram-Schmidt algorithm is:

For $j=2,\ldots,k$,

and

The result is an orthonormal list

such that

for every $j$.

50.8 Example in $\mathbb{R}^2$

Let

First,

Its norm is

Thus

Now remove from $v_2$ its projection onto $q_1$:

Therefore

So

The norm is

Thus

The final orthonormal basis is

50.9 Example in $\mathbb{R}^3$

Let

First,

Since

we have

Next,

Thus

Its norm is

Hence

Now compute $u_3$:

We have

and

Therefore

This gives

Its norm is

Thus

The three vectors $q_1,q_2,q_3$ form an orthonormal basis of $\mathbb{R}^3$.

50.10 Orthogonal Version

Sometimes one wants an orthogonal basis rather than an orthonormal basis. In that case, stop before normalization.

Define

and

Then

are nonzero and mutually orthogonal.

The normalized vectors are

The orthogonal version is often easier to write when the intermediate vectors are not unit vectors.

50.11 Span Preservation

Gram-Schmidt preserves spans step by step:

This follows from the construction. Each $u_j$ is built from $v_j$ and earlier $q_i$, which lie in the earlier span. Hence

Conversely,

so $v_j$ lies in the span of $u_1,\ldots,u_j$.

Thus the two lists generate the same subspace at each stage.

50.12 QR Factorization

Gram-Schmidt gives a factorization of a matrix.

Let $A$ be an $m\times n$ matrix with linearly independent columns

Apply Gram-Schmidt to these columns and obtain orthonormal vectors

Let $Q$ be the $m\times n$ matrix with columns $q_i$. Then

Each column $a_j$ lies in

Thus

Collecting these equations gives

where $R$ is upper triangular.

The entries of $R$ are

and

The QR factorization is one of the main computational uses of Gram-Schmidt.

50.13 Classical Gram-Schmidt

The formula

is called classical Gram-Schmidt.

It subtracts all projections of $v_j$ using inner products computed against the original vector $v_j$.

In exact arithmetic, this produces an orthonormal basis. In floating point arithmetic, the computed vectors may lose orthogonality when the original vectors are nearly linearly dependent.

This numerical weakness matters in practical computation. For stable algorithms, one often uses modified Gram-Schmidt, Householder reflections, or Givens rotations.

50.14 Modified Gram-Schmidt

Modified Gram-Schmidt subtracts projections one at a time from the current residual.

Start with

For $i=1,\ldots,j-1$, compute

then replace

After all previous directions have been removed, set

In exact arithmetic, classical and modified Gram-Schmidt give the same result. In floating point arithmetic, modified Gram-Schmidt usually preserves orthogonality better.

The reason is that each projection is removed from the current residual rather than from the original vector.

50.15 Linear Dependence and Zero Residuals

If the input list is linearly dependent, Gram-Schmidt produces a zero residual at some step.

That is, for some $j$,

This means

In this case, $v_j$ contributes no new direction and cannot be normalized.

A practical version of the algorithm skips zero residuals. If $u_j=0$, discard $v_j$. The remaining nonzero residuals form an orthogonal basis for the span of the original list.

This gives a method for extracting a basis from a spanning set.

50.16 Gram-Schmidt as Projection Residual

At each step, let

The vector

is the orthogonal projection of $v_j$ onto $W_{j-1}$.

Thus

So $u_j$ is the residual after projecting $v_j$ onto the old subspace.

This gives the geometric interpretation:

Gram-Schmidt keeps the new orthogonal part and normalizes it.

50.17 Gram Matrices and Nonzero Pivots

Let

be the Gram matrix of the first $j$ input vectors.

If $v_1,\ldots,v_j$ are linearly independent, then $G_j$ is positive definite. This guarantees that the construction has no zero residuals.

The squared lengths

measure the amount of genuinely new direction contributed by $v_j$ beyond the earlier span.

If $\|u_j\|$ is very small, then $v_j$ is nearly dependent on the earlier vectors. This is a warning sign for numerical instability.

50.18 Function Space Example

Gram-Schmidt also applies to function spaces.

Let $V$ be the space of polynomials on $[-1,1]$ with inner product

Start with

Applying Gram-Schmidt produces an orthogonal sequence of polynomials. With a conventional normalization, this gives the Legendre polynomials.

For example,

Since

the polynomial $x$ is already orthogonal to $1$.

For $x^2$, subtract its projection onto $1$. Since

and

the projection coefficient is

Thus the new orthogonal polynomial is

After scaling, this corresponds to the second Legendre polynomial.

50.19 Numerical Remarks

Gram-Schmidt is conceptually important, but its classical form can be numerically fragile. When vectors are nearly linearly dependent, subtraction may remove almost equal quantities. This causes cancellation and loss of orthogonality.

For numerical QR factorization, Householder transformations are usually preferred for high stability. Modified Gram-Schmidt is often acceptable and easier to implement in iterative methods.

The correct algorithm depends on the context:

The mathematical goal is the same: replace a basis by an orthonormal basis for the same subspace.

50.20 Summary

Gram-Schmidt orthogonalization converts a linearly independent list

into an orthonormal list

with the same successive spans.

The construction is

At each step, the algorithm subtracts the projection onto the old subspace and keeps the new orthogonal residual.

Gram-Schmidt explains how orthonormal bases arise, why QR factorization exists, and how projection can be performed by successive removal of old components.