Gram-Schmidt orthogonalization

An orthogonal basis makes inner products and coordinates easy to compute, but a basis usually arrives as an arbitrary linearly independent list. Gram-Schmidt turns that list into an orthogonal one by removing, at each stage, the part already explained by earlier directions. The order of the input matters: changing it can change the output, although the resulting list still spans the same subspace.

The projection idea

First consider one nonzero vector $v$ and a vector $w$. To remove a multiple of $v$ and leave a perpendicular remainder, choose $c$ so that

$$0=\langle w-cv,v\rangle=\langle w,v\rangle-c\|v\|^2, \qquad c=\frac{\langle w,v\rangle}{\|v\|^2}.$$

Since $v\ne0$, the denominator is positive and this coefficient is unique. With several mutually orthogonal directions, subtracting one such component does not change the inner products with the others.

Suppose $v_1,\dots,v_k$ are already nonzero and mutually orthogonal, and let $w\in\mathbb{R}^m$. The coefficient of the component of $w$ along $v_i$ is

$$\frac{\langle w,v_i\rangle}{\|v_i\|^2}.$$

Thus the part left after removing all earlier orthogonal directions is

$$r=w-\sum_{i=1}^{k}\frac{\langle w,v_i\rangle}{\|v_i\|^2}v_i.$$

The denominators are legal because an orthogonal set contains no zero vector. When $k=0$, the sum is empty and $r=w$. This empty case is useful for the zero subspace, but it never asks us to normalize the zero vector.

Theorem

Orthogonal remainder theorem

Let $S=\{v_1,\dots,v_k\}$ be an orthogonal subset of $\mathbb{R}^m$, and let $w\in\mathbb{R}^m$. Define

$$r=w-\sum_{j=1}^{k}\frac{\langle w,v_j\rangle}{\|v_j\|^2}v_j.$$

Then $\langle r,v_i\rangle=0$ for every $i$.

For a fixed $v_i$, expansion gives

$$\langle r,v_i\rangle =\langle w,v_i\rangle- \sum_{j=1}^{k} \frac{\langle w,v_j\rangle}{\|v_j\|^2}\langle v_j,v_i\rangle.$$

All terms with $j\ne i$ vanish. The remaining term is $\langle w,v_i\rangle-\langle w,v_i\rangle=0$. If $r=0$, the formula says that $w$ was already in the earlier span; for an arbitrary vector that can happen. Gram-Schmidt avoids this zero remainder by requiring an independent input list.

Projection and membership

For an orthogonal list $S=\{v_1,\dots,v_k\}$, the same formula gives a useful membership test. Define

$$r(w)=w-\sum_{i=1}^{k}\frac{\langle w,v_i\rangle}{\|v_i\|^2}v_i.$$

The orthogonal remainder theorem gives $r(w)\perp\operatorname{span}S$. Also,

$$r(w)=0 \quad\Longleftrightarrow\quad w\in\operatorname{span}S.$$

The forward implication is immediate from the projection formula. Conversely, if $w=\sum_i\alpha_i v_i$, taking the inner product with $v_i$ gives $\alpha_i=\langle w,v_i\rangle/\|v_i\|^2$ because the cross terms vanish; substitution gives $r(w)=0$. Thus a nonzero remainder records exactly the part of $w$ outside the current span.

Proof

Projection plus an orthogonal remainder

Let $U=\operatorname{span}S$ and set

$$p(w)=\sum_{i=1}^{k}\frac{\langle w,v_i\rangle}{\|v_i\|^2}v_i, \qquad r=w-p(w).$$

Then $p(w)\in U$, and the orthogonal remainder theorem gives $r\perp v_i$ for every generator. By linearity, $r\perp U$, so $w=p+r$. If $S$ is empty, the sum is $0$, $U=\{0\}$, and the same statement reads $w=0+w$.

