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 $𝐮 sub 1, and so on, 𝐮 sub k$ the projection of any vector $𝐲$ is

$proj (𝐲) = \frac{𝐲 \cdot 𝐮_{1}}{𝐮_{1} \cdot 𝐮_{1}} 𝐮_{1} + \dots + \frac{𝐲 \cdot 𝐮_{k}}{𝐮_{k} \cdot 𝐮_{k}} 𝐮_{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 $𝐮 sub 2$ changes nothing about the $𝐮 sub 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:

$𝐯_{1} = (1, 1, 0), 𝐯_{2} = (1, 0, 1), 𝐯_{3} = (0, 1, 1)$

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

minus 2

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

The determinant of the three starting vectors is $minus 2$ , so by the Invertible Matrix Theorem they are independent and span $ℝ^{3}$ . Nothing is wrong with this basis except its angles: $𝐯_{1} \cdot 𝐯_{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, $𝐮 sub 1 equals 𝐯 sub 1$ . Then take $𝐯 sub 2$ and remove the part of it that points along $𝐮 sub 1$ — its projection — leaving only what is perpendicular:

$𝐮_{2} = 𝐯_{2} - \frac{𝐯_{2} \cdot 𝐮_{1}}{𝐮_{1} \cdot 𝐮_{1}} 𝐮_{1} = (1, 0, 1) - \frac{1}{2} (1, 1, 0) = (0.5, - 0.5, 1)$

using $𝐯_{2} \cdot 𝐮_{1} = 1$ and $𝐮_{1} \cdot 𝐮_{1} = 2$ . Check the result: $𝐮_{1} \cdot 𝐮_{2} = 0.5 - 0.5 + 0 = 0$ , as intended.

A semi-transparent tilted plane holding two arrows that both start at a marked origin: a fixed red one and a blue one that swings as a slider is dragged. A short dashed gray arrow along the red one marks the projection of the blue vector onto it, and a dashed amber segment runs from the blue arrow's original tip to its current tip, showing the correction being removed. At the start of the slider the two arrows meet at a noticeably acute angle; at the end of the slider they meet at a right angle. Throughout, both arrows stay inside the same plane, so the pair always describes the same set of combinations. — The plane spanned by $𝐯 sub 1$ and $𝐯 sub 2$ , with the red $𝐮 sub 1 equals open parenthesis 1, 1, 0 close parenthesis$ fixed and the blue vector swinging as the slider $a$ subtracts more and more of the projection. The short dashed gray arrow along the red one is the projection $open parenthesis 0.5, 0.5, 0 close parenthesis$ being removed, and the dashed amber segment joins the blue vector's original tip to its current one.

Explore the figure

At $a equals 0$ the blue vector is $𝐯 sub 2 equals open parenthesis 1, 0, 1 close parenthesis$ and the two arrows 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) = 𝐮_{2}$ and now meets the red one at a right angle. The dashed amber segment has grown to exactly the length of the gray projection arrow, but it points the opposite way: it runs from the old tip to the new, because the projection is being subtracted rather than added.
Watch the plane while you drag, not the arrows. The blue vector stays inside the sheet the whole way. It has to: you only ever subtracted a multiple of $𝐮 sub 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:

$𝐮_{3} = 𝐯_{3} - \frac{𝐯_{3} \cdot 𝐮_{1}}{𝐮_{1} \cdot 𝐮_{1}} 𝐮_{1} - \frac{𝐯_{3} \cdot 𝐮_{2}}{𝐮_{2} \cdot 𝐮_{2}} 𝐮_{2}$

The dot products are $𝐯_{3} \cdot 𝐮_{1} = 1$ against $𝐮_{1} \cdot 𝐮_{1} = 2$ , giving coefficient $\frac{1}{2}$ ; and $𝐯_{3} \cdot 𝐮_{2} = 0 (0.5) + 1 (- 0.5) + 1 (1) = 0.5$ against $𝐮_{2} \cdot 𝐮_{2} = 0.25 + 0.25 + 1 = 1.5$ , giving coefficient $\frac{1}{3}$ . So

$𝐮_{3} = (0, 1, 1) - \frac{1}{2} (1, 1, 0) - \frac{1}{3} (0.5, - 0.5, 1) = (- \frac{2}{3}, \frac{2}{3}, \frac{2}{3})$

and the three are now mutually perpendicular: $𝐮_{1} \cdot 𝐮_{3} = - \frac{2}{3} + \frac{2}{3} + 0 = 0$ , and $𝐮_{2} \cdot 𝐮_{3} = - \frac{1}{3} - \frac{1}{3} + \frac{2}{3} = 0$ .

Notice that subtracting the $𝐮 sub 2$ projection did not disturb the $𝐮 sub 1$ work already done — because $𝐮 sub 1$ and $𝐮 sub 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 $𝐲 equals open parenthesis 3, 1, 0 close parenthesis$ onto the plane spanned by $𝐯 sub 1$ and $𝐯 sub 2$ , using the orthogonal pair $𝐮 sub 1, 𝐮 sub 2$ .

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

Against $𝐮 sub 1 equals open parenthesis 1, 1, 0 close parenthesis$ : $𝐲 \cdot 𝐮_{1} = 3 + 1 + 0 = 4$ and $𝐮_{1} \cdot 𝐮_{1} = 2$ , so the coefficient is $2$ .

Against $𝐮_{2} = (0.5, - 0.5, 1)$ : $𝐲 \cdot 𝐮_{2} = 1.5 - 0.5 + 0 = 1$ and $𝐮_{2} \cdot 𝐮_{2} = 1.5$ , so the coefficient is $\frac{2}{3}$ .

Therefore

$proj (𝐲) = 2 (1, 1, 0) + \frac{2}{3} (0.5, - 0.5, 1) = (2, 2, 0) + (\frac{1}{3}, - \frac{1}{3}, \frac{2}{3}) = (\frac{7}{3}, \frac{5}{3}, \frac{2}{3})$

Check it lands in the plane $z = x - y$ : $\frac{7}{3} - \frac{5}{3} = \frac{2}{3}$ , matching the third coordinate. The residual is $𝐲 - proj (𝐲) = (\frac{2}{3}, - \frac{2}{3}, - \frac{2}{3})$ , and it is perpendicular to both basis vectors — $\frac{2}{3} - \frac{2}{3} + 0 = 0$ against $𝐮 sub 1$ , and $\frac{1}{3} + \frac{1}{3} - \frac{2}{3} = 0$ against $𝐮 sub 2$ — which is the certificate that nothing in the plane is closer.

Had the basis been the original oblique $𝐯 sub 1, 𝐯 sub 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. Its chapter sequence is aligned to Interactive Linear Algebra (Margalit & Rabinoff, Georgia Tech, GNU FDL); this work is original, copies nothing from it, and is not affiliated with or endorsed by its authors. License: CC-BY-NC-SA-4.0.