6.4 Orthogonal projection and Gram–Schmidt

Let $𝑊$ be a subspace of an inner product space $𝑉$ , and let $𝐯 \in 𝑉$ . Which vector of $𝑊$ is closest to $𝐯$ ? When $𝑊$ is a plane through $𝟎$ in $ℝ^{3}$ , geometry gives the answer: drop the perpendicular from $𝐯$ to $𝑊$ , and take its foot. This section turns that answer into a theorem about every inner product space, provided $𝑊$ is finite-dimensional. The foot of the perpendicular is the orthogonal projection ${Pr}_{𝑊} (𝐯)$ . If $𝑊$ has an orthonormal basis, it is given by the formula from the proof of Bessel’s inequality (Theorem 6.3.24), and the Gram–Schmidt algorithm produces an orthonormal basis of every finite-dimensional subspace. The leftover vectors $𝐯 - {Pr}_{𝑊} (𝐯)$ make up the orthogonal complement $𝑊^{⟂}$ , which turns out to be a complement of $𝑊$ in the sense of Section 4.4. Since distances also make sense between functions, the same theorem answers questions such as: which quadratic polynomial is closest to $𝑒^{𝑡}$ on $[- 1, 1]$ ?

Throughout, $𝑉$ is an inner product space over $𝔽$ , where $𝔽$ is $ℝ$ or $ℂ$ (Notation 6.1.1). We do not assume that $𝑉$ is finite-dimensional. The subspaces we project onto will be finite-dimensional, but the ambient space is often a space of functions.

6.4.1Projecting onto the span of an orthonormal list

Intuition (From a line to a plane). In Section 6.2.1 we split a vector $𝐱$ against a nonzero vector $𝐲$ as $𝐱 = 𝑐 𝐲 + 𝐰$ , where $𝑐 𝐲$ lies on the line $span (𝐲)$ and $𝐰 ⟂ 𝐲$ (Figure 6.2.1). The vector $𝑐 𝐲$ is the foot of the perpendicular from $𝐱$ to the line, and the requirement $𝐰 ⟂ 𝐲$ forced $𝑐 = ⟨ 𝐱, 𝐲 ⟩ / {‖ 𝐲 ‖}^{2}$ .

Now replace the line by a plane $𝑊$ in $ℝ^{3}$ spanned by orthonormal vectors $𝐮_{1}, 𝐮_{2}$ , and look for the foot $𝐩$ of the perpendicular from $𝐯$ to $𝑊$ . That is, we want $𝐩 \in 𝑊$ such that $𝐯 - 𝐩$ is perpendicular to $𝑊$ . Write $𝐩 = 𝑎_{1} 𝐮_{1} + 𝑎_{2} 𝐮_{2}$ . By Proposition 6.3.9(c), $𝐯 - 𝐩 ⟂ 𝑊$ means that $𝐯 - 𝐩 ⟂ 𝐮_{𝑗}$ for $𝑗 = 1, 2$ , and taking the inner product with $𝐮_{𝑗}$ isolates the coefficient $𝑎_{𝑗}$ (Technique 6.3.12):

0 = ⟨ 𝐯 - 𝐩, 𝐮_{𝑗} ⟩ = ⟨ 𝐯, 𝐮_{𝑗} ⟩ - 𝑎_{𝑗} .

So $𝐩 =$ $⟨ 𝐯, 𝐮_{1} ⟩ 𝐮_{1} +$ $⟨ 𝐯, 𝐮_{2} ⟩ 𝐮_{2}$ . Each term is the shadow of $𝐯$ on one of the lines $span (𝐮_{1})$ and $span (𝐮_{2})$ . So the foot of the perpendicular to the plane is the sum of the feet of the perpendiculars to the two lines (Figure 6.4.1).

The shadows can be computed separately and then added because $𝐮_{1} ⟂ 𝐮_{2}$ . For a basis of $𝑊$ that is not orthogonal, the sum of the shadows is not the foot; see the example after Corollary 6.3.21.

Figure 6.4.1. Projecting

𝐯

onto the shaded plane

𝑊 = span (𝐮_{1}, 𝐮_{2})

, for orthonormal

𝐮_{1}, 𝐮_{2}

. The foot

{Pr}_{𝒪︀} (𝐯)

of the perpendicular is the sum of the shadows

⟨ 𝐯, 𝐮_{1} ⟩ 𝐮_{1}

and

⟨ 𝐯, 𝐮_{2} ⟩ 𝐮_{2}

𝐯

on the two axes, and

𝐯 - {Pr}_{𝒪︀} (𝐯)

is perpendicular to

𝑊

Definition 6.4.1 (Projection onto the span of an orthonormal list). Let $𝒪︀ = 𝐮_{1}, \dots, 𝐮_{𝑘}$ be an orthonormal list in $𝑉$ . The projection onto $span (𝒪︀)$ is the function ${Pr}_{𝒪︀} : 𝑉 \to 𝑉$ given by

{Pr}_{𝒪︀} (𝐯) = ⟨ 𝐯, 𝐮_{1} ⟩ 𝐮_{1} + \dots + ⟨ 𝐯, 𝐮_{𝑘} ⟩ 𝐮_{𝑘} .

If $𝑘 = 0$ , the sum is empty and ${Pr}_{𝒪︀} (𝐯) = 𝟎$ .

This is the vector $𝐩$ from the proof of Bessel’s inequality (Theorem 6.3.24). As with coordinates (Remark 6.3.19), $𝐯$ goes in the first slot. For a single unit vector $𝐮$ , ${Pr}_{𝐮} (𝐯) =$ $⟨ 𝐯, 𝐮 ⟩ 𝐮$ is the shadow of Technique 6.2.4, since there $𝑐 =$ $⟨ 𝐯, 𝐮 ⟩ / {‖ 𝐮 ‖}^{2} =$ $⟨ 𝐯, 𝐮 ⟩$ .

Example 6.4.2 (A projection in $ℝ^{3}$ ). Take the orthonormal list $𝒪︀ = 𝐮_{1}, 𝐮_{2}$ with $𝐮_{1} = \frac{1}{3} (1, 2, 2)$ and $𝐮_{2} = \frac{1}{3} (2, 1, - 2)$ from Example 6.3.16(c), and $𝐯 = (1, 2, 3)$ . In Example 6.3.20 we computed $⟨ 𝐯, 𝐮_{1} ⟩ = 11 / 3$ and $⟨ 𝐯, 𝐮_{2} ⟩ = - 2 / 3$ . So

{Pr}_{𝒪︀} (𝐯) = \frac{11}{9} (1, 2, 2) - \frac{2}{9} (2, 1, - 2) = \frac{1}{9} (7, 20, 26),

and $𝐯 -$ ${Pr}_{𝒪︀} (𝐯) =$ $\frac{1}{9} (2, - 2, 1)$ . This vector is orthogonal to $(1, 2, 2)$ and to $(2, 1, - 2)$ , as the intuition above predicts. Its squared length is $9 / 81 = 1 / 9$ , the deficit in Bessel’s inequality found in Example 6.3.25.

Example 6.4.3 (Projecting a function). Give $𝐶 [- 1, 1]$ the inner product $⟨ 𝑓, 𝑔 ⟩ =$ $\int_{- 1}^{1} 𝑓 (𝑡) 𝑔 (𝑡) d 𝑡$ (Proposition 6.1.13). By Example 6.3.17, $𝒪︀ = 1 / \sqrt{2}, \sqrt{3 / 2} 𝑡$ is orthonormal. Since $\int_{- 1}^{1} 𝑡^{2} d 𝑡 = 2 / 3$ and $\int_{- 1}^{1} 𝑡^{3} d 𝑡 = 0$ ,

\begin{aligned} {Pr}_{𝒪︀} (𝑡^{2}) & = ⟨ 𝑡^{2}, \frac{1}{\sqrt{2}} ⟩ \frac{1}{\sqrt{2}} + ⟨ 𝑡^{2}, \sqrt{\frac{3}{2}} 𝑡 ⟩ \sqrt{\frac{3}{2}} 𝑡 \\ = \frac{1}{2} \cdot \frac{2}{3} + 0 = \frac{1}{3} . \end{aligned}

So $𝑡^{2} - 1 / 3$ is orthogonal to $1$ and to $𝑡$ . The polynomial $𝑥^{2} - 1 / 3$ of Example 6.3.17 arises in exactly this way, and Section 6.4.2 turns the computation into an algorithm.

The next proposition collects what we know about ${Pr}_{𝒪︀}$ . Most of it was proved along the way to Bessel’s inequality.

Proposition 6.4.4 (Properties of ${Pr}_{𝒪︀}$ ). Let $𝒪︀ = 𝐮_{1}, \dots, 𝐮_{𝑘}$ be an orthonormal list in $𝑉$ , let $𝑊 = span (𝒪︀)$ , and let $𝐯 \in 𝑉$ .

(a) ${Pr}_{𝒪︀} (𝐯) \in 𝑊$ .
(b) $𝐯 - {Pr}_{𝒪︀} (𝐯) \in 𝑊^{⟂}$ .
(c) ${Pr}_{𝒪︀} (𝐯) = 𝐯$ if and only if $𝐯 \in 𝑊$ .
(d) ${Pr}_{𝒪︀}$ is linear.
(e) ${‖ 𝐯 ‖}^{2} =$ ${‖ {Pr}_{𝒪︀} (𝐯) ‖}^{2} +$ ${‖ 𝐯 - {Pr}_{𝒪︀} (𝐯) ‖}^{2}$ , and ${‖ {Pr}_{𝒪︀} (𝐯) ‖}^{2} =$ $\sum_{𝑗 = 1}^{𝑘} {| ⟨ 𝐯, 𝐮_{𝑗} ⟩ |}^{2}$ . In particular $‖ {Pr}_{𝒪︀} (𝐯) ‖ \leq ‖ 𝐯 ‖$ , with equality if and only if $𝐯 \in 𝑊$ .

Proof.routine

Uses. Definition 6.4.1 (Projection onto the span of an orthonormal list), Definition 6.3.15 (Orthonormal list, orthonormal basis), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ), Proposition 6.3.18 (Coordinates in an orthonormal basis), Theorem 6.3.3 (Pythagorean theorem), Corollary 6.3.6 (Pythagoras for orthogonal lists), Proposition 6.1.27 (Basic properties of the norm)

Techniques. Take an inner product to isolate a coefficient (Technique 6.3.12)

Hint 1. For (b), compute

⟨ 𝐯 - {Pr}_{𝒪︀} (𝐯), 𝐮_{𝑙} ⟩

for each

𝑙

; then pass from the

𝐮_{𝑙}

to all of

𝑊

Hint 2. For (c), one direction is (a), and the other is Proposition 6.3.18(a). For (d), each coefficient

⟨ 𝐯, 𝐮_{𝑗} ⟩

depends linearly on

𝐯

Hint 3. For (e), apply the Pythagorean theorem to

𝐯 =

{Pr}_{𝒪︀} (𝐯) +

(𝐯 - {Pr}_{𝒪︀} (𝐯))

, using (a) and (b).

Sketch. (a)

{Pr}_{𝒪︀} (𝐯)

is a combination of the

𝐮_{𝑗}

. (b)

⟨ 𝐯 - {Pr}_{𝒪︀} (𝐯), 𝐮_{𝑙} ⟩ =

⟨ 𝐯, 𝐮_{𝑙} ⟩ -

\sum_{𝑗} ⟨ 𝐯, 𝐮_{𝑗} ⟩ 𝛿_{𝑗 𝑙} =

0

, and Proposition 6.3.9(c) upgrades orthogonality to each

𝐮_{𝑙}

to orthogonality to

𝑊

. (c) follows from (a) and Proposition 6.3.18(a). (d) follows from linearity of the inner product in the first slot. (e) is Pythagoras for the orthogonal pieces in (a) and (b), plus Corollary 6.3.6; equality means

𝐯 - {Pr}_{𝒪︀} (𝐯) = 𝟎

, which is (c).

(a) ${Pr}_{𝒪︀} (𝐯)$ is a linear combination of $𝐮_{1}, \dots, 𝐮_{𝑘}$ .

(b) For each $𝑙$ , linearity in the first slot and orthonormality give

\begin{aligned} ⟨ 𝐯 - {Pr}_{𝒪︀} (𝐯), 𝐮_{𝑙} ⟩ & = ⟨ 𝐯, 𝐮_{𝑙} ⟩ - \sum_{𝑗 = 1}^{𝑘} ⟨ 𝐯, 𝐮_{𝑗} ⟩ ⟨ 𝐮_{𝑗}, 𝐮_{𝑙} ⟩ \\ = ⟨ 𝐯, 𝐮_{𝑙} ⟩ - ⟨ 𝐯, 𝐮_{𝑙} ⟩ = 0 . \end{aligned}

So $𝐯 - {Pr}_{𝒪︀} (𝐯) \in {𝒪︀}^{⟂}$ , and ${𝒪︀}^{⟂} =$ ${span (𝒪︀)}^{⟂} =$ $𝑊^{⟂}$ by Proposition 6.3.9(c).

(c) If ${Pr}_{𝒪︀} (𝐯) = 𝐯$ , then $𝐯 \in 𝑊$ by (a). Conversely, if $𝐯 \in 𝑊$ , then $𝐯 =$ $\sum_{𝑗} ⟨ 𝐯, 𝐮_{𝑗} ⟩ 𝐮_{𝑗} =$ ${Pr}_{𝒪︀} (𝐯)$ by Proposition 6.3.18(a).