Suppose also $w=p'+r'$ with $p'\in U$ and $r'\perp U$. Then $z=p-p'=r'-r$ belongs to $U$ and is perpendicular to $U$. Consequently $\langle z,z\rangle=0$, so $z=0$; hence $p=p'$ and $r=r'$. The decomposition into a part in $U$ and an orthogonal remainder is therefore unique.

This decomposition gives a precise meaning to “remove the old directions.” The vector $p(w)$ is the part reconstructed from the available orthogonal generators, and $r$ is the part that no linear combination of them can explain. If $w\in U$, the membership criterion says $r=0$, so the projection is all of $w$. If $w\notin U$, then $r\ne0$ and it supplies a new direction perpendicular to every direction already in $U$. In the Gram-Schmidt induction, this is why the next independent input cannot disappear: a zero residual would put it in the earlier span. The uniqueness argument also matters computationally. It says that two different lists of coefficients cannot produce two different “orthogonal parts” of the same vector while both satisfying the defining conditions. The condition $z\in U\cap U^\perp$ forces that ambiguity to vanish, because a real inner product is positive definite. This is the exact geometric content behind the coefficient formula, while the worked calculations show how to evaluate it without relying on a picture.

The Gram-Schmidt process

Theorem

Gram-Schmidt orthogonalization process

Let $k\ge1$ and let $w_1,\dots,w_k$ be a linearly independent list in $\mathbb{R}^m$. Define

$$v_1=w_1,$$

and, for $\ell=2,\dots,k$,

$$v_\ell=w_\ell-\sum_{j=1}^{\ell-1} \frac{\langle w_\ell,v_j\rangle}{\|v_j\|^2}v_j.$$

Then every $v_\ell$ is nonzero, the vectors $v_1,\dots,v_k$ are pairwise orthogonal, and for every $\ell$,

$$\operatorname{span}\{w_1,\dots,w_\ell\} = \operatorname{span}\{v_1,\dots,v_\ell\}.$$

The empty input list is handled separately: its span is the zero subspace $\{0\}$, and its output is the empty orthogonal list. There is no $v_1$ to define and no vector to normalize in that case.

The algorithm must use the constructed orthogonal vectors $v_j$ in the subtractions. The original $w_j$ generally are not orthogonal, so subtracting their projections independently does not remove the correct component.

Proof

The three invariants in the induction

We prove simultaneously at stage $\ell$ that (i) the new vector is nonzero, (ii) the constructed vectors are orthogonal, and (iii) the partial spans are equal. The base case is $v_1=w_1\ne0$; both spans are the same line.

Assume all three statements through $\ell-1$. The earlier $v_j$ are nonzero, so every denominator in the definition of $v_\ell$ is valid. The orthogonal remainder theorem gives $v_\ell\perp v_j$ for every $j<\ell$, proving the new orthogonality.

The defining equation writes $v_\ell$ as a combination of $w_\ell$ and earlier $v_j$, so the new $v$-span is contained in the new $w$-span. Rearranging gives

$$w_\ell=v_\ell+ \sum_{j=1}^{\ell-1} \frac{\langle w_\ell,v_j\rangle}{\|v_j\|^2}v_j,$$

which gives the reverse inclusion. Finally, if $v_\ell=0$, this equation places $w_\ell$ in $\operatorname{span}\{v_1,\dots,v_{\ell-1}\} =\operatorname{span}\{w_1,\dots,w_{\ell-1}\}$, contradicting input independence. Thus the new vector is nonzero, and all three assertions follow without assuming the conclusion in advance.

This is why orthogonality means more than a list of zero dot products: an orthogonal set also excludes zero vectors. The nonzero check makes normalization legal.

Subtract old directions in three dimensions

Worked example

Three independent vectors in $\mathbb R^3$

Take the ordered list

$$w_1=\begin{bmatrix}1\\0\\1\end{bmatrix},\qquad w_2=\begin{bmatrix}1\\1\\1\end{bmatrix},\qquad w_3=\begin{bmatrix}0\\1\\2\end{bmatrix}.$$

The determinant of the matrix with these columns is $2$, so the input is independent. First,

