Gram-Schmidt orthogonalization

Real inner products, their norms and the needed inequalities

An inner product on a real vector space is a map $\langle u,v\rangle\in\mathbb R$ that is symmetric, linear in each argument, and positive definite: $\langle v,v\rangle>0$ for $v\ne0$. Linearity gives $\langle0,v\rangle=0$. Define $\|v\|=\sqrt{\langle v,v\rangle}$. It is zero exactly at zero and satisfies $\|cv\|=|c|\|v\|$. The standard example on $\mathbb R^m$ is $\langle u,v\rangle=\sum_{i=1}^mu_iv_i$. Vectors are orthogonal when their inner product is zero, and a list is orthonormal when distinct members are orthogonal and each member has norm one.

If $v\ne0$, insert $t=\langle u,v\rangle/\|v\|^2$ into the nonnegative square $\|u-tv\|^2$. Expanding by bilinearity gives $\|u\|^2-\langle u,v\rangle^2/\|v\|^2\ge0$, hence $|\langle u,v\rangle|\le\|u\|\|v\|$. If $v=0$ the same inequality holds directly. Equality for $v\ne0$ means $\|u-tv\|=0$, equivalently $u=tv$; the zero-vector cases also give equality. Finally expand $\|u+v\|^2$ and apply the bound to its cross term to obtain $\|u+v\|^2\le(\|u\|+\|v\|)^2$. Both sides to be square-rooted are nonnegative, so the triangle inequality follows. Thus this is a norm, and normalization of any nonzero vector divides by a positive real number. No complex bilinear convention is being used.

Finite basis existence and extension, without a counting assumption

Let $V$ be a real vector space supplied with a finite spanning list $t_1,\ldots,t_N$. First prove that every independent list $u_1,\ldots,u_k$ has length at most $N$. After $j$ insertions, maintain a spanning list consisting of $u_1,\ldots,u_j$ and $N-j$ surviving old vectors. Expand $u_{j+1}$ in this list. Some coefficient on a surviving old vector is nonzero; otherwise $u_{j+1}$ would be in the span of the earlier $u_i$, contradicting independence. Solve for that old vector and replace it by $u_{j+1}$. The new list spans the same space and keeps every earlier insertion. If $k>N$, after $N$ steps the first $N$ independent vectors already span $V$, contradicting independence of $u_{N+1}$. This proves the bound, including $N=0$.

Every subspace $W$ has a finite basis. Start with the empty independent list. If its current span is not $W$, choose one vector of $W$ outside that span. A relation with nonzero coefficient on the new vector would express it in the old span, so the enlarged list remains independent. The proved bound permits at most $N$ additions; therefore the process stops with an independent spanning list for $W$. If $W=\{0\}$, it stops immediately with the empty basis. Starting instead with any given independent list in $W$ proves that list extends to a basis of $W$. Only a bounded finite selection is used. Finally, if two bases have sizes $p,q$, use each as the finite spanning list in the bound to obtain $p\le q$ and $q\le p$. Thus basis size, called dimension, is well-defined. This supplies the existence, extension and dimension facts used in rank–nullity.

Orthonormal bases and extension while retaining prescribed vectors

Suppose in addition that $V$ has a real positive-definite inner product. On an independent list $v_1,\ldots,v_s$, define successively

$$w_j=v_j-\sum_{i<j}\langle v_j,q_i\rangle q_i,\qquad q_j=w_j/\|w_j\|.$$

Inductively the previous $q_i$ are orthonormal. For $l<j$, taking the inner product with $q_l$ gives $\langle w_j,q_l\rangle=\langle v_j,q_l\rangle-\langle v_j,q_l\rangle=0$. If $w_j=0$, then $v_j$ lies in the previous span, a contradiction. Division by its positive norm is therefore legal. The displayed formula and its rearrangement show that the first $j$ old and new vectors span the same space, completing the induction. Apply this to a basis to obtain an orthonormal basis, also for a subspace. To extend a prescribed orthonormal list, first extend it to an ordinary basis by the proved theorem and then apply this construction in that order. On the prescribed first vectors no component is subtracted and the norm is one, so every prescribed vector is retained exactly. Empty lists and the zero subspace require no division. This proves the orthonormal extension used in SVD and projection existence.

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.