(d) For $𝐯, 𝐯^{'} \in 𝑉$ and $𝑎, 𝑏 \in 𝔽$ , linearity in the first slot gives $⟨ 𝑎 𝐯 + 𝑏 𝐯^{'}, 𝐮_{𝑗} ⟩ =$ $𝑎 ⟨ 𝐯, 𝐮_{𝑗} ⟩ +$ $𝑏 ⟨ 𝐯^{'}, 𝐮_{𝑗} ⟩$ for each $𝑗$ . Multiplying by $𝐮_{𝑗}$ and summing over $𝑗$ gives ${Pr}_{𝒪︀} (𝑎 𝐯 + 𝑏 𝐯^{'}) =$ $𝑎 {Pr}_{𝒪︀} (𝐯) +$ $𝑏 {Pr}_{𝒪︀} (𝐯^{'})$ .

(e) By (a) and (b), ${Pr}_{𝒪︀} (𝐯) ⟂ 𝐯 -$ ${Pr}_{𝒪︀} (𝐯)$ , and these two vectors add up to $𝐯$ . So the first identity is Theorem 6.3.3(a). The second is Corollary 6.3.6 applied to ${Pr}_{𝒪︀} (𝐯) =$ $\sum_{𝑗} ⟨ 𝐯, 𝐮_{𝑗} ⟩ 𝐮_{𝑗}$ . Since ${‖ 𝐯 - {Pr}_{𝒪︀} (𝐯) ‖}^{2} \geq 0$ , the first identity gives ${‖ {Pr}_{𝒪︀} (𝐯) ‖}^{2} \leq$ ${‖ 𝐯 ‖}^{2}$ , with equality if and only if $‖ 𝐯 - {Pr}_{𝒪︀} (𝐯) ‖ = 0$ . By Proposition 6.1.27(a), that happens if and only if ${Pr}_{𝒪︀} (𝐯) = 𝐯$ , that is, by (c), if and only if $𝐯 \in 𝑊$ . □

Part (e) is (6.3.2), and its inequality is Bessel’s inequality. The move behind it deserves a name, since it is the main source of upper bounds in this chapter.

Technique 6.4.5 (Projections shrink norms). Suppose $𝐱 = 𝐩 + 𝐪$ , where $𝐩$ lies in a subspace $𝑊$ and $𝐪 ⟂ 𝑊$ , as for $𝐩 = {Pr}_{𝒪︀} (𝐱)$ and $𝐪 = 𝐱 - {Pr}_{𝒪︀} (𝐱)$ . By Pythagoras,

{‖ 𝐱 ‖}^{2} = {‖ 𝐩 ‖}^{2} + {‖ 𝐪 ‖}^{2} .

So each piece is at most as long as $𝐱$ . Moreover $‖ 𝐩 ‖ = ‖ 𝐱 ‖$ exactly when $𝐪 = 𝟎$ , that is, when $𝐱 \in 𝑊$ , and $‖ 𝐪 ‖ = ‖ 𝐱 ‖$ exactly when $𝐩 = 𝟎$ .

Reach for it when you need an upper bound for a sum $\sum_{𝑗} {| ⟨ 𝐱, 𝐮_{𝑗} ⟩ |}^{2}$ over an orthonormal list, which is ${‖ {Pr}_{𝒪︀} (𝐱) ‖}^{2}$ , or more generally when the quantity to be bounded is the length of one orthogonal piece of a vector whose length you know. The equality case turns the bound into a test for membership in $𝑊$ . The canonical example is Bessel’s inequality (Theorem 6.3.24). In Theorem 6.4.33 the error $𝐯 - {Pr}_{𝑊} (𝐯)$ turns out to be the piece of $𝐯 - 𝐰$ orthogonal to $𝑊$ , for every $𝐰 \in 𝑊$ ; and in infinite dimensions (Section 15.3) Bessel’s inequality survives where Parseval’s identity needs more work.

Used in 3 places and 1 practice exercise

Theorem 6.4.33, Exercise 6.4.60, Problem 6.2; 1 practice exercise.

The projection is determined by orthogonality

Part (b) of Proposition 6.4.4 is the property that made $𝐩$ the foot of the perpendicular in the intuition above. It determines ${Pr}_{𝒪︀} (𝐯)$ completely. This matters because the condition “ $𝐩 \in 𝑊$ and $𝐯 - 𝐩 ⟂ 𝑊$ ” mentions only the subspace $𝑊$ , not the orthonormal list $𝒪︀$ that the formula uses.

Theorem 6.4.6 (The projection is characterized by orthogonality). Let $𝒪︀$ be an orthonormal list in $𝑉$ , let $𝑊 = span (𝒪︀)$ , and let $𝐯 \in 𝑉$ . Then ${Pr}_{𝒪︀} (𝐯)$ is the unique vector $𝐩 \in 𝑉$ such that

𝐩 \in 𝑊 and 𝐯 - 𝐩 \in 𝑊^{⟂} .

Proof (by two candidates).routine

Uses. Proposition 6.4.4 (Properties of ${Pr}_{𝒪︀}$ ), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ )

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. Existence is (a) and (b) of Proposition 6.4.4. For uniqueness, suppose that

𝐩

and

𝐩^{'}

both have the two properties, and look at

𝐩 - 𝐩^{'}

Hint 2.

𝐩 - 𝐩^{'}

lies in

𝑊

. It is also the difference of

𝐯 - 𝐩^{'}

and

𝐯 - 𝐩

, which lie in

𝑊^{⟂}

. What is

𝑊 \cap 𝑊^{⟂}

Sketch.

{Pr}_{𝒪︀} (𝐯)

has both properties by Proposition 6.4.4. If

𝐩

and

𝐩^{'}

both have them, then

𝐩 - 𝐩^{'} \in 𝑊

, and

𝐩 -

𝐩^{'} =

(𝐯 - 𝐩^{'}) -

(𝐯 - 𝐩) \in

𝑊^{⟂}

because

𝑊^{⟂}

is a subspace. So

𝐩 -

𝐩^{'} \in

𝑊 \cap

𝑊^{⟂} =

{𝟎}

By (a) and (b) of Proposition 6.4.4, $𝐩 = {Pr}_{𝒪︀} (𝐯)$ has both properties. Suppose $𝐩$ and $𝐩^{'}$ both have them. Since $𝑊$ is a subspace, $𝐩 - 𝐩^{'} \in 𝑊$ . Since $𝑊^{⟂}$ is a subspace (Proposition 6.3.9(a)),

𝐩 - 𝐩^{'} = (𝐯 - 𝐩^{'}) - (𝐯 - 𝐩) \in 𝑊^{⟂} .

So $𝐩 - 𝐩^{'} \in 𝑊 \cap 𝑊^{⟂}$ , which is ${𝟎}$ by Proposition 6.3.9(d). Hence $𝐩 = 𝐩^{'}$ . □

Proof (by computing coordinates).routine

Uses. Proposition 6.3.18 (Coordinates in an orthonormal basis), Proposition 6.4.4 (Properties of ${Pr}_{𝒪︀}$ ), Definition 6.4.1 (Projection onto the span of an orthonormal list)

Techniques. Take an inner product to isolate a coefficient (Technique 6.3.12)

Hint 1. Let

𝐩 \in 𝑊

with

𝐯 - 𝐩 ⟂ 𝑊

. Since

𝐩 \in span (𝒪︀)

, Proposition 6.3.18(a) expresses

𝐩

through the numbers

⟨ 𝐩, 𝐮_{𝑗} ⟩

Hint 2. Write

⟨ 𝐩, 𝐮_{𝑗} ⟩ =

⟨ 𝐯, 𝐮_{𝑗} ⟩ -

⟨ 𝐯 - 𝐩, 𝐮_{𝑗} ⟩

Sketch. Let

𝒪︀ = 𝐮_{1}, \dots, 𝐮_{𝑘}

. If

𝐩 \in 𝑊

and

𝐯 - 𝐩 ⟂ 𝑊

, then

𝐩 =

\sum_{𝑗} ⟨ 𝐩, 𝐮_{𝑗} ⟩ 𝐮_{𝑗}

and

⟨ 𝐩, 𝐮_{𝑗} ⟩ =

⟨ 𝐯, 𝐮_{𝑗} ⟩ -

0

. So

𝐩 = {Pr}_{𝒪︀} (𝐯)

. Existence is Proposition 6.4.4(a) and (b).

Write $𝒪︀ = 𝐮_{1}, \dots, 𝐮_{𝑘}$ . Existence is (a) and (b) of Proposition 6.4.4. Conversely, let $𝐩 \in 𝑊$ with $𝐯 - 𝐩 \in 𝑊^{⟂}$ . Since $𝐮_{𝑗} \in 𝑊$ , we have $⟨ 𝐯 - 𝐩, 𝐮_{𝑗} ⟩ = 0$ , so

⟨ 𝐩, 𝐮_{𝑗} ⟩ = ⟨ 𝐯, 𝐮_{𝑗} ⟩ - ⟨ 𝐯 - 𝐩, 𝐮_{𝑗} ⟩ = ⟨ 𝐯, 𝐮_{𝑗} ⟩ .

Since $𝐩 \in span (𝒪︀)$ , Proposition 6.3.18(a) gives

𝐩 = \sum_{𝑗 = 1}^{𝑘} ⟨ 𝐩, 𝐮_{𝑗} ⟩ 𝐮_{𝑗} = \sum_{𝑗 = 1}^{𝑘} ⟨ 𝐯, 𝐮_{𝑗} ⟩ 𝐮_{𝑗} = {Pr}_{𝒪︀} (𝐯),

as desired. □

The first proof never uses the formula for ${Pr}_{𝒪︀}$ . It shows that any two vectors with the two properties agree, whatever produced them, and all it needs is $𝑊 \cap 𝑊^{⟂} = {𝟎}$ . The second proof computes the coordinates of such a vector and recognizes them as those of ${Pr}_{𝒪︀} (𝐯)$ ; this is how the lecture argues. The first proof is the one that generalizes, and it gives the following technique.

Technique 6.4.7 (Recognize a projection by its two conditions). To show that a vector $𝐩$ is the projection of $𝐯$ onto $𝑊$ , do not compute the projection. Check the two conditions of Theorem 6.4.6: $𝐩 \in 𝑊$ , and $𝐯 - 𝐩 ⟂ 𝑊$ . By Proposition 6.3.9(c), the second condition only has to be checked against a spanning list of $𝑊$ . Uniqueness then does the rest, much as a two-sided inverse is recognized by checking two products (Technique 2.5.16).

Reach for it when a formula or a vector is proposed as a projection, when projections onto related subspaces are compared, and when you need to know that a projection does not depend on the choices made to compute it. The canonical example is Corollary 6.4.8. Later examples are the projection onto $𝑊^{⟂}$ (Proposition 6.4.29), the recognition of orthogonal projections among all linear maps (Proposition 6.4.30), and the projection formula of Section 6.5.

Used in 19 places and 4 practice exercises

Corollary 6.4.8, Exercise 6.4.28, Proposition 6.4.29, Proposition 6.4.30, Exercise 6.4.42, Exercise 6.4.49, Exercise 6.4.57, Exercise 6.4.58, Theorem 6.5.5, Proposition 6.5.13, Proposition 6.5.17, Proposition 6.5.23, Exercise 6.5.42, Corollary 6.6.29, Exercise 6.7.5, Exercise 6.7.13, Problem 6.2, Problem 6.4, Exercise 8.1.32; 4 practice exercises.

Corollary 6.4.8 (The projection depends only on the span). If

𝒪︀

and

{𝒪︀}^{'}

are orthonormal lists in

𝑉

with

span (𝒪︀) =

span ({𝒪︀}^{'})

, then

{Pr}_{𝒪︀} = {Pr}_{{𝒪︀}^{'}}

Proof.routine

Uses. Theorem 6.4.6 (The projection is characterized by orthogonality), Proposition 6.4.4 (Properties of ${Pr}_{𝒪︀}$ )

Techniques. Recognize a projection by its two conditions (Technique 6.4.7)

Hint 1. Let

𝑊

be the common span and fix

𝐯 \in 𝑉

. Which two properties does

{Pr}_{{𝒪︀}^{'}} (𝐯)

have?

Hint 2. Both properties mention only

𝑊

. Apply the uniqueness in Theorem 6.4.6 for the list

𝒪︀

Sketch. With

𝑊 =

span (𝒪︀) =

span ({𝒪︀}^{'})

, the vector

{Pr}_{{𝒪︀}^{'}} (𝐯)

lies in

𝑊

and

𝐯 - {Pr}_{{𝒪︀}^{'}} (𝐯) \in 𝑊^{⟂}

, by Proposition 6.4.4 for

{𝒪︀}^{'}

. These are the conditions that characterize

{Pr}_{𝒪︀} (𝐯)

in Theorem 6.4.6.

Let

𝑊 =

span (𝒪︀) =

span ({𝒪︀}^{'})

and

𝐯 \in 𝑉

. By (a) and (b) of Proposition 6.4.4, applied to the list

{𝒪︀}^{'}

, the vector

𝐩 = {Pr}_{{𝒪︀}^{'}} (𝐯)

lies in

𝑊

and satisfies

𝐯 - 𝐩 \in 𝑊^{⟂}

. By Theorem 6.4.6, applied to the list

𝒪︀

, the only vector with these two properties is

{Pr}_{𝒪︀} (𝐯)

. Hence

{Pr}_{{𝒪︀}^{'}} (𝐯) =

{Pr}_{𝒪︀} (𝐯)

for every

𝐯

. □

Example 6.4.9 (Two orthonormal bases, one projection). Let $𝑊 =$ ${𝐱 \in ℝ^{3} | 𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 0}$ . Both

\begin{aligned} 𝒪︀ & : 𝐚 = \frac{1}{\sqrt{2}} (1, - 1, 0), 𝐛 = \frac{1}{\sqrt{6}} (1, 1, - 2), \\ {𝒪︀}^{'} & : 𝐚^{'} = \frac{1}{\sqrt{2}} (1, 0, - 1), 𝐛^{'} = \frac{1}{\sqrt{6}} (1, - 2, 1) \end{aligned}

are orthonormal lists of two vectors in the $2$ -dimensional plane $𝑊$ , so both are orthonormal bases of $𝑊$ (Corollary 6.3.14). For $𝐯 = (3, 0, 0)$ ,

\begin{aligned} {Pr}_{𝒪︀} (𝐯) & = \frac{3}{2} (1, - 1, 0) + \frac{3}{6} (1, 1, - 2) = (2, - 1, - 1), \\ {Pr}_{{𝒪︀}^{'}} (𝐯) & = \frac{3}{2} (1, 0, - 1) + \frac{3}{6} (1, - 2, 1) = (2, - 1, - 1) . \end{aligned}

The individual shadows differ, because they depend on the axes, but their sums agree. As a check, $𝐯 -$ $(2, - 1, - 1) =$ $(1, 1, 1)$ is orthogonal to $𝑊$ .

By hand it is often easier to work with an orthogonal list and postpone normalizing.

Corollary 6.4.10 (Projecting with an orthogonal list). Let $𝐟_{1}, \dots, 𝐟_{𝑘}$ be an orthogonal list of nonzero vectors in $𝑉$ , and let $𝒪︀$ be the orthonormal list $𝐟_{1} / ‖ 𝐟_{1} ‖,$ $\dots,$ $𝐟_{𝑘} / ‖ 𝐟_{𝑘} ‖$ . Then

{Pr}_{𝒪︀} (𝐯) = \sum_{𝑗 = 1}^{𝑘} \frac{⟨ 𝐯, 𝐟_{𝑗} ⟩}{{‖ 𝐟_{𝑗} ‖}^{2}} 𝐟_{𝑗} for all 𝐯 \in 𝑉 .

Each term is unchanged if $𝐟_{𝑗}$ is replaced by $𝑐 𝐟_{𝑗}$ for a scalar $𝑐 \neq 0$ .

Proof.routine

Uses. Definition 6.4.1 (Projection onto the span of an orthonormal list), Proposition 6.1.4 (Sesquilinearity), Proposition 6.1.27 (Basic properties of the norm)

Hint 1. Substitute

𝐮_{𝑗} = 𝐟_{𝑗} / ‖ 𝐟_{𝑗} ‖

into Definition 6.4.1. Is

1 / ‖ 𝐟_{𝑗} ‖

real?

Hint 2. For the last claim, take

𝑐

out of both slots of

⟨ 𝐯, 𝑐 𝐟_{𝑗} ⟩

and out of

{‖ 𝑐 𝐟_{𝑗} ‖}^{2}

Sketch. Since

‖ 𝐟_{𝑗} ‖

is real,

⟨ 𝐯, 𝐟_{𝑗} / ‖ 𝐟_{𝑗} ‖ ⟩ 𝐟_{𝑗} / ‖ 𝐟_{𝑗} ‖ =

⟨ 𝐯, 𝐟_{𝑗} ⟩ / {‖ 𝐟_{𝑗} ‖}^{2} 𝐟_{𝑗}

. Replacing

𝐟_{𝑗}

𝑐 𝐟_{𝑗}

multiplies the term by

𝑐 𝑐 / {| 𝑐 |}^{2} = 1

Since $‖ 𝐟_{𝑗} ‖$ is a positive real number, it equals its conjugate, and Proposition 6.1.4 gives

⟨ 𝐯, \frac{𝐟_{𝑗}}{‖ 𝐟_{𝑗} ‖} ⟩ \frac{𝐟_{𝑗}}{‖ 𝐟_{𝑗} ‖} = \frac{⟨ 𝐯, 𝐟_{𝑗} ⟩}{{‖ 𝐟_{𝑗} ‖}^{2}} 𝐟_{𝑗} .

Summing over $𝑗$ gives the formula. If $𝐟_{𝑗}$ is replaced by $𝑐 𝐟_{𝑗}$ , the $𝑗$ th term becomes

\frac{⟨ 𝐯, 𝑐 𝐟_{𝑗} ⟩}{{‖ 𝑐 𝐟_{𝑗} ‖}^{2}} 𝑐 𝐟_{𝑗} = \frac{𝑐 𝑐}{{| 𝑐 |}^{2}} \cdot \frac{⟨ 𝐯, 𝐟_{𝑗} ⟩}{{‖ 𝐟_{𝑗} ‖}^{2}} 𝐟_{𝑗} = \frac{⟨ 𝐯, 𝐟_{𝑗} ⟩}{{‖ 𝐟_{𝑗} ‖}^{2}} 𝐟_{𝑗},

by Proposition 6.1.4 and Proposition 6.1.27(b). □

For $𝑘 = 1$ this is the shadow $⟨ 𝐯, 𝐟_{1} ⟩ / {‖ 𝐟_{1} ‖}^{2} 𝐟_{1}$ of Technique 6.2.4, and for an orthogonal basis of $𝑉$ it is Corollary 6.3.21.

Orthogonal projection onto a subspace

By Corollary 6.4.8, ${Pr}_{𝒪︀}$ depends only on the subspace spanned by $𝒪︀$ . So we may name it after the subspace.

Definition 6.4.11 (Orthogonal projection). Let $𝑊$ be a subspace of $𝑉$ that has an orthonormal basis $𝒪︀ = 𝐮_{1}, \dots, 𝐮_{𝑘}$ . The orthogonal projection onto $𝑊$ is the map ${Pr}_{𝑊} = {Pr}_{𝒪︀} : 𝑉 \to 𝑉$ , that is,

{Pr}_{𝑊} (𝐯) = ⟨ 𝐯, 𝐮_{1} ⟩ 𝐮_{1} + \dots + ⟨ 𝐯, 𝐮_{𝑘} ⟩ 𝐮_{𝑘} .

By Corollary 6.4.8 this does not depend on the choice of the orthonormal basis $𝒪︀$ . By Theorem 6.4.6, ${Pr}_{𝑊} (𝐯)$ is the unique vector $𝐩 \in 𝑊$ with $𝐯 - 𝐩 ⟂ 𝑊$ .

A basis is a finite list, so only a finite-dimensional subspace can have an orthonormal basis. Conversely, Theorem 6.4.20 below shows that every finite-dimensional subspace has one. So ${Pr}_{𝑊}$ is defined exactly for the finite-dimensional subspaces $𝑊$ of $𝑉$ , while $𝑉$ itself may be infinite-dimensional. In Example 6.4.3, for instance, ${Pr}_{𝑊} (𝑡^{2}) = 1 / 3$ for $𝑊 =$ $span (1, 𝑡) \subseteq$ $𝐶 [- 1, 1]$ .

Remark 6.4.12 (Why “orthogonal”). The map

𝑃 : ℝ^{2} \to ℝ^{2}

𝑃 (𝑥, 𝑦) =

(𝑥 - 𝑦, 0)

, also sends every vector into the

𝑥

-axis

𝑊

and fixes every vector of

𝑊

. It slides each point onto

𝑊

along the direction

(1, 1)

, not along the perpendicular. For instance

𝑃 (0, 1) = (- 1, 0)

, and

(0, 1) -

𝑃 (0, 1) =

(1, 1)

is not orthogonal to

𝑊

, whereas

{Pr}_{𝑊} (0, 1) = 𝟎

. Maps like

𝑃

, which project onto one subspace along another, exist in every vector space, with or without an inner product, and they belong with the direct sums of Section 4.4. Among them, the orthogonal projection is the one that moves every vector perpendicularly to

𝑊

. Proposition 6.4.30 shows how to recognize it.

Exercise 6.4.13.routine In $ℂ^{3}$ with the dot product, let $𝐮 = \frac{1}{\sqrt{2}} (1, 𝑖, 0)$ and $𝐯 = (0, 1, 1)$ .

(a)Compute ${Pr}_{𝐮} (𝐯)$ , and check that $𝐯 - {Pr}_{𝐮} (𝐯) ⟂ 𝐮$ .
(b)A student uses $⟨ 𝐮, 𝐯 ⟩ 𝐮$ instead. Show that this vector does not have the property in (a).

Solution.

Uses. Definition 6.4.1 (Projection onto the span of an orthonormal list), Definition 6.1.8 (Dot product), Proposition 6.4.4 (Properties of ${Pr}_{𝒪︀}$ )

Hint 1.

⟨ 𝐯, 𝐮 ⟩ = 𝐯 \cdot 𝐮

conjugates the entries of

𝐮

Hint 2. You should get

⟨ 𝐯, 𝐮 ⟩ = - 𝑖 / \sqrt{2}

, while

⟨ 𝐮, 𝐯 ⟩

is its conjugate.

Sketch. (a)

⟨ 𝐯, 𝐮 ⟩ =

(1 \cdot 𝑖) / \sqrt{2} =

- 𝑖 / \sqrt{2}

, so

{Pr}_{𝐮} (𝐯) =

(- 𝑖 / 2) (1, 𝑖, 0) =

(- 𝑖 / 2, 1 / 2, 0)

, and

𝐯 -

{Pr}_{𝐮} (𝐯) =

(𝑖 / 2, 1 / 2, 1)

has dot product

𝑖 / 2 + (1 / 2) (- 𝑖) = 0

with

(1, 𝑖, 0)

. (b)

⟨ 𝐮, 𝐯 ⟩ 𝐮 =

(𝑖 / 2, - 1 / 2, 0)

, and

𝐯

minus it has dot product

- 2 𝑖 \neq 0

with

(1, 𝑖, 0)

(a) By Definition 6.1.8, $⟨ 𝐯, 𝐮 ⟩ =$ $(0 \cdot 1 + 1 \cdot 𝑖 + 1 \cdot 0) / \sqrt{2} =$ $- 𝑖 / \sqrt{2}$ . So

\begin{aligned} {Pr}_{𝐮} (𝐯) & = - \frac{𝑖}{\sqrt{2}} \cdot \frac{1}{\sqrt{2}} (1, 𝑖, 0) \\ = - \frac{𝑖}{2} (1, 𝑖, 0) = (- \frac{𝑖}{2}, \frac{1}{2}, 0), \end{aligned}

and $𝐯 -$ ${Pr}_{𝐮} (𝐯) =$ $(𝑖 / 2, 1 / 2, 1)$ . Its dot product with $(1, 𝑖, 0)$ is $(𝑖 / 2) \cdot$ $1 +$ $(1 / 2) \cdot$ $𝑖 +$ $0 =$ $𝑖 / 2 -$ $𝑖 / 2 =$ $0$ , so it is orthogonal to $𝐮$ , as Proposition 6.4.4(b) says.

(b) $⟨ 𝐮, 𝐯 ⟩ =$ $⟨ 𝐯, 𝐮 ⟩ =$ $𝑖 / \sqrt{2}$ , so the student’s vector is $(𝑖 / 2) (1, 𝑖, 0) =$ $(𝑖 / 2, - 1 / 2, 0)$ , and $𝐯$ minus it is $(- 𝑖 / 2, 3 / 2, 1)$ . Its dot product with $(1, 𝑖, 0)$ is $- 𝑖 / 2 +$ $(3 / 2) (- 𝑖) =$ $- 2 𝑖 \neq$ $0$ . Over $ℂ$ the vector being projected belongs in the first slot.

6.4.2The Gram–Schmidt algorithm

To use Definition 6.4.11 we need orthonormal bases. A subspace usually arrives as the span of some list $𝐯_{1}, \dots, 𝐯_{𝑚}$ , such as the columns of a matrix or the monomials $1, 𝑥, \dots, 𝑥^{𝑛}$ , and that list is rarely orthonormal. The Gram–Schmidt algorithm converts it into an orthonormal basis of the same span.

Intuition (Keep only what is new). Process the vectors one at a time, and keep an orthonormal list $𝐮_{1}, \dots, 𝐮_{𝑘}$ with the same span as the vectors processed so far. When $𝐯_{𝑗}$ arrives, split it as in Figure 6.4.1: $𝐯_{𝑗}$ is its projection onto $span (𝐮_{1}, \dots, 𝐮_{𝑘})$ plus the remainder

𝐟 = 𝐯_{𝑗} - {Pr}_{𝐮_{1}, \dots, 𝐮_{𝑘}} (𝐯_{𝑗}) .

The projection lies in the span we already have, so it contributes nothing new. The remainder is orthogonal to $𝐮_{1}, \dots, 𝐮_{𝑘}$ by Proposition 6.4.4(b), so after normalizing it can be appended to the orthonormal list, and it carries exactly the direction that $𝐯_{𝑗}$ adds (Figure 6.4.2). If the remainder is $𝟎$ , then $𝐯_{𝑗}$ lies in the span of the earlier vectors and adds no new direction, so we skip it.

Algorithm 6.4.14 (Gram–Schmidt)

Input: A list $𝐯_{1}, \dots, 𝐯_{𝑚}$ in $𝑉$ .
Output: An orthonormal list $𝐮_{1}, \dots, 𝐮_{𝑘}$ , where $𝑘 \leq 𝑚$ , with $span (𝐮_{1}, \dots, 𝐮_{𝑘}) =$ $span (𝐯_{1}, \dots, 𝐯_{𝑚})$ .

Start with no vectors kept ( $𝑘 = 0$ ) and $𝑗 = 1$ .

Project. Subtract from $𝐯_{𝑗}$ its projection onto the span of the vectors kept so far:

𝐟 = 𝐯_{𝑗} - \sum_{𝑖 = 1}^{𝑘} ⟨ 𝐯_{𝑗}, 𝐮_{𝑖} ⟩ 𝐮_{𝑖} .

Keep or skip. If

𝐟 \neq 𝟎

, increase

𝑘

1

, and set

𝐟_{𝑘} = 𝐟

and

𝐮_{𝑘} = 𝐟_{𝑘} / ‖ 𝐟_{𝑘} ‖

. If

𝐟 = 𝟎

, keep nothing.

Repeat. If

𝑗 < 𝑚

, increase

𝑗

1

and return to step 1. Otherwise output

𝐮_{1}, \dots, 𝐮_{𝑘}

The sum in step 1 is ${Pr}_{𝒪︀} (𝐯_{𝑗})$ for the current list $𝒪︀ = 𝐮_{1}, \dots, 𝐮_{𝑘}$ ; when $𝑘 = 0$ it is empty and $𝐟 = 𝐯_{𝑗}$ . We call $𝐟_{1}, 𝐟_{2}, \dots$ the residuals. If no vector is skipped, then $𝑘 = 𝑗$ after the $𝑗$ th pass, and the algorithm is the recursion

\begin{aligned} 𝐟_{𝑗} & = 𝐯_{𝑗} - \sum_{𝑖 = 1}^{𝑗 - 1} ⟨ 𝐯_{𝑗}, 𝐮_{𝑖} ⟩ 𝐮_{𝑖}, \\ 𝐮_{𝑗} & = \frac{𝐟_{𝑗}}{‖ 𝐟_{𝑗} ‖} (𝑗 = 1, \dots, 𝑚) . \end{aligned}

(6.4.1)

Figure 6.4.2. Two passes of Gram–Schmidt. (a) The residual

𝐟_{2}

is what remains of

𝐯_{2}

after subtracting its shadow on the line through

𝐯_{1}

; normalizing

𝐯_{1}

and

𝐟_{2}

gives

𝐮_{1}

and

𝐮_{2}

. (b) In the next pass,

𝐯_{3}

is projected onto the shaded plane

span (𝐯_{1}, 𝐯_{2}) =

span (𝐮_{1}, 𝐮_{2})

, and the residual

𝐟_{3}

, normalized, gives

𝐮_{3}

That the output is orthonormal and has the right span is a statement about what the algorithm keeps true from one pass to the next, so we prove it as in Technique 3.3.5.

Theorem 6.4.15 (Gram–Schmidt is correct). Run Algorithm 6.4.14 on a list $𝐯_{1}, \dots, 𝐯_{𝑚}$ in $𝑉$ . For $0 \leq 𝑗 \leq 𝑚$ , let ${𝒪︀}_{𝑗}$ be the list of vectors kept after the first $𝑗$ passes, so that ${𝒪︀}_{0}$ is empty.

(a)For every $𝑗$ , ${𝒪︀}_{𝑗}$ is orthonormal and $span ({𝒪︀}_{𝑗}) =$ $span (𝐯_{1}, \dots, 𝐯_{𝑗})$ .
(b)In pass $𝑗$ , the vector $𝐯_{𝑗}$ is skipped if and only if $𝐯_{𝑗} \in$ $span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})$ .
(c)The output is an orthonormal basis of $span (𝐯_{1}, \dots, 𝐯_{𝑚})$ .
(d)If $𝐯_{1}, \dots, 𝐯_{𝑚}$ is linearly independent, then no vector is skipped, and the output $𝐮_{1}, \dots, 𝐮_{𝑚}$ satisfies $span (𝐮_{1}, \dots, 𝐮_{𝑗}) =$ $span (𝐯_{1}, \dots, 𝐯_{𝑗})$ and $⟨ 𝐯_{𝑗}, 𝐮_{𝑗} ⟩ =$ $‖ 𝐟_{𝑗} ‖ >$ $0$ for every $𝑗$ .

Proof.standard

Uses. Proposition 6.4.4 (Properties of ${Pr}_{𝒪︀}$ ), Proposition 1.3.18 (Comparing spans), Proposition 6.3.13 (Orthogonal lists are independent), Theorem 1.5.5 (Independence is decided at zero), Definition 6.3.15 (Orthonormal list, orthonormal basis)

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5), Induction on the length of a list (Technique 1.6.9), Double containment (Technique 1.3.14)

Hint 1. Prove (a) by induction on

𝑗

. In pass

𝑗

, let

𝑊 = span ({𝒪︀}_{𝑗 - 1})

. What do you know about

𝐟 =

𝐯_{𝑗} -

{Pr}_{{𝒪︀}_{𝑗 - 1}} (𝐯_{𝑗})

Hint 2. By Proposition 6.4.4,

𝐟 ⟂ 𝑊

, and

𝐟 = 𝟎

exactly when

𝐯_{𝑗} \in 𝑊

. In the case

𝐟 \neq 𝟎

, the new unit vector is orthogonal to the old ones.

Hint 3. For the spans, compare with Proposition 1.3.18 in both directions, using

𝐯_{𝑗} =

{Pr}_{{𝒪︀}_{𝑗 - 1}} (𝐯_{𝑗}) +

‖ 𝐟 ‖ 𝐮

Sketch. Induct on

𝑗

;

{𝒪︀}_{0}

is empty and spans

{𝟎}

. In pass

𝑗

, let

𝑊 =

span ({𝒪︀}_{𝑗 - 1}) =

span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})

. By Proposition 6.4.4,

𝐟 ⟂ 𝑊

, and

𝐟 = 𝟎

if and only if

𝐯_{𝑗} \in 𝑊

; this gives (b). If

𝐟 = 𝟎

, nothing changes, and

span (𝐯_{1}, \dots, 𝐯_{𝑗}) =

𝑊

. Otherwise

𝐮 = 𝐟 / ‖ 𝐟 ‖

is a unit vector orthogonal to

{𝒪︀}_{𝑗 - 1}

, and

𝐮 \in

span (𝐯_{1}, \dots, 𝐯_{𝑗})

and

𝐯_{𝑗} =

{Pr}_{{𝒪︀}_{𝑗 - 1}} (𝐯_{𝑗}) +

‖ 𝐟 ‖ 𝐮

give equal spans. (c) is (a) for

𝑗 = 𝑚

, with Proposition 6.3.13. For (d), independence rules out

𝐯_{𝑗} \in

span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})

, and

⟨ 𝐯_{𝑗}, 𝐮_{𝑗} ⟩ =

⟨ Pr (𝐯_{𝑗}) + ‖ 𝐟_{𝑗} ‖ 𝐮_{𝑗}, 𝐮_{𝑗} ⟩ =

‖ 𝐟_{𝑗} ‖

(a) We induct on $𝑗$ . For $𝑗 = 0$ , the empty list is orthonormal, and both sides equal ${𝟎}$ .

Let $1 \leq 𝑗 \leq 𝑚$ , and suppose that ${𝒪︀}_{𝑗 - 1} =$ $𝐮_{1},$ $\dots,$ $𝐮_{𝑘}$ is orthonormal with $span ({𝒪︀}_{𝑗 - 1}) =$ $span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})$ . Call this subspace $𝑊$ . Pass $𝑗$ computes $𝐟 =$ $𝐯_{𝑗} -$ ${Pr}_{{𝒪︀}_{𝑗 - 1}} (𝐯_{𝑗})$ . By (a) and (c) of Proposition 6.4.4, ${Pr}_{{𝒪︀}_{𝑗 - 1}} (𝐯_{𝑗}) \in$ $𝑊$ , and $𝐟 = 𝟎$ if and only if $𝐯_{𝑗} \in 𝑊$ .

Suppose $𝐟 = 𝟎$ . Then ${𝒪︀}_{𝑗} = {𝒪︀}_{𝑗 - 1}$ is orthonormal. Since $𝐯_{𝑗} \in$ $𝑊 =$ $span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})$ , Proposition 1.3.18 gives $span (𝐯_{1}, \dots, 𝐯_{𝑗}) =$ $span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1}) =$ $𝑊 =$ $span ({𝒪︀}_{𝑗})$ .

Suppose $𝐟 \neq 𝟎$ . Then ${𝒪︀}_{𝑗}$ is $𝐮_{1}, \dots, 𝐮_{𝑘}, 𝐮$ with $𝐮 = 𝐟 / ‖ 𝐟 ‖$ , a unit vector. By Proposition 6.4.4(b), $𝐟 \in 𝑊^{⟂}$ , so $⟨ 𝐮, 𝐮_{𝑖} ⟩ =$ $⟨ 𝐟, 𝐮_{𝑖} ⟩ / ‖ 𝐟 ‖ =$ $0$ for $𝑖 \leq 𝑘$ . Hence ${𝒪︀}_{𝑗}$ is orthonormal. For the spans we prove both containments with Proposition 1.3.18. Each $𝐮_{𝑖}$ with $𝑖 \leq 𝑘$ lies in $𝑊 \subseteq$ $span (𝐯_{1}, \dots, 𝐯_{𝑗})$ , and so does

𝐮 = \frac{1}{‖ 𝐟 ‖} (𝐯_{𝑗} - {Pr}_{{𝒪︀}_{𝑗 - 1}} (𝐯_{𝑗})),

because ${Pr}_{{𝒪︀}_{𝑗 - 1}} (𝐯_{𝑗}) \in$ $𝑊$ . So $span ({𝒪︀}_{𝑗}) \subseteq$ $span (𝐯_{1}, \dots, 𝐯_{𝑗})$ . Conversely, $𝐯_{1}, \dots, 𝐯_{𝑗 - 1}$ lie in $𝑊 =$ $span ({𝒪︀}_{𝑗 - 1}) \subseteq$ $span ({𝒪︀}_{𝑗})$ , and so does

𝐯_{𝑗} = {Pr}_{{𝒪︀}_{𝑗 - 1}} (𝐯_{𝑗}) + ‖ 𝐟 ‖ 𝐮 .

So $span (𝐯_{1}, \dots, 𝐯_{𝑗}) \subseteq$ $span ({𝒪︀}_{𝑗})$ , and the induction is complete.

(b) We saw in the proof of (a) that pass $𝑗$ keeps nothing exactly when $𝐯_{𝑗} \in$ $𝑊 =$ $span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})$ .

(c) The output is ${𝒪︀}_{𝑚}$ . By (a) it is orthonormal, hence linearly independent (Proposition 6.3.13), and it spans $span (𝐯_{1}, \dots, 𝐯_{𝑚})$ .

(d) If $𝐯_{𝑗} =$ $𝑐_{1} 𝐯_{1} +$ $\dots +$ $𝑐_{𝑗 - 1} 𝐯_{𝑗 - 1}$ for some $𝑗$ , then $𝑐_{1} 𝐯_{1} +$ $\dots +$ $𝑐_{𝑗 - 1} 𝐯_{𝑗 - 1} -$ $𝐯_{𝑗} =$ $𝟎$ is a linear relation with a nonzero coefficient, so the list is dependent (Theorem 1.5.5). So if the list is independent, (b) shows that nothing is skipped. Then ${𝒪︀}_{𝑗} = 𝐮_{1}, \dots, 𝐮_{𝑗}$ for every $𝑗$ , and (a) gives the equality of spans. Finally,

𝐯_{𝑗} = {Pr}_{{𝒪︀}_{𝑗 - 1}} (𝐯_{𝑗}) + ‖ 𝐟_{𝑗} ‖ 𝐮_{𝑗},

where the first term lies in $span (𝐮_{1}, \dots, 𝐮_{𝑗 - 1})$ and is therefore orthogonal to $𝐮_{𝑗}$ . Hence $⟨ 𝐯_{𝑗}, 𝐮_{𝑗} ⟩ =$ $‖ 𝐟_{𝑗} ‖ ⟨ 𝐮_{𝑗}, 𝐮_{𝑗} ⟩ =$ $‖ 𝐟_{𝑗} ‖$ , which is positive because $𝐟_{𝑗} \neq 𝟎$ . □

The invariant (a) is exactly what makes step 1 the right move. Because $span ({𝒪︀}_{𝑗 - 1})$ is the span of all the earlier vectors, the residual is orthogonal to each earlier output, not only to the most recent one. Subtracting only the shadow on $𝐮_{𝑗 - 1}$ would leave components along $𝐮_{1}, \dots, 𝐮_{𝑗 - 2}$ .

Remark 6.4.16 (Postponing the normalization). By Corollary 6.4.10, the projection in step 1 can be computed from the residuals instead of the normalized vectors:

𝐟 = 𝐯_{𝑗} - \sum_{𝑖 = 1}^{𝑘} \frac{⟨ 𝐯_{𝑗}, 𝐟_{𝑖} ⟩}{{‖ 𝐟_{𝑖} ‖}^{2}} 𝐟_{𝑖},

and each $𝐟_{𝑖}$ may be replaced by any nonzero multiple of itself without changing this sum. So by hand one runs the algorithm with residuals only, clears denominators in each residual as it appears, and normalizes once at the end. Square roots then appear only in the last step.

Example 6.4.17 (Gram–Schmidt in $ℝ^{3}$ ). Let $𝐯_{1} = (1, 1, 0)$ , $𝐯_{2} = (1, 0, 1)$ , $𝐯_{3} = (0, 1, 1)$ . Following Remark 6.4.16:

\begin{aligned} 𝐟_{1} & = (1, 1, 0), \\ 𝐟_{2} & = (1, 0, 1) - \frac{1}{2} (1, 1, 0) = \frac{1}{2} (1, - 1, 2), \end{aligned}

which we replace by $(1, - 1, 2)$ . Since $⟨ 𝐯_{3}, 𝐟_{1} ⟩ = 1$ with ${‖ 𝐟_{1} ‖}^{2} = 2$ , and $⟨ 𝐯_{3}, (1, - 1, 2) ⟩ = 1$ with ${‖ (1, - 1, 2) ‖}^{2} = 6$ ,

\begin{aligned} 𝐟_{3} & = (0, 1, 1) - \frac{1}{2} (1, 1, 0) - \frac{1}{6} (1, - 1, 2) \\ = \frac{2}{3} (- 1, 1, 1), \end{aligned}

which we replace by $(- 1, 1, 1)$ . The rescaled residuals $(1, 1, 0)$ , $(1, - 1, 2)$ , $(- 1, 1, 1)$ are pairwise orthogonal, and normalizing them gives the orthonormal basis

\begin{matrix} 𝐮_{1} = \frac{1}{\sqrt{2}} (1, 1, 0), 𝐮_{2} = \frac{1}{\sqrt{6}} (1, - 1, 2), \\ 𝐮_{3} = \frac{1}{\sqrt{3}} (- 1, 1, 1) \end{matrix}

of $ℝ^{3}$ . As Theorem 6.4.15(d) predicts, $⟨ 𝐯_{2}, 𝐮_{2} ⟩ = 3 / \sqrt{6} = \sqrt{3 / 2}$ is the length of the unrescaled residual $\frac{1}{2} (1, - 1, 2)$ .

\begin{matrix} 𝐟_{1} = (1, 1, 0), 𝐟_{2} = \frac{1}{2} (1, - 1, 2), \\ 𝐟_{3} = \frac{2}{3} (- 1, 1, 1) \end{matrix}

Gram–Schmidt on the vectors of Example 6.4.17, one step at a time, keeping the residuals unnormalized as in Remark 6.4.16; normalizing them gives

𝐮_{1}, 𝐮_{2}, 𝐮_{3}

. In the interactive version, drag or type the inputs; a vector typed into the span of the earlier ones is skipped.

Example 6.4.18 (A dependent list). Run the algorithm on $𝐯_{1} = (1, 1, 1)$ , $𝐯_{2} = (1, 2, 3)$ , $𝐯_{3} = (3, 4, 5)$ , $𝐯_{4} = (0, 0, 1)$ in $ℝ^{3}$ , again with residuals only. First $𝐟_{1} = (1, 1, 1)$ , and

𝐟_{2} = (1, 2, 3) - \frac{6}{3} (1, 1, 1) = (- 1, 0, 1) .

In the third pass, $⟨ 𝐯_{3}, 𝐟_{1} ⟩ = 12$ and $⟨ 𝐯_{3}, 𝐟_{2} ⟩ = 2$ , so

\begin{aligned} 𝐯_{3} - \frac{12}{3} (1, 1, 1) - \frac{2}{2} (- 1, 0, 1) \\ = (3 - 4 + 1, 4 - 4 - 0, 5 - 4 - 1) = 𝟎 . \end{aligned}

So $𝐯_{3}$ is skipped: by Theorem 6.4.15(b) it lies in $span (𝐯_{1}, 𝐯_{2})$ , and the computation even exhibits the relation $𝐯_{3} =$ $4 𝐟_{1} +$ $𝐟_{2} =$ $4 𝐯_{1} +$ $(𝐯_{2} - 2 𝐯_{1}) =$ $2 𝐯_{1} +$ $𝐯_{2}$ . In the fourth pass,

(0, 0, 1) - \frac{1}{3} (1, 1, 1) - \frac{1}{2} (- 1, 0, 1) = \frac{1}{6} (1, - 2, 1),

which we replace by $(1, - 2, 1)$ . The output, after normalizing, is $(1, 1, 1) / \sqrt{3}$ , $(- 1, 0, 1) / \sqrt{2}$ , $(1, - 2, 1) / \sqrt{6}$ : an orthonormal basis of $span (𝐯_{1}, \dots, 𝐯_{4}) =$ $ℝ^{3}$ .

So Gram–Schmidt also detects linear dependence, much as row reduction does, and the number of vectors it keeps is the dimension of the span.

Example 6.4.19 (Legendre polynomials). Give ${ℝ [𝑥]}_{\leq 3}$ the inner product $⟨ 𝑝, 𝑞 ⟩ =$ $\int_{- 1}^{1} 𝑝 (𝑡) 𝑞 (𝑡) d 𝑡$ of Example 6.3.17, and run Gram–Schmidt on $1, 𝑥, 𝑥^{2}, 𝑥^{3}$ . Since $⟨ 𝑥^{𝑖}, 𝑥^{𝑗} ⟩ =$ $\int_{- 1}^{1} 𝑡^{𝑖 + 𝑗} d 𝑡$ is $2 / (𝑖 + 𝑗 + 1)$ when $𝑖 + 𝑗$ is even and $0$ when $𝑖 + 𝑗$ is odd,

\begin{aligned} 𝑓_{1} & = 1, 𝑓_{2} = 𝑥 - \frac{⟨ 𝑥, 1 ⟩}{{‖ 1 ‖}^{2}} 1 = 𝑥, \\ 𝑓_{3} & = 𝑥^{2} - \frac{⟨ 𝑥^{2}, 1 ⟩}{{‖ 1 ‖}^{2}} 1 - \frac{⟨ 𝑥^{2}, 𝑥 ⟩}{{‖ 𝑥 ‖}^{2}} 𝑥 = 𝑥^{2} - \frac{2 / 3}{2} = 𝑥^{2} - \frac{1}{3}, \end{aligned}

which recovers the orthogonal basis of Example 6.3.17. The next pass gives $𝑓_{4} = 𝑥^{3} - (3 / 5) 𝑥$ , the polynomial of Exercise 6.3.49. By Theorem 6.4.15(d), $span (𝑓_{1}, \dots, 𝑓_{𝑗}) =$ $span (1, 𝑥, \dots, 𝑥^{𝑗 - 1})$ . So $𝑓_{𝑗 + 1} =$ $𝑥^{𝑗} -$ $Pr (𝑥^{𝑗})$ , where the projection is onto the polynomials of degree less than $𝑗$ : it has degree $𝑗$ , leading coefficient $1$ , and is orthogonal to every polynomial of degree less than $𝑗$ . Rescaled so that their value at $1$ is $1$ , these are the Legendre polynomials

\begin{matrix} 𝑃_{0} = 1, 𝑃_{1} = 𝑥, \\ 𝑃_{2} = \frac{1}{2} (3 𝑥^{2} - 1), 𝑃_{3} = \frac{1}{2} (5 𝑥^{3} - 3 𝑥) . \end{matrix}

The output depends on the inner product. The lecture’s example uses $⟨ 𝑝, 𝑞 ⟩ =$ $\int_{0}^{1} 𝑝 (𝑡) 𝑞 (𝑡) d 𝑡$ instead, and Gram–Schmidt applied to $1, 𝑥$ then gives $1, \sqrt{3} (2 𝑥 - 1)$ (compare Exercise 6.4.46).

Now we can show that the hypothesis of Definition 6.4.11 holds for every finite-dimensional subspace.

Theorem 6.4.20 (Orthonormal bases exist).

(a)Every finite-dimensional inner product space has an orthonormal basis.
(b)In a finite-dimensional inner product space, every orthonormal list extends to an orthonormal basis.
(c)Every finite-dimensional subspace $𝑊$ of an inner product space $𝑉$ has an orthonormal basis. In particular, ${Pr}_{𝑊}$ is defined.

Proof.routine

Uses. Theorem 6.4.15 (Gram–Schmidt is correct), Corollary 1.6.24 (Bases exist in finite dimensions), Definition 6.4.11 (Orthogonal projection), Definition 6.1.2 (Inner product)

Hint 1. Run Gram–Schmidt on a basis, or on any spanning list.

Hint 2. For (b), put the orthonormal list in front of a basis of

𝑉

. What does Gram–Schmidt do to vectors that are already orthonormal?

Sketch. (a) Gram–Schmidt turns a basis of

𝑉

into an orthonormal basis of its span, which is

𝑉

(Theorem 6.4.15(c)). (b) Run it on

𝐮_{1},

\dots,

𝐮_{𝑘},

𝐛_{1},

\dots,

𝐛_{𝑛}

for a basis

𝐛_{1}, \dots, 𝐛_{𝑛}

𝑉

: the first

𝑘

residuals are

𝐮_{1}, \dots, 𝐮_{𝑘}

themselves, and the output is an orthonormal basis of

𝑉

that starts with them. (c) The inner product restricted to

𝑊

is an inner product on

𝑊

; apply (a).

(a) Let $𝑉$ be finite-dimensional. It has a basis $𝐛_{1}, \dots, 𝐛_{𝑛}$ (Corollary 1.6.24). By Theorem 6.4.15(c), Gram–Schmidt turns it into an orthonormal basis of $span (𝐛_{1}, \dots, 𝐛_{𝑛}) =$ $𝑉$ .

(b) Let $𝐮_{1}, \dots, 𝐮_{𝑘}$ be orthonormal, and let $𝐛_{1}, \dots, 𝐛_{𝑛}$ be a basis of $𝑉$ . Run Gram–Schmidt on the list $𝐮_{1},$ $\dots,$ $𝐮_{𝑘},$ $𝐛_{1},$ $\dots,$ $𝐛_{𝑛}$ . In pass $𝑗 \leq 𝑘$ , the vectors kept so far are $𝐮_{1}, \dots, 𝐮_{𝑗 - 1}$ (by induction on $𝑗$ ), so the residual is

𝐮_{𝑗} - \sum_{𝑖 = 1}^{𝑗 - 1} ⟨ 𝐮_{𝑗}, 𝐮_{𝑖} ⟩ 𝐮_{𝑖} = 𝐮_{𝑗},

a unit vector, which is kept unchanged. So the output begins with $𝐮_{1}, \dots, 𝐮_{𝑘}$ , and by Theorem 6.4.15(c) it is an orthonormal basis of the span of the whole list, which is $𝑉$ because the list contains a basis.

(c) The inner product of $𝑉$ , restricted to pairs of vectors of $𝑊$ , satisfies the axioms of Definition 6.1.2 on $𝑊$ . So $𝑊$ is a finite-dimensional inner product space, and it has an orthonormal basis by (a). Then ${Pr}_{𝑊}$ is defined by Definition 6.4.11. □

Part (b) is the orthonormal version of extending an independent list to a basis (Theorem 4.1.16). Together with Parseval’s identity, part (a) completes the picture sketched after Theorem 6.3.22: every $𝑛$ -dimensional inner product space has an orthonormal basis, and its coordinates carry the inner product to the dot product of $𝔽^{𝑛}$ .

Exercise 6.4.21.routine In

ℂ^{3}

with the dot product, apply Gram–Schmidt to

𝐯_{1} = (1, 𝑖, 0)

𝐯_{2} = (1, 1, 1)

. What goes wrong if

⟨ 𝐯_{2}, 𝐮_{1} ⟩

is replaced by

⟨ 𝐮_{1}, 𝐯_{2} ⟩

in step 1?

Solution.

Uses. Algorithm 6.4.14 (Gram–Schmidt), Definition 6.1.8 (Dot product), Corollary 6.4.10 (Projecting with an orthogonal list)

Hint 1. Work with residuals:

𝐟_{2} =

𝐯_{2} -

⟨ 𝐯_{2}, 𝐟_{1} ⟩ / {‖ 𝐟_{1} ‖}^{2} 𝐟_{1}

with

𝐟_{1} = 𝐯_{1}

Hint 2.

⟨ 𝐯_{2}, 𝐟_{1} ⟩ =

1 +

𝑖 =

1 -

𝑖

and

{‖ 𝐟_{1} ‖}^{2} = 2

Sketch.

𝐟_{2} =

(1, 1, 1) -

((1 - 𝑖) / 2) (1, 𝑖, 0) =

((1 + 𝑖) / 2, (1 - 𝑖) / 2, 1)

, of squared norm

2

. So

𝐮_{1} = (1, 𝑖, 0) / \sqrt{2}

and

𝐮_{2} =

((1 + 𝑖) / 2, (1 - 𝑖) / 2, 1) / \sqrt{2}

. With the conjugated coefficient

(1 + 𝑖) / 2

, the residual has dot product

- 2 𝑖 \neq 0

with

𝐯_{1}

We use Remark 6.4.16. First $𝐟_{1} = (1, 𝑖, 0)$ with ${‖ 𝐟_{1} ‖}^{2} = 2$ . Next $⟨ 𝐯_{2}, 𝐟_{1} ⟩ =$ $1 \cdot$ $1 +$ $1 \cdot$ $𝑖 +$ $0 =$ $1 -$ $𝑖$ , so

\begin{aligned} 𝐟_{2} & = (1, 1, 1) - \frac{1 - 𝑖}{2} (1, 𝑖, 0) \\ = (1 - \frac{1 - 𝑖}{2}, 1 - \frac{𝑖 + 1}{2}, 1) \\ = (\frac{1 + 𝑖}{2}, \frac{1 - 𝑖}{2}, 1) . \end{aligned}

Check: $𝐟_{2} \cdot$ $𝐟_{1} =$ $(1 + 𝑖) / 2 +$ $((1 - 𝑖) / 2) 𝑖 =$ $(1 + 𝑖) / 2 +$ $(- 𝑖 - 1) / 2 =$ $0$ . Also ${‖ 𝐟_{2} ‖}^{2} =$ $1 / 2 +$ $1 / 2 +$ $1 =$ $2$ . So

𝐮_{1} = \frac{1}{\sqrt{2}} (1, 𝑖, 0), 𝐮_{2} = \frac{1}{\sqrt{2}} (\frac{1 + 𝑖}{2}, \frac{1 - 𝑖}{2}, 1) .

With the slots exchanged, the coefficient becomes $1 - 𝑖 / 2 = (1 + 𝑖) / 2$ , and the “residual” is $(1, 1, 1) -$ $((1 + 𝑖) / 2) (1, 𝑖, 0) =$ $((1 - 𝑖) / 2, (3 - 𝑖) / 2, 1)$ . Its dot product with $𝐯_{1}$ is $(1 - 𝑖) / 2 +$ $((3 - 𝑖) / 2) (- 𝑖) =$ $(1 - 𝑖 - 3 𝑖 - 1) / 2 =$ $- 2 𝑖 \neq$ $0$ , so the output would not be orthogonal.

6.4.3Orthogonal complements

In Orthogonality to a set we defined $𝐴^{⟂}$ for every subset $𝐴$ of $𝑉$ . When $𝐴$ is a subspace, $𝐴^{⟂}$ deserves a name of its own, which we now justify.

Definition 6.4.22 (Orthogonal complement). Let $𝑊$ be a subspace of $𝑉$ . The orthogonal complement of $𝑊$ is the subspace

𝑊^{⟂} = {𝐯 \in 𝑉 | ⟨ 𝐯, 𝐰 ⟩ = 0 for all 𝐰 \in 𝑊}

of Definition 6.3.8.

By Proposition 6.3.9, $𝑊^{⟂}$ is a subspace of $𝑉$ , $𝑊 \cap 𝑊^{⟂} = {𝟎}$ , and $𝑈 \subseteq 𝑊$ implies $𝑊^{⟂} \subseteq 𝑈^{⟂}$ . By Exercise 6.3.11, $𝑊 \subseteq {(𝑊^{⟂})}^{⟂}$ . Note that $𝑊^{⟂}$ depends on the ambient space: the perp of the $𝑥$ -axis is a line in $ℝ^{2}$ and a plane in $ℝ^{3}$ .

Example 6.4.23 (Orthogonal complements).

(a)In $ℝ^{3}$ , ${span ((1, 1, 1))}^{⟂}$ is the plane $𝑊 =$ ${𝐱 | 𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 0}$ of Example 6.4.9 (Example 6.3.10). Conversely $𝑊^{⟂} = span ((1, 1, 1))$ . Indeed $(1, 1, 1)$ is orthogonal to the spanning vectors $(1, - 1, 0)$ and $(1, 1, - 2)$ of $𝑊$ , so $span ((1, 1, 1)) \subseteq 𝑊^{⟂}$ , and Theorem 6.4.26 below gives equality.
(b)For $𝐴 \in ℝ^{𝑚 \times 𝑛}$ , let $𝑅 \subseteq ℝ^{𝑛}$ be the span of the rows of $𝐴$ . By Example 6.3.10 and Proposition 6.3.9(c), $ker 𝐴 = 𝑅^{⟂}$ : solving $𝐴 𝐱 = 𝟎$ means finding the vectors orthogonal to every row.
(c)In $𝐶 [- 1, 1]$ with $⟨ 𝑓, 𝑔 ⟩ =$ $\int_{- 1}^{1} 𝑓 (𝑡) 𝑔 (𝑡) d 𝑡$ , every odd function is orthogonal to every even function (Example 6.3.2(c)). Exercise 6.4.54 shows that the odd functions form exactly the orthogonal complement of the even functions.

The main theorem says that $𝑊^{⟂}$ really is a complement of $𝑊$ , as soon as $𝑊$ is finite-dimensional. The proof is already contained in Proposition 6.4.4: every vector is its projection onto $𝑊$ plus something orthogonal to $𝑊$ .

Theorem 6.4.24 (Orthogonal decomposition). Let $𝑊$ be a finite-dimensional subspace of $𝑉$ . Every $𝐯 \in 𝑉$ can be written in exactly one way as

𝐯 = 𝐰 + 𝐰^{'} with 𝐰 \in 𝑊 and 𝐰^{'} \in 𝑊^{⟂},

namely with $𝐰 = {Pr}_{𝑊} (𝐯)$ and $𝐰^{'} = 𝐯 - {Pr}_{𝑊} (𝐯)$ . That is, $𝑉 = 𝑊 \oplus 𝑊^{⟂}$ .

Proof.routine

Uses. Theorem 6.4.20 (Orthonormal bases exist), Proposition 6.4.4 (Properties of ${Pr}_{𝒪︀}$ ), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ), Definition 4.4.4 (Direct sum), Theorem 4.4.7 (Criteria for direct sums)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. For existence,

{Pr}_{𝑊}

is defined because

𝑊

has an orthonormal basis. Which properties of

{Pr}_{𝑊} (𝐯)

do you need?

Hint 2. For uniqueness, suppose

𝐰 + 𝐰^{'} = 𝐱 + 𝐱^{'}

with

𝐰, 𝐱 \in 𝑊

and

𝐰^{'}, 𝐱^{'} \in 𝑊^{⟂}

, and rearrange.

Sketch. By Theorem 6.4.20,

{Pr}_{𝑊}

is defined, and

𝐯 =

{Pr}_{𝑊} (𝐯) +

(𝐯 - {Pr}_{𝑊} (𝐯))

has its first piece in

𝑊

and its second in

𝑊^{⟂}

by Proposition 6.4.4. If

𝐰 + 𝐰^{'} = 𝐱 + 𝐱^{'}

are two such decompositions, then

𝐰 - 𝐱 = 𝐱^{'} - 𝐰^{'}

lies in

𝑊 \cap 𝑊^{⟂} = {𝟎}

By Theorem 6.4.20, $𝑊$ has an orthonormal basis, so ${Pr}_{𝑊}$ is defined. For $𝐯 \in 𝑉$ , (a) and (b) of Proposition 6.4.4 give ${Pr}_{𝑊} (𝐯) \in 𝑊$ and $𝐯 - {Pr}_{𝑊} (𝐯) \in 𝑊^{⟂}$ , and these two vectors add up to $𝐯$ . So a decomposition exists.

Suppose $𝐯 = 𝐰 + 𝐰^{'} = 𝐱 + 𝐱^{'}$ with $𝐰, 𝐱 \in 𝑊$ and $𝐰^{'}, 𝐱^{'} \in 𝑊^{⟂}$ . Then

𝐰 - 𝐱 = 𝐱^{'} - 𝐰^{'} .

The left side lies in $𝑊$ and the right side in $𝑊^{⟂}$ , since both are subspaces. So both sides lie in $𝑊 \cap 𝑊^{⟂} = {𝟎}$ (Proposition 6.3.9(d)), and $𝐰 = 𝐱$ , $𝐰^{'} = 𝐱^{'}$ . In the language of Section 4.4, $𝑉 = 𝑊 + 𝑊^{⟂}$ and $𝑊 \cap 𝑊^{⟂} = {𝟎}$ , so the sum is direct (Theorem 4.4.7, Definition 4.4.4). □

Uniqueness can also be read off from Theorem 6.4.6: if $𝐯 = 𝐰 + 𝐰^{'}$ with $𝐰 \in 𝑊$ and $𝐰^{'} \in 𝑊^{⟂}$ , then $𝐰 \in 𝑊$ and $𝐯 - 𝐰 = 𝐰^{'} ⟂ 𝑊$ , so $𝐰 = {Pr}_{𝑊} (𝐯)$ . In $ℝ^{3}$ the theorem says that every vector is the sum of a vector in a given plane through $𝟎$ and a vector along the normal line, which is how one splits a force into the part along a surface and the part pushing against it.

Note what was assumed: $𝑊$ is finite-dimensional, but $𝑉$ need not be. When $𝑊$ is infinite-dimensional the theorem can fail. Exercise 6.4.63 gives a proper subspace $𝑊$ of an inner product space $𝑉$ with $𝑊^{⟂} = {𝟎}$ , so that $𝑊 + 𝑊^{⟂} = 𝑊 \neq 𝑉$ ; Section 15.3 explains what survives in infinite dimensions.

Corollary 6.4.25 (Dimension of the orthogonal complement). Let

𝑉

be finite-dimensional and

𝑊

a subspace of

𝑉

. Then

dim 𝑊^{⟂} =

dim 𝑉 -

dim 𝑊

. More precisely, if

𝐮_{1}, \dots, 𝐮_{𝑛}

is an orthonormal basis of

𝑉

whose first

𝑘

vectors form an orthonormal basis of

𝑊

, then

𝐮_{𝑘 + 1}, \dots, 𝐮_{𝑛}

is an orthonormal basis of

𝑊^{⟂}

Proof (by the dimension formula).routine

Uses. Theorem 6.4.24 (Orthogonal decomposition), Theorem 4.4.19 (Dimension of a sum), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ), Proposition 4.1.21 (Dimensions of subspaces)

Techniques. Dimension counting (Technique 4.2.24)

Hint 1.

𝑊

and

𝑊^{⟂}

are finite-dimensional because

𝑉

is. What does Theorem 6.4.24 say about

𝑊 + 𝑊^{⟂}

and

𝑊 \cap 𝑊^{⟂}

Hint 2. Apply

dim (𝑊 + 𝑊^{⟂}) =

dim 𝑊 +

dim 𝑊^{⟂} -

dim (𝑊 \cap 𝑊^{⟂})

Sketch.

𝑉 = 𝑊 + 𝑊^{⟂}

and

𝑊 \cap 𝑊^{⟂} = {𝟎}

, so the dimension formula gives

dim 𝑉 =

dim 𝑊 +

dim 𝑊^{⟂} -

0

Subspaces of the finite-dimensional space $𝑉$ are finite-dimensional (Proposition 4.1.21). By Theorem 6.4.24, $𝑊 + 𝑊^{⟂} = 𝑉$ , and $𝑊 \cap 𝑊^{⟂} = {𝟎}$ by Proposition 6.3.9(d). By Theorem 4.4.19,

\begin{aligned} dim 𝑉 & = dim (𝑊 + 𝑊^{⟂}) \\ = dim 𝑊 + dim 𝑊^{⟂} - dim (𝑊 \cap 𝑊^{⟂}) \\ = dim 𝑊 + dim 𝑊^{⟂}, \end{aligned}

which gives the dimension formula. The statement about bases is proved in the second approach. □

Proof (by extending an orthonormal basis).routine

Uses. Theorem 6.4.20 (Orthonormal bases exist), Proposition 6.3.18 (Coordinates in an orthonormal basis), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ), Definition 6.3.15 (Orthonormal list, orthonormal basis)

Techniques. Double containment (Technique 1.3.14), Take an inner product to isolate a coefficient (Technique 6.3.12)

Hint 1. Take an orthonormal basis

𝐮_{1}, \dots, 𝐮_{𝑘}

𝑊

and extend it to an orthonormal basis

𝐮_{1}, \dots, 𝐮_{𝑛}

𝑉

with Theorem 6.4.20(b). Guess

𝑊^{⟂}

Hint 2. Show

span (𝐮_{𝑘 + 1}, \dots, 𝐮_{𝑛}) =

𝑊^{⟂}

by double containment. For

\subseteq

, test against the spanning list

𝐮_{1}, \dots, 𝐮_{𝑘}

𝑊

. For

\supseteq

, expand

𝐯 \in 𝑊^{⟂}

in the basis.

Sketch. Extend an orthonormal basis

𝐮_{1}, \dots, 𝐮_{𝑘}

𝑊

to one of

𝑉

. Each

𝐮_{𝑗}

with

𝑗 > 𝑘

is orthogonal to

𝐮_{1}, \dots, 𝐮_{𝑘}

, hence to

𝑊

. Conversely,

𝐯 \in 𝑊^{⟂}

has

⟨ 𝐯, 𝐮_{𝑗} ⟩ = 0

for

𝑗 \leq 𝑘

, so its expansion

\sum_{𝑗} ⟨ 𝐯, 𝐮_{𝑗} ⟩ 𝐮_{𝑗}

involves only

𝐮_{𝑘 + 1}, \dots, 𝐮_{𝑛}

. So

𝐮_{𝑘 + 1}, \dots, 𝐮_{𝑛}

is an orthonormal basis of

𝑊^{⟂}

, and

dim 𝑊^{⟂} = 𝑛 - 𝑘

By Theorem 6.4.20, $𝑊$ has an orthonormal basis $𝐮_{1}, \dots, 𝐮_{𝑘}$ , and it extends to an orthonormal basis $𝐮_{1}, \dots, 𝐮_{𝑛}$ of $𝑉$ , where $𝑛 = dim 𝑉$ . (Conversely, every orthonormal basis of $𝑉$ whose first $𝑘$ vectors span $𝑊$ arises this way.) Let $𝑈 =$ $span (𝐮_{𝑘 + 1}, \dots, 𝐮_{𝑛})$ . We show $𝑈 = 𝑊^{⟂}$ by double containment.

For $𝑗 > 𝑘$ , $𝐮_{𝑗}$ is orthogonal to $𝐮_{1}, \dots, 𝐮_{𝑘}$ , so $𝐮_{𝑗} \in 𝑊^{⟂}$ by Proposition 6.3.9(c). As $𝑊^{⟂}$ is a subspace, $𝑈 \subseteq 𝑊^{⟂}$ . Conversely, let $𝐯 \in 𝑊^{⟂}$ . Then $⟨ 𝐯, 𝐮_{𝑗} ⟩ = 0$ for $𝑗 \leq 𝑘$ , so by Proposition 6.3.18(b),

𝐯 = \sum_{𝑗 = 1}^{𝑛} ⟨ 𝐯, 𝐮_{𝑗} ⟩ 𝐮_{𝑗} = \sum_{𝑗 = 𝑘 + 1}^{𝑛} ⟨ 𝐯, 𝐮_{𝑗} ⟩ 𝐮_{𝑗} \in 𝑈 .

So $𝑊^{⟂} = 𝑈$ . The list $𝐮_{𝑘 + 1}, \dots, 𝐮_{𝑛}$ is orthonormal and spans $𝑊^{⟂}$ , so it is an orthonormal basis of $𝑊^{⟂}$ , and $dim 𝑊^{⟂} =$ $𝑛 -$ $𝑘 =$ $dim 𝑉 -$ $dim 𝑊$ . □

The first proof counts. The second builds the basis of $𝑊^{⟂}$ , and it shows that, in coordinates with respect to an orthonormal basis adapted to $𝑊$ , the decomposition $𝐯 =$ ${Pr}_{𝑊} (𝐯) +$ $(𝐯 - {Pr}_{𝑊} (𝐯))$ simply splits the coordinate vector into its first $𝑘$ entries and the rest.

For the matrix $𝐴$ of Example 6.4.23(b), the corollary gives $dim 𝑅 = 𝑛 - dim ker 𝐴$ , and rank–nullity (Theorem 4.2.11) gives $dim im 𝐴 =$ $𝑛 -$ $dim ker 𝐴$ . So the rows of a real matrix span a space of the same dimension as its columns. This is Theorem 4.3.8 for real matrices, obtained here by a dimension count.

Since $𝑊 \subseteq {(𝑊^{⟂})}^{⟂}$ always holds, the next question is whether taking the complement twice returns $𝑊$ . In $ℝ^{3}$ the complement of a plane is its normal line, and the complement of that line is the plane again.

Theorem 6.4.26 (The double complement). Let

𝑊

be a finite-dimensional subspace of

𝑉

. Then

{(𝑊^{⟂})}^{⟂} = 𝑊

Proof (by the orthogonal decomposition).standard

Uses. Theorem 6.4.24 (Orthogonal decomposition), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ), Exercise 6.3.11

Techniques. Double containment (Technique 1.3.14)

Hint 1. One containment,

𝑊 \subseteq {(𝑊^{⟂})}^{⟂}

, holds for every subset (Exercise 6.3.11). For the other, take

𝐯 \in {(𝑊^{⟂})}^{⟂}

and decompose it with Theorem 6.4.24.

Hint 2. Write

𝐯 = {Pr}_{𝑊} (𝐯) + 𝐰^{'}

with

𝐰^{'} \in 𝑊^{⟂}

. Show that

𝐰^{'}

also lies in

{(𝑊^{⟂})}^{⟂}

Sketch.

𝑊 \subseteq {(𝑊^{⟂})}^{⟂}

always. Conversely, if

𝐯 \in {(𝑊^{⟂})}^{⟂}

, write

𝐯 = {Pr}_{𝑊} (𝐯) + 𝐰^{'}

with

𝐰^{'} \in 𝑊^{⟂}

. Both

𝐯

and

{Pr}_{𝑊} (𝐯) \in 𝑊

lie in the subspace

{(𝑊^{⟂})}^{⟂}

, so

𝐰^{'} \in

𝑊^{⟂} \cap

{(𝑊^{⟂})}^{⟂} =

{𝟎}

, and

𝐯 = {Pr}_{𝑊} (𝐯) \in 𝑊

By Exercise 6.3.11,

𝑊 \subseteq {(𝑊^{⟂})}^{⟂}

. Conversely, let

𝐯 \in {(𝑊^{⟂})}^{⟂}

. By Theorem 6.4.24,

𝐯 = {Pr}_{𝑊} (𝐯) + 𝐰^{'}

with

𝐰^{'} \in 𝑊^{⟂}

. Here

𝐯 \in {(𝑊^{⟂})}^{⟂}

by assumption and

{Pr}_{𝑊} (𝐯) \in

𝑊 \subseteq

{(𝑊^{⟂})}^{⟂}

, so

𝐰^{'} =

𝐯 -

{Pr}_{𝑊} (𝐯) \in

{(𝑊^{⟂})}^{⟂}

, since

{(𝑊^{⟂})}^{⟂}

is a subspace. So

𝐰^{'}

lies in

𝑊^{⟂}

and in

{(𝑊^{⟂})}^{⟂}

, and Proposition 6.3.9(d), applied to the subspace

𝑊^{⟂}

, gives

𝐰^{'} = 𝟎

. Hence

𝐯 = {Pr}_{𝑊} (𝐯) \in 𝑊

. □

Proof (by counting dimensions, when $𝑉$ is finite-dimensional).routine

Uses. Corollary 6.4.25 (Dimension of the orthogonal complement), Proposition 4.1.21 (Dimensions of subspaces), Exercise 6.3.11

Techniques. Dimension counting (Technique 4.2.24)

Hint 1. You know

𝑊 \subseteq {(𝑊^{⟂})}^{⟂}

. Compare dimensions.

Hint 2. Apply Corollary 6.4.25 twice: once to

𝑊

and once to

𝑊^{⟂}

Sketch.

𝑊 \subseteq {(𝑊^{⟂})}^{⟂}

, and

dim {(𝑊^{⟂})}^{⟂} =

𝑛 -

(𝑛 - dim 𝑊) =

dim 𝑊

by Corollary 6.4.25 applied twice. A subspace of the same finite dimension as a space containing it is that space.

Suppose $𝑉$ is finite-dimensional, with $𝑛 = dim 𝑉$ . By Corollary 6.4.25, applied to $𝑊$ and then to $𝑊^{⟂}$ ,

dim {(𝑊^{⟂})}^{⟂} = 𝑛 - dim 𝑊^{⟂} = 𝑛 - (𝑛 - dim 𝑊) = dim 𝑊 .

Since $𝑊 \subseteq {(𝑊^{⟂})}^{⟂}$ (Exercise 6.3.11) and the dimensions agree, $𝑊 = {(𝑊^{⟂})}^{⟂}$ by Proposition 4.1.21. □

The second proof is shorter but needs $𝑉$ finite-dimensional, so that $𝑊^{⟂}$ has a dimension at all. The first needs only that $𝑊$ is finite-dimensional, which is the setting of the approximation problems below, where $𝑉$ is a space of functions.

Corollary 6.4.27 (Testing whether a subspace is everything). Let

𝑊

be a finite-dimensional subspace of

𝑉

. Then

𝑊 = 𝑉

if and only if

𝑊^{⟂} = {𝟎}

Proof.routine

Uses. Theorem 6.4.24 (Orthogonal decomposition), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ )

Hint 1. One direction is

𝑉^{⟂} = {𝟎}

(Proposition 6.3.9(d)).

Hint 2. For the other, decompose an arbitrary

𝐯 \in 𝑉

with Theorem 6.4.24.

Sketch. If

𝑊 = 𝑉

, then

𝑊^{⟂} = 𝑉^{⟂} = {𝟎}

. If

𝑊^{⟂} = {𝟎}

, then every

𝐯

equals

{Pr}_{𝑊} (𝐯) + 𝟎 \in 𝑊

𝑊 = 𝑉

, then

𝑊^{⟂} = 𝑉^{⟂} = {𝟎}

by Proposition 6.3.9(d). Conversely, suppose

𝑊^{⟂} = {𝟎}

, and let

𝐯 \in 𝑉

. By Theorem 6.4.24,

𝐯 -

{Pr}_{𝑊} (𝐯) \in

𝑊^{⟂} =

{𝟎}

, so

𝐯 = {Pr}_{𝑊} (𝐯) \in 𝑊

. Hence

𝑊 = 𝑉

. □

So to show that a finite-dimensional subspace $𝑊$ is all of $𝑉$ , it suffices to show that the only vector orthogonal to $𝑊$ is $𝟎$ .

Exercise 6.4.28.routine Let

𝑊 =

{𝐱 \in ℝ^{4} | 𝑥_{1} + 𝑥_{2} + 𝑥_{3} + 𝑥_{4} = 0}

. Find

𝑊^{⟂}

, a formula for

{Pr}_{𝑊^{⟂}}

, and the vector of

𝑊

closest to

𝐞_{1}

Solution.

Uses. Theorem 6.4.26 (The double complement), Corollary 6.4.10 (Projecting with an orthogonal list), Theorem 6.4.6 (The projection is characterized by orthogonality), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ )

Techniques. Recognize a projection by its two conditions (Technique 6.4.7)

Hint 1.

𝑊 = {span (𝐣)}^{⟂}

for

𝐣 = (1, 1, 1, 1)

. Apply Theorem 6.4.26.

Hint 2.

{Pr}_{𝑊^{⟂}}

is the projection onto a line. For the closest vector, guess

𝐞_{1} - {Pr}_{𝑊^{⟂}} (𝐞_{1})

and check the two conditions of Technique 6.4.7 for the subspace

𝑊

Sketch.

𝑊 = {span (𝐣)}^{⟂}

, so

𝑊^{⟂} = span (𝐣)

by Theorem 6.4.26, and

{Pr}_{𝑊^{⟂}} (𝐱) =

((𝑥_{1} + 𝑥_{2} + 𝑥_{3} + 𝑥_{4}) / 4) 𝐣

. The vector

𝐩 =

𝐞_{1} -

𝐣 / 4 =

(3 / 4, - 1 / 4, - 1 / 4, - 1 / 4)

lies in

𝑊

, and

𝐞_{1} - 𝐩 = 𝐣 / 4 \in 𝑊^{⟂}

, so

𝐩 = {Pr}_{𝑊} (𝐞_{1})

Let $𝐣 = (1, 1, 1, 1)$ . Then $𝑊 =$ ${𝐣}^{⟂} =$ ${span (𝐣)}^{⟂}$ by Proposition 6.3.9(c), and $span (𝐣)$ is finite-dimensional, so Theorem 6.4.26 gives $𝑊^{⟂} =$ ${({span (𝐣)}^{⟂})}^{⟂} =$ $span (𝐣)$ . By Corollary 6.4.10 with the single vector $𝐣$ , ${‖ 𝐣 ‖}^{2} = 4$ ,

{Pr}_{𝑊^{⟂}} (𝐱) = \frac{𝑥_{1} + 𝑥_{2} + 𝑥_{3} + 𝑥_{4}}{4} 𝐣 .

In particular ${Pr}_{𝑊^{⟂}} (𝐞_{1}) = 𝐣 / 4$ . Let

𝐩 = 𝐞_{1} - \frac{1}{4} 𝐣 = (\frac{3}{4}, - \frac{1}{4}, - \frac{1}{4}, - \frac{1}{4}) .

Its coordinates add up to $0$ , so $𝐩 \in 𝑊$ , and $𝐞_{1} - 𝐩 = 𝐣 / 4 \in 𝑊^{⟂}$ . By Theorem 6.4.6 (applied with an orthonormal basis of $𝑊$ ), $𝐩 = {Pr}_{𝑊} (𝐞_{1})$ . By Theorem 6.4.33 below, this is the vector of $𝑊$ closest to $𝐞_{1}$ , at distance $‖ 𝐣 / 4 ‖ = 1 / 2$ . (Proposition 6.4.29(d) below explains the shortcut: ${Pr}_{𝑊} = id - {Pr}_{𝑊^{⟂}}$ .)

The projection as a linear map

We now collect the properties of ${Pr}_{𝑊}$ as a map $𝑉 \to 𝑉$ .

Proposition 6.4.29 (The orthogonal projection as a linear map). Let $𝑊$ be a finite-dimensional subspace of $𝑉$ , and let $𝑃 = {Pr}_{𝑊}$ .

(a) $𝑃$ is linear, $im 𝑃 = 𝑊$ , and $ker 𝑃 = 𝑊^{⟂}$ .
(b) $𝑃^{2} = 𝑃$ . In fact $𝑃 (𝐰) = 𝐰$ for every $𝐰 \in 𝑊$ .
(c) $⟨ 𝑃 𝐯, 𝐱 ⟩ =$ $⟨ 𝑃 𝐯, 𝑃 𝐱 ⟩ =$ $⟨ 𝐯, 𝑃 𝐱 ⟩$ for all $𝐯, 𝐱 \in 𝑉$ .
(d)If $𝑉$ is finite-dimensional, then ${id}_{𝑉} - 𝑃 = {Pr}_{𝑊^{⟂}}$ .

Proof.routine

Uses. Proposition 6.4.4 (Properties of ${Pr}_{𝒪︀}$ ), Theorem 6.4.6 (The projection is characterized by orthogonality), Definition 6.4.11 (Orthogonal projection), Theorem 6.4.20 (Orthonormal bases exist), Proposition 4.1.21 (Dimensions of subspaces), Exercise 6.3.11

Techniques. Recognize a projection by its two conditions (Technique 6.4.7)

Hint 1. For

ker 𝑃

, apply Theorem 6.4.6: when is

𝟎

the vector

𝐩

with

𝐩 \in 𝑊

and

𝐯 - 𝐩 ⟂ 𝑊

Hint 2. For (c), split the vector in the second slot as

𝐱 = 𝑃 𝐱 + (𝐱 - 𝑃 𝐱)

, and the vector in the first slot similarly.

Hint 3. For (d), check that

𝐯 - 𝑃 𝐯

satisfies the two conditions that characterize

{Pr}_{𝑊^{⟂}} (𝐯)

Sketch. (a) Linearity is Proposition 6.4.4(d). The image lies in

𝑊

and contains every

𝐰 = 𝑃 𝐰

𝑃 𝐯 = 𝟎

if and only if

𝟎 \in 𝑊

and

𝐯 - 𝟎 ⟂ 𝑊

, that is,

𝐯 \in 𝑊^{⟂}

. (b)

𝑃 𝐯 \in 𝑊

is fixed. (c)

⟨ 𝑃 𝐯, 𝐱 - 𝑃 𝐱 ⟩ = 0

and

⟨ 𝐯 - 𝑃 𝐯, 𝑃 𝐱 ⟩ = 0

. (d)

𝐯 - 𝑃 𝐯 \in 𝑊^{⟂}

, and

𝐯 -

(𝐯 - 𝑃 𝐯) =

𝑃 𝐯 \in

𝑊

is orthogonal to

𝑊^{⟂}

(a) $𝑃$ is linear by Proposition 6.4.4(d), and $im 𝑃 \subseteq 𝑊$ by part (a) of the same proposition. If $𝐰 \in 𝑊$ , then $𝑃 𝐰 = 𝐰$ by part (c), so $𝑊 \subseteq im 𝑃$ . For the kernel: by Theorem 6.4.6, $𝑃 𝐯 = 𝟎$ if and only if $𝟎$ satisfies $𝟎 \in 𝑊$ and $𝐯 - 𝟎 \in 𝑊^{⟂}$ , that is, if and only if $𝐯 \in 𝑊^{⟂}$ .

(b) For $𝐯 \in 𝑉$ , $𝑃 𝐯 \in 𝑊$ , so $𝑃 (𝑃 𝐯) = 𝑃 𝐯$ by Proposition 6.4.4(c).

(c) Let $𝐯, 𝐱 \in 𝑉$ . Since $𝑃 𝐯 \in 𝑊$ and $𝐱 - 𝑃 𝐱 \in 𝑊^{⟂}$ ,

⟨ 𝑃 𝐯, 𝐱 ⟩ = ⟨ 𝑃 𝐯, 𝑃 𝐱 ⟩ + ⟨ 𝑃 𝐯, 𝐱 - 𝑃 𝐱 ⟩ = ⟨ 𝑃 𝐯, 𝑃 𝐱 ⟩ .

Similarly, since $𝐯 - 𝑃 𝐯 \in 𝑊^{⟂}$ and $𝑃 𝐱 \in 𝑊$ ,

⟨ 𝐯, 𝑃 𝐱 ⟩ = ⟨ 𝑃 𝐯, 𝑃 𝐱 ⟩ + ⟨ 𝐯 - 𝑃 𝐯, 𝑃 𝐱 ⟩ = ⟨ 𝑃 𝐯, 𝑃 𝐱 ⟩ .

(d) Since $𝑉$ is finite-dimensional, so is $𝑊^{⟂}$ (Proposition 4.1.21), so ${Pr}_{𝑊^{⟂}}$ is defined (Theorem 6.4.20). Let $𝐯 \in 𝑉$ and $𝐩 = 𝐯 - 𝑃 𝐯$ . Then $𝐩 \in 𝑊^{⟂}$ by Proposition 6.4.4(b), and $𝐯 -$ $𝐩 =$ $𝑃 𝐯 \in$ $𝑊 \subseteq$ ${(𝑊^{⟂})}^{⟂}$ (Exercise 6.3.11). These are the two conditions of Theorem 6.4.6 for the subspace $𝑊^{⟂}$ , so $𝐩 = {Pr}_{𝑊^{⟂}} (𝐯)$ . □

In (d), finite-dimensionality of $𝑉$ was used only to know that ${Pr}_{𝑊^{⟂}}$ is defined. For any $𝑉$ , the map $𝐯 \mapsto 𝐯 - {Pr}_{𝑊} (𝐯)$ is linear, has image $𝑊^{⟂}$ , and picks out the $𝑊^{⟂}$ -component in Theorem 6.4.24.

Parts (b) and (c) characterize orthogonal projections among all linear maps. Part (b) alone does not: the map $𝑃$ of Remark 6.4.12 satisfies $𝑃^{2} = 𝑃$ , but $⟨ 𝑃 𝐞_{2}, 𝐞_{1} ⟩ =$ $⟨ (- 1, 0), (1, 0) ⟩ =$ $- 1$ while $⟨ 𝐞_{2}, 𝑃 𝐞_{1} ⟩ =$ $⟨ 𝐞_{2}, 𝐞_{1} ⟩ =$ $0$ .

Proposition 6.4.30 (Recognizing orthogonal projections). Let $𝑉$ be finite-dimensional and $𝑃 \in L (𝑉)$ . Then $𝑃 = {Pr}_{𝑊}$ for some subspace $𝑊$ of $𝑉$ if and only if

𝑃^{2} = 𝑃 and ⟨ 𝑃 𝐯, 𝐱 ⟩ = ⟨ 𝐯, 𝑃 𝐱 ⟩ for all 𝐯, 𝐱 \in 𝑉 .

In that case $𝑊 = im 𝑃$ .

Proof.standard

Uses. Proposition 6.4.29 (The orthogonal projection as a linear map), Theorem 6.4.6 (The projection is characterized by orthogonality), Theorem 6.4.20 (Orthonormal bases exist), Proposition 4.1.21 (Dimensions of subspaces)

Techniques. Recognize a projection by its two conditions (Technique 6.4.7)

Hint 1. One direction is Proposition 6.4.29(a)–(c). For the other, the only candidate is

𝑊 = im 𝑃

. Check the two conditions that characterize

{Pr}_{𝑊} (𝐯)

for the vector

𝑃 𝐯

Hint 2. Every vector of

𝑊

has the form

𝑃 𝐱

. Move

𝑃

across the inner product:

⟨ 𝐯 - 𝑃 𝐯, 𝑃 𝐱 ⟩ =

⟨ 𝑃 (𝐯 - 𝑃 𝐯), 𝐱 ⟩

Sketch. If

𝑃 = {Pr}_{𝑊}

, then

𝑃^{2} = 𝑃

, the symmetry holds, and

im 𝑃 = 𝑊

, by Proposition 6.4.29. Conversely, let

𝑊 = im 𝑃

. Then

𝑃 𝐯 \in 𝑊

, and for every

𝑃 𝐱 \in 𝑊

⟨ 𝐯 - 𝑃 𝐯, 𝑃 𝐱 ⟩ =

⟨ 𝑃 𝐯 - 𝑃^{2} 𝐯, 𝐱 ⟩ =

0

. So

𝑃 𝐯 = {Pr}_{𝑊} (𝐯)

by Theorem 6.4.6.

If $𝑃 = {Pr}_{𝑊}$ , then $𝑃^{2} = 𝑃$ and $⟨ 𝑃 𝐯, 𝐱 ⟩ =$ $⟨ 𝐯, 𝑃 𝐱 ⟩$ by (b) and (c) of Proposition 6.4.29, and $im 𝑃 = 𝑊$ by part (a).

Conversely, suppose $𝑃$ has the two properties, and let $𝑊 = im 𝑃$ . It is a subspace of the finite-dimensional space $𝑉$ , so it is finite-dimensional (Proposition 4.1.21) and ${Pr}_{𝑊}$ is defined (Theorem 6.4.20). Let $𝐯 \in 𝑉$ . Then $𝑃 𝐯 \in 𝑊$ . Every vector of $𝑊$ has the form $𝑃 𝐱$ for some $𝐱 \in 𝑉$ , and by the second property, applied to the vectors $𝐯 - 𝑃 𝐯$ and $𝐱$ ,

\begin{aligned} ⟨ 𝐯 - 𝑃 𝐯, 𝑃 𝐱 ⟩ & = ⟨ 𝑃 (𝐯 - 𝑃 𝐯), 𝐱 ⟩ \\ = ⟨ 𝑃 𝐯 - 𝑃^{2} 𝐯, 𝐱 ⟩ = ⟨ 𝟎, 𝐱 ⟩ = 0 . \end{aligned}

So $𝐯 - 𝑃 𝐯 \in 𝑊^{⟂}$ . By Theorem 6.4.6, $𝑃 𝐯 = {Pr}_{𝑊} (𝐯)$ . As $𝐯$ was arbitrary, $𝑃 = {Pr}_{𝑊}$ . □

The second condition says that $𝑃$ can be moved from one slot of the inner product to the other. In the language of Section 6.6, it says that $𝑃$ equals its adjoint, $𝑃^{*} = 𝑃$ , that is, $𝑃$ is self-adjoint (Definition 6.6.26). So the orthogonal projections are exactly the operators with $𝑃^{2} = 𝑃 = 𝑃^{*}$ . For $𝑉 = 𝔽^{𝑛}$ with the dot product, Proposition 6.3.27(d) shows that the condition says that the matrix of $𝑃$ is Hermitian.

Projection matrices

In $𝔽^{𝑛}$ with the dot product, ${Pr}_{𝑊}$ is a linear map $𝔽^{𝑛} \to 𝔽^{𝑛}$ , so it is multiplication by a matrix. The matrix is built from an orthonormal basis of $𝑊$ and its conjugate transpose.

Theorem 6.4.31 (The matrix of an orthogonal projection). Let $𝑊$ be a subspace of $𝔽^{𝑛}$ with the dot product, let $𝐮_{1}, \dots, 𝐮_{𝑘}$ be an orthonormal basis of $𝑊$ , and let $𝑄 \in 𝔽^{𝑛 \times 𝑘}$ be the matrix with columns $𝐮_{1}, \dots, 𝐮_{𝑘}$ . Then

{Pr}_{𝑊} (𝐱) = 𝑄 𝑄^{*} 𝐱 for all 𝐱 \in 𝔽^{𝑛},

and $𝑄 𝑄^{*} =$ $𝐮_{1} 𝐮_{1}^{*} +$ $\dots +$ $𝐮_{𝑘} 𝐮_{𝑘}^{*}$ . Moreover $𝑄^{*} 𝑄 = 𝐼_{𝑘}$ , while the $𝑛 \times 𝑛$ matrix $𝑃 = 𝑄 𝑄^{*}$ satisfies $𝑃^{2} = 𝑃$ and $𝑃^{*} = 𝑃$ .

Proof.routine

Uses. Definition 6.3.26 (Conjugate transpose), Proposition 2.4.8 (Four views of the product), Definition 6.1.8 (Dot product), Theorem 6.3.29 (Orthonormal columns), Proposition 6.3.27 (Properties of the conjugate transpose), Proposition 2.4.14 (Algebra of matrices)

Hint 1. Compute

𝑄^{*} 𝐱

entry by entry. Row

𝑖

𝑄^{*}

𝐮_{𝑖}^{*}

Hint 2. The entries of

𝑄^{*} 𝐱

are the coefficients

⟨ 𝐱, 𝐮_{𝑖} ⟩

, and multiplying by

𝑄

combines the columns of

𝑄

with these coefficients.

Sketch. The

𝑖

th entry of

𝑄^{*} 𝐱

𝐮_{𝑖}^{*} 𝐱 =

𝐱 \cdot

𝐮_{𝑖} =

⟨ 𝐱, 𝐮_{𝑖} ⟩

, so

𝑄 (𝑄^{*} 𝐱) =

\sum_{𝑖} ⟨ 𝐱, 𝐮_{𝑖} ⟩ 𝐮_{𝑖} =

{Pr}_{𝑊} (𝐱)

. Columns times rows gives

𝑄 𝑄^{*} =

\sum_{𝑖} 𝐮_{𝑖} 𝐮_{𝑖}^{*}

. Then

𝑄^{*} 𝑄 = 𝐼_{𝑘}

is Theorem 6.3.29, so

{(𝑄 𝑄^{*})}^{2} =

𝑄 (𝑄^{*} 𝑄) 𝑄^{*} =

𝑄 𝑄^{*}

, and

{(𝑄 𝑄^{*})}^{*} = 𝑄 𝑄^{*}

Row $𝑖$ of $𝑄^{*}$ is $𝐮_{𝑖}^{*}$ (Definition 6.3.26), so the $𝑖$ th entry of $𝑄^{*} 𝐱$ is $𝐮_{𝑖}^{*} 𝐱 =$ $𝐱 \cdot$ $𝐮_{𝑖} =$ $⟨ 𝐱, 𝐮_{𝑖} ⟩$ (Definition 6.1.8). By the column view of Proposition 2.4.8, $𝑄 (𝑄^{*} 𝐱)$ is the combination of the columns of $𝑄$ with these coefficients:

𝑄 𝑄^{*} 𝐱 = \sum_{𝑖 = 1}^{𝑘} ⟨ 𝐱, 𝐮_{𝑖} ⟩ 𝐮_{𝑖} = {Pr}_{𝑊} (𝐱) .

The columns-times-rows view of Proposition 2.4.8 gives $𝑄 𝑄^{*} =$ $\sum_{𝑖} 𝐮_{𝑖} 𝐮_{𝑖}^{*}$ , since column $𝑖$ of $𝑄$ is $𝐮_{𝑖}$ and row $𝑖$ of $𝑄^{*}$ is $𝐮_{𝑖}^{*}$ . Next, $𝑄^{*} 𝑄 = 𝐼_{𝑘}$ by Theorem 6.3.29. Hence, by associativity and Proposition 6.3.27,

\begin{aligned} {(𝑄 𝑄^{*})}^{2} & = 𝑄 (𝑄^{*} 𝑄) 𝑄^{*} = 𝑄 𝑄^{*}, \\ {(𝑄 𝑄^{*})}^{*} & = {(𝑄^{*})}^{*} 𝑄^{*} = 𝑄 𝑄^{*} . \end{aligned}

□

The two products of $𝑄$ and $𝑄^{*}$ play different roles. $𝑄^{*} 𝑄 = 𝐼_{𝑘}$ records that the columns are orthonormal. $𝑄 𝑄^{*}$ is the projection onto their span, and it equals $𝐼_{𝑛}$ only when $𝑘 = 𝑛$ , that is, when $𝑄$ is unitary. This is the identification promised after Theorem 6.3.29. Each term $𝐮_{𝑖} 𝐮_{𝑖}^{*}$ is the projection onto the line $span (𝐮_{𝑖})$ , so ${Pr}_{𝑊}$ is the sum of the projections onto the lines of an orthonormal basis, as in Figure 6.4.1. By Corollary 6.4.10, for an orthogonal basis $𝐟_{1}, \dots, 𝐟_{𝑘}$ of $𝑊$ the matrix is

\sum_{𝑖 = 1}^{𝑘} \frac{𝐟_{𝑖} 𝐟_{𝑖}^{*}}{𝐟_{𝑖}^{*} 𝐟_{𝑖}} .

In particular, the projection onto the line spanned by a nonzero $𝐚 \in 𝔽^{𝑛}$ has matrix $𝐚 𝐚^{*} / (𝐚^{*} 𝐚)$ . For a general basis of $𝑊$ the formula needs an inverse, $𝐴 {(𝐴^{*} 𝐴)}^{- 1} 𝐴^{*}$ , which is the subject of Section 6.5.

Example 6.4.32 (Projecting onto a plane in $ℝ^{3}$ ). Let $𝑊$ be the plane $𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 0$ of Example 6.4.9, and $𝐣 = (1, 1, 1)$ , so that $𝑊^{⟂} = span (𝐣)$ (Example 6.4.23(a)). By Proposition 6.4.29(d) and the formula for lines,

{Pr}_{𝑊} = 𝐼_{3} - \frac{𝐣 𝐣^{𝖳}}{3} = \frac{1}{3} (\begin{matrix} 2 & - 1 & - 1 \\ - 1 & 2 & - 1 \\ - 1 & - 1 & 2 \end{matrix}) .

For instance ${Pr}_{𝑊} (3, 0, 0) =$ $(2, - 1, - 1)$ , as in Example 6.4.9. The same matrix comes from Theorem 6.4.31 with $𝑄$ built from either orthonormal basis of Example 6.4.9. Projecting onto $𝑊^{⟂}$ and subtracting needed one rank-one matrix instead of two, a trick worth remembering when $𝑊^{⟂}$ is smaller than $𝑊$ .

6.4.4Best approximation

We return to the question that opened the section: which vector of $𝑊$ is closest to $𝐯$ ?

Intuition (The right triangle). Let $𝑊$ be a plane through $𝟎$ in $ℝ^{3}$ , and $𝐰$ any point of $𝑊$ . The three points $𝐯$ , ${Pr}_{𝑊} (𝐯)$ , and $𝐰$ form a triangle with a right angle at ${Pr}_{𝑊} (𝐯)$ : one leg, $𝐯 - {Pr}_{𝑊} (𝐯)$ , is perpendicular to $𝑊$ , and the other, ${Pr}_{𝑊} (𝐯) - 𝐰$ , lies in $𝑊$ (Figure 6.4.3). The distance from $𝐯$ to $𝐰$ is the hypotenuse, which is longer than the leg $𝐯 - {Pr}_{𝑊} (𝐯)$ unless the other leg is $𝟎$ . So no point of $𝑊$ is closer to $𝐯$ than ${Pr}_{𝑊} (𝐯)$ , and every other point of $𝑊$ is farther away.

This is the shadow argument of Figure 6.2.1, with the line replaced by a subspace. It uses only Pythagoras, so it works in every inner product space.

Figure 6.4.3. For every

𝐰 \in 𝑊

, the points

𝐯

{Pr}_{𝑊} (𝐯)

𝐰

form a right triangle. Its hypotenuse

𝐯 - 𝐰

is longer than the leg

𝐯 - {Pr}_{𝑊} (𝐯)

unless

𝐰 = {Pr}_{𝑊} (𝐯)

Theorem 6.4.33 (Best approximation). Let $𝑊$ be a finite-dimensional subspace of $𝑉$ , and let $𝐯 \in 𝑉$ . Then

‖ 𝐯 - {Pr}_{𝑊} (𝐯) ‖ \leq ‖ 𝐯 - 𝐰 ‖ for every 𝐰 \in 𝑊,

with equality if and only if $𝐰 = {Pr}_{𝑊} (𝐯)$ . That is, ${Pr}_{𝑊} (𝐯)$ is the unique vector of $𝑊$ closest to $𝐯$ . If $𝐮_{1}, \dots, 𝐮_{𝑘}$ is an orthonormal basis of $𝑊$ , the least distance is given by

{‖ 𝐯 - {Pr}_{𝑊} (𝐯) ‖}^{2} = {‖ 𝐯 ‖}^{2} - \sum_{𝑗 = 1}^{𝑘} {| ⟨ 𝐯, 𝐮_{𝑗} ⟩ |}^{2} .

Proof (by Pythagoras).routine

Uses. Proposition 6.4.4 (Properties of ${Pr}_{𝒪︀}$ ), Theorem 6.3.3 (Pythagorean theorem), Proposition 6.1.27 (Basic properties of the norm), Theorem 6.4.20 (Orthonormal bases exist)

Techniques. Orthogonal decomposition (Technique 6.2.4), Projections shrink norms (Technique 6.4.5)

Hint 1. Write

𝐯 -

𝐰 =

(𝐯 - {Pr}_{𝑊} (𝐯)) +

({Pr}_{𝑊} (𝐯) - 𝐰)

. Where do the two pieces lie?

Hint 2. The first piece is in

𝑊^{⟂}

and the second is in

𝑊

, so they are orthogonal. Apply the Pythagorean theorem.

Hint 3. The formula for the least distance is Proposition 6.4.4(e).

Sketch. For

𝐰 \in 𝑊

𝐯 -

𝐰 =

(𝐯 - {Pr}_{𝑊} (𝐯)) +

({Pr}_{𝑊} (𝐯) - 𝐰)

, with the first piece in

𝑊^{⟂}

and the second in

𝑊

. By Pythagoras,

{‖ 𝐯 - 𝐰 ‖}^{2} =

{‖ 𝐯 - {Pr}_{𝑊} (𝐯) ‖}^{2} +

{‖ {Pr}_{𝑊} (𝐯) - 𝐰 ‖}^{2}

, which is at least

{‖ 𝐯 - {Pr}_{𝑊} (𝐯) ‖}^{2}

, with equality exactly when

𝐰 = {Pr}_{𝑊} (𝐯)

. The distance formula is Proposition 6.4.4(e).

${Pr}_{𝑊}$ is defined by Theorem 6.4.20. Let $𝐰 \in 𝑊$ . Then

𝐯 - 𝐰 = (𝐯 - {Pr}_{𝑊} (𝐯)) + ({Pr}_{𝑊} (𝐯) - 𝐰),

where $𝐯 - {Pr}_{𝑊} (𝐯) \in 𝑊^{⟂}$ by Proposition 6.4.4(b), and ${Pr}_{𝑊} (𝐯) - 𝐰 \in 𝑊$ because both terms lie in $𝑊$ . So the two pieces are orthogonal, and by Theorem 6.3.3(a),

\begin{aligned} {‖ 𝐯 - 𝐰 ‖}^{2} & = {‖ 𝐯 - {Pr}_{𝑊} (𝐯) ‖}^{2} + {‖ {Pr}_{𝑊} (𝐯) - 𝐰 ‖}^{2} \\ \geq {‖ 𝐯 - {Pr}_{𝑊} (𝐯) ‖}^{2} . \end{aligned}

(6.4.2)

Taking nonnegative square roots gives the inequality. By (6.4.2), equality holds if and only if $‖ {Pr}_{𝑊} (𝐯) - 𝐰 ‖ = 0$ , that is (Proposition 6.1.27(a)), if and only if $𝐰 = {Pr}_{𝑊} (𝐯)$ . Finally, by Proposition 6.4.4(e),

\begin{aligned} {‖ 𝐯 - {Pr}_{𝑊} (𝐯) ‖}^{2} & = {‖ 𝐯 ‖}^{2} - {‖ {Pr}_{𝑊} (𝐯) ‖}^{2} \\ = {‖ 𝐯 ‖}^{2} - \sum_{𝑗 = 1}^{𝑘} {| ⟨ 𝐯, 𝐮_{𝑗} ⟩ |}^{2} . \end{aligned}

□

Proof (by completing the square).standard

Uses. Proposition 6.1.29 (Expanding a norm), Proposition 6.1.4 (Sesquilinearity), Corollary 6.3.6 (Pythagoras for orthogonal lists), Theorem 6.4.20 (Orthonormal bases exist), Definition 6.4.11 (Orthogonal projection)

Techniques. A sum of nonnegative terms (Technique 6.1.9)

Hint 1. Fix an orthonormal basis

𝐮_{1}, \dots, 𝐮_{𝑘}

𝑊

, write

𝐰 = \sum_{𝑗} 𝑐_{𝑗} 𝐮_{𝑗}

and

𝑎_{𝑗} = ⟨ 𝐯, 𝐮_{𝑗} ⟩

, and expand

{‖ 𝐯 - 𝐰 ‖}^{2}

as a function of

𝑐_{1}, \dots, 𝑐_{𝑘}

Hint 2. You should get

{‖ 𝐯 ‖}^{2} +

\sum_{𝑗} ({| 𝑐_{𝑗} |}^{2} - 2 Re (𝑐_{𝑗} 𝑎_{𝑗}))

. Complete the square in each

𝑐_{𝑗}

, using

{| 𝑐 - 𝑎 |}^{2} =

{| 𝑐 |}^{2} -

2 Re (𝑐 𝑎) +

{| 𝑎 |}^{2}

Sketch. With

𝐰 = \sum_{𝑗} 𝑐_{𝑗} 𝐮_{𝑗}

and

𝑎_{𝑗} = ⟨ 𝐯, 𝐮_{𝑗} ⟩

{‖ 𝐯 - 𝐰 ‖}^{2} =

{‖ 𝐯 ‖}^{2} -

2 Re ⟨ 𝐯, 𝐰 ⟩ +

{‖ 𝐰 ‖}^{2} =

{‖ 𝐯 ‖}^{2} +

\sum_{𝑗} ({| 𝑐_{𝑗} |}^{2} - 2 Re (𝑐_{𝑗} 𝑎_{𝑗})) =

{‖ 𝐯 ‖}^{2} -

\sum_{𝑗} {| 𝑎_{𝑗} |}^{2} +

\sum_{𝑗} {| 𝑐_{𝑗} - 𝑎_{𝑗} |}^{2}

. The last sum is nonnegative and vanishes exactly when every

𝑐_{𝑗} = 𝑎_{𝑗}

, that is, when

𝐰 = {Pr}_{𝑊} (𝐯)

By Theorem 6.4.20, $𝑊$ has an orthonormal basis $𝐮_{1}, \dots, 𝐮_{𝑘}$ . Let $𝑎_{𝑗} = ⟨ 𝐯, 𝐮_{𝑗} ⟩$ , so that ${Pr}_{𝑊} (𝐯) =$ $\sum_{𝑗} 𝑎_{𝑗} 𝐮_{𝑗}$ . Every $𝐰 \in 𝑊$ is $𝐰 = \sum_{𝑗} 𝑐_{𝑗} 𝐮_{𝑗}$ for unique scalars $𝑐_{𝑗}$ . By Proposition 6.1.29 with $𝑎 = - 1$ ,

{‖ 𝐯 - 𝐰 ‖}^{2} = {‖ 𝐯 ‖}^{2} - 2 Re ⟨ 𝐯, 𝐰 ⟩ + {‖ 𝐰 ‖}^{2} .

By Proposition 6.1.4, $⟨ 𝐯, 𝐰 ⟩ =$ $\sum_{𝑗} 𝑐_{𝑗} ⟨ 𝐯, 𝐮_{𝑗} ⟩ =$ $\sum_{𝑗} 𝑐_{𝑗} 𝑎_{𝑗}$ , and by Corollary 6.3.6, ${‖ 𝐰 ‖}^{2} = \sum_{𝑗} {| 𝑐_{𝑗} |}^{2}$ . For complex numbers $𝑐$ and $𝑎$ , ${| 𝑐 - 𝑎 |}^{2} =$ $(𝑐 - 𝑎) (𝑐 - 𝑎) =$ ${| 𝑐 |}^{2} -$ $2 Re (𝑐 𝑎) +$ ${| 𝑎 |}^{2}$ . Hence

\begin{aligned} {‖ 𝐯 - 𝐰 ‖}^{2} & = {‖ 𝐯 ‖}^{2} + \sum_{𝑗 = 1}^{𝑘} ({| 𝑐_{𝑗} |}^{2} - 2 Re (𝑐_{𝑗} 𝑎_{𝑗})) \\ = {‖ 𝐯 ‖}^{2} - \sum_{𝑗 = 1}^{𝑘} {| 𝑎_{𝑗} |}^{2} + \sum_{𝑗 = 1}^{𝑘} {| 𝑐_{𝑗} - 𝑎_{𝑗} |}^{2} . \end{aligned}

The first two terms do not depend on $𝐰$ , and the last sum is a sum of nonnegative terms, which is $0$ if and only if $𝑐_{𝑗} = 𝑎_{𝑗}$ for every $𝑗$ . So ${‖ 𝐯 - 𝐰 ‖}^{2}$ is smallest exactly when $𝐰 =$ $\sum_{𝑗} 𝑎_{𝑗} 𝐮_{𝑗} =$ ${Pr}_{𝑊} (𝐯)$ , and the smallest value is ${‖ 𝐯 ‖}^{2} - \sum_{𝑗} {| 𝑎_{𝑗} |}^{2}$ . □

The first proof starts from the candidate ${Pr}_{𝑊} (𝐯)$ and shows that it wins. The second does not need to know the answer in advance: completing the square produces the minimizing coefficients $𝑐_{𝑗} = ⟨ 𝐯, 𝐮_{𝑗} ⟩$ and the minimum at the same time, and it shows that the squared error grows like $\sum_{𝑗} {| 𝑐_{𝑗} - 𝑎_{𝑗} |}^{2}$ as $𝐰$ moves away from the optimum. In the language of Technique 6.4.5, the first proof says that for every $𝐰 \in 𝑊$ , the error $𝐯 - {Pr}_{𝑊} (𝐯)$ is the piece of $𝐯 - 𝐰$ orthogonal to $𝑊$ : moving $𝐰$ around $𝑊$ changes only the piece in $𝑊$ , and dropping that piece can only shorten a vector.

The theorem gives a third reason why ${Pr}_{𝑊}$ does not depend on the orthonormal basis used to compute it: “the closest vector of $𝑊$ ” is defined by distances alone. Putting Theorem 6.4.6 and Theorem 6.4.33 together, for $𝐩 \in 𝑊$ the following are equivalent:

(i) $𝐩 = {Pr}_{𝑊} (𝐯)$ , the formula computed from an orthonormal basis of $𝑊$ ;
(ii) $𝐯 - 𝐩 ⟂ 𝑊$ ;
(iii) $‖ 𝐯 - 𝐩 ‖ \leq ‖ 𝐯 - 𝐰 ‖$ for every $𝐰 \in 𝑊$ .

In proofs one usually checks (ii), in computations one uses (i), and in applications the reason to care is (iii).

Definition 6.4.34 (Distance to a subspace). Let $𝑊$ be a finite-dimensional subspace of $𝑉$ and $𝐯 \in 𝑉$ . The distance from $𝐯$ to $𝑊$ is

dist (𝐯, 𝑊) = min_{𝐰 \in 𝑊} ‖ 𝐯 - 𝐰 ‖ = ‖ 𝐯 - {Pr}_{𝑊} (𝐯) ‖ .

The minimum exists by Theorem 6.4.33. So $dist (𝐯, 𝑊) = 0$ if and only if $𝐯 \in 𝑊$ , and by Theorem 6.4.24, $dist (𝐯, 𝑊)$ is the length of the component of $𝐯$ in $𝑊^{⟂}$ . When $𝑉$ is finite-dimensional, that component is ${Pr}_{𝑊^{⟂}} (𝐯)$ (Proposition 6.4.29(d)).

Example 6.4.35 (Distance to a hyperplane). Let $𝐧 \in 𝔽^{𝑛}$ be nonzero and $𝐻 =$ ${𝐧}^{⟂} =$ ${𝐱 \in 𝔽^{𝑛} | 𝐱 \cdot 𝐧 = 0}$ . Then $𝐻 = {span (𝐧)}^{⟂}$ (Proposition 6.3.9(c)), so $𝐻^{⟂} = span (𝐧)$ by Theorem 6.4.26. By Proposition 6.4.29(d), $𝐯 -$ ${Pr}_{𝐻} (𝐯) =$ ${Pr}_{span (𝐧)} (𝐯) =$ $(⟨ 𝐯, 𝐧 ⟩ / {‖ 𝐧 ‖}^{2}) 𝐧$ , and therefore

dist (𝐯, 𝐻) = \frac{| ⟨ 𝐯, 𝐧 ⟩ |}{‖ 𝐧 ‖} .

For the plane $2 𝑥_{1} - 𝑥_{2} + 2 𝑥_{3} = 0$ in $ℝ^{3}$ and $𝐯 = (1, 1, 1)$ , with $𝐧 = (2, - 1, 2)$ : $⟨ 𝐯, 𝐧 ⟩ = 3$ and $‖ 𝐧 ‖ = 3$ , so $dist (𝐯, 𝐻) = 1$ , and the closest point of the plane is $𝐯 -$ $(3 / 9) 𝐧 =$ $(1 / 3, 4 / 3, 1 / 3)$ . This is the point-to-plane formula of multivariable calculus, now proved in every dimension and over $ℂ$ .

Exercise 6.4.36.routine Find the point of the plane

𝑊 =

span ((1, 1, 0), (1, 0, 1))

ℝ^{3}

closest to

𝐯 = (0, 0, 3)

, and the distance from

𝐯

𝑊

. Check your answer with Example 6.4.35.

Solution.

Uses. Example 6.4.17 (Gram–Schmidt in $ℝ^{3}$ ), Theorem 6.4.33 (Best approximation), Example 6.4.35 (Distance to a hyperplane)

Hint 1. Example 6.4.17 already contains an orthonormal basis of

𝑊

Hint 2.

𝐮_{1} = (1, 1, 0) / \sqrt{2}

and

𝐮_{2} = (1, - 1, 2) / \sqrt{6}

. For the check, a normal vector of

𝑊

𝐮_{3}

Sketch. With

𝐮_{1}, 𝐮_{2}

from Example 6.4.17,

⟨ 𝐯, 𝐮_{1} ⟩ = 0

and

⟨ 𝐯, 𝐮_{2} ⟩ = 6 / \sqrt{6}

, so

{Pr}_{𝑊} (𝐯) = (1, - 1, 2)

and

𝐯 -

{Pr}_{𝑊} (𝐯) =

(- 1, 1, 1)

, of length

\sqrt{3}

. With

𝐧 = (- 1, 1, 1)

| ⟨ 𝐯, 𝐧 ⟩ | / ‖ 𝐧 ‖ =

3 / \sqrt{3} =

\sqrt{3}

By Example 6.4.17, $𝐮_{1} = (1, 1, 0) / \sqrt{2}$ , $𝐮_{2} = (1, - 1, 2) / \sqrt{6}$ is an orthonormal basis of $span (𝐯_{1}, 𝐯_{2}) = 𝑊$ . Here $⟨ 𝐯, 𝐮_{1} ⟩ = 0$ and $⟨ 𝐯, 𝐮_{2} ⟩ = 6 / \sqrt{6}$ , so by Theorem 6.4.33 the closest point is

{Pr}_{𝑊} (𝐯) = 0 \cdot 𝐮_{1} + \frac{6}{\sqrt{6}} \cdot \frac{1}{\sqrt{6}} (1, - 1, 2) = (1, - 1, 2) .

The distance is $‖ 𝐯 -$ ${Pr}_{𝑊} (𝐯) ‖ =$ $‖ (- 1, 1, 1) ‖ =$ $\sqrt{3}$ . Check: $(- 1, 1, 1)$ is orthogonal to $(1, 1, 0)$ and $(1, 0, 1)$ , so $𝑊 = {𝐧}^{⟂}$ with $𝐧 = (- 1, 1, 1)$ (both are planes, and one contains the other), and Example 6.4.35 gives $| ⟨ 𝐯, 𝐧 ⟩ | / ‖ 𝐧 ‖ =$ $3 / \sqrt{3} =$ $\sqrt{3}$ .

Approximating functions

In a space of functions, Theorem 6.4.33 solves approximation problems. The inner product decides what “close” means. For $⟨ 𝑓, 𝑔 ⟩ =$ $\int_{- 1}^{1} 𝑓 (𝑡) 𝑔 (𝑡) d 𝑡$ , the distance $‖ 𝑓 -$ $𝑝 ‖ =$ ${(\int_{- 1}^{1} {(𝑓 (𝑡) - 𝑝 (𝑡))}^{2} d 𝑡)}^{1 / 2}$ measures the error on average over the interval: it is small when $𝑓 - 𝑝$ is small on most of $[- 1, 1]$ , even if it is larger at a few points.

Example 6.4.37 (The quadratic closest to $𝑒^{𝑡}$ ). In $𝐶 [- 1, 1]$ with $⟨ 𝑓, 𝑔 ⟩ =$ $\int_{- 1}^{1} 𝑓 (𝑡) 𝑔 (𝑡) d 𝑡$ , let $𝑊$ be the subspace of polynomial functions of degree at most $2$ . Which $𝑝 \in 𝑊$ makes $\int_{- 1}^{1} {(𝑒^{𝑡} - 𝑝 (𝑡))}^{2} d 𝑡$ as small as possible? By Theorem 6.4.33 the answer is $𝑝 = {Pr}_{𝑊} (𝑒^{𝑡})$ . The orthogonal basis $1, 𝑡, 𝑡^{2} - 1 / 3$ of Example 6.4.19, whose squared norms are $2$ , $2 / 3$ , and $8 / 45$ , and Corollary 6.4.10 give

𝑝 = \frac{⟨ 𝑒^{𝑡}, 1 ⟩}{2} + \frac{⟨ 𝑒^{𝑡}, 𝑡 ⟩}{2 / 3} 𝑡 + \frac{⟨ 𝑒^{𝑡}, 𝑡^{2} - 1 / 3 ⟩}{8 / 45} (𝑡^{2} - \frac{1}{3}) .

Integrating by parts,

\begin{aligned} \int_{- 1}^{1} 𝑒^{𝑡} d 𝑡 & = 𝑒 - 𝑒^{- 1}, \\ \int_{- 1}^{1} 𝑡 𝑒^{𝑡} d 𝑡 & = 2 𝑒^{- 1}, \\ \int_{- 1}^{1} 𝑡^{2} 𝑒^{𝑡} d 𝑡 & = 𝑒 - 5 𝑒^{- 1}, \end{aligned}

so $⟨ 𝑒^{𝑡}, 𝑡^{2} - 1 / 3 ⟩ =$ $𝑒 -$ $5 𝑒^{- 1} -$ $(𝑒 - 𝑒^{- 1}) / 3 =$ $(2 / 3) (𝑒 - 7 𝑒^{- 1})$ . Therefore

\begin{aligned} 𝑝 (𝑡) & = \frac{𝑒 - 𝑒^{- 1}}{2} + 3 𝑒^{- 1} 𝑡 + \frac{15}{4} (𝑒 - 7 𝑒^{- 1}) (𝑡^{2} - \frac{1}{3}) \\ \approx 0.9963 + 1.1036 𝑡 + 0.5367 𝑡^{2} . \end{aligned}

Compare the Taylor polynomial $𝑇 (𝑡) = 1 + 𝑡 + 𝑡^{2} / 2$ , which is also quadratic. Figure 6.4.4 plots both errors. Near $0$ , $𝑇$ is better: it agrees with $𝑒^{𝑡}$ to second order there. Over the whole interval, $𝑝$ is better. Its squared distance from $𝑒^{𝑡}$ is $\int_{- 1}^{1} {(𝑒^{𝑡} - 𝑝)}^{2} \approx$ $0.0014$ , against $\int_{- 1}^{1} {(𝑒^{𝑡} - 𝑇)}^{2} \approx$ $0.0090$ for $𝑇$ , and even its largest error on $[- 1, 1]$ is smaller: about $0.082$ at $𝑡 = 1$ , against $0.218$ for $𝑇$ .

Figure 6.4.4. The errors

𝑒^{𝑡} - 𝑝 (𝑡)

of the best quadratic approximation in the sense of Example 6.4.37, and

𝑒^{𝑡} - 𝑇 (𝑡)

of the Taylor polynomial

𝑇 (𝑡) = 1 + 𝑡 + 𝑡^{2} / 2

, on

[- 1, 1]

. The Taylor error is tiny near

0

and large near the ends; the projection spreads the error over the interval and changes sign three times.

The error $𝑔 (𝑡) =$ $𝑒^{𝑡} -$ $𝑝 (𝑡)$ is orthogonal to $1$ , $𝑡$ , and $𝑡^{2}$ . It has at most three zeros, since $𝑔^{‴} = 𝑒^{𝑡} > 0$ and, by Rolle’s theorem, four zeros of $𝑔$ would give a zero of $𝑔^{‴}$ . With this, the argument of Exercise 6.4.61 shows that $𝑔$ changes sign at least three times in $(- 1, 1)$ , as Figure 6.4.4 shows. The same recipe works for any continuous $𝑓$ and any degree $𝑛$ : run Gram–Schmidt on $1, 𝑡, \dots, 𝑡^{𝑛}$ once, and then each approximation costs $𝑛 + 1$ integrals. A function need not be differentiable to have a best approximation; Exercise 6.4.44 finds the quadratic closest to $| 𝑡 |$ , which has no Taylor polynomial at $0$ .

Aside (Fourier truncation).Beyond 21-242 Take the inner product $⟨ 𝑓, 𝑔 ⟩ =$ $\frac{1}{2 𝜋} \int_{0}^{2 𝜋} 𝑓 (𝑡) 𝑔 (𝑡) d 𝑡$ on $𝐶 ([0, 2 𝜋], ℂ)$ and the orthonormal functions $𝑒_{𝑘} (𝑡) =$ $cos 𝑘 𝑡 +$ $𝑖 sin 𝑘 𝑡$ of Aside (Fourier coefficients), and let $𝑊_{𝑁} =$ $span (𝑒_{- 𝑁}, \dots, 𝑒_{𝑁})$ , the trigonometric polynomials of degree at most $𝑁$ . By Theorem 6.4.33, the trigonometric polynomial of degree at most $𝑁$ closest to $𝑓$ is the partial Fourier sum

𝑆_{𝑁} 𝑓 = {Pr}_{𝑊_{𝑁}} (𝑓) = \sum_{𝑘 = - 𝑁}^{𝑁} 𝑐_{𝑘} 𝑒_{𝑘}, 𝑐_{𝑘} = ⟨ 𝑓, 𝑒_{𝑘} ⟩,

and ${‖ 𝑓 - 𝑆_{𝑁} 𝑓 ‖}^{2} =$ ${‖ 𝑓 ‖}^{2} -$ $\sum_{𝑘 = - 𝑁}^{𝑁} {| 𝑐_{𝑘} |}^{2}$ . Since $𝑊_{𝑁} \subseteq 𝑊_{𝑁 + 1}$ , the error can only decrease as $𝑁$ grows. For $𝑓 (𝑡) = 𝑡$ , integration by parts gives $𝑐_{0} = 𝜋$ and $𝑐_{𝑘} = 𝑖 / 𝑘$ for $𝑘 \neq 0$ , so

\begin{aligned} 𝑆_{𝑁} 𝑓 (𝑡) & = 𝜋 - 2 \sum_{𝑘 = 1}^{𝑁} \frac{sin 𝑘 𝑡}{𝑘}, \\ {‖ 𝑓 - 𝑆_{𝑁} 𝑓 ‖}^{2} & = \frac{4 𝜋^{2}}{3} - 𝜋^{2} - 2 \sum_{𝑘 = 1}^{𝑁} \frac{1}{𝑘^{2}} . \end{aligned}

The left side is nonnegative, so $\sum_{𝑘 = 1}^{𝑁} 1 / 𝑘^{2} \leq$ $𝜋^{2} / 6$ for every $𝑁$ . In fact the error tends to $0$ as $𝑁 \to \infty$ (Section 15.3), which gives Euler’s formula $\sum_{𝑘 = 1}^{\infty} 1 / 𝑘^{2} = 𝜋^{2} / 6$ .

Figure 6.4.5. The function

𝑡

[0, 2 𝜋]

and its partial Fourier sums

𝑆_{1}

𝑆_{3}

𝑆_{12}

. Each

𝑆_{𝑁}

is the closest trigonometric polynomial of degree at most

𝑁

in the mean-square sense, and the fit improves with

𝑁

except near the ends of the interval.

Best approximation in $𝔽^{𝑚}$ is the subject of Section 6.5. There $𝑊$ is the image of a matrix $𝐴$ , and ${Pr}_{im 𝐴} (𝐛)$ is the closest one can come to solving an inconsistent system $𝐴 𝐱 = 𝐛$ .

6.4.5QR factorization Beyond 21-242

QR factorization is Gram–Schmidt in matrix form. It is not covered in lecture; see LADR 7D.

Gram–Schmidt applied to the columns of a matrix factors the matrix. If $𝐴$ has linearly independent columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ and Gram–Schmidt turns them into $𝐮_{1}, \dots, 𝐮_{𝑛}$ , then $span (𝐮_{1}, \dots, 𝐮_{𝑗}) =$ $span (𝐚_{1}, \dots, 𝐚_{𝑗})$ for each $𝑗$ . So each $𝐚_{𝑗}$ is a combination of $𝐮_{1}, \dots, 𝐮_{𝑗}$ only, and recording the coefficients produces an upper triangular matrix.

Theorem 6.4.38 (QR factorization). Let

𝐴 \in 𝔽^{𝑚 \times 𝑛}

have linearly independent columns

𝐚_{1}, \dots, 𝐚_{𝑛}

. Then there are unique matrices

𝑄 \in 𝔽^{𝑚 \times 𝑛}

with orthonormal columns and

𝑅 \in 𝔽^{𝑛 \times 𝑛}

upper triangular with positive real diagonal entries such that

𝐴 = 𝑄 𝑅

. The columns of

𝑄

are the output

𝐮_{1}, \dots, 𝐮_{𝑛}

of Gram–Schmidt applied to

𝐚_{1}, \dots, 𝐚_{𝑛}

, and

𝑟_{𝑖 𝑗} =

⟨ 𝐚_{𝑗}, 𝐮_{𝑖} ⟩

for

𝑖 \leq 𝑗

Proof.hard

Uses. Theorem 6.4.15 (Gram–Schmidt is correct), Proposition 6.3.18 (Coordinates in an orthonormal basis), Proposition 2.4.8 (Four views of the product), Lemma 3.3.32 (Products and inverses of triangular matrices), Theorem 6.3.29 (Orthonormal columns), Exercise 6.3.57, Proposition 6.3.27 (Properties of the conjugate transpose)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. For existence, by Theorem 6.4.15(d),

𝐚_{𝑗} \in

span (𝐮_{1}, \dots, 𝐮_{𝑗})

. Expand it with Proposition 6.3.18(a), and read the coefficients as column

𝑗

𝑅

Hint 2. For uniqueness, suppose

𝑄 𝑅 = 𝑄^{'} 𝑅^{'}

. Then

𝑄 = 𝑄^{'} 𝑈

with

𝑈 = 𝑅^{'} 𝑅^{- 1}

. What kind of matrix is

𝑈

, and what does

𝑄^{*} 𝑄 = 𝐼_{𝑛}

say about it?

Hint 3. An upper triangular unitary matrix is diagonal (Exercise 6.3.57(c)).

Sketch. Existence:

𝐚_{𝑗} =

\sum_{𝑖 \leq 𝑗} ⟨ 𝐚_{𝑗}, 𝐮_{𝑖} ⟩ 𝐮_{𝑖}

, so column

𝑗

𝐴

𝑄

times the column

(𝑟_{1 𝑗}, \dots, 𝑟_{𝑗 𝑗}, 0, \dots, 0)

, and

𝑟_{𝑗 𝑗} = ‖ 𝐟_{𝑗} ‖ > 0

by Theorem 6.4.15(d). Uniqueness: if

𝑄 𝑅 = 𝑄^{'} 𝑅^{'}

, then

𝑈 = 𝑅^{'} 𝑅^{- 1}

is upper triangular with positive diagonal and

𝑄 = 𝑄^{'} 𝑈

; then

𝐼_{𝑛} = 𝑄^{*} 𝑄 = 𝑈^{*} 𝑈

, so

𝑈

is unitary and upper triangular, hence diagonal with entries of modulus

1

, hence

𝑈 = 𝐼_{𝑛}

Existence. By Theorem 6.4.15(d), Gram–Schmidt applied to $𝐚_{1}, \dots, 𝐚_{𝑛}$ skips nothing, and its output $𝐮_{1}, \dots, 𝐮_{𝑛}$ is orthonormal with $𝐚_{𝑗} \in$ $span (𝐮_{1}, \dots, 𝐮_{𝑗})$ . By Proposition 6.3.18(a),

𝐚_{𝑗} = \sum_{𝑖 = 1}^{𝑗} ⟨ 𝐚_{𝑗}, 𝐮_{𝑖} ⟩ 𝐮_{𝑖} .

Let $𝑄$ have columns $𝐮_{1}, \dots, 𝐮_{𝑛}$ , and let $𝑟_{𝑖 𝑗} =$ $⟨ 𝐚_{𝑗}, 𝐮_{𝑖} ⟩$ for $𝑖 \leq 𝑗$ and $𝑟_{𝑖 𝑗} = 0$ for $𝑖 > 𝑗$ . Then $𝑅$ is upper triangular, $𝑟_{𝑗 𝑗} = ‖ 𝐟_{𝑗} ‖ > 0$ by Theorem 6.4.15(d), and by the column view of Proposition 2.4.8, column $𝑗$ of $𝑄 𝑅$ is $\sum_{𝑖} 𝑟_{𝑖 𝑗} 𝐮_{𝑖} =$ $𝐚_{𝑗}$ . So $𝐴 = 𝑄 𝑅$ .

Uniqueness. Suppose $𝐴 = 𝑄 𝑅 = 𝑄^{'} 𝑅^{'}$ , where both pairs have the stated properties. An upper triangular matrix $𝑅$ with nonzero diagonal entries is invertible with upper triangular inverse, whose diagonal entries are $1 / 𝑟_{𝑗 𝑗}$ : write $𝑅 = 𝐷 𝑁$ with $𝐷$ the diagonal matrix of the $𝑟_{𝑗 𝑗}$ and $𝑁 = 𝐷^{- 1} 𝑅$ unit upper triangular, and apply Lemma 3.3.32 to get $𝑅^{- 1} = 𝑁^{- 1} 𝐷^{- 1}$ . So $𝑈 = 𝑅^{'} 𝑅^{- 1}$ is upper triangular with diagonal entries $𝑟_{𝑗 𝑗}^{'} / 𝑟_{𝑗 𝑗} > 0$ , again by Lemma 3.3.32. Multiplying $𝑄 𝑅 = 𝑄^{'} 𝑅^{'}$ on the right by $𝑅^{- 1}$ gives $𝑄 = 𝑄^{'} 𝑈$ . Since $𝑄$ and $𝑄^{'}$ have orthonormal columns, Theorem 6.3.29 and Proposition 6.3.27 give

𝐼_{𝑛} = 𝑄^{*} 𝑄 = 𝑈^{*} 𝑄^{' *} 𝑄^{'} 𝑈 = 𝑈^{*} 𝑈 .

So the square matrix $𝑈$ is unitary and upper triangular. By Exercise 6.3.57(c) it is diagonal with diagonal entries of modulus $1$ , and these entries are positive, so $𝑈 = 𝐼_{𝑛}$ . Hence $𝑅^{'} = 𝑈 𝑅 = 𝑅$ and $𝑄^{'} = 𝑄 𝑈^{- 1} = 𝑄$ . □

The factorization repackages several earlier facts. The columns of $𝑄$ are an orthonormal basis of $im 𝐴$ , so ${Pr}_{im 𝐴} = 𝑄 𝑄^{*}$ by Theorem 6.4.31. If $𝐴$ is square, then $𝑄$ is unitary, so $| det 𝐴 | =$ $| det 𝑄 | det 𝑅 =$ $𝑟_{11} \dots 𝑟_{𝑛 𝑛}$ (Theorem 5.4.10, Proposition 5.3.15, Exercise 6.3.57), and the system $𝐴 𝐱 = 𝐛$ becomes $𝑅 𝐱 = 𝑄^{*} 𝐛$ , which is solved by back substitution. Section 6.5 uses the same reduction for inconsistent systems.

Example 6.4.39 (A QR factorization). Let $𝐴$ have the columns $𝐚_{1} = (1, 1, 0)$ , $𝐚_{2} = (1, 0, 1)$ , $𝐚_{3} = (0, 1, 1)$ of Example 6.4.17. The output of Gram–Schmidt was $𝐮_{1} = (1, 1, 0) / \sqrt{2}$ , $𝐮_{2} = (1, - 1, 2) / \sqrt{6}$ , $𝐮_{3} = (- 1, 1, 1) / \sqrt{3}$ , and the entries of $𝑅$ are the inner products $𝑟_{𝑖 𝑗} =$ $⟨ 𝐚_{𝑗}, 𝐮_{𝑖} ⟩$ :

𝐴 = (\begin{matrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix}) = 𝑄 𝑅,

where

\begin{aligned} 𝑄 & = (\begin{matrix} 1 / \sqrt{2} & 1 / \sqrt{6} & - 1 / \sqrt{3} \\ 1 / \sqrt{2} & - 1 / \sqrt{6} & 1 / \sqrt{3} \\ 0 & 2 / \sqrt{6} & 1 / \sqrt{3} \end{matrix}), \\ 𝑅 & = (\begin{matrix} \sqrt{2} & 1 / \sqrt{2} & 1 / \sqrt{2} \\ 0 & 3 / \sqrt{6} & 1 / \sqrt{6} \\ 0 & 0 & 2 / \sqrt{3} \end{matrix}) . \end{aligned}

The diagonal entries $\sqrt{2}$ , $3 / \sqrt{6}$ , $2 / \sqrt{3}$ are the lengths of the residuals, and their product is $2 = | det 𝐴 |$ .

In floating-point arithmetic, Algorithm 6.4.14 as written can lose orthogonality badly when the columns are nearly dependent. Practical codes reorder the same computation (modified Gram–Schmidt) or build $𝑄$ from reflections instead (Section 9.3).

Exercises

Exercise 6.4.40.routine In $ℝ^{4}$ , let $𝑊 =$ $span (𝐯_{1}, 𝐯_{2}, 𝐯_{3})$ with $𝐯_{1} = (1, 1, 1, 1)$ , $𝐯_{2} = (2, 0, 0, 2)$ , $𝐯_{3} = (0, 2, 0, 0)$ .

(a)Find an orthonormal basis of $𝑊$ with Gram–Schmidt.
(b)Find ${Pr}_{𝑊} (𝐛)$ for $𝐛 = (1, 2, 3, 4)$ , and $dist (𝐛, 𝑊)$ .
(c)Find $𝑊^{⟂}$ .

Solution.

Uses. Algorithm 6.4.14 (Gram–Schmidt), Remark 6.4.16 (Postponing the normalization), Corollary 6.4.10 (Projecting with an orthogonal list), Theorem 6.4.33 (Best approximation), Corollary 6.4.25 (Dimension of the orthogonal complement)

Hint 1. Run the algorithm with residuals only (Remark 6.4.16). The coefficients are

⟨ 𝐯_{𝑗}, 𝐟_{𝑖} ⟩ / {‖ 𝐟_{𝑖} ‖}^{2}

Hint 2. The residuals are

(1, 1, 1, 1)

(1, - 1, - 1, 1)

(0, 1, - 1, 0)

. For (b), use Corollary 6.4.10 with these.

Hint 3. For (c),

dim 𝑊^{⟂} = 1

, and

𝐛 - {Pr}_{𝑊} (𝐛)

is a nonzero vector of

𝑊^{⟂}

Sketch.

𝐟_{1} = (1, 1, 1, 1)

𝐟_{2} =

𝐯_{2} -

𝐟_{1} =

(1, - 1, - 1, 1)

𝐟_{3} =

𝐯_{3} -

𝐟_{1} / 2 +

𝐟_{2} / 2 =

(0, 1, - 1, 0)

. Then

{Pr}_{𝑊} (𝐛) =

(10 / 4) 𝐟_{1} +

0 𝐟_{2} -

(1 / 2) 𝐟_{3} =

(5 / 2, 2, 3, 5 / 2)

, and

𝐛 -

{Pr}_{𝑊} (𝐛) =

(3 / 2) (- 1, 0, 0, 1)

, of length

3 / \sqrt{2}

𝑊^{⟂} =

span ((1, 0, 0, - 1))

(a) By Remark 6.4.16 we may work with residuals. First $𝐟_{1} = (1, 1, 1, 1)$ , with ${‖ 𝐟_{1} ‖}^{2} = 4$ . Next $⟨ 𝐯_{2}, 𝐟_{1} ⟩ = 4$ , so

𝐟_{2} = (2, 0, 0, 2) - (1, 1, 1, 1) = (1, - 1, - 1, 1),

with ${‖ 𝐟_{2} ‖}^{2} = 4$ . Then $⟨ 𝐯_{3}, 𝐟_{1} ⟩ = 2$ and $⟨ 𝐯_{3}, 𝐟_{2} ⟩ = - 2$ , so

\begin{aligned} 𝐟_{3} & = (0, 2, 0, 0) - \frac{1}{2} (1, 1, 1, 1) + \frac{1}{2} (1, - 1, - 1, 1) \\ = (0, 1, - 1, 0), \end{aligned}

with ${‖ 𝐟_{3} ‖}^{2} = 2$ . No residual is $𝟎$ , so $𝐯_{1}, 𝐯_{2}, 𝐯_{3}$ is independent, and

\begin{matrix} 𝐮_{1} = \frac{1}{2} (1, 1, 1, 1), 𝐮_{2} = \frac{1}{2} (1, - 1, - 1, 1), \\ 𝐮_{3} = \frac{1}{\sqrt{2}} (0, 1, - 1, 0) \end{matrix}

is an orthonormal basis of $𝑊$ (Theorem 6.4.15).

(b) We have $⟨ 𝐛, 𝐟_{1} ⟩ = 10$ , $⟨ 𝐛, 𝐟_{2} ⟩ =$ $1 -$ $2 -$ $3 +$ $4 =$ $0$ , and $⟨ 𝐛, 𝐟_{3} ⟩ = - 1$ . By Corollary 6.4.10,

\begin{aligned} {Pr}_{𝑊} (𝐛) & = \frac{10}{4} (1, 1, 1, 1) + 0 - \frac{1}{2} (0, 1, - 1, 0) \\ = (\frac{5}{2}, 2, 3, \frac{5}{2}) . \end{aligned}

So $𝐛 -$ ${Pr}_{𝑊} (𝐛) =$ $(- 3 / 2, 0, 0, 3 / 2)$ , which is indeed orthogonal to $𝐟_{1}, 𝐟_{2}, 𝐟_{3}$ , and by Theorem 6.4.33, $dist (𝐛, 𝑊) =$ $\sqrt{9 / 4 + 9 / 4} =$ $3 / \sqrt{2}$ .

(c) By Corollary 6.4.25, $dim 𝑊^{⟂} = 4 - 3 = 1$ . The vector $(1, 0, 0, - 1)$ is orthogonal to $𝐟_{1}$ , $𝐟_{2}$ , $𝐟_{3}$ , which span $𝑊$ , so it lies in $𝑊^{⟂}$ (Proposition 6.3.9(c)). Hence $𝑊^{⟂} =$ $span ((1, 0, 0, - 1))$ . As it must, $𝐛 -$ ${Pr}_{𝑊} (𝐛) =$ $- (3 / 2) (1, 0, 0, - 1)$ lies in $𝑊^{⟂}$ .

Exercise 6.4.41.routine Let

𝑊 =

span ((1, 0, 1), (1, 1, 0))

ℝ^{3}

. Find the matrix

𝑃

{Pr}_{𝑊}

in two ways: (a) by Gram–Schmidt and Theorem 6.4.31, and (b) from a vector

𝐧

spanning

𝑊^{⟂}

. Check that

𝑃^{2} = 𝑃

𝑃^{𝖳} = 𝑃

, and

tr 𝑃 = 2

Solution.

Uses. Theorem 6.4.31 (The matrix of an orthogonal projection), Corollary 6.4.10 (Projecting with an orthogonal list), Proposition 6.4.29 (The orthogonal projection as a linear map), Corollary 6.4.25 (Dimension of the orthogonal complement)

Hint 1. Gram–Schmidt with residuals gives

(1, 0, 1)

and

(1, 2, - 1)

. Use

\sum_{𝑖} 𝐟_{𝑖} 𝐟_{𝑖}^{𝖳} / {‖ 𝐟_{𝑖} ‖}^{2}

Hint 2. For (b), find

𝐧 \neq 𝟎

orthogonal to both spanning vectors; then

𝑃 =

𝐼_{3} -

𝐧 𝐧^{𝖳} / {‖ 𝐧 ‖}^{2}

by Proposition 6.4.29(d).

Sketch. Both ways give

𝑃 =

(1 / 3) (\begin{matrix} 2 & 1 & 1 \\ 1 & 2 & - 1 \\ 1 & - 1 & 2 \end{matrix})

: in (a) as

(1 / 2) 𝐟_{1} 𝐟_{1}^{𝖳} +

(1 / 6) 𝐟_{2} 𝐟_{2}^{𝖳}

with

𝐟_{1} = (1, 0, 1)

𝐟_{2} = (1, 2, - 1)

, and in (b) as

𝐼_{3} - (1 / 3) 𝐧 𝐧^{𝖳}

with

𝐧 = (- 1, 1, 1)

. The trace is

6 / 3 = 2 = dim 𝑊

(a) Gram–Schmidt with residuals: $𝐟_{1} = (1, 0, 1)$ , and $(1, 1, 0) -$ $(1 / 2) (1, 0, 1) =$ $(1 / 2, 1, - 1 / 2)$ , which we replace by $𝐟_{2} = (1, 2, - 1)$ . By Theorem 6.4.31 and Corollary 6.4.10,

\begin{aligned} 𝑃 & = \frac{1}{2} (\begin{matrix} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{matrix}) + \frac{1}{6} (\begin{matrix} 1 & 2 & - 1 \\ 2 & 4 & - 2 \\ - 1 & - 2 & 1 \end{matrix}) \\ = \frac{1}{3} (\begin{matrix} 2 & 1 & 1 \\ 1 & 2 & - 1 \\ 1 & - 1 & 2 \end{matrix}) . \end{aligned}

(b) The vector $𝐧 = (- 1, 1, 1)$ is orthogonal to $(1, 0, 1)$ and $(1, 1, 0)$ , so it lies in $𝑊^{⟂}$ , which is a line by Corollary 6.4.25. So $𝑊^{⟂} = span (𝐧)$ and, by Proposition 6.4.29(d),

\begin{aligned} 𝑃 & = 𝐼_{3} - \frac{𝐧 𝐧^{𝖳}}{3} = 𝐼_{3} - \frac{1}{3} (\begin{matrix} 1 & - 1 & - 1 \\ - 1 & 1 & 1 \\ - 1 & 1 & 1 \end{matrix}) \\ = \frac{1}{3} (\begin{matrix} 2 & 1 & 1 \\ 1 & 2 & - 1 \\ 1 & - 1 & 2 \end{matrix}) . \end{aligned}

The matrix is symmetric, and $tr 𝑃 = (2 + 2 + 2) / 3 = 2$ . For $𝑃^{2} = 𝑃$ , by Theorem 6.4.31 there is nothing to check, but directly: the first row of $3 𝑃$ times the columns of $3 𝑃$ gives $(4 + 1 + 1, 2 + 2 - 1, 2 - 1 + 2) =$ $(6, 3, 3)$ , which is $3$ times the first row of $3 𝑃$ , and similarly for the other rows; so ${(3 𝑃)}^{2} = 3 (3 𝑃)$ , that is, $𝑃^{2} = 𝑃$ .

Exercise 6.4.42.routine To project $𝐯 = (1, 2, 3)$ onto $𝑊 = span (𝐚, 𝐛)$ , where $𝐚 = (1, 0, 0)$ and $𝐛 = (1, 1, 0)$ , a student adds the shadows of $𝐯$ on the two spanning vectors:

\frac{⟨ 𝐯, 𝐚 ⟩}{{‖ 𝐚 ‖}^{2}} 𝐚 + \frac{⟨ 𝐯, 𝐛 ⟩}{{‖ 𝐛 ‖}^{2}} 𝐛 = (1, 0, 0) + \frac{3}{2} (1, 1, 0) = (\frac{5}{2}, \frac{3}{2}, 0) .

Find the error, show that the answer fails the test of Theorem 6.4.6, and compute ${Pr}_{𝑊} (𝐯)$ correctly.

Solution.

Uses. Corollary 6.4.10 (Projecting with an orthogonal list), Theorem 6.4.6 (The projection is characterized by orthogonality), Algorithm 6.4.14 (Gram–Schmidt)

Techniques. Recognize a projection by its two conditions (Technique 6.4.7)

Hint 1. Which hypothesis of Corollary 6.4.10 does the list

𝐚, 𝐛

fail?

Hint 2. Check whether

𝐯 - (5 / 2, 3 / 2, 0)

is orthogonal to

𝐚

. To fix the computation, orthogonalize

𝐚, 𝐛

first.

Sketch. The formula needs an orthogonal list, and

⟨ 𝐚, 𝐛 ⟩ = 1 \neq 0

. The student’s

𝐯 -

𝐩 =

(- 3 / 2, 1 / 2, 3)

has inner product

- 3 / 2

with

𝐚

. Gram–Schmidt replaces

𝐛

(0, 1, 0)

, and then

{Pr}_{𝑊} (𝐯) =

(1, 0, 0) +

(0, 2, 0) =

(1, 2, 0)

The formula of Corollary 6.4.10 holds for orthogonal lists, and $⟨ 𝐚, 𝐛 ⟩ = 1 \neq 0$ . The test of Theorem 6.4.6 detects the error: for $𝐩 = (5 / 2, 3 / 2, 0)$ , the vector $𝐯 -$ $𝐩 =$ $(- 3 / 2, 1 / 2, 3)$ has $⟨ 𝐯 - 𝐩, 𝐚 ⟩ = - 3 / 2 \neq 0$ , so $𝐯 - 𝐩 \notin 𝑊^{⟂}$ .

Gram–Schmidt turns $𝐚, 𝐛$ into the orthogonal list $𝐚$ , $𝐛 -$ $⟨ 𝐛, 𝐚 ⟩ 𝐚 =$ $(0, 1, 0)$ with the same span, so $𝑊$ is the $𝑥_{1} 𝑥_{2}$ -plane. Now Corollary 6.4.10 applies:

{Pr}_{𝑊} (𝐯) = 1 \cdot (1, 0, 0) + 2 \cdot (0, 1, 0) = (1, 2, 0),

and $𝐯 -$ ${Pr}_{𝑊} (𝐯) =$ $(0, 0, 3)$ is orthogonal to $𝑊$ . The student’s vector even lies in $𝑊$ ; it is just the wrong vector of $𝑊$ .

Exercise 6.4.43.routine Run Gram–Schmidt on

𝐯_{1} = (1, 0, 1, 0)

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

𝐯_{3} = (0, 1, - 1, 0)

𝐯_{4} = (0, 0, 0, 1)

ℝ^{4}

. Which vector is skipped? Use the computation to write the skipped vector as a combination of the earlier ones, and give

dim span (𝐯_{1}, \dots, 𝐯_{4})

Solution.

Uses. Algorithm 6.4.14 (Gram–Schmidt), Theorem 6.4.15 (Gram–Schmidt is correct), Remark 6.4.16 (Postponing the normalization)

Hint 1. Use residuals.

𝐟_{1} = (1, 0, 1, 0)

and

𝐟_{2}

is a multiple of

(1, 2, - 1, 0)

Hint 2. The third residual is

𝟎

. Its formula expresses

𝐯_{3}

through

𝐟_{1}

and

𝐟_{2}

; rewrite those in terms of

𝐯_{1}

and

𝐯_{2}

Sketch.

𝐟_{1} = (1, 0, 1, 0)

;

𝐟_{2} = 𝐯_{2} - 𝐟_{1} / 2

, rescaled to

𝐠 =

(1, 2, - 1, 0) =

2 𝐯_{2} -

𝐯_{1}

;

𝐯_{3} -

(- 1 / 2) 𝐟_{1} -

(3 / 6) 𝐠 =

𝟎

, so

𝐯_{3}

is skipped and

𝐯_{3} =

- 𝐯_{1} / 2 +

𝐠 / 2 =

𝐯_{2} -

𝐯_{1}

;

𝐯_{4}

is already orthogonal to the others. The dimension is

3

With residuals (Remark 6.4.16): $𝐟_{1} = (1, 0, 1, 0)$ , ${‖ 𝐟_{1} ‖}^{2} = 2$ . Then $⟨ 𝐯_{2}, 𝐟_{1} ⟩ = 1$ , and

𝐯_{2} - \frac{1}{2} 𝐟_{1} = (\frac{1}{2}, 1, - \frac{1}{2}, 0),

which we replace by $𝐠 =$ $(1, 2, - 1, 0) =$ $2 𝐯_{2} -$ $𝐯_{1}$ , with ${‖ 𝐠 ‖}^{2} = 6$ . In the third pass, $⟨ 𝐯_{3}, 𝐟_{1} ⟩ = - 1$ and $⟨ 𝐯_{3}, 𝐠 ⟩ = 2 + 1 = 3$ , so

\begin{aligned} 𝐯_{3} + \frac{1}{2} (1, 0, 1, 0) - \frac{3}{6} (1, 2, - 1, 0) \\ = (0 + \frac{1}{2} - \frac{1}{2}, 1 - 1, - 1 + \frac{1}{2} + \frac{1}{2}, 0) = 𝟎 . \end{aligned}

So $𝐯_{3}$ is skipped, and by Theorem 6.4.15(b) it lies in $span (𝐯_{1}, 𝐯_{2})$ . Explicitly, $𝐯_{3} =$ $- (1 / 2) 𝐯_{1} +$ $(1 / 2) (2 𝐯_{2} - 𝐯_{1}) =$ $𝐯_{2} -$ $𝐯_{1}$ , which is easily checked. Finally $𝐯_{4}$ is orthogonal to $𝐟_{1}$ and $𝐠$ , so its residual is $𝐯_{4}$ itself. Three vectors are kept, so the output

\frac{1}{\sqrt{2}} (1, 0, 1, 0), \frac{1}{\sqrt{6}} (1, 2, - 1, 0), (0, 0, 0, 1)

is an orthonormal basis of $span (𝐯_{1}, \dots, 𝐯_{4})$ (Theorem 6.4.15(c)), whose dimension is therefore $3$ .

Exercise 6.4.44.standard In

𝐶 [- 1, 1]

with

⟨ 𝑓, 𝑔 ⟩ =

\int_{- 1}^{1} 𝑓 (𝑡) 𝑔 (𝑡) d 𝑡

, find the polynomial functions of degree at most

0

, at most

1

, and at most

2

closest to

𝑓 (𝑡) = | 𝑡 |

, and the squared distance from

𝑓

to each.

Solution.

Uses. Theorem 6.4.33 (Best approximation), Example 6.4.19 (Legendre polynomials), Corollary 6.4.10 (Projecting with an orthogonal list)

Hint 1. Use the orthogonal basis

1, 𝑡, 𝑡^{2} - 1 / 3

of Example 6.4.19, with squared norms

2

2 / 3

8 / 45

. Each new degree adds one term to the projection.

Hint 2.

⟨ | 𝑡 |, 1 ⟩ = 1

⟨ | 𝑡 |, 𝑡 ⟩ = 0

(odd integrand), and

⟨ | 𝑡 |, 𝑡^{2} ⟩ =

2 \int_{0}^{1} 𝑡^{3} d 𝑡 =

1 / 2

Hint 3. The squared distance is

{‖ 𝑓 ‖}^{2}

minus the squared norm of the projection, and each term contributes

{⟨ 𝑓, 𝐟_{𝑗} ⟩}^{2} / {‖ 𝐟_{𝑗} ‖}^{2}

Sketch. The coefficients are

1 / 2

0

, and

(1 / 6) / (8 / 45) =

15 / 16

. So the best constant and the best linear function are both

1 / 2

, with squared distance

2 / 3 - 1 / 2 = 1 / 6

, and the best quadratic is

1 / 2 +

(15 / 16) (𝑡^{2} - 1 / 3) =

(3 + 15 𝑡^{2}) / 16

, with squared distance

1 / 6 -

(1 / 36) (45 / 8) =

1 / 96

Let $𝑓 (𝑡) = | 𝑡 |$ . The polynomial functions of degree at most $𝑛$ form a finite-dimensional subspace $𝑊_{𝑛}$ , and by Theorem 6.4.33 the closest one to $𝑓$ is ${Pr}_{𝑊_{𝑛}} (𝑓)$ . By Example 6.4.19, $1$ ; $1, 𝑡$ ; and $1, 𝑡, 𝑡^{2} - 1 / 3$ are orthogonal bases of $𝑊_{0}$ , $𝑊_{1}$ , $𝑊_{2}$ , with squared norms $2$ , $2 / 3$ , $8 / 45$ . We need

\begin{aligned} ⟨ 𝑓, 1 ⟩ & = 2 \int_{0}^{1} 𝑡 d 𝑡 = 1, ⟨ 𝑓, 𝑡 ⟩ = 0, \\ ⟨ 𝑓, 𝑡^{2} - \frac{1}{3} ⟩ & = 2 \int_{0}^{1} 𝑡^{3} d 𝑡 - \frac{1}{3} = \frac{1}{2} - \frac{1}{3} = \frac{1}{6}, \end{aligned}

where $⟨ 𝑓, 𝑡 ⟩ = 0$ because $| 𝑡 | 𝑡$ is odd. By Corollary 6.4.10,

\begin{aligned} {Pr}_{𝑊_{0}} (𝑓) & = {Pr}_{𝑊_{1}} (𝑓) = \frac{1}{2}, \\ {Pr}_{𝑊_{2}} (𝑓) & = \frac{1}{2} + \frac{1 / 6}{8 / 45} (𝑡^{2} - \frac{1}{3}) \\ = \frac{1}{2} + \frac{15}{16} (𝑡^{2} - \frac{1}{3}) = \frac{3 + 15 𝑡^{2}}{16} . \end{aligned}

For the distances, ${‖ 𝑓 ‖}^{2} =$ $\int_{- 1}^{1} 𝑡^{2} d 𝑡 =$ $2 / 3$ , and by Theorem 6.4.33 (applied with the normalized basis, whose squared inner products with $𝑓$ are ${⟨ 𝑓, 𝐟_{𝑗} ⟩}^{2} / {‖ 𝐟_{𝑗} ‖}^{2}$ ),

\begin{aligned} {dist (𝑓, 𝑊_{0})}^{2} & = {dist (𝑓, 𝑊_{1})}^{2} = \frac{2}{3} - \frac{1^{2}}{2} = \frac{1}{6}, \\ {dist (𝑓, 𝑊_{2})}^{2} & = \frac{1}{6} - \frac{{(1 / 6)}^{2}}{8 / 45} = \frac{1}{6} - \frac{5}{32} = \frac{1}{96} . \end{aligned}

The best linear approximation is no better than the best constant, because $𝑓$ is even and $𝑡$ is odd. Allowing $𝑡^{2}$ cuts the squared error by a factor of $16$ , although $| 𝑡 |$ is not differentiable at $0$ and has no Taylor polynomial there.

Exercise 6.4.45.standard Find the minimum of

\int_{- 1}^{1} {(𝑡^{3} - 𝑎 - 𝑏 𝑡 - 𝑐 𝑡^{2})}^{2} d 𝑡

over all

𝑎, 𝑏, 𝑐 \in ℝ

, and the values of

𝑎, 𝑏, 𝑐

that attain it.

Solution.

Uses. Theorem 6.4.33 (Best approximation), Example 6.4.19 (Legendre polynomials), Exercise 6.3.49

Hint 1. The integral is

{‖ 𝑡^{3} - 𝑝 ‖}^{2}

for

𝑝 = 𝑎 + 𝑏 𝑡 + 𝑐 𝑡^{2}

in the subspace

𝑊

of polynomial functions of degree at most

2

. Which

𝑝

minimizes it?

Hint 2.

𝑝 = {Pr}_{𝑊} (𝑡^{3})

, and

𝑡^{3} - {Pr}_{𝑊} (𝑡^{3})

is the fourth Gram–Schmidt residual of Example 6.4.19.

Sketch. By Theorem 6.4.33 the minimizer is

𝑝 = {Pr}_{𝑊} (𝑡^{3})

, and

𝑡^{3} - {Pr}_{𝑊} (𝑡^{3})

is the residual

𝑡^{3} - (3 / 5) 𝑡

from Gram–Schmidt on

1, 𝑡, 𝑡^{2}, 𝑡^{3}

. So

𝑎 = 𝑐 = 0

𝑏 = 3 / 5

, and the minimum is

{‖ 𝑡^{3} - (3 / 5) 𝑡 ‖}^{2} =

8 / 175

(Exercise 6.3.49).

Let $𝑊$ be the space of polynomial functions of degree at most $2$ in $𝐶 [- 1, 1]$ with $⟨ 𝑓, 𝑔 ⟩ = \int_{- 1}^{1} 𝑓 𝑔$ . The integral is ${‖ 𝑡^{3} - 𝑝 ‖}^{2}$ with $𝑝 =$ $𝑎 +$ $𝑏 𝑡 +$ $𝑐 𝑡^{2} \in$ $𝑊$ , and as $(𝑎, 𝑏, 𝑐)$ ranges over $ℝ^{3}$ , $𝑝$ ranges over all of $𝑊$ . By Theorem 6.4.33 the minimum is attained exactly at $𝑝 = {Pr}_{𝑊} (𝑡^{3})$ .

By Example 6.4.19, $𝑊 = span (1, 𝑡, 𝑡^{2})$ , and the fourth Gram–Schmidt residual is $𝑡^{3} -$ ${Pr}_{𝑊} (𝑡^{3}) =$ $𝑡^{3} -$ $(3 / 5) 𝑡$ . So ${Pr}_{𝑊} (𝑡^{3}) = (3 / 5) 𝑡$ : the minimum is attained exactly at $𝑎 = 0$ , $𝑏 = 3 / 5$ , $𝑐 = 0$ , and its value is

\begin{aligned} {‖ 𝑡^{3} - \frac{3}{5} 𝑡 ‖}^{2} & = \int_{- 1}^{1} (𝑡^{6} - \frac{6}{5} 𝑡^{4} + \frac{9}{25} 𝑡^{2}) d 𝑡 \\ = \frac{2}{7} - \frac{12}{25} + \frac{6}{25} = \frac{8}{175}, \end{aligned}

as computed in Exercise 6.3.49. (Calculus would set three partial derivatives to $0$ and solve a $3 \times 3$ system; the orthogonal basis does that work once and for all.)

Exercise 6.4.46.standard Give ${ℝ [𝑥]}_{\leq 2}$ the inner product $⟨ 𝑝, 𝑞 ⟩ =$ $\int_{0}^{1} 𝑝 (𝑡) 𝑞 (𝑡) d 𝑡$ used in lecture.

(a)Apply Gram–Schmidt to $1, 𝑥, 𝑥^{2}$ , and show that the output is $1$ , $\sqrt{3} (2 𝑥 - 1)$ , $\sqrt{5} (6 𝑥^{2} - 6 𝑥 + 1)$ .
(b)Find ${min}_{𝑎, 𝑏 \in ℝ} \int_{0}^{1} {(𝑡^{2} - 𝑎 - 𝑏 𝑡)}^{2} d 𝑡$ .

Solution.

Uses. Algorithm 6.4.14 (Gram–Schmidt), Remark 6.4.16 (Postponing the normalization), Theorem 6.4.33 (Best approximation)

Hint 1.

⟨ 𝑥^{𝑖}, 𝑥^{𝑗} ⟩ =

1 / (𝑖 + 𝑗 + 1)

. Work with residuals.

Hint 2. The residuals are

1

𝑥 - 1 / 2

𝑥^{2} - 𝑥 + 1 / 6

, with squared norms

1

1 / 12

1 / 180

Hint 3. For (b), the minimizer is

𝑎 + 𝑏 𝑥 = Pr (𝑥^{2})

onto

span (1, 𝑥)

, and the minimum is the squared norm of the third residual.

Sketch.

𝑓_{1} = 1

;

𝑓_{2} =

𝑥 -

⟨ 𝑥, 1 ⟩ =

𝑥 -

1 / 2

;

𝑓_{3} =

𝑥^{2} -

1 / 3 -

(1 / 12) / (1 / 12) (𝑥 - 1 / 2) =

𝑥^{2} -

𝑥 +

1 / 6

. Normalizing with

{‖ 𝑓_{2} ‖}^{2} = 1 / 12

and

{‖ 𝑓_{3} ‖}^{2} = 1 / 180

gives the list. (b) The minimum is

{‖ 𝑓_{3} ‖}^{2} = 1 / 180

, at

𝑎 + 𝑏 𝑡 = 𝑡 - 1 / 6

(a) Here $⟨ 𝑥^{𝑖}, 𝑥^{𝑗} ⟩ =$ $\int_{0}^{1} 𝑡^{𝑖 + 𝑗} d 𝑡 =$ $1 / (𝑖 + 𝑗 + 1)$ . With residuals: $𝑓_{1} = 1$ , ${‖ 𝑓_{1} ‖}^{2} = 1$ , and $𝑓_{2} =$ $𝑥 -$ $⟨ 𝑥, 1 ⟩ \cdot$ $1 =$ $𝑥 -$ $1 / 2$ , with

{‖ 𝑓_{2} ‖}^{2} = \int_{0}^{1} {(𝑡 - \frac{1}{2})}^{2} d 𝑡 = \frac{1}{12} .

Next, $⟨ 𝑥^{2}, 1 ⟩ = 1 / 3$ and $⟨ 𝑥^{2}, 𝑥 - 1 / 2 ⟩ =$ $1 / 4 -$ $1 / 6 =$ $1 / 12$ , so

𝑓_{3} = 𝑥^{2} - \frac{1}{3} - \frac{1 / 12}{1 / 12} (𝑥 - \frac{1}{2}) = 𝑥^{2} - 𝑥 + \frac{1}{6} .

Expanding, ${‖ 𝑓_{3} ‖}^{2} =$ $\int_{0}^{1} (𝑡^{4} - 2 𝑡^{3} + (4 / 3) 𝑡^{2} - 𝑡 / 3 + 1 / 36) d 𝑡 =$ $1 / 5 -$ $1 / 2 +$ $4 / 9 -$ $1 / 6 +$ $1 / 36 =$ $1 / 180$ . Normalizing,

\begin{aligned} 𝑢_{1} & = 1, \\ 𝑢_{2} & = \sqrt{12} (𝑥 - \frac{1}{2}) = \sqrt{3} (2 𝑥 - 1), \\ 𝑢_{3} & = \sqrt{180} (𝑥^{2} - 𝑥 + \frac{1}{6}) = \sqrt{5} (6 𝑥^{2} - 6 𝑥 + 1) . \end{aligned}

The first two are the output of the lecture’s example.

(b) As $(𝑎, 𝑏)$ ranges over $ℝ^{2}$ , $𝑎 + 𝑏 𝑥$ ranges over $𝑊 =$ $span (1, 𝑥) =$ $span (𝑓_{1}, 𝑓_{2})$ . By Theorem 6.4.33, the minimum is ${dist (𝑥^{2}, 𝑊)}^{2} =$ ${‖ 𝑥^{2} - {Pr}_{𝑊} (𝑥^{2}) ‖}^{2}$ , and $𝑥^{2} - {Pr}_{𝑊} (𝑥^{2})$ is the residual $𝑓_{3}$ . So the minimum is $1 / 180$ , attained at $𝑎 +$ $𝑏 𝑥 =$ $𝑥^{2} -$ $𝑓_{3} =$ $𝑥 -$ $1 / 6$ , that is, $𝑎 = - 1 / 6$ , $𝑏 = 1$ .

Exercise 6.4.47.standard Let $𝑈$ and $𝑊$ be subspaces of $𝑉$ .

(a)Show that ${(𝑈 + 𝑊)}^{⟂} = 𝑈^{⟂} \cap 𝑊^{⟂}$ .
(b)Suppose $𝑉$ is finite-dimensional. Show that ${(𝑈 \cap 𝑊)}^{⟂} = 𝑈^{⟂} + 𝑊^{⟂}$ .

Solution.

Uses. Definition 6.4.22 (Orthogonal complement), Proposition 1.4.24 (The sum of two subspaces), Theorem 6.4.26 (The double complement), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ )

Techniques. Double containment (Technique 1.3.14)

Hint 1. For (a), unwind the definitions. One containment uses

𝑈, 𝑊 \subseteq 𝑈 + 𝑊

; the other expands

⟨ 𝐯, 𝐮 + 𝐰 ⟩

Hint 2. For (b), apply (a) to the subspaces

𝑈^{⟂}

and

𝑊^{⟂}

, then take

⟂

of both sides.

Hint 3. Theorem 6.4.26 says

{(𝑋^{⟂})}^{⟂} = 𝑋

for every subspace

𝑋

of the finite-dimensional space

𝑉

Sketch. (a)

𝑈, 𝑊 \subseteq 𝑈 + 𝑊

gives

{(𝑈 + 𝑊)}^{⟂} \subseteq 𝑈^{⟂} \cap 𝑊^{⟂}

; conversely

⟨ 𝐯, 𝐮 + 𝐰 ⟩ =

⟨ 𝐯, 𝐮 ⟩ +

⟨ 𝐯, 𝐰 ⟩ =

0

. (b) By (a) and Theorem 6.4.26,

{(𝑈^{⟂} + 𝑊^{⟂})}^{⟂} =

𝑈^{⟂ ⟂} \cap

𝑊^{⟂ ⟂} =

𝑈 \cap

𝑊

. Taking

⟂

and using Theorem 6.4.26 again,

𝑈^{⟂} + 𝑊^{⟂} = {(𝑈 \cap 𝑊)}^{⟂}

(a) Since $𝑈 \subseteq 𝑈 + 𝑊$ and $𝑊 \subseteq 𝑈 + 𝑊$ (Proposition 1.4.24), Proposition 6.3.9(b) gives ${(𝑈 + 𝑊)}^{⟂} \subseteq 𝑈^{⟂}$ and ${(𝑈 + 𝑊)}^{⟂} \subseteq 𝑊^{⟂}$ . Conversely, let $𝐯 \in 𝑈^{⟂} \cap 𝑊^{⟂}$ . Every vector of $𝑈 + 𝑊$ is $𝐮 + 𝐰$ with $𝐮 \in 𝑈$ and $𝐰 \in 𝑊$ , and

⟨ 𝐯, 𝐮 + 𝐰 ⟩ = ⟨ 𝐯, 𝐮 ⟩ + ⟨ 𝐯, 𝐰 ⟩ = 0 + 0 = 0 .

So $𝐯 \in {(𝑈 + 𝑊)}^{⟂}$ .

(b) Every subspace $𝑋$ of the finite-dimensional space $𝑉$ is finite-dimensional, so ${(𝑋^{⟂})}^{⟂} = 𝑋$ by Theorem 6.4.26. Apply (a) to the subspaces $𝑈^{⟂}$ and $𝑊^{⟂}$ :

{(𝑈^{⟂} + 𝑊^{⟂})}^{⟂} = {(𝑈^{⟂})}^{⟂} \cap {(𝑊^{⟂})}^{⟂} = 𝑈 \cap 𝑊 .

Taking orthogonal complements of both sides and applying Theorem 6.4.26 to $𝑋 = 𝑈^{⟂} + 𝑊^{⟂}$ ,

𝑈^{⟂} + 𝑊^{⟂} = {({(𝑈^{⟂} + 𝑊^{⟂})}^{⟂})}^{⟂} = {(𝑈 \cap 𝑊)}^{⟂},

as desired.

Exercise 6.4.48.standard Let $𝑉$ be a finite-dimensional inner product space and $𝑈, 𝑊$ subspaces of $𝑉$ . Prove or disprove each statement.

(a)If $𝑉 = 𝑈 \oplus 𝑊$ , then $𝑊 = 𝑈^{⟂}$ .
(b)If every vector of $𝑈$ is orthogonal to every vector of $𝑊$ and $𝑈 + 𝑊 = 𝑉$ , then $𝑊 = 𝑈^{⟂}$ .
(c) ${Pr}_{𝑈} {Pr}_{𝑊} = {Pr}_{𝑊} {Pr}_{𝑈}$ .
(d)If $‖ {Pr}_{𝑊} (𝐯) ‖ = ‖ 𝐯 ‖$ , then $𝐯 \in 𝑊$ .
(e)Every $𝑃 \in L (𝑉)$ with $𝑃^{2} = 𝑃$ satisfies $‖ 𝑃 𝐯 ‖ \leq ‖ 𝐯 ‖$ for all $𝐯 \in 𝑉$ .

Solution.

Uses. Theorem 6.4.24 (Orthogonal decomposition), Proposition 6.4.4 (Properties of ${Pr}_{𝒪︀}$ ), Remark 6.4.12 (Why “orthogonal”), Definition 4.4.4 (Direct sum)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. For (a), (c), and (e), look in

ℝ^{2}

, using lines that are neither equal nor perpendicular.

Hint 2. For (b),

𝑊 \subseteq 𝑈^{⟂}

is clear. For the other containment, write

𝐯 \in 𝑈^{⟂}

𝐮 + 𝐰

and take the inner product with

𝐮

Hint 3. For (d), use Proposition 6.4.4(e).

Sketch. (a) False:

ℝ^{2} =

span (𝐞_{1}) \oplus

span ((1, 1))

. (b) True: if

𝐯 = 𝐮 + 𝐰 \in 𝑈^{⟂}

, then

0 = ⟨ 𝐯, 𝐮 ⟩ = {‖ 𝐮 ‖}^{2}

. (c) False: for

𝑈 = span (𝐞_{1})

𝑊 = span ((1, 1))

{Pr}_{𝑈} {Pr}_{𝑊} 𝐞_{1} =

(1 / 2, 0)

but

{Pr}_{𝑊} {Pr}_{𝑈} 𝐞_{1} =

(1 / 2, 1 / 2)

. (d) True, by the equality case of Bessel. (e) False:

𝑃 (𝑥, 𝑦) =

(𝑥 + 𝑦, 0)

has

𝑃^{2} = 𝑃

and

‖ 𝑃 (1, 1) ‖ = 2 > \sqrt{2}

(a) False. In $ℝ^{2}$ , let $𝑈 = span (𝐞_{1})$ and $𝑊 = span ((1, 1))$ . Then $𝑈 \cap 𝑊 = {𝟎}$ and $𝑈 + 𝑊 = ℝ^{2}$ , so $𝑉 = 𝑈 \oplus 𝑊$ , but $𝑈^{⟂} = span (𝐞_{2}) \neq 𝑊$ . Every subspace has many complements, and $𝑈^{⟂}$ is only one of them.

(b) True. By hypothesis $𝑊 \subseteq 𝑈^{⟂}$ . Conversely, let $𝐯 \in 𝑈^{⟂}$ , and write $𝐯 = 𝐮 + 𝐰$ with $𝐮 \in 𝑈$ and $𝐰 \in 𝑊$ . Then

0 = ⟨ 𝐯, 𝐮 ⟩ = ⟨ 𝐮, 𝐮 ⟩ + ⟨ 𝐰, 𝐮 ⟩ = {‖ 𝐮 ‖}^{2},

so $𝐮 = 𝟎$ and $𝐯 = 𝐰 \in 𝑊$ .

(c) False. With $𝑈$ and $𝑊$ as in (a), ${Pr}_{𝑊} (𝐞_{1}) =$ $(1 / 2) (1, 1)$ , so

\begin{aligned} {Pr}_{𝑈} {Pr}_{𝑊} (𝐞_{1}) & = {Pr}_{𝑈} (\frac{1}{2}, \frac{1}{2}) = (\frac{1}{2}, 0), \\ {Pr}_{𝑊} {Pr}_{𝑈} (𝐞_{1}) & = {Pr}_{𝑊} (𝐞_{1}) = (\frac{1}{2}, \frac{1}{2}) . \end{aligned}

(Exercise 6.4.58 shows when the two products agree.)

(d) True. By Proposition 6.4.4(e) applied to an orthonormal basis of $𝑊$ , $‖ {Pr}_{𝑊} (𝐯) ‖ = ‖ 𝐯 ‖$ holds only if $𝐯 \in 𝑊$ .

(e) False. $𝑃 (𝑥, 𝑦) =$ $(𝑥 + 𝑦, 0)$ is linear with $𝑃^{2} (𝑥, 𝑦) =$ $𝑃 (𝑥 + 𝑦, 0) =$ $(𝑥 + 𝑦, 0) =$ $𝑃 (𝑥, 𝑦)$ , but $‖ 𝑃 (1, 1) ‖ =$ $‖ (2, 0) ‖ =$ $2 >$ $\sqrt{2} =$ $‖ (1, 1) ‖$ . Like the map of Remark 6.4.12, $𝑃$ projects onto the $𝑥$ -axis along a direction that is not perpendicular to it (here $(1, - 1)$ ), and such projections can stretch vectors. Exercise 6.4.57 shows that this is the only way an idempotent can fail to shrink norms.

Exercise 6.4.49.standard Let $𝑈$ and $𝑊$ be finite-dimensional subspaces of $𝑉$ .

(a)Suppose every vector of $𝑈$ is orthogonal to every vector of $𝑊$ . Show that ${Pr}_{𝑈 + 𝑊} = {Pr}_{𝑈} + {Pr}_{𝑊}$ and ${Pr}_{𝑈} {Pr}_{𝑊} = 0$ .
(b)Conversely, show that if ${Pr}_{𝑈} {Pr}_{𝑊} = 0$ , then every vector of $𝑈$ is orthogonal to every vector of $𝑊$ .

Solution.

Uses. Theorem 6.4.6 (The projection is characterized by orthogonality), Proposition 6.4.29 (The orthogonal projection as a linear map), Proposition 1.4.24 (The sum of two subspaces), Theorem 6.4.20 (Orthonormal bases exist)

Techniques. Recognize a projection by its two conditions (Technique 6.4.7)

Hint 1. For (a), check the two conditions of Technique 6.4.7 for

𝐩 =

{Pr}_{𝑈} (𝐯) +

{Pr}_{𝑊} (𝐯)

and the subspace

𝑈 + 𝑊

. (

𝑈 + 𝑊

is finite-dimensional: concatenate orthonormal bases.)

Hint 2. For

{Pr}_{𝑈} {Pr}_{𝑊} = 0

{Pr}_{𝑊} (𝐯) \in

𝑊 \subseteq

𝑈^{⟂} =

ker {Pr}_{𝑈}

Hint 3. For (b), compute

⟨ 𝐰, 𝐮 ⟩ =

⟨ {Pr}_{𝑊} 𝐰, {Pr}_{𝑈} 𝐮 ⟩

and move

{Pr}_{𝑈}

across with Proposition 6.4.29(c).

Sketch. (a)

𝑈 + 𝑊

is spanned by the concatenation of orthonormal bases of

𝑈

and

𝑊

, which is orthonormal. For

𝐩 =

{Pr}_{𝑈} (𝐯) +

{Pr}_{𝑊} (𝐯) \in

𝑈 +

𝑊

⟨ 𝐯 - 𝐩, 𝐮 ⟩ =

⟨ 𝐯 - {Pr}_{𝑈} (𝐯), 𝐮 ⟩ -

⟨ {Pr}_{𝑊} (𝐯), 𝐮 ⟩ =

0

for

𝐮 \in 𝑈

, and similarly for

𝑊

; so

𝐩 = {Pr}_{𝑈 + 𝑊} (𝐯)

. Also

{Pr}_{𝑊} (𝐯) \in

𝑊 \subseteq

𝑈^{⟂} =

ker {Pr}_{𝑈}

. (b)

⟨ 𝐰, 𝐮 ⟩ =

⟨ {Pr}_{𝑊} 𝐰, {Pr}_{𝑈} 𝐮 ⟩ =

⟨ {Pr}_{𝑈} {Pr}_{𝑊} 𝐰, 𝐮 ⟩ =

0

(a) Let $𝐮_{1}, \dots, 𝐮_{𝑘}$ and $𝐰_{1}, \dots, 𝐰_{𝑙}$ be orthonormal bases of $𝑈$ and $𝑊$ (Theorem 6.4.20). By hypothesis $⟨ 𝐮_{𝑖}, 𝐰_{𝑗} ⟩ = 0$ , so the concatenated list is orthonormal, and it spans $𝑈 + 𝑊$ . So $𝑈 + 𝑊$ is finite-dimensional and ${Pr}_{𝑈 + 𝑊}$ is defined. (In fact the formula of Definition 6.4.11 for this basis already gives the claim; we give the argument of Technique 6.4.7 instead.)

Let $𝐯 \in 𝑉$ and $𝐩 =$ ${Pr}_{𝑈} (𝐯) +$ ${Pr}_{𝑊} (𝐯)$ , which lies in $𝑈 + 𝑊$ . For $𝐮 \in 𝑈$ , we have ${Pr}_{𝑊} (𝐯) \in 𝑊$ , so $⟨ {Pr}_{𝑊} (𝐯), 𝐮 ⟩ = 0$ by hypothesis, and

\begin{aligned} ⟨ 𝐯 - 𝐩, 𝐮 ⟩ & = ⟨ 𝐯 - {Pr}_{𝑈} (𝐯), 𝐮 ⟩ - ⟨ {Pr}_{𝑊} (𝐯), 𝐮 ⟩ \\ = 0 - 0 = 0 . \end{aligned}

In the same way $⟨ 𝐯 - 𝐩, 𝐰 ⟩ = 0$ for $𝐰 \in 𝑊$ . So $𝐯 - 𝐩$ is orthogonal to every $𝐮 + 𝐰$ , that is, to $𝑈 + 𝑊$ , and $𝐩 = {Pr}_{𝑈 + 𝑊} (𝐯)$ by Theorem 6.4.6.

The hypothesis says $𝑊 \subseteq 𝑈^{⟂}$ , and $𝑈^{⟂} = ker {Pr}_{𝑈}$ by Proposition 6.4.29(a). Since ${Pr}_{𝑊} (𝐯) \in 𝑊$ , we get ${Pr}_{𝑈} {Pr}_{𝑊} (𝐯) = 𝟎$ for every $𝐯$ .

(b) Let $𝐮 \in 𝑈$ and $𝐰 \in 𝑊$ . Then $𝐮 = {Pr}_{𝑈} (𝐮)$ and $𝐰 = {Pr}_{𝑊} (𝐰)$ , and by Proposition 6.4.29(c) for ${Pr}_{𝑈}$ ,

\begin{aligned} ⟨ 𝐰, 𝐮 ⟩ & = ⟨ {Pr}_{𝑊} (𝐰), {Pr}_{𝑈} (𝐮) ⟩ = ⟨ {Pr}_{𝑈} ({Pr}_{𝑊} (𝐰)), 𝐮 ⟩ \\ = ⟨ 𝟎, 𝐮 ⟩ = 0 . \end{aligned}

Exercise 6.4.50.standard Find the error in the following argument, and decide whether the claim is true.

Claim. If $𝑈$ and $𝑊$ are finite-dimensional subspaces of $𝑉$ , then ${Pr}_{𝑈 + 𝑊} = {Pr}_{𝑈} + {Pr}_{𝑊}$ .

Argument. Let $𝐯 \in 𝑉$ and $𝐩 =$ ${Pr}_{𝑈} (𝐯) +$ ${Pr}_{𝑊} (𝐯)$ , which lies in $𝑈 + 𝑊$ . We have $𝐯 - {Pr}_{𝑈} (𝐯) ⟂ 𝑈$ and ${Pr}_{𝑊} (𝐯) ⟂ 𝑈$ , so $𝐯 -$ $𝐩 =$ $(𝐯 - {Pr}_{𝑈} (𝐯)) -$ ${Pr}_{𝑊} (𝐯) ⟂ 𝑈$ . In the same way $𝐯 - 𝐩 ⟂ 𝑊$ , so $𝐯 - 𝐩 ⟂ 𝑈 + 𝑊$ . By Theorem 6.4.6, $𝐩 = {Pr}_{𝑈 + 𝑊} (𝐯)$ .

Solution.

Uses. Theorem 6.4.6 (The projection is characterized by orthogonality), Exercise 6.4.49

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Every step but one is an instance of something proved in this section. Which statement about

{Pr}_{𝑊} (𝐯)

has no justification?

Hint 2. Test the claim with

𝑈 = 𝑊

Sketch. The step “

{Pr}_{𝑊} (𝐯) ⟂ 𝑈

” is unjustified:

{Pr}_{𝑊} (𝐯)

lies in

𝑊

, and

𝑊

need not be orthogonal to

𝑈

. The claim is false: for

𝑈 = 𝑊 = span (𝐞_{1})

ℝ^{2}

{Pr}_{𝑈} + {Pr}_{𝑊} = 2 {Pr}_{𝑈}

, which sends

𝐞_{1}

2 𝐞_{1}

, while

{Pr}_{𝑈 + 𝑊} (𝐞_{1}) = 𝐞_{1}

. It is true when

𝑈 ⟂ 𝑊

(Exercise 6.4.49).

The error is the assertion ${Pr}_{𝑊} (𝐯) ⟂ 𝑈$ . All we know is that ${Pr}_{𝑊} (𝐯) \in 𝑊$ , and a vector of $𝑊$ is orthogonal to $𝑈$ only if, for instance, every vector of $𝑊$ is orthogonal to every vector of $𝑈$ .

The claim is false. Let $𝑈 = 𝑊 = span (𝐞_{1})$ in $ℝ^{2}$ . Then $𝑈 + 𝑊 = 𝑈$ , and

({Pr}_{𝑈} + {Pr}_{𝑊}) (𝐞_{1}) = 2 𝐞_{1} \neq 𝐞_{1} = {Pr}_{𝑈 + 𝑊} (𝐞_{1}) .

The argument becomes correct under the extra hypothesis that every vector of $𝑈$ is orthogonal to every vector of $𝑊$ , and then it proves Exercise 6.4.49(a).

Exercise 6.4.51.standard Let $𝑊$ be a $𝑘$ -dimensional subspace of $𝔽^{𝑛}$ , and let $𝑃$ be the matrix of ${Pr}_{𝑊}$ .

(a)Show that $rank 𝑃 = tr 𝑃 = 𝑘$ .
(b)Show that $𝑝_{𝑖 𝑖} = {‖ 𝑃 𝐞_{𝑖} ‖}^{2}$ for each $𝑖$ , and deduce that $\sum_{𝑖 = 1}^{𝑛} {‖ {Pr}_{𝑊} (𝐞_{𝑖}) ‖}^{2} =$ $𝑘$ .
(c)Deduce that some standard basis vector $𝐞_{𝑖}$ satisfies ${dist (𝐞_{𝑖}, 𝑊)}^{2} \leq$ $1 -$ $𝑘 / 𝑛$ .

Solution.

Uses. Theorem 6.4.31 (The matrix of an orthogonal projection), Proposition 2.4.28 (Cyclicity of the trace), Proposition 6.4.29 (The orthogonal projection as a linear map), Theorem 6.4.33 (Best approximation), Theorem 6.4.20 (Orthonormal bases exist)

Techniques. Cyclicity of trace (Technique 2.4.29)

Hint 1. By Theorem 6.4.31,

𝑃 = 𝑄 𝑄^{*}

with

𝑄^{*} 𝑄 = 𝐼_{𝑘}

. Use cyclicity of the trace.

Hint 2. For (b),

𝑝_{𝑖 𝑖} =

(𝑃 𝐞_{𝑖}) \cdot

𝐞_{𝑖}

. Use Proposition 6.4.29(c).

Hint 3. For (c),

{dist (𝐞_{𝑖}, 𝑊)}^{2} =

1 -

{‖ {Pr}_{𝑊} (𝐞_{𝑖}) ‖}^{2}

, and the

𝑛

numbers

{‖ {Pr}_{𝑊} (𝐞_{𝑖}) ‖}^{2}

add up to

𝑘

Sketch. (a)

rank 𝑃 =

dim im {Pr}_{𝑊} =

𝑘

, and

tr (𝑄 𝑄^{*}) =

tr (𝑄^{*} 𝑄) =

tr 𝐼_{𝑘} =

𝑘

. (b)

𝑝_{𝑖 𝑖} =

⟨ 𝑃 𝐞_{𝑖}, 𝐞_{𝑖} ⟩ =

⟨ 𝑃 𝐞_{𝑖}, 𝑃 𝐞_{𝑖} ⟩

; sum over

𝑖

. (c)

{dist (𝐞_{𝑖}, 𝑊)}^{2} =

1 -

𝑝_{𝑖 𝑖}

, and the average of the

𝑝_{𝑖 𝑖}

𝑘 / 𝑛

, so some

𝑝_{𝑖 𝑖} \geq 𝑘 / 𝑛

(a) By Proposition 6.4.29(a), the image of ${Pr}_{𝑊}$ is $𝑊$ , so $rank 𝑃 = dim 𝑊 = 𝑘$ . By Theorem 6.4.20, $𝑊$ has an orthonormal basis, and by Theorem 6.4.31, $𝑃 = 𝑄 𝑄^{*}$ with $𝑄 \in 𝔽^{𝑛 \times 𝑘}$ and $𝑄^{*} 𝑄 = 𝐼_{𝑘}$ . By Proposition 2.4.28, $tr 𝑃 =$ $tr (𝑄 𝑄^{*}) =$ $tr (𝑄^{*} 𝑄) =$ $tr 𝐼_{𝑘} =$ $𝑘$ .

(b) The $𝑖$ th entry of $𝑃 𝐞_{𝑖}$ is $𝑝_{𝑖 𝑖}$ , so $𝑝_{𝑖 𝑖} =$ $(𝑃 𝐞_{𝑖}) \cdot$ $𝐞_{𝑖} =$ $⟨ 𝑃 𝐞_{𝑖}, 𝐞_{𝑖} ⟩$ . By Proposition 6.4.29(c), this equals $⟨ 𝑃 𝐞_{𝑖}, 𝑃 𝐞_{𝑖} ⟩ =$ ${‖ 𝑃 𝐞_{𝑖} ‖}^{2}$ . Summing over $𝑖$ and using (a), $\sum_{𝑖} {‖ {Pr}_{𝑊} (𝐞_{𝑖}) ‖}^{2} =$ $tr 𝑃 =$ $𝑘$ .

(c) By Theorem 6.4.33, ${dist (𝐞_{𝑖}, 𝑊)}^{2} =$ ${‖ 𝐞_{𝑖} ‖}^{2} -$ ${‖ {Pr}_{𝑊} (𝐞_{𝑖}) ‖}^{2} =$ $1 -$ $𝑝_{𝑖 𝑖}$ . The $𝑛$ numbers $𝑝_{𝑖 𝑖}$ add up to $𝑘$ , so the largest of them is at least $𝑘 / 𝑛$ . For that $𝑖$ , ${dist (𝐞_{𝑖}, 𝑊)}^{2} \leq$ $1 -$ $𝑘 / 𝑛$ . (For the plane of Example 6.4.32, every $𝑝_{𝑖 𝑖}$ equals $2 / 3$ , so the bound is attained by all three.)

Exercise 6.4.52.standard Let $𝑊$ be a finite-dimensional subspace of $𝑉$ and $𝐯 \in 𝑉$ with $𝐯 \notin 𝑊$ .

(a)Show that
$dist (𝐯, 𝑊) = max {| ⟨ 𝐯, 𝐱 ⟩ | | 𝐱 \in 𝑊^{⟂}, ‖ 𝐱 ‖ = 1},$
and find the $𝐱$ attaining the maximum.
(b)In $𝐶 [- 1, 1]$ with $⟨ 𝑓, 𝑔 ⟩ = \int_{- 1}^{1} 𝑓 𝑔$ , find the largest value of $\int_{- 1}^{1} 𝑡^{3} 𝑔 (𝑡) d 𝑡$ over all $𝑔$ with $\int_{- 1}^{1} 𝑔^{2} = 1$ that are orthogonal to $1, 𝑡, 𝑡^{2}$ .

Solution.

Uses. Theorem 6.4.24 (Orthogonal decomposition), Theorem 6.2.1 (Cauchy–Schwarz inequality), Definition 6.4.34 (Distance to a subspace), Exercise 6.4.45

Techniques. Apply Cauchy–Schwarz to a well-chosen inner product (Technique 6.2.21)

Hint 1. For

𝐱 \in 𝑊^{⟂}

⟨ 𝐯, 𝐱 ⟩ =

⟨ 𝐯 - {Pr}_{𝑊} (𝐯), 𝐱 ⟩

. Why?

Hint 2. Apply Cauchy–Schwarz, and find when equality holds.

Hint 3. For (b),

𝑊

is the space of polynomial functions of degree at most

2

; the distance from

𝑡^{3}

to it was found in Exercise 6.4.45.

Sketch. For a unit

𝐱 \in 𝑊^{⟂}

⟨ {Pr}_{𝑊} (𝐯), 𝐱 ⟩ = 0

, so

| ⟨ 𝐯, 𝐱 ⟩ | =

| ⟨ 𝐯 - {Pr}_{𝑊} (𝐯), 𝐱 ⟩ | \leq

‖ 𝐯 -

{Pr}_{𝑊} (𝐯) ‖

by Cauchy–Schwarz. Equality holds for

𝐱 =

(𝐯 - {Pr}_{𝑊} (𝐯)) / dist (𝐯, 𝑊)

, which is a unit vector in

𝑊^{⟂}

. (b) The maximum is

dist (𝑡^{3}, 𝑊) =

\sqrt{8 / 175}

, at

𝑔 =

(𝑡^{3} - 3 𝑡 / 5) / \sqrt{8 / 175}

(a) Let $𝐫 = 𝐯 - {Pr}_{𝑊} (𝐯)$ , so $𝐫 \in 𝑊^{⟂}$ and $‖ 𝐫 ‖ =$ $dist (𝐯, 𝑊) >$ $0$ because $𝐯 \notin 𝑊$ . For a unit vector $𝐱 \in 𝑊^{⟂}$ , $⟨ {Pr}_{𝑊} (𝐯), 𝐱 ⟩ = 0$ since ${Pr}_{𝑊} (𝐯) \in 𝑊$ , so by Theorem 6.2.1

| ⟨ 𝐯, 𝐱 ⟩ | = | ⟨ 𝐫, 𝐱 ⟩ | \leq ‖ 𝐫 ‖ ‖ 𝐱 ‖ = dist (𝐯, 𝑊) .

For $𝐱 = 𝐫 / ‖ 𝐫 ‖$ , which is a unit vector in $𝑊^{⟂}$ , we get $⟨ 𝐯, 𝐱 ⟩ =$ $⟨ 𝐫, 𝐫 ⟩ / ‖ 𝐫 ‖ =$ $‖ 𝐫 ‖$ . So the maximum exists and equals $dist (𝐯, 𝑊)$ . By the equality case of Cauchy–Schwarz, the maximizers are the unit vectors $𝐱 = 𝜆 𝐫 / ‖ 𝐫 ‖$ with $| 𝜆 | = 1$ .

(b) Let $𝑊$ be the space of polynomial functions of degree at most $2$ . A function orthogonal to $1, 𝑡, 𝑡^{2}$ is orthogonal to $𝑊$ (Proposition 6.3.9(c)), so we are maximizing $⟨ 𝑡^{3}, 𝑔 ⟩$ over unit vectors $𝑔 \in 𝑊^{⟂}$ . By (a) and Exercise 6.4.45, the maximum of $| ⟨ 𝑡^{3}, 𝑔 ⟩ |$ is $dist (𝑡^{3}, 𝑊) =$ $\sqrt{8 / 175}$ , attained at $𝑔 = \pm 𝑞 / ‖ 𝑞 ‖$ with $𝑞 = 𝑡^{3} - (3 / 5) 𝑡$ . Taking the plus sign makes $⟨ 𝑡^{3}, 𝑔 ⟩$ positive, so the largest value of $\int_{- 1}^{1} 𝑡^{3} 𝑔$ is $\sqrt{8 / 175} \approx 0.214$ .

So the distance from $𝐯$ to $𝑊$ can be computed in two dual ways: as a minimum over $𝑊$ , or as a maximum over unit vectors of $𝑊^{⟂}$ .

Exercise 6.4.53.standard

(a)Let $𝑈$ be a finite-dimensional subspace of $𝑉$ , and let $𝐱_{0}, 𝐲 \in 𝑉$ . Show that among the vectors of $𝐱_{0} +$ $𝑈 =$ ${𝐱_{0} + 𝐮 | 𝐮 \in 𝑈}$ , the one closest to $𝐲$ is $𝐱_{0} + {Pr}_{𝑈} (𝐲 - 𝐱_{0})$ , and that it is unique.
(b)Find the solution of smallest norm of the system $𝑥_{1} + 𝑥_{2} = 2$ , $𝑥_{2} + 𝑥_{3} = 2$ in $ℝ^{3}$ , and check that it is orthogonal to every solution of the homogeneous system.

Solution.

Uses. Theorem 6.4.33 (Best approximation), Proposition 3.1.19 (Solution sets are translates of the kernel), Corollary 6.4.10 (Projecting with an orthogonal list)

Hint 1.

‖ 𝐲 -

(𝐱_{0} + 𝐮) ‖ =

‖ (𝐲 - 𝐱_{0}) -

𝐮 ‖

. So you are approximating

𝐲 - 𝐱_{0}

by vectors of

𝑈

Hint 2. For (b), the solution set is

𝐱_{0} + ker 𝐴

(Proposition 3.1.19), and the closest point to

𝐲 = 𝟎

is wanted.

Sketch. (a) By Theorem 6.4.33 applied to

𝐲 - 𝐱_{0}

‖ (𝐲 - 𝐱_{0}) - 𝐮 ‖

is minimized exactly at

𝐮 = {Pr}_{𝑈} (𝐲 - 𝐱_{0})

. (b) With

𝐱_{0} = (2, 0, 2)

and

ker 𝐴 =

span ((1, - 1, 1))

, the answer is

𝐱_{0} -

{Pr}_{ker 𝐴} (𝐱_{0}) =

(2, 0, 2) -

(4 / 3) (1, - 1, 1) =

(2 / 3, 4 / 3, 2 / 3)

, which is orthogonal to

(1, - 1, 1)

(a) For $𝐮 \in 𝑈$ , $‖ 𝐲 -$ $(𝐱_{0} + 𝐮) ‖ =$ $‖ (𝐲 - 𝐱_{0}) -$ $𝐮 ‖$ . By Theorem 6.4.33, applied to the vector $𝐲 - 𝐱_{0}$ and the subspace $𝑈$ , this is smallest exactly when $𝐮 = {Pr}_{𝑈} (𝐲 - 𝐱_{0})$ . So $𝐱_{0} + {Pr}_{𝑈} (𝐲 - 𝐱_{0})$ is the unique closest vector.

(b) Let $𝐴 = (\begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{matrix})$ . One solution is $𝐱_{0} = (2, 0, 2)$ , and $ker 𝐴 =$ $span ((1, - 1, 1))$ : the equations say $𝑥_{1} = - 𝑥_{2} = 𝑥_{3}$ . By Proposition 3.1.19 the solution set is $𝐱_{0} + ker 𝐴$ . The solution of smallest norm is the one closest to $𝐲 = 𝟎$ , which by (a) is

\begin{aligned} 𝐱_{0} + {Pr}_{ker 𝐴} (- 𝐱_{0}) & = 𝐱_{0} - \frac{⟨ 𝐱_{0}, (1, - 1, 1) ⟩}{3} (1, - 1, 1) \\ = (2, 0, 2) - \frac{4}{3} (1, - 1, 1) \\ = (\frac{2}{3}, \frac{4}{3}, \frac{2}{3}), \end{aligned}

using Corollary 6.4.10. Check: $2 / 3 + 4 / 3 = 2$ and $4 / 3 + 2 / 3 = 2$ ; the norm is $\sqrt{24 / 9} = \sqrt{8 / 3}$ ; and $(2 / 3, 4 / 3, 2 / 3) \cdot$ $(1, - 1, 1) =$ $0$ . In general the least-norm solution is $𝐱_{0} - {Pr}_{ker 𝐴} (𝐱_{0})$ , the component of any solution in ${(ker 𝐴)}^{⟂}$ , which for real $𝐴$ is the span of the rows (Example 6.4.23(b), Theorem 6.4.26). It is the only solution in ${(ker 𝐴)}^{⟂}$ .

Exercise 6.4.54.standard In $𝐶 [- 1, 1]$ with $⟨ 𝑓, 𝑔 ⟩ =$ $\int_{- 1}^{1} 𝑓 (𝑡) 𝑔 (𝑡) d 𝑡$ , let $𝐸$ be the subspace of even functions and $𝑂$ the subspace of odd functions.

(a)Show that $𝐸^{⟂} = 𝑂$ and $𝑂^{⟂} = 𝐸$ .
(b)Let $𝑓 \in 𝐶 [- 1, 1]$ and $𝑓_{𝑒} (𝑡) =$ $(𝑓 (𝑡) + 𝑓 (- 𝑡)) / 2$ . Show that $𝑓_{𝑒}$ is the unique even function closest to $𝑓$ , although $𝐸$ is infinite-dimensional.

Solution.

Uses. Example 6.3.2 (Orthogonal vectors), Proposition 6.1.27 (Basic properties of the norm), Theorem 6.3.3 (Pythagorean theorem), Definition 6.4.22 (Orthogonal complement)

Hint 1.

𝑂 \subseteq 𝐸^{⟂}

because the product of an even and an odd function is odd. For

𝐸^{⟂} \subseteq 𝑂

, write

𝑓 \in 𝐸^{⟂}

𝑓_{𝑒} + 𝑓_{𝑜}

and pair

𝑓

with

𝑓_{𝑒}

Hint 2. For (b),

𝑓 - 𝑓_{𝑒} = 𝑓_{𝑜}

is odd, hence orthogonal to

𝐸

. Run the Pythagoras argument of Theorem 6.4.33 by hand.

Sketch. (a) Odd times even is odd, with integral

0

, so

𝑂 \subseteq 𝐸^{⟂}

. If

𝑓 \in 𝐸^{⟂}

, then

0 =

⟨ 𝑓, 𝑓_{𝑒} ⟩ =

{‖ 𝑓_{𝑒} ‖}^{2} +

⟨ 𝑓_{𝑜}, 𝑓_{𝑒} ⟩ =

{‖ 𝑓_{𝑒} ‖}^{2}

, so

𝑓 = 𝑓_{𝑜} \in 𝑂

. The same with

𝐸

and

𝑂

exchanged gives

𝑂^{⟂} = 𝐸

. (b) For

𝑔 \in 𝐸

𝑓 -

𝑔 =

𝑓_{𝑜} +

(𝑓_{𝑒} - 𝑔)

with

𝑓_{𝑜} ⟂ 𝑓_{𝑒} - 𝑔

, so

{‖ 𝑓 - 𝑔 ‖}^{2} =

{‖ 𝑓_{𝑜} ‖}^{2} +

{‖ 𝑓_{𝑒} - 𝑔 ‖}^{2} \geq

{‖ 𝑓_{𝑜} ‖}^{2}

, with equality only for

𝑔 = 𝑓_{𝑒}

Every $𝑓 \in 𝐶 [- 1, 1]$ is $𝑓 = 𝑓_{𝑒} + 𝑓_{𝑜}$ with $𝑓_{𝑒} (𝑡) =$ $(𝑓 (𝑡) + 𝑓 (- 𝑡)) / 2$ even and $𝑓_{𝑜} (𝑡) =$ $(𝑓 (𝑡) - 𝑓 (- 𝑡)) / 2$ odd, both continuous.

(a) If $𝑔$ is even and $ℎ$ is odd, then $𝑔 ℎ$ is odd, so $⟨ 𝑔, ℎ ⟩ = 0$ (Example 6.3.2(c)). This gives $𝑂 \subseteq 𝐸^{⟂}$ and $𝐸 \subseteq 𝑂^{⟂}$ . Conversely, let $𝑓 \in 𝐸^{⟂}$ . Since $𝑓_{𝑒} \in 𝐸$ ,

0 = ⟨ 𝑓, 𝑓_{𝑒} ⟩ = ⟨ 𝑓_{𝑒}, 𝑓_{𝑒} ⟩ + ⟨ 𝑓_{𝑜}, 𝑓_{𝑒} ⟩ = {‖ 𝑓_{𝑒} ‖}^{2},

so $𝑓_{𝑒} = 𝟎$ (Proposition 6.1.27) and $𝑓 = 𝑓_{𝑜} \in 𝑂$ . Similarly, if $𝑓 \in 𝑂^{⟂}$ , then $0 =$ $⟨ 𝑓, 𝑓_{𝑜} ⟩ =$ ${‖ 𝑓_{𝑜} ‖}^{2}$ , so $𝑓 = 𝑓_{𝑒} \in 𝐸$ .

(b) Let $𝑔 \in 𝐸$ . Then $𝑓 -$ $𝑔 =$ $𝑓_{𝑜} +$ $(𝑓_{𝑒} - 𝑔)$ , where $𝑓_{𝑜} \in 𝑂 = 𝐸^{⟂}$ and $𝑓_{𝑒} - 𝑔 \in 𝐸$ . By Theorem 6.3.3,

{‖ 𝑓 - 𝑔 ‖}^{2} = {‖ 𝑓_{𝑜} ‖}^{2} + {‖ 𝑓_{𝑒} - 𝑔 ‖}^{2} \geq {‖ 𝑓_{𝑜} ‖}^{2} = {‖ 𝑓 - 𝑓_{𝑒} ‖}^{2},

with equality if and only if $𝑔 = 𝑓_{𝑒}$ . So $𝑓_{𝑒}$ is the unique even function closest to $𝑓$ . The proof of Theorem 6.4.33 only needed the decomposition $𝑓 = 𝑓_{𝑒} + 𝑓_{𝑜}$ into a part in $𝐸$ and a part orthogonal to $𝐸$ . For finite-dimensional subspaces that decomposition always exists (Theorem 6.4.24); here it exists for a reason specific to $𝐸$ , and Exercise 6.4.63 shows that it need not exist in general.

Exercise 6.4.55.standard

(a)Let $𝐮_{1}, \dots, 𝐮_{𝑚}$ and $𝐮_{1}^{'}, \dots, 𝐮_{𝑚}^{'}$ be orthonormal lists in $𝑉$ with $span (𝐮_{1}, \dots, 𝐮_{𝑗}) =$ $span (𝐮_{1}^{'}, \dots, 𝐮_{𝑗}^{'})$ for every $𝑗$ . Show that $𝐮_{𝑗}^{'} = 𝜆_{𝑗} 𝐮_{𝑗}$ for scalars $𝜆_{𝑗}$ with $| 𝜆_{𝑗} | = 1$ .
(b)Let $𝐯_{1}, \dots, 𝐯_{𝑚}$ be linearly independent. Show that the output of Gram–Schmidt is the only orthonormal list $𝐮_{1}, \dots, 𝐮_{𝑚}$ such that, for every $𝑗$ , $span (𝐮_{1}, \dots, 𝐮_{𝑗}) =$ $span (𝐯_{1}, \dots, 𝐯_{𝑗})$ and $⟨ 𝐯_{𝑗}, 𝐮_{𝑗} ⟩$ is a positive real number.

Solution.

Uses. Proposition 6.3.18 (Coordinates in an orthonormal basis), Theorem 6.4.15 (Gram–Schmidt is correct), Proposition 6.1.4 (Sesquilinearity), Proposition 6.1.27 (Basic properties of the norm)

Techniques. Take an inner product to isolate a coefficient (Technique 6.3.12)

Hint 1.

𝐮_{𝑗}^{'} \in

span (𝐮_{1}, \dots, 𝐮_{𝑗})

, so expand it with Proposition 6.3.18(a). Which coefficients vanish?

Hint 2. For

𝑖 < 𝑗

𝐮_{𝑖} \in

span (𝐮_{1}^{'}, \dots, 𝐮_{𝑗 - 1}^{'})

, which is orthogonal to

𝐮_{𝑗}^{'}

Hint 3. For (b), compare an arbitrary such list with the Gram–Schmidt output using (a), and use

⟨ 𝐯_{𝑗}, 𝜆 𝐮_{𝑗} ⟩ =

𝜆 ⟨ 𝐯_{𝑗}, 𝐮_{𝑗} ⟩

Sketch. (a)

𝐮_{𝑗}^{'} =

\sum_{𝑖 \leq 𝑗} ⟨ 𝐮_{𝑗}^{'}, 𝐮_{𝑖} ⟩ 𝐮_{𝑖}

, and for

𝑖 < 𝑗

𝐮_{𝑖} \in

span (𝐮_{1}^{'}, \dots, 𝐮_{𝑗 - 1}^{'})

, which is orthogonal to

𝐮_{𝑗}^{'}

. So

𝐮_{𝑗}^{'} = 𝜆_{𝑗} 𝐮_{𝑗}

, and

| 𝜆_{𝑗} | = ‖ 𝐮_{𝑗}^{'} ‖ = 1

. (b) By Theorem 6.4.15(d) the output satisfies the conditions. For another such list, (a) gives

𝐮_{𝑗}^{'} = 𝜆_{𝑗} 𝐮_{𝑗}

, and

⟨ 𝐯_{𝑗}, 𝐮_{𝑗}^{'} ⟩ =

𝜆_{𝑗} ⟨ 𝐯_{𝑗}, 𝐮_{𝑗} ⟩

with both inner products positive, so

𝜆_{𝑗} > 0

and

| 𝜆_{𝑗} | = 1

force

𝜆_{𝑗} = 1

(a) Fix $𝑗$ . Since $𝐮_{𝑗}^{'} \in$ $span (𝐮_{1}^{'}, \dots, 𝐮_{𝑗}^{'}) =$ $span (𝐮_{1}, \dots, 𝐮_{𝑗})$ , Proposition 6.3.18(a) gives

𝐮_{𝑗}^{'} = \sum_{𝑖 = 1}^{𝑗} ⟨ 𝐮_{𝑗}^{'}, 𝐮_{𝑖} ⟩ 𝐮_{𝑖} .

For $𝑖 < 𝑗$ , $𝐮_{𝑖} \in$ $span (𝐮_{1}, \dots, 𝐮_{𝑗 - 1}) =$ $span (𝐮_{1}^{'}, \dots, 𝐮_{𝑗 - 1}^{'})$ , and $𝐮_{𝑗}^{'}$ is orthogonal to each of $𝐮_{1}^{'}, \dots, 𝐮_{𝑗 - 1}^{'}$ , hence to their span (Proposition 6.3.9(c)). So $⟨ 𝐮_{𝑗}^{'}, 𝐮_{𝑖} ⟩ = 0$ for $𝑖 < 𝑗$ , and $𝐮_{𝑗}^{'} = 𝜆_{𝑗} 𝐮_{𝑗}$ with $𝜆_{𝑗} = ⟨ 𝐮_{𝑗}^{'}, 𝐮_{𝑗} ⟩$ . Then $1 =$ $‖ 𝐮_{𝑗}^{'} ‖ =$ $| 𝜆_{𝑗} | ‖ 𝐮_{𝑗} ‖ =$ $| 𝜆_{𝑗} |$ by Proposition 6.1.27(b).

(b) By Theorem 6.4.15(d), the output $𝐮_{1}, \dots, 𝐮_{𝑚}$ of Gram–Schmidt has both properties. Let $𝐮_{1}^{'}, \dots, 𝐮_{𝑚}^{'}$ be another orthonormal list with both properties. The two lists have the same spans $span (𝐯_{1}, \dots, 𝐯_{𝑗})$ , so by (a), $𝐮_{𝑗}^{'} = 𝜆_{𝑗} 𝐮_{𝑗}$ with $| 𝜆_{𝑗} | = 1$ . By Proposition 6.1.4,

⟨ 𝐯_{𝑗}, 𝐮_{𝑗}^{'} ⟩ = 𝜆_{𝑗} ⟨ 𝐯_{𝑗}, 𝐮_{𝑗} ⟩ .

Both inner products are positive reals, so $𝜆_{𝑗}$ is a positive real number of modulus $1$ , that is, $𝜆_{𝑗} = 1$ . Hence $𝐮_{𝑗}^{'} = 𝐮_{𝑗}$ for every $𝑗$ .

Exercise 6.4.56.standard Give

ℝ [𝑥]

the inner product

⟨ 𝑝, 𝑞 ⟩ =

\int_{- 1}^{1} 𝑝 (𝑡) 𝑞 (𝑡) d 𝑡

, and let

𝑛 \geq 1

. Among all polynomials of degree

𝑛

with leading coefficient

1

, show that exactly one has the smallest norm, namely

𝑥^{𝑛} - {Pr}_{𝑊} (𝑥^{𝑛})

with

𝑊 = {ℝ [𝑥]}_{\leq 𝑛 - 1}

, the

(𝑛 + 1)

st Gram–Schmidt residual of

1, 𝑥, 𝑥^{2}, \dots

. Find the smallest value of

\int_{- 1}^{1} {𝑝 (𝑡)}^{2} d 𝑡

for

𝑛 = 2

and

𝑛 = 3

Solution.

Uses. Theorem 6.4.33 (Best approximation), Example 6.4.19 (Legendre polynomials), Exercise 6.3.49

Hint 1. The polynomials of degree

𝑛

with leading coefficient

1

are exactly the

𝑥^{𝑛} - 𝑞

with

𝑞 \in {ℝ [𝑥]}_{\leq 𝑛 - 1}

Hint 2. Minimizing

‖ 𝑥^{𝑛} - 𝑞 ‖

over

𝑞 \in 𝑊

is a best-approximation problem.

Sketch. Such polynomials are

𝑥^{𝑛} - 𝑞

with

𝑞 \in 𝑊

, and

‖ 𝑥^{𝑛} - 𝑞 ‖

is minimized exactly at

𝑞 = {Pr}_{𝑊} (𝑥^{𝑛})

. By Theorem 6.4.15(d),

𝑊

is the span of the first

𝑛

Gram–Schmidt outputs, so

𝑥^{𝑛} - {Pr}_{𝑊} (𝑥^{𝑛})

is the next residual. For

𝑛 = 2, 3

these are

𝑥^{2} - 1 / 3

and

𝑥^{3} - (3 / 5) 𝑥

, with squared norms

8 / 45

and

8 / 175

A polynomial of degree $𝑛$ with leading coefficient $1$ is $𝑥^{𝑛} - 𝑞$ with $𝑞 \in 𝑊 = {ℝ [𝑥]}_{\leq 𝑛 - 1}$ , and every such difference is one. The space $𝑊$ is finite-dimensional, so by Theorem 6.4.33, $‖ 𝑥^{𝑛} - 𝑞 ‖$ is smallest for exactly one $𝑞 \in 𝑊$ , namely $𝑞 = {Pr}_{𝑊} (𝑥^{𝑛})$ . When Gram–Schmidt is run on $1, 𝑥, 𝑥^{2}, \dots$ , the first $𝑛$ outputs span $span (1, \dots, 𝑥^{𝑛 - 1}) =$ $𝑊$ (Theorem 6.4.15(d)), so the next residual is exactly $𝑥^{𝑛} - {Pr}_{𝑊} (𝑥^{𝑛})$ .

By Example 6.4.19, for $𝑛 = 2$ the minimizer is $𝑥^{2} - 1 / 3$ , with ${‖ 𝑥^{2} - 1 / 3 ‖}^{2} = 8 / 45$ (Example 6.3.17), and for $𝑛 = 3$ it is $𝑥^{3} - (3 / 5) 𝑥$ , with squared norm $8 / 175$ (Exercise 6.3.49). So among all monic quadratics, $𝑥^{2} - 1 / 3$ is the smallest on $[- 1, 1]$ in the mean-square sense.

Exercise 6.4.57.hard Let

𝑉

be finite-dimensional and let

𝑃 \in L (𝑉)

satisfy

𝑃^{2} = 𝑃

. Show that the following are equivalent:

(i) $𝑃$ is an orthogonal projection, that is, $𝑃 = {Pr}_{im 𝑃}$ ;
(ii)every vector of $ker 𝑃$ is orthogonal to every vector of $im 𝑃$ ;
(iii) $‖ 𝑃 𝐯 ‖ \leq ‖ 𝐯 ‖$ for every $𝐯 \in 𝑉$ .

Solution.

Uses. Proposition 6.4.29 (The orthogonal projection as a linear map), Proposition 6.4.4 (Properties of ${Pr}_{𝒪︀}$ ), Theorem 6.4.6 (The projection is characterized by orthogonality), Proposition 6.1.29 (Expanding a norm)

Techniques. Recognize a projection by its two conditions (Technique 6.4.7), Orthogonal decomposition (Technique 6.2.4), Proving TFAE (Technique 2.7.1)

Hint 1. (i)

\Rightarrow

(iii) is Bessel. For (ii)

\Rightarrow

(i), check the two conditions of Technique 6.4.7 for

𝑃 𝐯

; note

𝐯 - 𝑃 𝐯 \in ker 𝑃

Hint 2. For (iii)

\Rightarrow

(ii), take

𝐮 \in im 𝑃

and

𝐰 \in ker 𝑃

. Then

𝑃 𝐮 = 𝐮

, so

𝑃 (𝐮 + 𝜆 𝐰) = 𝐮

for every scalar

𝜆

, and (iii) gives

‖ 𝐮 ‖ \leq ‖ 𝐮 + 𝜆 𝐰 ‖

Hint 3. Choose

𝜆

to make

𝐮 + 𝜆 𝐰

the part of

𝐮

orthogonal to

𝐰

, as in Technique 6.2.4.

Sketch. (i)

\Rightarrow

(iii): Proposition 6.4.4(e). (iii)

\Rightarrow

(ii): for

𝐮 \in im 𝑃

𝐰 \in ker 𝑃

𝐰 \neq 𝟎

, and

𝜆 = - ⟨ 𝐮, 𝐰 ⟩ / {‖ 𝐰 ‖}^{2}

, we get

{‖ 𝐮 ‖}^{2} =

{‖ 𝑃 (𝐮 + 𝜆 𝐰) ‖}^{2} \leq

{‖ 𝐮 + 𝜆 𝐰 ‖}^{2} =

{‖ 𝐮 ‖}^{2} -

{| ⟨ 𝐮, 𝐰 ⟩ |}^{2} / {‖ 𝐰 ‖}^{2}

, so

⟨ 𝐮, 𝐰 ⟩ = 0

. (ii)

\Rightarrow

(i):

𝑃 𝐯 \in im 𝑃

and

𝐯 -

𝑃 𝐯 \in

ker 𝑃 \subseteq

{(im 𝑃)}^{⟂}

, so

𝑃 𝐯 = {Pr}_{im 𝑃} (𝐯)

We prove (i) $\Rightarrow$ (iii) $\Rightarrow$ (ii) $\Rightarrow$ (i).

(i) $\Rightarrow$ (iii). This is Proposition 6.4.4(e), applied to an orthonormal basis of $im 𝑃$ .

(iii) $\Rightarrow$ (ii). Let $𝐮 \in im 𝑃$ and $𝐰 \in ker 𝑃$ ; we may assume $𝐰 \neq 𝟎$ . Write $𝐮 = 𝑃 𝐱$ ; then $𝑃 𝐮 =$ $𝑃^{2} 𝐱 =$ $𝑃 𝐱 =$ $𝐮$ . So for every scalar $𝜆$ , $𝑃 (𝐮 + 𝜆 𝐰) =$ $𝐮 +$ $𝜆 𝟎 =$ $𝐮$ , and (iii) gives $‖ 𝐮 ‖ \leq ‖ 𝐮 + 𝜆 𝐰 ‖$ . Take $𝜆 = - ⟨ 𝐮, 𝐰 ⟩ / {‖ 𝐰 ‖}^{2}$ . By Proposition 6.1.29,

\begin{aligned} {‖ 𝐮 + 𝜆 𝐰 ‖}^{2} & = {‖ 𝐮 ‖}^{2} + 2 Re (𝜆 ⟨ 𝐮, 𝐰 ⟩) + {| 𝜆 |}^{2} {‖ 𝐰 ‖}^{2} \\ = {‖ 𝐮 ‖}^{2} - 2 \frac{{| ⟨ 𝐮, 𝐰 ⟩ |}^{2}}{{‖ 𝐰 ‖}^{2}} + \frac{{| ⟨ 𝐮, 𝐰 ⟩ |}^{2}}{{‖ 𝐰 ‖}^{2}} \\ = {‖ 𝐮 ‖}^{2} - \frac{{| ⟨ 𝐮, 𝐰 ⟩ |}^{2}}{{‖ 𝐰 ‖}^{2}} . \end{aligned}

Combined with ${‖ 𝐮 ‖}^{2} \leq {‖ 𝐮 + 𝜆 𝐰 ‖}^{2}$ , this gives ${| ⟨ 𝐮, 𝐰 ⟩ |}^{2} \leq 0$ , so $⟨ 𝐮, 𝐰 ⟩ = 0$ .

(ii) $\Rightarrow$ (i). Let $𝑊 = im 𝑃$ , which is finite-dimensional. For $𝐯 \in 𝑉$ , $𝑃 𝐯 \in 𝑊$ , and $𝑃 (𝐯 - 𝑃 𝐯) =$ $𝑃 𝐯 -$ $𝑃^{2} 𝐯 =$ $𝟎$ , so $𝐯 - 𝑃 𝐯 \in ker 𝑃$ . By (ii), $𝐯 - 𝑃 𝐯 \in 𝑊^{⟂}$ . By Theorem 6.4.6, $𝑃 𝐯 = {Pr}_{𝑊} (𝐯)$ .

So an idempotent operator fails to be an orthogonal projection exactly when it stretches some vector, as the map in Exercise 6.4.48(e) does.

Exercise 6.4.58.hard Let

𝑉

be finite-dimensional, let

𝑈

and

𝑊

be subspaces, and let

𝑃 = {Pr}_{𝑈}

and

𝑄 = {Pr}_{𝑊}

. Show that

𝑃 𝑄

is an orthogonal projection if and only if

𝑃 𝑄 = 𝑄 𝑃

, and that in this case

𝑃 𝑄 = {Pr}_{𝑈 \cap 𝑊}

Solution.

Uses. Proposition 6.4.30 (Recognizing orthogonal projections), Proposition 6.4.29 (The orthogonal projection as a linear map), Proposition 6.1.37 (Inner products distinguish vectors)

Techniques. Recognize a projection by its two conditions (Technique 6.4.7)

Hint 1. Both directions go through Proposition 6.4.30. Compute

⟨ 𝑃 𝑄 𝐯, 𝐱 ⟩

by moving

𝑃

and then

𝑄

to the other slot.

Hint 2. You get

⟨ 𝑃 𝑄 𝐯, 𝐱 ⟩ =

⟨ 𝐯, 𝑄 𝑃 𝐱 ⟩

. Compare this with the symmetry condition for

𝑃 𝑄

Hint 3. For the image:

im 𝑃 𝑄 \subseteq 𝑈

always, and

𝑃 𝑄 = 𝑄 𝑃

puts it inside

𝑊

too. Conversely,

𝑃 𝑄 𝐳 = 𝐳

for

𝐳 \in 𝑈 \cap 𝑊

Sketch. By Proposition 6.4.29(c),

⟨ 𝑃 𝑄 𝐯, 𝐱 ⟩ =

⟨ 𝑄 𝐯, 𝑃 𝐱 ⟩ =

⟨ 𝐯, 𝑄 𝑃 𝐱 ⟩

. If

𝑃 𝑄 = 𝑄 𝑃

, then

{(𝑃 𝑄)}^{2} =

𝑃^{2} 𝑄^{2} =

𝑃 𝑄

and

⟨ 𝑃 𝑄 𝐯, 𝐱 ⟩ =

⟨ 𝐯, 𝑃 𝑄 𝐱 ⟩

, so

𝑃 𝑄

is an orthogonal projection onto

im 𝑃 𝑄 = 𝑈 \cap 𝑊

. Conversely, if

𝑃 𝑄

is an orthogonal projection, its symmetry gives

⟨ 𝐯, 𝑃 𝑄 𝐱 ⟩ =

⟨ 𝐯, 𝑄 𝑃 𝐱 ⟩

for all

𝐯

, so

𝑃 𝑄 = 𝑄 𝑃

For all $𝐯, 𝐱 \in 𝑉$ , Proposition 6.4.29(c), applied first to $𝑃$ and then to $𝑄$ , gives

⟨ 𝑃 𝑄 𝐯, 𝐱 ⟩ = ⟨ 𝑄 𝐯, 𝑃 𝐱 ⟩ = ⟨ 𝐯, 𝑄 𝑃 𝐱 ⟩ .

(6.4.3)

Suppose $𝑃 𝑄 = 𝑄 𝑃$ . Then ${(𝑃 𝑄)}^{2} =$ $𝑃 𝑄 𝑃 𝑄 =$ $𝑃 𝑃 𝑄 𝑄 =$ $𝑃^{2} 𝑄^{2} =$ $𝑃 𝑄$ by Proposition 6.4.29(b), and by (6.4.3), $⟨ 𝑃 𝑄 𝐯, 𝐱 ⟩ =$ $⟨ 𝐯, 𝑄 𝑃 𝐱 ⟩ =$ $⟨ 𝐯, 𝑃 𝑄 𝐱 ⟩$ . By Proposition 6.4.30, $𝑃 𝑄 = {Pr}_{im 𝑃 𝑄}$ . Its image lies in $im 𝑃 = 𝑈$ , and since $𝑃 𝑄 = 𝑄 𝑃$ also in $im 𝑄 = 𝑊$ . Conversely, if $𝐳 \in 𝑈 \cap 𝑊$ , then $𝑃 𝑄 𝐳 = 𝑃 𝐳 = 𝐳$ , so $𝐳 \in im 𝑃 𝑄$ . Hence $im 𝑃 𝑄 = 𝑈 \cap 𝑊$ and $𝑃 𝑄 = {Pr}_{𝑈 \cap 𝑊}$ .

Conversely, suppose $𝑃 𝑄$ is an orthogonal projection. By Proposition 6.4.30, $⟨ 𝑃 𝑄 𝐯, 𝐱 ⟩ =$ $⟨ 𝐯, 𝑃 𝑄 𝐱 ⟩$ for all $𝐯, 𝐱$ , and comparing with (6.4.3) gives $⟨ 𝐯, 𝑃 𝑄 𝐱 - 𝑄 𝑃 𝐱 ⟩ =$ $0$ for all $𝐯$ . Taking $𝐯 = 𝑃 𝑄 𝐱 - 𝑄 𝑃 𝐱$ shows that this vector has norm $0$ , so $𝑃 𝑄 𝐱 = 𝑄 𝑃 𝐱$ for every $𝐱$ .

Exercise 6.4.48(c) gives two subspaces for which $𝑃 𝑄$ is not an orthogonal projection. The commuting case includes $𝑈 \subseteq 𝑊$ , where $𝑃 𝑄 = 𝑄 𝑃 = 𝑃$ , and $𝑈 ⟂ 𝑊$ , where $𝑃 𝑄 = 𝑄 𝑃 = 0$ (Exercise 6.4.49).

Exercise 6.4.59.hard Let $𝐯_{1}, \dots, 𝐯_{𝑚}$ be linearly independent in $𝑉$ , with Gram matrix $𝐺$ (Definition 6.3.28). Run Gram–Schmidt, with residuals $𝐟_{𝑗}$ and output $𝐮_{𝑗}$ , and let $𝑅 \in 𝔽^{𝑚 \times 𝑚}$ have entries $𝑟_{𝑖 𝑗} =$ $⟨ 𝐯_{𝑗}, 𝐮_{𝑖} ⟩$ .

(a)Show that $𝑅$ is upper triangular with diagonal entries $‖ 𝐟_{1} ‖, \dots, ‖ 𝐟_{𝑚} ‖$ , and that $𝐺 = 𝑅^{*} 𝑅$ .
(b)Deduce that $det 𝐺 =$ ${‖ 𝐟_{1} ‖}^{2} \dots {‖ 𝐟_{𝑚} ‖}^{2}$ , and that ${dist (𝐯_{𝑚}, span (𝐯_{1}, \dots, 𝐯_{𝑚 - 1}))}^{2} =$ $det 𝐺_{𝑚} / det 𝐺_{𝑚 - 1}$ , where $𝐺_{𝑗}$ is the Gram matrix of $𝐯_{1}, \dots, 𝐯_{𝑗}$ and $det 𝐺_{0} = 1$ .
(c)(Hadamard’s inequality.) Show that $det 𝐺 \leq$ ${‖ 𝐯_{1} ‖}^{2} \dots {‖ 𝐯_{𝑚} ‖}^{2}$ , with equality if and only if the list is orthogonal. Deduce that $| det 𝐴 | \leq$ $‖ 𝐚_{1} ‖ \dots ‖ 𝐚_{𝑛} ‖$ for every $𝐴 \in 𝔽^{𝑛 \times 𝑛}$ with columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ .

Solution.

Uses. Theorem 6.4.15 (Gram–Schmidt is correct), Theorem 6.3.22 (Parseval’s identity), Proposition 5.3.15 (Triangular matrices), Theorem 5.4.10 (Multiplicativity), Exercise 6.3.57, Technique 6.4.5 (Projections shrink norms), Theorem 6.3.29 (Orthonormal columns), Theorem 5.4.7 (Invertibility and the determinant), Proposition 6.4.29 (The orthogonal projection as a linear map)

Techniques. Gram matrices (Technique 6.3.31)

Hint 1. For

𝑖 > 𝑗

𝐯_{𝑗} \in

span (𝐮_{1}, \dots, 𝐮_{𝑗})

is orthogonal to

𝐮_{𝑖}

. For the product,

{(𝑅^{*} 𝑅)}_{𝑖 𝑗} =

\sum_{𝑙} 𝑟_{𝑙 𝑖} 𝑟_{𝑙 𝑗}

; recognize Parseval’s identity in

span (𝐮_{1}, \dots, 𝐮_{𝑚})

Hint 2. For (b), take determinants:

det 𝑅^{*} = det 𝑅

. Gram–Schmidt on

𝐯_{1}, \dots, 𝐯_{𝑗}

produces the same first

𝑗

residuals.

Hint 3. For (c),

𝐟_{𝑗} =

𝐯_{𝑗} -

Pr (𝐯_{𝑗})

, and projections shrink norms.

Sketch. (a)

𝑟_{𝑖 𝑗} = 0

for

𝑖 > 𝑗

since

𝐯_{𝑗} ⟂ 𝐮_{𝑖}

, and

𝑟_{𝑗 𝑗} = ‖ 𝐟_{𝑗} ‖

by Theorem 6.4.15(d). By Parseval in the span of the

𝐮

’s,

{(𝑅^{*} 𝑅)}_{𝑖 𝑗} =

\sum_{𝑙} ⟨ 𝐯_{𝑗}, 𝐮_{𝑙} ⟩ ⟨ 𝐯_{𝑖}, 𝐮_{𝑙} ⟩ =

⟨ 𝐯_{𝑗}, 𝐯_{𝑖} ⟩ =

𝑔_{𝑖 𝑗}

. (b)

det 𝐺 =

{| det 𝑅 |}^{2} =

\prod_{𝑗} {‖ 𝐟_{𝑗} ‖}^{2}

; the ratio of consecutive Gram determinants is

{‖ 𝐟_{𝑚} ‖}^{2}

, the squared distance. (c)

‖ 𝐟_{𝑗} ‖ \leq ‖ 𝐯_{𝑗} ‖

with equality iff

𝐯_{𝑗} ⟂ 𝐯_{1}, \dots, 𝐯_{𝑗 - 1}

. For

𝐴

with independent columns,

𝐺 = 𝐴^{*} 𝐴

and

det 𝐺 = {| det 𝐴 |}^{2}

(a) Let $𝑈 =$ $span (𝐮_{1}, \dots, 𝐮_{𝑚}) =$ $span (𝐯_{1}, \dots, 𝐯_{𝑚})$ . For $𝑖 > 𝑗$ , $𝐯_{𝑗} \in$ $span (𝐮_{1}, \dots, 𝐮_{𝑗})$ (Theorem 6.4.15(d)), which is orthogonal to $𝐮_{𝑖}$ , so $𝑟_{𝑖 𝑗} = 0$ : $𝑅$ is upper triangular. Also $𝑟_{𝑗 𝑗} =$ $⟨ 𝐯_{𝑗}, 𝐮_{𝑗} ⟩ =$ $‖ 𝐟_{𝑗} ‖$ by Theorem 6.4.15(d). Note that $𝑟_{𝑙 𝑖} =$ $⟨ 𝐯_{𝑖}, 𝐮_{𝑙} ⟩$ for all $𝑙$ and $𝑖$ . Since $𝐮_{1}, \dots, 𝐮_{𝑚}$ is an orthonormal basis of the inner product space $𝑈$ , which contains every $𝐯_{𝑖}$ , Theorem 6.3.22(a) gives

{(𝑅^{*} 𝑅)}_{𝑖 𝑗} = \sum_{𝑙 = 1}^{𝑚} 𝑟_{𝑙 𝑖} 𝑟_{𝑙 𝑗} = \sum_{𝑙 = 1}^{𝑚} ⟨ 𝐯_{𝑗}, 𝐮_{𝑙} ⟩ ⟨ 𝐯_{𝑖}, 𝐮_{𝑙} ⟩ = ⟨ 𝐯_{𝑗}, 𝐯_{𝑖} ⟩ = 𝑔_{𝑖 𝑗} .

(b) By Theorem 5.4.10 and Exercise 6.3.57(a), $det 𝐺 =$ $det (𝑅^{*}) det 𝑅 =$ $det 𝑅 det 𝑅 =$ ${| det 𝑅 |}^{2}$ , and by Proposition 5.3.15, $det 𝑅 =$ $𝑟_{11} \dots 𝑟_{𝑚 𝑚} =$ $‖ 𝐟_{1} ‖ \dots ‖ 𝐟_{𝑚} ‖$ . So $det 𝐺 = \prod_{𝑗} {‖ 𝐟_{𝑗} ‖}^{2}$ . Gram–Schmidt processes the list in order, so running it on $𝐯_{1}, \dots, 𝐯_{𝑗}$ produces the residuals $𝐟_{1}, \dots, 𝐟_{𝑗}$ , and $det 𝐺_{𝑗} =$ $\prod_{𝑖 \leq 𝑗} {‖ 𝐟_{𝑖} ‖}^{2}$ . Hence $det 𝐺_{𝑚} / det 𝐺_{𝑚 - 1} =$ ${‖ 𝐟_{𝑚} ‖}^{2}$ . Finally $𝐟_{𝑚} =$ $𝐯_{𝑚} -$ ${Pr}_{𝑋} (𝐯_{𝑚})$ with $𝑋 =$ $span (𝐮_{1}, \dots, 𝐮_{𝑚 - 1}) =$ $span (𝐯_{1}, \dots, 𝐯_{𝑚 - 1})$ , so $‖ 𝐟_{𝑚} ‖ =$ $dist (𝐯_{𝑚}, 𝑋)$ by Theorem 6.4.33.

(c) Write $𝑋_{𝑗} =$ $span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})$ , so $𝐟_{𝑗} =$ $𝐯_{𝑗} -$ ${Pr}_{𝑋_{𝑗}} (𝐯_{𝑗})$ . By Technique 6.4.5, $‖ 𝐟_{𝑗} ‖ \leq ‖ 𝐯_{𝑗} ‖$ , with equality if and only if ${Pr}_{𝑋_{𝑗}} (𝐯_{𝑗}) = 𝟎$ , that is (Proposition 6.4.29(a)), if and only if $𝐯_{𝑗} ⟂ 𝑋_{𝑗}$ . Multiplying these inequalities between nonnegative numbers, $det 𝐺 \leq \prod_{𝑗} {‖ 𝐯_{𝑗} ‖}^{2}$ , with equality if and only if $𝐯_{𝑗} ⟂ 𝐯_{𝑖}$ for all $𝑖 < 𝑗$ , that is, if and only if the list is orthogonal.

For $𝐴 \in 𝔽^{𝑛 \times 𝑛}$ : if its columns are dependent, then $𝐴$ is not invertible and $det 𝐴 = 0$ (Theorem 5.4.7), and there is nothing to prove. Otherwise, by Theorem 6.3.29, $𝐴^{*} 𝐴$ is the Gram matrix $𝐺$ of the columns, so ${| det 𝐴 |}^{2} =$ $det 𝐴 det 𝐴 =$ $det (𝐴^{*} 𝐴) =$ $det 𝐺 \leq$ $\prod_{𝑗} {‖ 𝐚_{𝑗} ‖}^{2}$ . Geometrically: the volume of a box is at most the product of its side lengths, with equality only for a rectangular box.

Exercise 6.4.60.hard Let $𝑉$ be finite-dimensional, and let $𝑊_{1}, \dots, 𝑊_{𝑚}$ be subspaces of $𝑉$ with

{Pr}_{𝑊_{1}} + \dots + {Pr}_{𝑊_{𝑚}} = {id}_{𝑉} .

Show that every vector of $𝑊_{𝑖}$ is orthogonal to every vector of $𝑊_{𝑗}$ for $𝑖 \neq 𝑗$ , and that every $𝐯 \in 𝑉$ can be written in exactly one way as $𝐯 = 𝐰_{1} + \dots + 𝐰_{𝑚}$ with $𝐰_{𝑖} \in 𝑊_{𝑖}$ .

Solution.

Uses. Proposition 6.4.29 (The orthogonal projection as a linear map), Proposition 6.1.27 (Basic properties of the norm)

Techniques. A sum of nonnegative terms (Technique 6.1.9), Projections shrink norms (Technique 6.4.5)

Hint 1. Write

𝑃_{𝑖} = {Pr}_{𝑊_{𝑖}}

. For any

𝐯

, compute

{‖ 𝐯 ‖}^{2} =

⟨ 𝐯, \sum_{𝑖} 𝑃_{𝑖} 𝐯 ⟩

and rewrite each term with Proposition 6.4.29(c).

Hint 2. You get

{‖ 𝐯 ‖}^{2} =

\sum_{𝑖} {‖ 𝑃_{𝑖} 𝐯 ‖}^{2}

. Now take

𝐯 \in 𝑊_{1}

Sketch. With

𝑃_{𝑖} = {Pr}_{𝑊_{𝑖}}

{‖ 𝐯 ‖}^{2} =

\sum_{𝑖} ⟨ 𝑃_{𝑖} 𝐯, 𝐯 ⟩ =

\sum_{𝑖} {‖ 𝑃_{𝑖} 𝐯 ‖}^{2}

. For

𝐯 \in 𝑊_{𝑖}

, the

𝑖

th term is

{‖ 𝐯 ‖}^{2}

, so

𝑃_{𝑗} 𝐯 = 𝟎

for

𝑗 \neq 𝑖

, that is,

𝐯 \in ker 𝑃_{𝑗} = 𝑊_{𝑗}^{⟂}

. Existence of the decomposition:

𝐯 = \sum_{𝑖} 𝑃_{𝑖} 𝐯

. Uniqueness: apply

𝑃_{𝑖}

\sum_{𝑗} 𝐰_{𝑗}

, which kills

𝐰_{𝑗}

for

𝑗 \neq 𝑖

and fixes

𝐰_{𝑖}

Write $𝑃_{𝑖} = {Pr}_{𝑊_{𝑖}}$ . For every $𝐯 \in 𝑉$ , by the hypothesis and Proposition 6.4.29(c),

\begin{aligned} {‖ 𝐯 ‖}^{2} & = ⟨ \sum_{𝑖 = 1}^{𝑚} 𝑃_{𝑖} 𝐯, 𝐯 ⟩ = \sum_{𝑖 = 1}^{𝑚} ⟨ 𝑃_{𝑖} 𝐯, 𝐯 ⟩ \\ = \sum_{𝑖 = 1}^{𝑚} ⟨ 𝑃_{𝑖} 𝐯, 𝑃_{𝑖} 𝐯 ⟩ = \sum_{𝑖 = 1}^{𝑚} {‖ 𝑃_{𝑖} 𝐯 ‖}^{2} . \end{aligned}

Now let $𝐯 \in 𝑊_{𝑖}$ . Then $𝑃_{𝑖} 𝐯 = 𝐯$ , so the identity reads ${‖ 𝐯 ‖}^{2} =$ ${‖ 𝐯 ‖}^{2} +$ $\sum_{𝑗 \neq 𝑖} {‖ 𝑃_{𝑗} 𝐯 ‖}^{2}$ . A sum of nonnegative terms is $0$ only if each term is, so $𝑃_{𝑗} 𝐯 = 𝟎$ for every $𝑗 \neq 𝑖$ , that is, $𝐯 \in ker 𝑃_{𝑗} = 𝑊_{𝑗}^{⟂}$ (Proposition 6.4.29(a)). So every vector of $𝑊_{𝑖}$ is orthogonal to every vector of $𝑊_{𝑗}$ .

For $𝐯 \in 𝑉$ , the hypothesis gives $𝐯 = 𝑃_{1} 𝐯 + \dots + 𝑃_{𝑚} 𝐯$ with $𝑃_{𝑖} 𝐯 \in 𝑊_{𝑖}$ . If also $𝐯 = 𝐰_{1} + \dots + 𝐰_{𝑚}$ with $𝐰_{𝑗} \in 𝑊_{𝑗}$ , apply $𝑃_{𝑖}$ : for $𝑗 \neq 𝑖$ , $𝐰_{𝑗} \in$ $𝑊_{𝑗} \subseteq$ $𝑊_{𝑖}^{⟂} =$ $ker 𝑃_{𝑖}$ , and $𝑃_{𝑖} 𝐰_{𝑖} = 𝐰_{𝑖}$ . So $𝑃_{𝑖} 𝐯 = 𝐰_{𝑖}$ , and the decomposition is unique.

For example, if $𝐮_{1}, \dots, 𝐮_{𝑛}$ is an orthonormal basis of $𝑉$ , then ${Pr}_{span (𝐮_{1})} +$ $\dots +$ ${Pr}_{span (𝐮_{𝑛})} =$ ${id}_{𝑉}$ by Proposition 6.3.18(b). The exercise says that every decomposition of ${id}_{𝑉}$ into orthogonal projections looks like a grouping of such a basis.

Exercise 6.4.61.hard Let

𝑛 \geq 1

, and let

𝑝 \in ℝ [𝑥]

be a polynomial of degree

𝑛

with

\int_{- 1}^{1} 𝑝 (𝑡) 𝑞 (𝑡) d 𝑡 =

0

for every polynomial

𝑞

of degree less than

𝑛

. (For example, the Legendre polynomial

𝑃_{𝑛}

of Example 6.4.19.) Show that

𝑝

has

𝑛

distinct roots, all in the open interval

(- 1, 1)

Solution.

Uses. Lemma 6.1.14 (Nonnegative functions with zero integral), Proposition 7.1.22 (Counting roots), the intermediate value theorem

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Let

𝑡_{1} < \dots < 𝑡_{𝑟}

be the points of

(- 1, 1)

where

𝑝

changes sign. Build a polynomial

𝑠

of degree

𝑟

such that

𝑝 𝑠

does not change sign on

[- 1, 1]

Hint 2. Take

𝑠 (𝑡) =

(𝑡 - 𝑡_{1}) \dots (𝑡 - 𝑡_{𝑟})

. If

𝑟 < 𝑛

, then

\int_{- 1}^{1} 𝑝 𝑠 = 0

by hypothesis. Why is that impossible?

Hint 3. A continuous function that is

\geq 0

[- 1, 1]

and has integral

0

vanishes on

[- 1, 1]

(Lemma 6.1.14).

Sketch.

𝑝

has finitely many roots, so

(- 1, 1)

splits into finitely many open intervals on which

𝑝

has constant sign. Let

𝑡_{1} < \dots < 𝑡_{𝑟}

be the roots at which the sign changes, and

𝑠 = \prod_{𝑖} (𝑡 - 𝑡_{𝑖})

. Then

𝑝 𝑠

has constant sign on

[- 1, 1]

and is not identically zero there, so

\int 𝑝 𝑠 \neq 0

. If

𝑟 < 𝑛

deg 𝑠 < 𝑛

and the hypothesis gives

\int 𝑝 𝑠 = 0

, a contradiction. So

𝑝

has at least

𝑛

distinct roots in

(- 1, 1)

, and at most

𝑛

roots in all.

The polynomial $𝑝$ is nonzero, so it has at most $𝑛$ roots (Proposition 7.1.22). Let $𝑎_{1} < \dots < 𝑎_{𝑁}$ be its roots in $(- 1, 1)$ , and put $𝑎_{0} = - 1$ , $𝑎_{𝑁 + 1} = 1$ . On each open interval $(𝑎_{𝑘}, 𝑎_{𝑘 + 1})$ , $𝑝$ has no root, so by the intermediate value theorem it has constant sign there. Say that $𝑝$ changes sign at $𝑎_{𝑘}$ ( $1 \leq 𝑘 \leq 𝑁$ ) if its signs on $(𝑎_{𝑘 - 1}, 𝑎_{𝑘})$ and $(𝑎_{𝑘}, 𝑎_{𝑘 + 1})$ differ, and let $𝑡_{1} < \dots < 𝑡_{𝑟}$ be the roots at which $𝑝$ changes sign. Let

𝑠 (𝑡) = (𝑡 - 𝑡_{1}) (𝑡 - 𝑡_{2}) \dots (𝑡 - 𝑡_{𝑟})

( $𝑠 = 1$ if $𝑟 = 0$ ). Each factor $𝑡 - 𝑡_{𝑖}$ changes sign at $𝑡_{𝑖}$ and nowhere else, so $𝑠$ has constant sign on each interval $(𝑎_{𝑘}, 𝑎_{𝑘 + 1})$ and changes sign exactly at $𝑡_{1}, \dots, 𝑡_{𝑟}$ . Hence the product $𝑝 𝑠$ has constant sign on each $(𝑎_{𝑘}, 𝑎_{𝑘 + 1})$ , and at each $𝑎_{𝑘}$ either both factors change sign or neither does, so $𝑝 𝑠$ has the same sign on all of these intervals. Replacing $𝑠$ by $- 𝑠$ if necessary, $𝑝 𝑠 \geq 0$ on $[- 1, 1]$ by continuity.

Suppose $𝑟 < 𝑛$ . Then $deg 𝑠 = 𝑟 < 𝑛$ , so $\int_{- 1}^{1} 𝑝 (𝑡) 𝑠 (𝑡) d 𝑡 =$ $0$ by hypothesis. Since $𝑝 𝑠$ is continuous and nonnegative on $[- 1, 1]$ , Lemma 6.1.14 gives $𝑝 𝑠 = 0$ on $[- 1, 1]$ . But $𝑝 𝑠$ is a nonzero polynomial, with finitely many roots, a contradiction. So $𝑟 \geq 𝑛$ : $𝑝$ has at least $𝑛$ distinct roots in $(- 1, 1)$ . Since it has at most $𝑛$ roots, these are all of its roots.

The argument used only that $𝑝$ is continuous, has finitely many zeros in $[- 1, 1]$ , and is orthogonal to all polynomials of degree less than $𝑛$ . So it applies to the error $𝑒^{𝑡} - 𝑝 (𝑡)$ of Example 6.4.37 with $𝑛 = 3$ : that error has at most three zeros (see the remark after Example 6.4.37), and therefore changes sign at least three times in $(- 1, 1)$ .

Exercise 6.4.62.challenge Let

𝐯_{1}, \dots, 𝐯_{𝑚} \in ℝ^{𝑛}

satisfy

⟨ 𝐯_{𝑖}, 𝐯_{𝑗} ⟩ < 0

for all

𝑖 \neq 𝑗

. Show that

𝑚 \leq 𝑛 + 1

, and find

𝑛 + 1

such vectors in

ℝ^{𝑛}

Solution.

Uses. Corollary 6.4.25 (Dimension of the orthogonal complement), Corollary 6.4.10 (Projecting with an orthogonal list), Proposition 6.4.4 (Properties of ${Pr}_{𝒪︀}$ )

Techniques. Induction on the length of a list (Technique 1.6.9), Orthogonal decomposition (Technique 6.2.4)

Hint 1. Induct on the dimension, proving the statement for every

𝑛

-dimensional subspace of some

ℝ^{𝑁}

. Project the first

𝑚 - 1

vectors onto the hyperplane

𝐯_{𝑚}^{⟂}

Hint 2. Let

𝐰_{𝑖} =

𝐯_{𝑖} -

𝑐_{𝑖} 𝐯_{𝑚}

with

𝑐_{𝑖} =

⟨ 𝐯_{𝑖}, 𝐯_{𝑚} ⟩ / {‖ 𝐯_{𝑚} ‖}^{2} <

0

. Compute

⟨ 𝐰_{𝑖}, 𝐰_{𝑗} ⟩

for

𝑖 \neq 𝑗

Hint 3.

⟨ 𝐰_{𝑖}, 𝐰_{𝑗} ⟩ =

⟨ 𝐯_{𝑖}, 𝐯_{𝑗} ⟩ -

𝑐_{𝑖} 𝑐_{𝑗} {‖ 𝐯_{𝑚} ‖}^{2} <

0

, since

𝑐_{𝑖} 𝑐_{𝑗} > 0

. For the example, try

𝐞_{𝑖} - 𝑡 (1, \dots, 1)

and

- (1, \dots, 1)

Sketch. Prove, by induction on

𝑛

, that pairwise negative inner products allow at most

𝑛 + 1

vectors in any

𝑛

-dimensional subspace

𝑉

ℝ^{𝑁}

. For

𝑛 = 0

only

𝟎

exists and

⟨ 𝟎, 𝟎 ⟩ = 0

, so

𝑚 \leq 1

. For

𝑛 \geq 1

and

𝑚 \geq 2

, all

𝐯_{𝑖} \neq 𝟎

; project

𝐯_{1}, \dots, 𝐯_{𝑚 - 1}

onto

𝑈 = 𝐯_{𝑚}^{⟂} \cap 𝑉

, of dimension

𝑛 - 1

. The projections

𝐰_{𝑖} =

𝐯_{𝑖} -

𝑐_{𝑖} 𝐯_{𝑚}

have

⟨ 𝐰_{𝑖}, 𝐰_{𝑗} ⟩ =

⟨ 𝐯_{𝑖}, 𝐯_{𝑗} ⟩ -

𝑐_{𝑖} 𝑐_{𝑗} {‖ 𝐯_{𝑚} ‖}^{2} <

0

, so

𝑚 - 1 \leq 𝑛

. Example:

𝐞_{𝑖} - (1 / 2 𝑛) 𝐣

for

𝑖 \leq 𝑛

, and

- 𝐣

, with

𝐣 = (1, \dots, 1)

We prove, by induction on $𝑛 \geq 0$ , the following statement: if $𝑉$ is an $𝑛$ -dimensional subspace of $ℝ^{𝑁}$ (for some $𝑁$ ) and $𝐯_{1}, \dots, 𝐯_{𝑚} \in 𝑉$ satisfy $⟨ 𝐯_{𝑖}, 𝐯_{𝑗} ⟩ < 0$ for all $𝑖 \neq 𝑗$ , then $𝑚 \leq 𝑛 + 1$ . The case $𝑉 = ℝ^{𝑛}$ is the claim.

If $𝑛 = 0$ , then $𝑉 = {𝟎}$ and $⟨ 𝟎, 𝟎 ⟩ = 0$ , so there is no pair $𝑖 \neq 𝑗$ , and $𝑚 \leq 1$ .

Let $𝑛 \geq 1$ , and assume the statement for $(𝑛 - 1)$ -dimensional subspaces. If $𝑚 \leq 2$ there is nothing to prove, so let $𝑚 \geq 3$ . Every $𝐯_{𝑖}$ is nonzero, since $⟨ 𝐯_{𝑖}, 𝐯_{𝑗} ⟩ \neq 0$ for some $𝑗 \neq 𝑖$ . Let $𝑈 =$ ${𝐱 \in 𝑉 | ⟨ 𝐱, 𝐯_{𝑚} ⟩ = 0}$ , the orthogonal complement of $span (𝐯_{𝑚})$ inside the inner product space $𝑉$ , so $dim 𝑈 = 𝑛 - 1$ by Corollary 6.4.25. For $𝑖 < 𝑚$ let

𝑐_{𝑖} = \frac{⟨ 𝐯_{𝑖}, 𝐯_{𝑚} ⟩}{{‖ 𝐯_{𝑚} ‖}^{2}} < 0, 𝐰_{𝑖} = 𝐯_{𝑖} - 𝑐_{𝑖} 𝐯_{𝑚} .

By Corollary 6.4.10 and Proposition 6.4.4(b), $𝐰_{𝑖} =$ $𝐯_{𝑖} -$ ${Pr}_{span (𝐯_{𝑚})} (𝐯_{𝑖}) \in$ $𝑈$ . For $𝑖 \neq 𝑗$ , both less than $𝑚$ ,

\begin{aligned} ⟨ 𝐰_{𝑖}, 𝐰_{𝑗} ⟩ & = ⟨ 𝐯_{𝑖}, 𝐯_{𝑗} ⟩ - 𝑐_{𝑗} ⟨ 𝐯_{𝑖}, 𝐯_{𝑚} ⟩ - 𝑐_{𝑖} ⟨ 𝐯_{𝑚}, 𝐯_{𝑗} ⟩ + 𝑐_{𝑖} 𝑐_{𝑗} {‖ 𝐯_{𝑚} ‖}^{2} \\ = ⟨ 𝐯_{𝑖}, 𝐯_{𝑗} ⟩ - 𝑐_{𝑖} 𝑐_{𝑗} {‖ 𝐯_{𝑚} ‖}^{2} - 𝑐_{𝑖} 𝑐_{𝑗} {‖ 𝐯_{𝑚} ‖}^{2} + 𝑐_{𝑖} 𝑐_{𝑗} {‖ 𝐯_{𝑚} ‖}^{2} \\ = ⟨ 𝐯_{𝑖}, 𝐯_{𝑗} ⟩ - 𝑐_{𝑖} 𝑐_{𝑗} {‖ 𝐯_{𝑚} ‖}^{2} < 0, \end{aligned}

because $⟨ 𝐯_{𝑖}, 𝐯_{𝑗} ⟩ < 0$ and $𝑐_{𝑖} 𝑐_{𝑗} > 0$ . So $𝐰_{1}, \dots, 𝐰_{𝑚 - 1}$ are vectors in the $(𝑛 - 1)$ -dimensional space $𝑈$ with pairwise negative inner products, and the induction hypothesis gives $𝑚 - 1 \leq 𝑛$ , that is, $𝑚 \leq 𝑛 + 1$ .

For an example with $𝑚 = 𝑛 + 1$ , let $𝐣 = (1, \dots, 1) \in ℝ^{𝑛}$ , $𝐯_{𝑖} =$ $𝐞_{𝑖} -$ $(1 / 2 𝑛) 𝐣$ for $𝑖 = 1, \dots, 𝑛$ , and $𝐯_{𝑛 + 1} = - 𝐣$ . For $𝑖 \neq 𝑘 \leq 𝑛$ ,

\begin{aligned} ⟨ 𝐯_{𝑖}, 𝐯_{𝑘} ⟩ & = 0 - \frac{1}{2 𝑛} - \frac{1}{2 𝑛} + \frac{𝑛}{4 𝑛^{2}} = - \frac{3}{4 𝑛} < 0, \\ ⟨ 𝐯_{𝑖}, 𝐯_{𝑛 + 1} ⟩ & = - 1 + \frac{𝑛}{2 𝑛} = - \frac{1}{2} < 0 . \end{aligned}

The proof is an induction on dimension in which projecting onto a hyperplane preserves the hypothesis. The triangularization theorems of Section 7.5 are proved by the same pattern (Technique 7.5.12).

Exercise 6.4.63.hardBeyond 21-242 Give $ℝ [𝑥]$ the inner product $⟨ 𝑝, 𝑞 ⟩ =$ $\sum_{𝑘 \geq 0} 𝑝_{𝑘} 𝑞_{𝑘}$ , where $𝑝 = \sum_{𝑘} 𝑝_{𝑘} 𝑥^{𝑘}$ and $𝑞 = \sum_{𝑘} 𝑞_{𝑘} 𝑥^{𝑘}$ , and let $𝑊 =$ ${𝑝 \in ℝ [𝑥] | 𝑝 (1) = 0}$ .

(a)Show that $𝑊$ is a subspace with $𝑊 \neq ℝ [𝑥]$ , but $𝑊^{⟂} = {𝟎}$ .
(b)Deduce that $ℝ [𝑥] \neq 𝑊 \oplus 𝑊^{⟂}$ and ${(𝑊^{⟂})}^{⟂} \neq 𝑊$ .
(c)Show that no vector of $𝑊$ is closest to the constant polynomial $1$ , although ${inf}_{𝑤 \in 𝑊} ‖ 1 - 𝑤 ‖ = 0$ .

Solution.

Uses. Definition 1.2.13 (Polynomials), Definition 1.2.17 (Evaluation), Proposition 1.2.18 (Degree and evaluation versus the operations), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ), Theorem 6.4.24 (Orthogonal decomposition)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. The sum defining

⟨ 𝑝, 𝑞 ⟩

is finite.

𝑊

is the set of polynomials killed by evaluation at

1

, and

1 \notin 𝑊

Hint 2. For

𝑞 \in 𝑊^{⟂}

, test against

𝑥^{𝑘} - 𝑥^{𝑘 + 1} \in 𝑊

. What does

⟨ 𝑞, 𝑥^{𝑘} - 𝑥^{𝑘 + 1} ⟩ =

0

say about the coefficients of

𝑞

Hint 3. For (c), try

𝑤_{𝑛} =

1 -

(1 + 𝑥 + \dots + 𝑥^{𝑛}) / (𝑛 + 1)

Sketch. (a)

𝑊

is closed under the operations since evaluation respects them, and

1 \notin 𝑊

. If

𝑞 ⟂ 𝑊

, then

0 =

⟨ 𝑞, 𝑥^{𝑘} - 𝑥^{𝑘 + 1} ⟩ =

𝑞_{𝑘} -

𝑞_{𝑘 + 1}

for all

𝑘

, so all coefficients of

𝑞

are equal, and since almost all are

0

𝑞 = 0

. (b)

𝑊 + 𝑊^{⟂} = 𝑊

and

{(𝑊^{⟂})}^{⟂} = 𝑉

. (c)

𝑤_{𝑛} \in 𝑊

and

{‖ 1 - 𝑤_{𝑛} ‖}^{2} =

1 / (𝑛 + 1) \to

0

, but

‖ 1 - 𝑤 ‖ > 0

for every

𝑤 \in 𝑊

since

1 \notin 𝑊

(a) For each $𝑝$ only finitely many $𝑝_{𝑘}$ are nonzero, so the sum is finite. It is symmetric and linear in each slot, and $⟨ 𝑝, 𝑝 ⟩ =$ $\sum_{𝑘} 𝑝_{𝑘}^{2} >$ $0$ for $𝑝 \neq 0$ , so it is an inner product (it is the dot product of coefficient sequences). By Proposition 1.2.18, $(𝑎 𝑝 + 𝑏 𝑞) (1) =$ $𝑎 𝑝 (1) +$ $𝑏 𝑞 (1)$ , so $𝑊$ is a subspace, and $1 \notin 𝑊$ , so $𝑊 \neq ℝ [𝑥]$ .

Let $𝑞 \in 𝑊^{⟂}$ . For each $𝑘 \geq 0$ , the polynomial $𝑥^{𝑘} - 𝑥^{𝑘 + 1}$ vanishes at $1$ , so it lies in $𝑊$ , and

0 = ⟨ 𝑞, 𝑥^{𝑘} - 𝑥^{𝑘 + 1} ⟩ = 𝑞_{𝑘} - 𝑞_{𝑘 + 1} .

So $𝑞_{0} = 𝑞_{1} = 𝑞_{2} = \dots$ . Since $𝑞_{𝑘} = 0$ for all large $𝑘$ , every coefficient is $0$ , and $𝑞 = 0$ . Hence $𝑊^{⟂} = {𝟎}$ .

(b) $𝑊 + 𝑊^{⟂} = 𝑊 \neq ℝ [𝑥]$ , so $ℝ [𝑥]$ is not $𝑊 \oplus 𝑊^{⟂}$ . And ${(𝑊^{⟂})}^{⟂} =$ ${𝟎}^{⟂} =$ $ℝ [𝑥] \neq$ $𝑊$ (Proposition 6.3.9(d)). Both conclusions of Theorem 6.4.24 and Theorem 6.4.26 fail. The hypothesis that breaks is finite-dimensionality: $𝑊$ contains the independent list $1 -$ $𝑥,$ $𝑥 -$ $𝑥^{2},$ $𝑥^{2} -$ $𝑥^{3},$ $\dots$ , of every length, so it has no (finite) orthonormal basis, and ${Pr}_{𝑊}$ cannot be defined.

(c) Let $𝑤_{𝑛} =$ $1 -$ $(1 + 𝑥 + \dots + 𝑥^{𝑛}) / (𝑛 + 1)$ . Then $𝑤_{𝑛} (1) = 1 - 1 = 0$ , so $𝑤_{𝑛} \in 𝑊$ , and

{‖ 1 - 𝑤_{𝑛} ‖}^{2} = {‖ \frac{1 + 𝑥 + \dots + 𝑥^{𝑛}}{𝑛 + 1} ‖}^{2} = \frac{𝑛 + 1}{{(𝑛 + 1)}^{2}} = \frac{1}{𝑛 + 1} .

So ${inf}_{𝑤 \in 𝑊} ‖ 1 - 𝑤 ‖ = 0$ . But $1 \notin 𝑊$ , so $‖ 1 - 𝑤 ‖ > 0$ for every $𝑤 \in 𝑊$ . If some $𝑤 \in 𝑊$ were closest to $1$ , then $‖ 1 -$ $𝑤 ‖ \leq$ $‖ 1 -$ $𝑤_{𝑛} ‖ =$ ${(𝑛 + 1)}^{- 1 / 2}$ for every $𝑛$ , forcing $‖ 1 - 𝑤 ‖ = 0$ , which is impossible. In the spaces of Section 15.3, which are complete, closest points do exist for closed subspaces, and this kind of example disappears.

Exercise 6.4.64.routineBeyond 21-242 Let $𝐴 = (\begin{matrix} 1 & 3 \\ 2 & 3 \\ 2 & 0 \end{matrix})$ .

(a)Find the QR factorization of $𝐴$ .
(b)Use it to find ${Pr}_{im 𝐴} (𝐞_{1})$ .
(c)Check that $𝐴^{𝖳} 𝐴 = 𝑅^{𝖳} 𝑅$ .

Solution.

Uses. Theorem 6.4.38 (QR factorization), Theorem 6.4.31 (The matrix of an orthogonal projection), Algorithm 6.4.14 (Gram–Schmidt)

Hint 1. Gram–Schmidt on the columns:

‖ 𝐚_{1} ‖ = 3

, and

⟨ 𝐚_{2}, 𝐮_{1} ⟩

is an integer.

Hint 2.

𝐮_{1} = (1, 2, 2) / 3

and

𝐮_{2} = (2, 1, - 2) / 3

. For (b),

{Pr}_{im 𝐴} = 𝑄 𝑄^{𝖳}

Sketch.

𝐮_{1} = (1, 2, 2) / 3

𝑟_{11} = 3

;

𝑟_{12} = ⟨ 𝐚_{2}, 𝐮_{1} ⟩ = 3

𝐟_{2} =

(3, 3, 0) -

(1, 2, 2) =

(2, 1, - 2)

𝑟_{22} = 3

. So

𝑅 = (\begin{matrix} 3 & 3 \\ 0 & 3 \end{matrix})

. Then

{Pr}_{im 𝐴} (𝐞_{1}) =

(1 / 9) (1, 2, 2) +

(2 / 9) (2, 1, - 2) =

(5, 4, - 2) / 9

, and

𝐴^{𝖳} 𝐴 =

(\begin{matrix} 9 & 9 \\ 9 & 18 \end{matrix}) =

𝑅^{𝖳} 𝑅

(a) Let $𝐚_{1} = (1, 2, 2)$ and $𝐚_{2} = (3, 3, 0)$ . Then $‖ 𝐚_{1} ‖ = 3$ , so $𝐮_{1} = (1, 2, 2) / 3$ and $𝑟_{11} = 3$ . Next $𝑟_{12} =$ $⟨ 𝐚_{2}, 𝐮_{1} ⟩ =$ $(3 + 6 + 0) / 3 =$ $3$ , and $𝐟_{2} =$ $𝐚_{2} -$ $3 𝐮_{1} =$ $(2, 1, - 2)$ , with $𝑟_{22} = ‖ 𝐟_{2} ‖ = 3$ and $𝐮_{2} = (2, 1, - 2) / 3$ . By Theorem 6.4.38,

𝐴 = 𝑄 𝑅, 𝑄 = \frac{1}{3} (\begin{matrix} 1 & 2 \\ 2 & 1 \\ 2 & - 2 \end{matrix}), 𝑅 = (\begin{matrix} 3 & 3 \\ 0 & 3 \end{matrix}) .

(b) The columns of $𝑄$ are an orthonormal basis of $im 𝐴$ , so by Theorem 6.4.31,

\begin{aligned} {Pr}_{im 𝐴} (𝐞_{1}) & = ⟨ 𝐞_{1}, 𝐮_{1} ⟩ 𝐮_{1} + ⟨ 𝐞_{1}, 𝐮_{2} ⟩ 𝐮_{2} \\ = \frac{1}{9} (1, 2, 2) + \frac{2}{9} (2, 1, - 2) = \frac{1}{9} (5, 4, - 2) . \end{aligned}

(c) $𝐴^{𝖳} 𝐴 =$ $(\begin{matrix} 1 + 4 + 4 & 3 + 6 + 0 \\ 3 + 6 + 0 & 9 + 9 + 0 \end{matrix}) =$ $(\begin{matrix} 9 & 9 \\ 9 & 18 \end{matrix})$ and $𝑅^{𝖳} 𝑅 =$ $(\begin{matrix} 3 & 0 \\ 3 & 3 \end{matrix}) (\begin{matrix} 3 & 3 \\ 0 & 3 \end{matrix}) =$ $(\begin{matrix} 9 & 9 \\ 9 & 18 \end{matrix})$ . In general $𝐴^{*} 𝐴 =$ $𝑅^{*} 𝑄^{*} 𝑄 𝑅 =$ $𝑅^{*} 𝑅$ , which is Exercise 6.4.59(a) for the columns of $𝐴$ .

More practice

The practice bank has 38 exercises on this section’s topics.