$$v_1=w_1=\begin{bmatrix}1\\0\\1\end{bmatrix}, \qquad \|v_1\|^2=2.$$

For the second vector,

$$\frac{\langle w_2,v_1\rangle}{\|v_1\|^2} =\frac{2}{2}=1,\qquad v_2=w_2-v_1=\begin{bmatrix}0\\1\\0\end{bmatrix}.$$

For the third, both constructed directions matter:

$$\frac{\langle w_3,v_1\rangle}{\|v_1\|^2} =\frac{2}{2}=1,\qquad \frac{\langle w_3,v_2\rangle}{\|v_2\|^2} =\frac{1}{1}=1,$$

so

$$v_3=w_3-v_1-v_2=\begin{bmatrix}-1\\0\\1\end{bmatrix}.$$

The squared norms are $2,1,2$, and direct products give

$$\langle v_1,v_2\rangle=\langle v_1,v_3\rangle =\langle v_2,v_3\rangle=0.$$

The span invariant is visible:

$$w_2=v_1+v_2,\qquad w_3=v_1+v_2+v_3.$$

Thus the output spans exactly the same $\mathbb{R}^3$ as the input.

The arithmetic at the third stage can be audited before accepting the answer: $\langle w_3,v_1\rangle=0\cdot1+1\cdot0+2\cdot1=2$ and $\langle w_3,v_2\rangle=0\cdot0+1\cdot1+2\cdot0=1$. The subtraction therefore removes $(1,0,1)^T+(0,1,0)^T$, leaving $(-1,0,1)^T$; this explains the negative first coordinate rather than treating it as a sign to be guessed.

Counterexample mode

Why original w-vectors cannot replace v-vectors

A tempting but incorrect third step is

$$w_3- \frac{\langle w_3,w_1\rangle}{\|w_1\|^2}w_1- \frac{\langle w_3,w_2\rangle}{\|w_2\|^2}w_2 =w_3-w_1-w_2=\begin{bmatrix}-2\\0\\0\end{bmatrix}.$$

This vector has dot product $-2$ with $w_1$, so it is not orthogonal to the first direction. The repair is to subtract projections onto $v_1$ and $v_2$, which gives the correct $v_3=(-1,0,1)^T$. The input and constructed lists are different even though their partial spans agree.

Keep fractional projection coefficients exact

Here the projection coefficients are fractions. Keep them exact through each subtraction, then check orthogonality and the equality of spans.

Worked example

Fractional projections in three dimensions

Start with

$$w_1=(1,1,0)^T,\qquad w_2=(1,0,1)^T,\qquad w_3=(0,1,1)^T.$$

Step	Projection data	New orthogonal vector	Span preserved
$v_1$	none	$v_1=w_1=(1,1,0)^T$	$\operatorname{Span}\{v_1\}=\operatorname{Span}\{w_1\}$
$v_2$	$\langle w_2,v_1\rangle/\|v_1\|^2=1/2$	$v_2=w_2-\frac12v_1=(1/2,-1/2,1)^T$	$\operatorname{Span}\{v_1,v_2\}=\operatorname{Span}\{w_1,w_2\}$
$v_3$	$\langle w_3,v_1\rangle/\|v_1\|^2=1/2$, $\langle w_3,v_2\rangle/\|v_2\|^2=1/3$	$v_3=w_3-\frac12v_1-\frac13v_2=(-2/3,2/3,2/3)^T$	$\operatorname{Span}\{v_1,v_2,v_3\}=\operatorname{Span}\{w_1,w_2,w_3\}$

The input determinant is $-2$, so these columns are independent. In particular, the final residual must be nonzero. Here $\|v_2\|^2=3/2$ and $\langle w_3,v_2\rangle=0(1/2)+1(-1/2)+1(1)=1/2$; hence the second coefficient in the third row is $(1/2)/(3/2)=1/3$. The resulting $v_3$ has squared norm $4/3$, and direct products give $v_1\cdot v_2=v_1\cdot v_3=v_2\cdot v_3=0$.

