6.4 Orthogonal Sets and Gram-Schmidt

The least-squares computation of the last section was heavy in a specific way. Fitting a plane to seven points meant assembling the normal equations and solving a $3 \times 3$ system, and the reason was that the model's columns were oblique — the $x$ -column overlapped both of the others, so no coefficient could be settled without settling the rest at once. (Not every pair was at fault: on that particular data the $y$ -column and the column of ones happen to be orthogonal already. One oblique pair is enough to force the system.)

Suppose the spanning vectors had been mutually perpendicular. Then projecting onto their span would decompose completely: for an orthogonal set $\mathbf{u}_1, \dots, \mathbf{u}_k$ the projection of any vector $\mathbf{y}$ is

$\operatorname{proj}(\mathbf{y}) = \frac{\mathbf{y} \cdot \mathbf{u}_1}{\mathbf{u}_1 \cdot \mathbf{u}_1}\,\mathbf{u}_1 + \dots + \frac{\mathbf{y} \cdot \mathbf{u}_k}{\mathbf{u}_k \cdot \mathbf{u}_k}\,\mathbf{u}_k$

with each coefficient computed on its own, from two dot products, with no system to solve. The formula is right precisely because the vectors do not overlap: adding a multiple of $\mathbf{u}_2$ changes nothing about the $\mathbf{u}_1$ component, since their dot product is zero.

So it is worth having a way to manufacture orthogonality. Start with vectors that span what you want but sit at awkward angles:

$\mathbf{v}_1 = (1, 1, 0), \qquad \mathbf{v}_2 = (1, 0, 1), \qquad \mathbf{v}_3 = (0, 1, 1)$

They are independent — their determinant is not zero — so they are a basis of $\mathbb{R}^3$ , just not a convenient one.

-2

A basis, but an awkward one ✓ Computed · mojocas 0.1.0 ✓ Agrees with the text

The determinant of the three starting vectors is $-2$ , so by the Invertible Matrix Theorem they are independent and span $\mathbb{R}^3$ . Nothing is wrong with this basis except its angles: $\mathbf{v}_1 \cdot \mathbf{v}_2 = 1$ , not $0$ , so the vectors overlap and projections onto their span cannot be computed one coefficient at a time.

One step, watched

Gram-Schmidt fixes the angles one vector at a time. Keep the first vector as it is, $\mathbf{u}_1 = \mathbf{v}_1$ . Then take $\mathbf{v}_2$ and remove the part of it that points along $\mathbf{u}_1$ — its projection — leaving only what is perpendicular:

$\mathbf{u}_2 = \mathbf{v}_2 - \frac{\mathbf{v}_2 \cdot \mathbf{u}_1}{\mathbf{u}_1 \cdot \mathbf{u}_1}\,\mathbf{u}_1 = (1, 0, 1) - \tfrac{1}{2}(1, 1, 0) = (0.5, \; -0.5, \; 1)$

using $\mathbf{v}_2 \cdot \mathbf{u}_1 = 1$ and $\mathbf{u}_1 \cdot \mathbf{u}_1 = 2$ . Check the result: $\mathbf{u}_1 \cdot \mathbf{u}_2 = 0.5 - 0.5 + 0 = 0$ , as intended.

A semi-transparent tilted plane holding two vectors, drawn as segments that both start at a marked origin: a fixed red one and a blue one that swings as a slider is dragged. A small gray dot partway along the red segment marks where the projection of the blue vector's starting position onto the red one ends, and an amber segment runs from the blue vector's original tip to its current tip, showing the correction being removed. The slider starts halfway. At the start of its range the two vectors meet at a noticeably acute angle and the amber segment has no length; at the end of its range they meet at a right angle and the amber segment is as long as the projection, from the origin to the gray dot. Throughout, both vectors stay inside the same plane, so the pair always describes the same set of combinations. — The plane spanned by $\mathbf{v}_1$ and $\mathbf{v}_2$ , with the red $\mathbf{u}_1 = (1, 1, 0)$ fixed and the blue vector swinging as the slider $a$ subtracts more and more of the projection. The gray dot partway along the red one marks the tip of the projection $(0.5, 0.5, 0)$ being removed, and the amber segment joins the blue vector's original tip to its current one. The slider starts halfway, at $a = 0.5$ .

Explore the figure

