6.4 The Gram-Schmidt process

Big idea

The projection formula needs an orthogonal basis. Most subspaces arrive with a basis that is not orthogonal, so something has to manufacture one.

The construction is short. Keep the first vector. For the second, subtract off its projection onto the first, which removes exactly the part that overlapped and leaves something perpendicular. For the third, subtract its projections onto both of the previous results. Continue. At every stage the new vector is the old one minus everything already accounted for.

Nothing is lost along the way. After $k$ steps the new vectors span exactly what the first $k$ old vectors spanned, so the process converts a basis into an orthogonal basis for the same subspace, not for a different one. Normalizing at the end makes it orthonormal, and bookkeeping the coefficients turns the whole run into a matrix factorization.

Decoder

“Subtract the projection” is one instruction doing two jobs. The projection is the part of the new vector that the earlier vectors can already build; removing it guarantees the remainder is orthogonal to all of them. So the step is both a cleanup (drop the redundant part) and an orthogonalization (what remains cannot be reached by the earlier vectors at all).

One practical note that textbook statements leave implicit: at any stage you may replace the vector you just produced by any nonzero scalar multiple of it. Orthogonality is unaffected and the span is unaffected. Clearing fractions immediately keeps every later dot product in whole numbers, and it is worth doing by hand every time.

Definitions and results

The process. Given a basis $\{\mathbf{x}_1, \dots, \mathbf{x}_p\}$ for a subspace $W$, define

$$ \mathbf{v}_1 = \mathbf{x}_1 $$

$$ \mathbf{v}_2 = \mathbf{x}_2 - \frac{\mathbf{x}_2 \cdot \mathbf{v}_1}{\mathbf{v}_1 \cdot \mathbf{v}_1}\mathbf{v}_1 $$

$$ \mathbf{v}_3 = \mathbf{x}_3 - \frac{\mathbf{x}_3 \cdot \mathbf{v}_1}{\mathbf{v}_1 \cdot \mathbf{v}_1}\mathbf{v}_1 - \frac{\mathbf{x}_3 \cdot \mathbf{v}_2}{\mathbf{v}_2 \cdot \mathbf{v}_2}\mathbf{v}_2 $$

and so on, each $\mathbf{v}_k$ being $\mathbf{x}_k$ minus its projection onto the span of the previous results. Then $\{\mathbf{v}_1, \dots, \mathbf{v}_p\}$ is an orthogonal basis for $W$, and for each $k$ the first $k$ of them span the same subspace as the first $k$ of the originals.

Why no vector dies. Each $\mathbf{v}_k$ is nonzero, because $\mathbf{v}_k = \mathbf{0}$ would mean $\mathbf{x}_k$ is a combination of the earlier vectors, contradicting independence. If you run the process on a dependent list, a zero does appear, and that is a signal to discard that vector and continue.

Order matters, the answer does not. Feeding the same vectors in a different order produces a different orthogonal basis. Both are valid, and both give the same projection for any target, since the projection depends on the subspace alone.

Orthonormal basis. Divide each $\mathbf{v}_k$ by its length. The result is an orthonormal basis for $W$, usually written $\{\mathbf{q}_1, \dots, \mathbf{q}_p\}$.

QR factorization. If $A$ is $m \times n$ with linearly independent columns, then $A = QR$, where $Q$ is $m \times n$ with orthonormal columns produced by this process, and $R$ is $n \times n$, upper triangular, with positive diagonal entries. The entries of $R$ are the coefficients that rebuild the original columns from the orthonormal ones, and they can be read off as $R = Q^TA$: entry $(i,j)$ is $\mathbf{q}_i \cdot \mathbf{a}_j$. $R$ is upper triangular because $\mathbf{a}_j$ lies in the span of the first $j$ orthonormal vectors, so its later coordinates are zero.

Why the factorization is useful. $Q$ inverts by transposing and $R$ solves by back substitution, so a system $A\mathbf{x} = \mathbf{b}$ with independent columns becomes $R\mathbf{x} = Q^T\mathbf{b}$, which costs no elimination. The next section reuses exactly this to solve least-squares problems.

Checking your work. After each step, dot the new vector against every earlier one and confirm you get zero. Errors in this process compound: a wrong $\mathbf{v}_2$ corrupts $\mathbf{v}_3$ and everything after it, and the final set will fail an orthogonality check with no indication of which step went wrong. Testing at each step localizes the mistake to one subtraction.

Where it is used. Beyond producing bases for the projection formula, the process supplies the orthonormal columns that make a projection matrix cheap, it factors a matrix for solving least-squares problems, and it runs unchanged in any inner product space, which is how orthogonal families of polynomials get built later in the chapter.