Normalization and boundary cases

Theorem

From an orthogonal basis to an orthonormal basis

If $v_1,\dots,v_k$ is an orthogonal basis, define

$$u_i=\frac{v_i}{\|v_i\|}.$$

Every $u_i$ has norm $1$, and scaling preserves pairwise orthogonality. The result is an orthonormal basis of the same subspace.

Worked example

Normalize the first $\mathbb R^3$ output

For the first $\mathbb R^3$ example,

$$\|v_1\|=\sqrt2,\qquad \|v_2\|=1,\qquad \|v_3\|=\sqrt2.$$

Therefore

$$u_1=\frac1{\sqrt2}\begin{bmatrix}1\\0\\1\end{bmatrix},\qquad u_2=\begin{bmatrix}0\\1\\0\end{bmatrix},\qquad u_3=\frac1{\sqrt2}\begin{bmatrix}-1\\0\\1\end{bmatrix}.$$

This uses the first output, not the distinct table input.

Because each norm is positive, $u_i$ keeps the orientation of $v_i$; multiplying by $\|v_i\|$ recovers the exact vector rather than its negative.

For the unit checks, $\|u_1\|^2=(1/2)\|v_1\|^2=1$, $\|u_2\|^2=1$, and $\|u_3\|^2=(1/2)\|v_3\|^2=1$. Moreover, $v_i=\|v_i\|u_i$, so each $v_i$ is recovered from $u_i$ by scaling; both directions of every span equality are preserved.

Worked example

An orthonormal basis from a constraint in $\mathbb R^4$

Let

$$V=N\begin{bmatrix}1&1&1&1\end{bmatrix} =\{x\in\mathbb{R}^4:x_1+x_2+x_3+x_4=0\}.$$

Writing $x=(-a-b-c,a,b,c)^T$ shows that $V$ has the basis

$$w_1=\begin{bmatrix}-1\\1\\0\\0\end{bmatrix},\quad w_2=\begin{bmatrix}-1\\0\\1\\0\end{bmatrix},\quad w_3=\begin{bmatrix}-1\\0\\0\\1\end{bmatrix}.$$

These vectors are independent: if $a_1w_1+a_2w_2+a_3w_3=0$, then coordinates 2, 3, and 4 force $a_1=a_2=a_3=0$. The constraint already shows that they lie in $V$.

The process gives

$$v_1=w_1,\qquad v_2=w_2-\frac12v_1= \begin{bmatrix}-1/2\\-1/2\\1\\0\end{bmatrix},$$

Here $\langle w_2,v_1\rangle=1$ and $\|v_1\|^2=2$, giving the coefficient $1/2$. Also $\langle w_3,v_1\rangle=1$, while $\langle w_3,v_2\rangle=1/2$ and $\|v_2\|^2=3/2$, giving $(1/2)/(3/2)=1/3$. Thus

$$v_3=w_3-\frac12v_1-\frac13v_2 =\begin{bmatrix}-1/3\\-1/3\\-1/3\\1\end{bmatrix}.$$

Their squared norms are $2,3/2,4/3$. Hence

$$u_1=\frac1{\sqrt2}\begin{bmatrix}-1\\1\\0\\0\end{bmatrix},\quad u_2=\frac1{\sqrt6}\begin{bmatrix}-1\\-1\\2\\0\end{bmatrix},\quad u_3=\frac1{\sqrt{12}}\begin{bmatrix}-1\\-1\\-1\\3\end{bmatrix}.$$

For example, $\|v_2\|^2=1/4+1/4+1=3/2$ and $\|v_3\|^2=1/9+1/9+1/9+1=4/3$; the displayed scaling factors make all three norms equal to $1$. Each vector has coordinate sum zero and each pair has dot product zero. Since $v_i=\|v_i\|u_i$, each $v_i$ is recovered from $u_i$ by scaling, so normalization preserves both directions of every span equality. The nullspace has dimension $3$, so these vectors form an orthonormal basis of $V$.