Set $a = 0$ . The blue vector is now $\mathbf{v}_2 = (1, 0, 1)$ , the amber segment has shrunk to nothing, and the two vectors meet at an obviously acute angle. This is the awkward basis you started with.
Drag $a$ to $1$ . The blue vector swings to $(0.5, -0.5, 1) = \mathbf{u}_2$ and now meets the red one at a right angle. The amber segment has grown to exactly the length of the projection — the distance from the origin to the gray dot — but it runs the opposite way to the projection: from the old tip to the new, because the projection is being subtracted rather than added.
Watch the plane while you drag, not the vectors. The blue vector stays inside the sheet the whole way. It has to: you only ever subtracted a multiple of $\mathbf{u}_1$ , which is itself in the sheet.
That is the property worth keeping. At every slider setting the red and blue vectors span the same plane, so Gram-Schmidt has changed the description without changing the thing described.

Doing all three

The third vector must be cleared of both previous directions, so subtract both projections:

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

The dot products are $\mathbf{v}_3 \cdot \mathbf{u}_1 = 1$ against $\mathbf{u}_1 \cdot \mathbf{u}_1 = 2$ , giving coefficient $\tfrac12$ ; and $\mathbf{v}_3 \cdot \mathbf{u}_2 = 0(0.5) + 1(-0.5) + 1(1) = 0.5$ against $\mathbf{u}_2 \cdot \mathbf{u}_2 = 0.25 + 0.25 + 1 = 1.5$ , giving coefficient $\tfrac13$ . So

$\mathbf{u}_3 = (0, 1, 1) - \tfrac{1}{2}(1, 1, 0) - \tfrac{1}{3}(0.5, -0.5, 1) = \left(-\tfrac{2}{3}, \; \tfrac{2}{3}, \; \tfrac{2}{3}\right)$

and the three are now mutually perpendicular: $\mathbf{u}_1 \cdot \mathbf{u}_3 = -\tfrac23 + \tfrac23 + 0 = 0$ , and $\mathbf{u}_2 \cdot \mathbf{u}_3 = -\tfrac13 - \tfrac13 + \tfrac23 = 0$ .

Notice that subtracting the $\mathbf{u}_2$ projection did not disturb the $\mathbf{u}_1$ work already done — because $\mathbf{u}_1$ and $\mathbf{u}_2$ are perpendicular, adding a multiple of one leaves the other's component untouched. Each step is safe from the steps before it, which is what makes the process work at all rather than chasing its own tail.

Example 1 Projection, the cheap way

Project $\mathbf{y} = (3, 1, 0)$ onto the plane spanned by $\mathbf{v}_1$ and $\mathbf{v}_2$ , using the orthogonal pair $\mathbf{u}_1, \mathbf{u}_2$ .

Show solution

With an orthogonal basis the two coefficients are independent, so compute them separately.

Against $\mathbf{u}_1 = (1, 1, 0)$ : $\mathbf{y} \cdot \mathbf{u}_1 = 3 + 1 + 0 = 4$ and $\mathbf{u}_1 \cdot \mathbf{u}_1 = 2$ , so the coefficient is $2$ .

Against $\mathbf{u}_2 = (0.5, -0.5, 1)$ : $\mathbf{y} \cdot \mathbf{u}_2 = 1.5 - 0.5 + 0 = 1$ and $\mathbf{u}_2 \cdot \mathbf{u}_2 = 1.5$ , so the coefficient is $\tfrac{2}{3}$ .

Therefore

$\operatorname{proj}(\mathbf{y}) = 2\,(1, 1, 0) + \tfrac{2}{3}\,(0.5, -0.5, 1) = (2, 2, 0) + \left(\tfrac13, -\tfrac13, \tfrac23\right) = \left(\tfrac73, \tfrac53, \tfrac23\right)$

Check it lands in the plane $z = x - y$ : $\tfrac73 - \tfrac53 = \tfrac23$ , matching the third coordinate. The residual is $\mathbf{y} - \operatorname{proj}(\mathbf{y}) = \left(\tfrac23, -\tfrac23, -\tfrac23\right)$ , and it is perpendicular to both basis vectors — $\tfrac23 - \tfrac23 + 0 = 0$ against $\mathbf{u}_1$ , and $\tfrac13 + \tfrac13 - \tfrac23 = 0$ against $\mathbf{u}_2$ — which is the certificate that nothing in the plane is closer.

Had the basis been the original oblique $\mathbf{v}_1, \mathbf{v}_2$ , this would have required assembling and solving the normal equations. Four dot products replaced a linear system, and that saving is the whole reason to orthogonalize.

An original work of XYZ Homework, built around interactive XYZ 3D figures. Chapters 1–6 follow the topic sequence of Interactive Linear Algebra (Margalit & Rabinoff, Georgia Tech, GNU FDL). Chapter 0's scope (its topics, their order, and the idea each figure shows) follows the Vectors chapter of Ximera's Linear Algebra: An Interactive Introduction. The prose, worked examples and figures were written for this book, which is not affiliated with or endorsed by the authors of either work. License: CC-BY-NC-SA-4.0.