Worked examples

Orthogonalizing three vectors

Start with

$$ \mathbf{x}_1 = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \qquad \mathbf{x}_2 = \begin{bmatrix} 2 \\ 0 \\ 1 \end{bmatrix}, \qquad \mathbf{x}_3 = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} $$

The determinant of the matrix with these columns is $-3$, so they are independent and span $\mathbb{R}^3$.

Step one: $\mathbf{v}_1 = \mathbf{x}_1 = (1,1,0)$, with $\mathbf{v}_1 \cdot \mathbf{v}_1 = 2$.

Step two: $\mathbf{x}_2 \cdot \mathbf{v}_1 = 2 + 0 + 0 = 2$, so the coefficient is $2/2 = 1$ and

$$ \mathbf{v}_2 = \begin{bmatrix} 2 \\ 0 \\ 1 \end{bmatrix} - \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ -1 \\ 1 \end{bmatrix} $$

Check: $\mathbf{v}_2 \cdot \mathbf{v}_1 = 1 - 1 + 0 = 0$. Also $\mathbf{v}_2 \cdot \mathbf{v}_2 = 3$.

Step three: $\mathbf{x}_3 \cdot \mathbf{v}_1 = 0 + 1 + 0 = 1$, giving coefficient $1/2$, and $\mathbf{x}_3 \cdot \mathbf{v}_2 = 0 - 1 + 1 = 0$, giving coefficient $0$. So

$$ \mathbf{v}_3 = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} - \frac{1}{2}\begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} -1/2 \\ 1/2 \\ 1 \end{bmatrix} $$

Rescale by $2$ to clear the fractions: $\mathbf{v}_3' = (-1, 1, 2)$.

Check all three pairs: $\mathbf{v}_1 \cdot \mathbf{v}_2 = 0$ as computed, $\mathbf{v}_1 \cdot \mathbf{v}_3' = -1 + 1 + 0 = 0$, and $\mathbf{v}_2 \cdot \mathbf{v}_3' = -1 - 1 + 2 = 0$. An orthogonal basis for $\mathbb{R}^3$.

To make it orthonormal, divide by the lengths $\sqrt{2}$, $\sqrt{3}$, and $\sqrt{6}$.

A QR factorization by hand

Let $A$ have the first two vectors above as columns:

$$ A = \begin{bmatrix} 1 & 2 \\ 1 & 0 \\ 0 & 1 \end{bmatrix} $$

From the previous example the orthogonal pair is $(1,1,0)$ and $(1,-1,1)$, so

$$ \mathbf{q}_1 = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \qquad \mathbf{q}_2 = \frac{1}{\sqrt{3}}\begin{bmatrix} 1 \\ -1 \\ 1 \end{bmatrix} $$

Compute $R = Q^TA$ entry by entry. $\mathbf{q}_1 \cdot \mathbf{a}_1 = 2/\sqrt{2} = \sqrt{2}$. $\mathbf{q}_1 \cdot \mathbf{a}_2 = 2/\sqrt{2} = \sqrt{2}$. $\mathbf{q}_2 \cdot \mathbf{a}_1 = (1 - 1 + 0)/\sqrt{3} = 0$, as the triangular shape requires. $\mathbf{q}_2 \cdot \mathbf{a}_2 = (2 - 0 + 1)/\sqrt{3} = \sqrt{3}$.

$$ R = \begin{bmatrix} \sqrt{2} & \sqrt{2} \\ 0 & \sqrt{3} \end{bmatrix} $$

Check the product column by column. The first column of $QR$ is $\sqrt{2}\,\mathbf{q}_1 = (1,1,0)$, which is $\mathbf{a}_1$. The second is $\sqrt{2}\,\mathbf{q}_1 + \sqrt{3}\,\mathbf{q}_2 = (1,1,0) + (1,-1,1) = (2,0,1)$, which is $\mathbf{a}_2$. The factorization is correct, and the diagonal entries $\sqrt{2}$ and $\sqrt{3}$ are the lengths of the orthogonal vectors the process produced.

Practice

Run the process on small bases: subtract the projections, rescale to keep the arithmetic clean, and verify the pairwise dot products before moving on.

Then confirm what you produced is genuinely an orthogonal or orthonormal set.

Videos

The second half of the lecture runs the process and derives the factorization. Watch for the point where the triangular shape of the second factor is explained by which vectors were available at each step.

Quiz

Five items on orthogonalizing a basis and checking the result.