The $\mathbb R^4$ arithmetic also verifies the span claim in both directions. From the three definitions,

$$w_2=v_2+\frac12v_1,\qquad w_3=v_3+\frac12v_1+\frac13v_2.$$

Conversely, each displayed $v_i$ is built from the corresponding $w_i$ and previous vectors. Thus the change from $w$ to $v$ is triangular with diagonal coefficient $1$, so no direction is lost. The normalized vectors stay in $V$: for $u_1$ the coordinate sum is $(-1+1)/\sqrt2=0$, for $u_2$ it is $(-1-1+2)/\sqrt6=0$, and for $u_3$ it is $(-1-1-1+3)/\sqrt{12}=0$. Their squared lengths are respectively $2/2$, $(1+1+4)/6$, and $(1+1+1+9)/12$, all equal to $1$. These coordinate checks certify the constraint and the normalization independently of the orthogonality calculation.

Theorem

Every finite-dimensional subspace has an orthonormal basis

Every subspace of $\mathbb{R}^m$ has a finite basis. In positive dimension, Gram-Schmidt gives a nonzero orthogonal basis, and normalization gives an orthonormal basis. The zero subspace has the empty basis, already orthogonal and orthonormal by the empty-list convention; no division by a norm occurs.

Common mistake

Dependent input creates a zero remainder

If $w_1=(1,0)^T$ and $w_2=(2,0)^T$, then

$$v_2=w_2-\frac{\langle w_2,v_1\rangle}{\|v_1\|^2}v_1 =(2,0)^T-2(1,0)^T=0.$$

The next normalization would be undefined. Remove redundant vectors first; Gram-Schmidt is designed for an independent ordered list.

Quick checks

Checkpoint

What is the first Gram-Schmidt vector $v_1$?

Read the first line of the recursive definition.

Solution · Answer

It is $v_1=w_1$; the first input direction is retained.

Checkpoint

What property does Gram-Schmidt preserve besides orthogonality?

Use the partial-span equality.

Solution · Answer

It preserves every partial span: $\operatorname{span}\{w_1,\dots,w_\ell\}=\operatorname{span}\{v_1,\dots,v_\ell\}$.

Checkpoint

How do you turn an orthogonal basis into an orthonormal basis?

Use the norm of each constructed vector.

Solution · Answer

For every nonzero $v_i$, divide by its norm: $u_i=v_i/\|v_i\|$.

Checkpoint

Apply the first two steps to $w_1=(1,2,0)$ and $w_2=(2,0,1)$.

Compute $v_1$, then the single projection coefficient.

Solution · Guided solution

$v_1=(1,2,0)^T$, and the projection coefficient is $\langle w_2,v_1\rangle/\|v_1\|^2=2/5$. Hence

$$v_2=(2,0,1)^T-\frac25(1,2,0)^T=(8/5,-4/5,1)^T.$$

Check $v_1\cdot v_2=8/5-8/5=0$. Also $w_2=v_2+\frac25v_1$, so the old and new pairs span the same plane.

Checkpoint

Why is a zero remainder a warning for an independent input list?

Relate a zero remainder to the earlier span.

Solution · Guided solution

The remainder is zero exactly when the current vector lies in the earlier span, which contradicts independence.

Checkpoint

Suppose orthogonal vectors $v_1,v_2$ have norms 3 and 4. What are the corresponding unit vectors?

Normalize each vector separately.

Solution · Guided solution

They are $u_1=v_1/3$ and $u_2=v_2/4$; both have norm $1$ and remain orthogonal.

Related notes

Read 9.2 Orthogonal sets and orthonormal bases first, because Gram-Schmidt uses the orthogonal coefficient formula. The constraint-space example also uses the nullspace and basis methods from 6.2 Subspaces and 6.5 Basis and dimension.

The next note, 9.4 Cauchy-Schwarz and triangle inequalities, develops inequalities that bound these inner-product calculations.