Books
Theme
Text size
Width

[ and ] go to the previous and next page.

These problems combine the sections of Chapter 6 with each other and with earlier chapters: linear systems, dimension, affine subspaces, determinants, and traces. The first three are review prompts: state a main result, prove it without looking, and then answer a question that the text did not ask. The rest are ordered roughly by difficulty. Problems of kind “competition” are harder than anything the course expects, and two problems that go beyond the course are marked. Section 6.7 compares the techniques these problems call for.

Review: state and prove

Problem 6.1.standard
  1. (a)State the Cauchy–Schwarz inequality, including its equality case.
  2. (b)Prove it, by any of the three methods of Section 6.2.1, without looking.
  3. (c)Let 𝐱,𝐲 be nonzero vectors in an inner product space. Show that

    ‖𝐱‖𝐱‖−𝐲‖𝐲‖‖≤2‖𝐱−𝐲‖‖𝐱‖+‖𝐲‖,

    and that equality holds if and only if ‖𝐱‖=‖𝐲‖ or 𝐲 is a negative real multiple of 𝐱.

Solution.

Uses. Theorem 6.2.1 (Cauchy–Schwarz inequality), Proposition 6.1.29 (Expanding a norm), Lemma 6.2.3 (The easy half of (b)), Theorem 6.2.11 (Triangle inequality)

Techniques. Orthogonal decomposition (Technique 6.2.4), A nonnegative quadratic has nonpositive discriminant (Technique 6.2.7)

Hint 1. For (b), if 𝐲≠𝟎, write 𝐱=𝑐𝐲+𝐰 with 𝐰⟂𝐲 and expand ‖𝐱‖2.
Hint 2. For (c), write 𝑎=‖𝐱‖, 𝑏=‖𝐲‖, 𝑟=Re⟨𝐱,𝐲⟩, and express the squares of both sides through 𝑎, 𝑏, 𝑟.
Hint 3. After clearing denominators, the difference of the two sides of (c) factors as (𝑎−𝑏)2(𝑎𝑏+𝑟). Why is 𝑎𝑏+𝑟≥0?
Sketch. (b) With 𝑐=⟨𝐱,𝐲⟩/‖𝐲‖2 and 𝐰=𝐱−𝑐𝐲⟂𝐲, ‖𝐱‖2=‖𝐰‖2+|⟨𝐱,𝐲⟩|2/‖𝐲‖2. (c) The left side squared is 2(𝑎𝑏−𝑟)/(𝑎𝑏) and the right side squared is 4((𝑎−𝑏)2+2(𝑎𝑏−𝑟))/(𝑎+𝑏)2. After clearing denominators, the inequality between the squares becomes (𝑎𝑏−𝑟)(𝑎+𝑏)2≤2𝑎𝑏((𝑎−𝑏)2+2(𝑎𝑏−𝑟)), and the right side minus the left is (𝑎−𝑏)2(𝑎𝑏+𝑟)≥0, since −𝑟≤|⟨𝐱,𝐲⟩|≤𝑎𝑏 by Cauchy–Schwarz. Equality iff 𝑎=𝑏 or 𝑟=−𝑎𝑏, and the latter means −𝐲 is a positive multiple of 𝐱.

(a) For all vectors 𝐱,𝐲 in an inner product space, |⟨𝐱,𝐲⟩|≤‖𝐱‖‖𝐲‖, with equality if and only if one of 𝐱,𝐲 is a scalar multiple of the other (Theorem 6.2.1).

(b) If 𝐲=𝟎, both sides are 0 and 𝐲=0𝐱. Let 𝐲≠𝟎, 𝑐=⟨𝐱,𝐲⟩/‖𝐲‖2, and 𝐰=𝐱−𝑐𝐲. Then ⟨𝐰,𝐲⟩=⟨𝐱,𝐲⟩−𝑐‖𝐲‖2=0, so by Proposition 6.1.29 the cross term in ‖𝐰+𝑐𝐲‖2 vanishes:

‖𝐱‖2=‖𝐰‖2+|𝑐|2‖𝐲‖2=‖𝐰‖2+|⟨𝐱,𝐲⟩|2‖𝐲‖2.

Dropping ‖𝐰‖2≥0 and multiplying by ‖𝐲‖2 gives the inequality. Equality holds exactly when 𝐰=𝟎, that is, 𝐱=𝑐𝐲; the converse is Lemma 6.2.3.

(c) Let 𝑎=‖𝐱‖>0, 𝑏=‖𝐲‖>0, and 𝑟=Re⟨𝐱,𝐲⟩. By Proposition 6.1.29 with the real scalars 1/𝑎 and 1/𝑏,

‖𝐱𝑎−𝐲𝑏‖2=1−2𝑟𝑎𝑏+1=2(𝑎𝑏−𝑟)𝑎𝑏,

and ‖𝐱−𝐲‖2=𝑎2−2𝑟+𝑏2=(𝑎−𝑏)2+2(𝑎𝑏−𝑟). Both sides of the claimed inequality are nonnegative, so it is equivalent to the inequality between their squares, and after multiplying by 𝑎𝑏(𝑎+𝑏)2/2>0, to

(𝑎𝑏−𝑟)(𝑎+𝑏)2≤2𝑎𝑏((𝑎−𝑏)2+2(𝑎𝑏−𝑟)).

Since (𝑎+𝑏)2=(𝑎−𝑏)2+4𝑎𝑏, the left side is (𝑎𝑏−𝑟)(𝑎−𝑏)2+4𝑎𝑏(𝑎𝑏−𝑟), and the right side minus the left side is

2𝑎𝑏(𝑎−𝑏)2−(𝑎𝑏−𝑟)(𝑎−𝑏)2=(𝑎−𝑏)2(𝑎𝑏+𝑟).

By Cauchy–Schwarz, −𝑟≤|⟨𝐱,𝐲⟩|≤𝑎𝑏, so 𝑎𝑏+𝑟≥0, which proves the inequality.

Equality holds if and only if (𝑎−𝑏)2(𝑎𝑏+𝑟)=0, that is, 𝑎=𝑏 or 𝑟=−𝑎𝑏. If 𝑟=−𝑎𝑏, then Re⟨𝐱,−𝐲⟩=‖𝐱‖‖−𝐲‖. Since Re𝑧≤|𝑧| and Cauchy–Schwarz bounds |⟨𝐱,−𝐲⟩| by the same number, ⟨𝐱,−𝐲⟩=‖𝐱‖‖−𝐲‖, and by Theorem 6.2.11(b) one of 𝐱,−𝐲 is a nonnegative real multiple of the other. Both are nonzero, so 𝐲=−𝑠𝐱 with 𝑠>0. Conversely, if 𝐲=−𝑠𝐱 with 𝑠>0, then 𝑟=−𝑠𝑎2=−𝑎𝑏.

The inequality says that sending nonzero vectors to the unit sphere along rays moves them apart by at most 2/(‖𝐱‖+‖𝐲‖) times their distance. Its proof used only Re⟨𝐱,𝐲⟩≥−‖𝐱‖‖𝐲‖. In a general normed space the same inequality holds with 4 in place of 2 (Dunkl and Williams, 1964).

Problem 6.2.standard Let 𝑊 be a finite-dimensional subspace of an inner product space 𝑉.

  1. (a)State the orthogonal decomposition theorem and the best-approximation theorem for 𝑊.
  2. (b)Prove both, using only that 𝑊 has an orthonormal basis 𝐮1,…,𝐮𝑘 (Theorem 6.4.20) and the formula Pr𝑊(𝐯)=∑𝑗⟨𝐯,𝐮𝑗⟩𝐮𝑗.
  3. (c)On ℝ2, let ‖𝐱‖∞=max(|𝑥1|,|𝑥2|). Find all points of 𝑊=span(𝐞1) closest to 𝐞2 for this norm. Which step of your proof in (b) has no analogue for ‖⋅‖∞?

Solution.

Uses. Theorem 6.4.24 (Orthogonal decomposition), Theorem 6.4.33 (Best approximation), Proposition 6.3.9 (Properties of 𝐴⟂), Theorem 6.3.3 (Pythagorean theorem), Proposition 6.1.30 (Parallelogram law), Aside (Norms that do not come from inner products) (Norms that do not come from inner products)

Techniques. Projections shrink norms (Technique 6.4.5), Recognize a projection by its two conditions (Technique 6.4.7)

Hint 1. For existence in (b), check ⟨𝐯−Pr𝑊(𝐯),𝐮𝑗⟩=0 for each 𝑗. For uniqueness, what is 𝑊∩𝑊⟂?
Hint 2. For best approximation, write 𝐯−𝐰=(𝐯−Pr𝑊(𝐯))+(Pr𝑊(𝐯)−𝐰) and use Pythagoras. In (c), compute ‖𝐞2−𝑡𝐞1‖∞.
Sketch. (b) 𝐯−Pr𝑊(𝐯) is orthogonal to each 𝐮𝑗, hence to 𝑊; two decompositions differ by a vector of 𝑊∩𝑊⟂={𝟎}. For 𝐰∈𝑊, Pythagoras gives ‖𝐯−𝐰‖2=‖𝐯−Pr𝑊(𝐯)‖2+‖Pr𝑊(𝐯)−𝐰‖2. (c) ‖𝐞2−𝑡𝐞1‖∞=max(|𝑡|,1), so every 𝑡𝐞1 with |𝑡|≤1 is closest. The Pythagorean step fails: ‖⋅‖∞ violates the parallelogram law, so it comes from no inner product.

(a) Orthogonal decomposition (Theorem 6.4.24): every 𝐯∈𝑉 can be written in exactly one way as 𝐯=𝐰+𝐰′ with 𝐰∈𝑊 and 𝐰′∈𝑊⟂, namely with 𝐰=Pr𝑊(𝐯). Best approximation (Theorem 6.4.33): ‖𝐯−Pr𝑊(𝐯)‖≤‖𝐯−𝐰‖ for every 𝐰∈𝑊, with equality only for 𝐰=Pr𝑊(𝐯).

(b) Existence. Let 𝐩=Pr𝑊(𝐯)=∑𝑖⟨𝐯,𝐮𝑖⟩𝐮𝑖∈𝑊. For each 𝑗, since ⟨𝐮𝑖,𝐮𝑗⟩=𝛿𝑖𝑗,

⟨𝐯−𝐩,𝐮𝑗⟩=⟨𝐯,𝐮𝑗⟩−∑𝑖⟨𝐯,𝐮𝑖⟩⟨𝐮𝑖,𝐮𝑗⟩=0.

A vector orthogonal to each 𝐮𝑗 is orthogonal to their span 𝑊 (Proposition 6.3.9(c)), so 𝐯−𝐩∈𝑊⟂, and 𝐯=𝐩+(𝐯−𝐩) is a decomposition.

Uniqueness. If 𝐰1+𝐰1′=𝐰2+𝐰2′ with 𝐰𝑖∈𝑊 and 𝐰𝑖′∈𝑊⟂, then 𝐳=𝐰1−𝐰2=𝐰2′−𝐰1′ lies in 𝑊∩𝑊⟂, so ⟨𝐳,𝐳⟩=0 and 𝐳=𝟎.

Best approximation. Let 𝐰∈𝑊. Then 𝐯−𝐰=(𝐯−𝐩)+(𝐩−𝐰), where the first piece lies in 𝑊⟂ and the second in 𝑊. By Theorem 6.3.3,

‖𝐯−𝐰‖2=‖𝐯−𝐩‖2+‖𝐩−𝐰‖2≥‖𝐯−𝐩‖2,

with equality if and only if ‖𝐩−𝐰‖=0, that is, 𝐰=𝐩.

(c) The points of 𝑊 are 𝑡𝐞1=(𝑡,0), and ‖𝐞2−𝑡𝐞1‖∞=‖(−𝑡,1)‖∞=max(|𝑡|,1)≥1, with equality if and only if |𝑡|≤1. So the distance from 𝐞2 to 𝑊 is 1, and it is attained at every point (𝑡,0) with −1≤𝑡≤1.

The step with no analogue is the Pythagorean identity, which made the closest point unique: it adds the positive number ‖𝐩−𝐰‖2 for every 𝐰≠𝐩. The norm ‖⋅‖∞ does not come from any inner product, since it violates the parallelogram law (Proposition 6.1.30): ‖𝐞1+𝐞2‖∞2+‖𝐞1−𝐞2‖∞2=2, while 2‖𝐞1‖∞2+2‖𝐞2‖∞2=4. So there is no orthogonality to make the error perpendicular to 𝑊 (compare Aside (Norms that do not come from inner products)). Closest points still exist here, but uniqueness, and the linear formula for Pr𝑊, are features of inner products.

Problem 6.3.standard
  1. (a)State the theorem on the kernels and images of 𝑇 and 𝑇∗ (Section 6.6.4).
  2. (b)Let 𝑇∈L(𝑉,𝑊) have an adjoint. Prove that ker𝑇∗=(im𝑇)⟂, and, if 𝑉 is finite-dimensional, that im𝑇∗=(ker𝑇)⟂.
  3. (c)(Fredholm alternative.) Let 𝐴∈𝔽𝑚×𝑛 and 𝐛∈𝔽𝑚. Show that exactly one of the following holds: 𝐴𝐱=𝐛 has a solution 𝐱∈𝔽𝑛; or there is 𝐲∈𝔽𝑚 with 𝐴∗𝐲=𝟎 and 𝐲∗𝐛≠0. Use this to decide whether the system

    𝑥1+𝑥2=1,𝑥2+𝑥3=1,𝑥1−𝑥3=1

    has a solution, and likewise with right-hand side (1,1,0).

Solution.

Uses. Theorem 6.6.21 (Kernels and images of adjoints), Definition 6.6.8 (Adjoint), Proposition 6.1.37 (Inner products distinguish vectors), Proposition 6.6.18 (Properties of the adjoint), Theorem 6.4.26 (The double complement), Example 6.6.10 (The adjoint of a matrix), Corollary 6.6.22 (𝑇 and 𝑇∗ have the same rank), Theorem 4.2.11 (Rank–nullity)

Techniques. Move an operator across the inner product (Technique 6.6.20), Show a vector is zero via its norm (Technique 6.1.36)

Hint 1. For (b), 𝐰∈ker𝑇∗ if and only if ⟨𝐯,𝑇∗𝐰⟩=0 for every 𝐯. Move 𝑇∗ across.
Hint 2. For the second statement, apply the first one to 𝑇∗, whose adjoint is 𝑇, and take perps.
Hint 3. For (c), 𝐴𝐱=𝐛 is solvable if and only if 𝐛∈im𝐴=(ker𝐴∗)⟂. For the example, look for a combination of the three equations whose left side is 0.
Sketch. (b) 𝑇∗𝐰=𝟎 iff ⟨𝐯,𝑇∗𝐰⟩=0 for all 𝐯 iff ⟨𝑇𝐯,𝐰⟩=0 for all 𝐯 iff 𝐰⟂im𝑇. Applied to 𝑇∗: ker𝑇=(im𝑇∗)⟂, and the double perp gives im𝑇∗=(ker𝑇)⟂. (c) 𝐛∈im𝐴 iff 𝐛⟂ker𝐴∗; the second alternative says exactly that this fails. For the example, 𝐲=(1,−1,−1) spans ker𝐴𝖳; 𝐲𝖳(1,1,1)=−1, so no solution, while 𝐲𝖳(1,1,0)=0, and (1,0,1) is a solution.

(a) Let 𝑇∈L(𝑉,𝑊) have an adjoint. Then ker𝑇∗=(im𝑇)⟂ and ker𝑇=(im𝑇∗)⟂. If 𝑉 is finite-dimensional, also im𝑇∗=(ker𝑇)⟂ and im𝑇=(ker𝑇∗)⟂, so that 𝑉=ker𝑇⊕im𝑇∗ and 𝑊=im𝑇⊕ker𝑇∗ (Theorem 6.6.21).

(b) Let 𝐰∈𝑊. A vector of 𝑉 is 𝟎 if and only if it is orthogonal to every vector of 𝑉 (Proposition 6.1.37). So

𝑇∗𝐰=𝟎⟺⟨𝐯,𝑇∗𝐰⟩=0for all𝐯∈𝑉⟺⟨𝑇𝐯,𝐰⟩=0for all𝐯∈𝑉⟺𝐰∈(im𝑇)⟂,

using Definition 6.6.8 in the middle. This proves ker𝑇∗=(im𝑇)⟂.

By Proposition 6.6.18, 𝑇∗ has the adjoint 𝑇. Applying what we just proved to 𝑇∗ gives ker𝑇=(im𝑇∗)⟂. If 𝑉 is finite-dimensional, so is its subspace im𝑇∗, and Theorem 6.4.26 gives (ker𝑇)⟂=((im𝑇∗)⟂)⟂=im𝑇∗.

(c) With dot products, the map 𝐱↦𝐴𝐱 from 𝔽𝑛 to 𝔽𝑚 has the adjoint 𝐲↦𝐴∗𝐲 (Example 6.6.10). Applying (b) to the adjoint, with the finite-dimensional space 𝔽𝑚 in the role of 𝑉, gives im𝐴=(ker𝐴∗)⟂. So 𝐴𝐱=𝐛 has a solution if and only if 𝐲∗𝐛=⟨𝐛,𝐲⟩=0 for every 𝐲∈ker𝐴∗. The second alternative says precisely that this fails for some 𝐲, so exactly one of the two holds.

For the example, 𝐴=(11001110−1) is real, so 𝐴∗=𝐴𝖳. Subtracting the second equation from the first gives 𝑥1−𝑥3, so 𝐲=(1,−1,−1) satisfies 𝐴𝖳𝐲=𝟎, as one checks column by column. With 𝐛=(1,1,1), 𝐲𝖳𝐛=1−1−1=−1≠0, so the system has no solution. With 𝐛′=(1,1,0), 𝐲𝖳𝐛′=0. The first two rows of 𝐴 are independent and the third is their difference, so rank𝐴=2, rank𝐴𝖳=2 (Corollary 6.6.22), and ker𝐴𝖳=span(𝐲) by Theorem 4.2.11. So 𝐛′⟂ker𝐴𝖳, and the system is solvable; indeed 𝐱=(1,0,1) works.

The vector 𝐲 is a certificate of inconsistency that can be checked without solving anything. Row reduction finds it too (as the combination of rows that produces 0=−1), but (b) explains why it must exist: the right-hand side has to be orthogonal to every relation among the rows.

Synthesis problems

Problem 6.4.standard Let 𝐩0,…,𝐩𝑘∈ℝ𝑛 be such that 𝐯𝑖=𝐩𝑖−𝐩0 (1≤𝑖≤𝑘) are linearly independent, and let 𝐴=𝐩0+span(𝐯1,…,𝐯𝑘), the smallest affine subspace containing the points (Section 4.7).

  1. (a)Show that exactly one point 𝐜∈𝐴 is equidistant from 𝐩0,…,𝐩𝑘. (It is the circumcenter of the points.)
  2. (b)Show that 𝐪∈ℝ𝑛 is equidistant from 𝐩0,…,𝐩𝑘 if and only if 𝐪−𝐜⟂𝐯𝑖 for every 𝑖. Deduce that 𝐜 is the point of 𝐴 closest to every such 𝐪, and that for 𝑘=𝑛 the circumcenter is the only point of ℝ𝑛 equidistant from the 𝑛+1 points.
  3. (c)Find the circumcenter and the common distance for 𝐩0=𝟎, 𝐩1=(2,0,0), and 𝐩2=(1,2,2).

Solution.

Uses. Proposition 6.1.29 (Expanding a norm), Definition 6.3.28 (Gram matrix), Proposition 6.3.30 (Gram matrices detect independence), Theorem 6.4.6 (The projection is characterized by orthogonality), Theorem 6.4.33 (Best approximation)

Techniques. Gram matrices (Technique 6.3.31), Recognize a projection by its two conditions (Technique 6.4.7)

Hint 1. Write 𝐜=𝐩0+𝐳. Expand ‖𝐳−𝐯𝑖‖2=‖𝐳‖2. What linear condition on 𝐳 do you get?
Hint 2. The conditions are ⟨𝐳,𝐯𝑖⟩=‖𝐯𝑖‖2/2. With 𝐳=∑𝑗𝑡𝑗𝐯𝑗 they become a linear system whose matrix is the Gram matrix of 𝐯1,…,𝐯𝑘.
Sketch. ‖𝐜−𝐩𝑖‖=‖𝐜−𝐩0‖ iff ⟨𝐜−𝐩0,𝐯𝑖⟩=‖𝐯𝑖‖2/2. For 𝐜−𝐩0=∑𝑗𝑡𝑗𝐯𝑗 this is 𝐺𝐭=𝐝 with 𝐺 the invertible Gram matrix, so 𝐜 is unique. For any 𝐪 the same conditions hold with 𝐪; subtracting gives 𝐪−𝐜⟂𝐯𝑖, so 𝐜−𝐩0 is the projection of 𝐪−𝐩0. (c) 𝐺=(4229), 𝐝=(2,9/2), 𝐭=(9/32,7/16), 𝐜=(1,7/8,7/8), distance 92/8.

(a) Every point of 𝐴 is 𝐜=𝐩0+𝐳 with 𝐳∈𝑈=span(𝐯1,…,𝐯𝑘). Since 𝐜−𝐩𝑖=𝐳−𝐯𝑖, Proposition 6.1.29 gives

‖𝐜−𝐩𝑖‖2=‖𝐳‖2−2⟨𝐳,𝐯𝑖⟩+‖𝐯𝑖‖2=‖𝐜−𝐩0‖2−2⟨𝐳,𝐯𝑖⟩+‖𝐯𝑖‖2.

So 𝐜 is equidistant from all the points if and only if

⟨𝐳,𝐯𝑖⟩=12‖𝐯𝑖‖2(1≤𝑖≤𝑘).

Write 𝐳=∑𝑗𝑡𝑗𝐯𝑗. Then ⟨𝐳,𝐯𝑖⟩=∑𝑗𝑡𝑗⟨𝐯𝑗,𝐯𝑖⟩=(𝐺𝐭)𝑖, where 𝐺 is the Gram matrix of 𝐯1,…,𝐯𝑘 (Definition 6.3.28). So the conditions say 𝐺𝐭=𝐝 with 𝑑𝑖=‖𝐯𝑖‖2/2. The 𝐯𝑖 are independent, so 𝐺 is invertible (Proposition 6.3.30), and there is exactly one 𝐭, hence (by independence again) exactly one 𝐳∈𝑈 and one 𝐜∈𝐴.

(b) The computation in (a) did not use 𝐳∈𝑈: for every 𝐪∈ℝ𝑛, 𝐪 is equidistant from the points if and only if 𝐳=𝐪−𝐩0 satisfies these 𝑘 conditions. Since 𝐜−𝐩0 satisfies it, subtracting shows that 𝐪 is equidistant if and only if ⟨𝐪−𝐜,𝐯𝑖⟩=0 for all 𝑖.

For such 𝐪, the vector 𝐜−𝐩0 lies in 𝑈, and (𝐪−𝐩0)−(𝐜−𝐩0)=𝐪−𝐜 is orthogonal to 𝑈. By Theorem 6.4.6, 𝐜−𝐩0=Pr𝑈(𝐪−𝐩0). For any 𝐚=𝐩0+𝐮∈𝐴, Theorem 6.4.33 gives

‖𝐪−𝐚‖=‖(𝐪−𝐩0)−𝐮‖≥‖(𝐪−𝐩0)−Pr𝑈(𝐪−𝐩0)‖=‖𝐪−𝐜‖,

with equality only for 𝐚=𝐜. If 𝑘=𝑛, then 𝑈=ℝ𝑛, so 𝑈⟂={𝟎} and 𝐪=𝐜.

(c) Here 𝐯1=(2,0,0) and 𝐯2=(1,2,2), so

𝐺=(4229),𝐝=(29/2),𝐭=𝐺−1𝐝=132(9−2−24)(29/2)=(9/327/16).

So 𝐜=(9/32)(2,0,0)+(7/16)(1,2,2)=(1,7/8,7/8). Check: ‖𝐜‖2=1+49/32=81/32, ‖𝐜−𝐩1‖2=1+49/32=81/32, and ‖𝐜−𝐩2‖2=0+2⋅81/64=81/32. The common distance is 9/32=92/8.

By (b), the points of ℝ3 equidistant from the three vertices form the line through 𝐜 perpendicular to the plane of the triangle; the circumcenter is where that line meets the plane.

Problem 6.5.standard Let 𝑥0,…,𝑥𝑛∈ℝ be distinct, let 𝑉=ℝ[𝑥]≤𝑛, and let

⟨𝑝,𝑞⟩=∑𝑘=0𝑛𝑝(𝑥𝑘)𝑞(𝑥𝑘).
  1. (a)Show that this is an inner product on 𝑉, and that the Lagrange polynomials 𝐿0,…,𝐿𝑛 of the nodes (Definition 3.4.26) form an orthonormal basis, in which the coordinates of 𝑝 are 𝑝(𝑥0),…,𝑝(𝑥𝑛).
  2. (b)Deduce that the matrix with (𝑖,𝑗) entry ∑𝑘𝑥𝑘𝑖+𝑗 (0≤𝑖,𝑗≤𝑛) is invertible. (Compare Problem 5.9.)
  3. (c)Let 𝑦0,…,𝑦𝑛∈ℝ, let 𝑝∈𝑉 satisfy 𝑝(𝑥𝑘)=𝑦𝑘 for all 𝑘 (Theorem 3.4.24), and let 𝑑<𝑛. Show that Prℝ[𝑥]≤𝑑(𝑝) is the least-squares polynomial of degree at most 𝑑 for the data (𝑥𝑘,𝑦𝑘), in the sense of Proposition 6.5.21.
  4. (d)For the nodes −1,0,1 and the values 0,1,3, find 𝑝 and the least-squares line by (c).

Solution.

Uses. Definition 6.1.2 (Inner product), Lemma 3.4.23 (Too many roots), Proposition 6.3.18 (Coordinates in an orthonormal basis), Corollary 6.3.14 (Counting orthogonal vectors), Proposition 6.3.30 (Gram matrices detect independence), Theorem 6.4.33 (Best approximation), Proposition 6.5.21 (Polynomial fits)

Techniques. Take an inner product to isolate a coefficient (Technique 6.3.12), A sum of nonnegative terms (Technique 6.1.9)

Hint 1. For definiteness, a polynomial of degree at most 𝑛 with 𝑛+1 roots is zero. For the Lagrange polynomials, compute ⟨𝐿𝑖,𝐿𝑗⟩ from 𝐿𝑖(𝑥𝑘)=𝛿𝑖𝑘.
Hint 2. In (c), ‖𝑝−𝑞‖2=∑𝑘(𝑦𝑘−𝑞(𝑥𝑘))2 for every 𝑞. In (d), 1 and 𝑥 are orthogonal for this inner product.
Sketch. (a) Positivity is a sum of squares, and ∑𝑘𝑝(𝑥𝑘)2=0 forces 𝑛+1 roots, so 𝑝=0. ⟨𝐿𝑖,𝐿𝑗⟩=∑𝑘𝛿𝑖𝑘𝛿𝑗𝑘=𝛿𝑖𝑗, and 𝑛+1 orthonormal vectors in an (𝑛+1)-dimensional space form a basis; ⟨𝑝,𝐿𝑗⟩=𝑝(𝑥𝑗). (b) It is the Gram matrix of the basis 1,𝑥,…,𝑥𝑛. (c) ‖𝑝−𝑞‖2 is the sum of squared residuals of 𝑞, so its minimizer is the projection. (d) 𝑝=1+3𝑥/2+𝑥2/2; with ‖1‖2=3, ‖𝑥‖2=2, ⟨𝑝,1⟩=4, ⟨𝑝,𝑥⟩=3, the line is 𝑦=4/3+3𝑥/2.

(a) The formula is linear in 𝑝 and symmetric, since evaluation at a point is linear. Also ⟨𝑝,𝑝⟩=∑𝑘𝑝(𝑥𝑘)2≥0, and if it is 0, then every 𝑝(𝑥𝑘)=0 (Technique 6.1.9), so 𝑝, which has degree at most 𝑛 and 𝑛+1 distinct roots, is 0 by Lemma 3.4.23. So this is an inner product.

Since 𝐿𝑖(𝑥𝑘)=𝛿𝑖𝑘,

⟨𝐿𝑖,𝐿𝑗⟩=∑𝑘=0𝑛𝐿𝑖(𝑥𝑘)𝐿𝑗(𝑥𝑘)=∑𝑘=0𝑛𝛿𝑖𝑘𝛿𝑗𝑘=𝛿𝑖𝑗.

So 𝐿0,…,𝐿𝑛 is orthonormal, and since dim𝑉=𝑛+1 it is an orthonormal basis (Corollary 6.3.14). By Proposition 6.3.18 the coordinates of 𝑝 are ⟨𝑝,𝐿𝑗⟩=∑𝑘𝑝(𝑥𝑘)𝛿𝑗𝑘=𝑝(𝑥𝑗), that is, 𝑝=∑𝑗𝑝(𝑥𝑗)𝐿𝑗. The Lagrange interpolation formula is the coordinate formula for this orthonormal basis.

(b) The (𝑖,𝑗) entry is ∑𝑘𝑥𝑘𝑗𝑥𝑘𝑖=⟨𝑥𝑗,𝑥𝑖⟩, so the matrix is the Gram matrix of 1,𝑥,…,𝑥𝑛 (Definition 6.3.28). These polynomials are independent, so the Gram matrix is invertible by Proposition 6.3.30. Problem 5.9 computes its determinant as ∏𝑖<𝑗(𝑥𝑗−𝑥𝑖)2; here invertibility came from the positivity of an inner product instead.

(c) For every 𝑞∈ℝ[𝑥]≤𝑑,

‖𝑝−𝑞‖2=∑𝑘=0𝑛(𝑝(𝑥𝑘)−𝑞(𝑥𝑘))2=∑𝑘=0𝑛(𝑦𝑘−𝑞(𝑥𝑘))2,

the sum of squared residuals of 𝑞. By Theorem 6.4.33, this is smallest exactly for 𝑞=Prℝ[𝑥]≤𝑑(𝑝), so that projection is the least-squares polynomial of Proposition 6.5.21, and in particular it is unique.

(d) 𝑝=1+(3/2)𝑥+(1/2)𝑥2 satisfies 𝑝(−1)=0, 𝑝(0)=1, 𝑝(1)=3. For this inner product ⟨1,𝑥⟩=−1+0+1=0, ‖1‖2=3, and ‖𝑥‖2=2, while ⟨𝑝,1⟩=0+1+3=4 and ⟨𝑝,𝑥⟩=0+0+3=3. By Corollary 6.4.10,

Prℝ[𝑥]≤1(𝑝)=43+32𝑥.

This agrees with Proposition 6.5.17: the mean of the nodes is 0, the mean of the values is 4/3, and the slope is ∑𝑘𝑥𝑘𝑦𝑘/∑𝑘𝑥𝑘2=3/2.

Problem 6.6.standard Find the error in the following argument, and show that the claim is false.

Claim. Let 𝑉 be a finite-dimensional real inner product space and 𝑇∈L(𝑉) with ⟨𝑇𝐯,𝐯⟩≥0 for every 𝐯∈𝑉. Then 𝑇 is self-adjoint.

Proof. Let 𝑆=𝑇−𝑇∗. For every 𝐯,

⟨𝑇∗𝐯,𝐯⟩=⟨𝐯,𝑇𝐯⟩=⟨𝑇𝐯,𝐯⟩=⟨𝑇𝐯,𝐯⟩,

the last step because ⟨𝑇𝐯,𝐯⟩≥0 is real. So ⟨𝑆𝐯,𝐯⟩=0 for every 𝐯, and 𝑆=0 by Proposition 6.1.41.

  1. (a)Then show that the same argument is correct for complex inner product spaces.
  2. (b)Over ℝ, show that ⟨𝑇𝐯,𝐯⟩=⟨𝐻𝐯,𝐯⟩ for every 𝐯, where 𝐻=(𝑇+𝑇∗)/2.

Solution.

Uses. Proposition 6.1.41 (Over ℂ, the values ⟨𝑇𝐯,𝐯⟩ determine 𝑇), Example 6.1.39 (A rotation), Proposition 6.6.18 (Properties of the adjoint), Proposition 6.6.30 (Self-adjoint means real values)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18), Plug in clever test vectors (Technique 6.1.40)

Hint 1. Which hypotheses does Proposition 6.1.41 have? Over ℝ, compute ⟨𝑆𝐯,𝐯⟩ for 𝑆=𝑇−𝑇∗ without using any hypothesis on 𝑇.
Hint 2. Try 𝑇=𝐼2+𝐽 with 𝐽 the rotation by 𝜋/2.
Sketch. Proposition 6.1.41 needs complex scalars. Over ℝ, ⟨𝑇∗𝐯,𝐯⟩=⟨𝑇𝐯,𝐯⟩ for every 𝑇, so the argument proves nothing, and 𝑇=(1−111) has ⟨𝑇𝐯,𝐯⟩=‖𝐯‖2 but 𝑇𝖳≠𝑇. (a) Over ℂ the conjugation step uses that ⟨𝑇𝐯,𝐯⟩ is real, and Proposition 6.1.41 applies. (b) ⟨𝑇∗𝐯,𝐯⟩=⟨𝑇𝐯,𝐯⟩ over ℝ, so averaging gives the claim.

The error. The last step cites Proposition 6.1.41, which is about complex inner product spaces. Over ℝ, 𝑆=𝑇−𝑇∗ satisfies 𝑆∗=−𝑆 (Proposition 6.6.18), and every such operator has ⟨𝑆𝐯,𝐯⟩=⟨𝐯,𝑆∗𝐯⟩=−⟨𝐯,𝑆𝐯⟩=−⟨𝑆𝐯,𝐯⟩, hence ⟨𝑆𝐯,𝐯⟩=0, whether or not 𝑆=0. In fact over ℝ the first display holds for every 𝑇, so the argument never used the hypothesis, which is a sign that something is wrong.

The claim is false. Let 𝑇=(1−111) on ℝ2 with the dot product. Then

⟨𝑇𝐯,𝐯⟩=(𝑣1−𝑣2)𝑣1+(𝑣1+𝑣2)𝑣2=𝑣12+𝑣22≥0,

but 𝑇∗=𝑇𝖳=(11−11)≠𝑇. Here 𝑇=𝐼2+𝐽 with 𝐽 the rotation of Example 6.1.39, and 𝐽 contributes nothing to ⟨𝑇𝐯,𝐯⟩.

(a) Over ℂ every step is correct. The conjugation step is the definition of the adjoint followed by conjugate symmetry, and the hypothesis is used exactly where it should be: a nonnegative number equals its conjugate. Then ⟨𝑆𝐯,𝐯⟩=0 for every 𝐯, and Proposition 6.1.41 gives 𝑆=0. (This is one half of Proposition 6.6.30.)

(b) Over ℝ, ⟨𝑇∗𝐯,𝐯⟩=⟨𝐯,𝑇𝐯⟩=⟨𝑇𝐯,𝐯⟩ by symmetry of the real inner product. So

⟨𝐻𝐯,𝐯⟩=12(⟨𝑇𝐯,𝐯⟩+⟨𝑇∗𝐯,𝐯⟩)=⟨𝑇𝐯,𝐯⟩.

The numbers ⟨𝑇𝐯,𝐯⟩ see only the self-adjoint part 𝐻 of a real operator, and adding any 𝐾 with 𝐾∗=−𝐾 to 𝑇 does not change them. This is why Section 8.3 requires positive operators to be self-adjoint by definition.

Problem 6.7.standard Prove or disprove each statement.

  1. (a)If 𝐴∈ℝ𝑚×𝑛 has orthonormal columns, then 𝐴𝐴𝖳=𝐼𝑚.
  2. (b)For every 𝐴∈ℂ𝑛×𝑛, det(𝐴∗𝐴) is a nonnegative real number.
  3. (c)If 𝑃∈ℝ𝑛×𝑛 satisfies 𝑃2=𝑃 and 𝑃𝖳𝑃=𝑃𝑃𝖳, then 𝑃 is the matrix of an orthogonal projection.
  4. (d)If 𝑈,𝑊 are subspaces of a finite-dimensional inner product space 𝑉, then dim(𝑈∩𝑊⟂)≥dim𝑈−dim𝑊.
  5. (e)For 𝐴∈ℝ𝑛×𝑛: ‖𝐴𝐱‖≤‖𝐱‖ for every 𝐱∈ℝ𝑛 if and only if |det𝐴|≤1.

Solution.

Uses. Theorem 6.4.31 (The matrix of an orthogonal projection), Theorem 5.4.10 (Multiplicativity), Exercise 6.3.57, Lemma 6.5.4 (The orthogonal complement of a column space), Theorem 6.4.6 (The projection is characterized by orthogonality), Proposition 6.4.29 (The orthogonal projection as a linear map), Theorem 4.2.11 (Rank–nullity), Exercise 6.4.59

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18), Move an operator across the inner product (Technique 6.6.20)

Hint 1. (a) Try 𝑚>𝑛. (b) det(𝐴∗)=det𝐴. (c) First show ‖𝑃𝐯‖=‖𝑃𝖳𝐯‖, and deduce ker𝑃=ker𝑃𝖳.
Hint 2. (d) Apply rank–nullity to Pr𝑊 restricted to 𝑈. (e) One direction is Hadamard’s inequality from Exercise 6.4.59(c); for the other, try a diagonal matrix.
Sketch. (a) False: 𝐴=𝐞1∈ℝ2×1 gives 𝐴𝐴𝖳=diag(1,0); in general 𝐴𝐴𝖳 is the projection onto im𝐴. (b) True: det(𝐴∗𝐴)=|det𝐴|2. (c) True: normality gives ker𝑃=ker𝑃𝖳=(im𝑃)⟂, so 𝐯−𝑃𝐯∈ker𝑃⟂im𝑃. (d) True: the restriction of Pr𝑊 to 𝑈 has kernel 𝑈∩𝑊⟂ and image in 𝑊. (e) “Only if” is true by Hadamard, since the columns 𝐴𝐞𝑗 have length at most 1; “if” is false for diag(2,1/2).

(a) False. 𝐴=(10)∈ℝ2×1 has one orthonormal column, but 𝐴𝐴𝖳=(1000)≠𝐼2. In general 𝐴𝐴𝖳 is the matrix of Prim𝐴 (Theorem 6.4.31), which is 𝐼𝑚 only when im𝐴=ℝ𝑚, that is, when 𝑚=𝑛.

(b) True. By Theorem 5.4.10 and Exercise 6.3.57(a), det(𝐴∗𝐴)=det(𝐴∗)det𝐴=det𝐴det𝐴=|det𝐴|2≥0.

(c) True. Let 𝐯∈ℝ𝑛. Using the dot product, ‖𝑃𝐯‖2=⟨𝑃𝖳𝑃𝐯,𝐯⟩=⟨𝑃𝑃𝖳𝐯,𝐯⟩=‖𝑃𝖳𝐯‖2, so ker𝑃=ker𝑃𝖳, and ker𝑃𝖳=(im𝑃)⟂ by Lemma 6.5.4. Now 𝑃𝐯∈im𝑃, and 𝑃(𝐯−𝑃𝐯)=𝑃𝐯−𝑃2𝐯=𝟎, so 𝐯−𝑃𝐯∈ker𝑃=(im𝑃)⟂. By Theorem 6.4.6, 𝑃𝐯=Prim𝑃(𝐯) for every 𝐯.

(d) True. Let 𝑅:𝑈→𝑊 be the restriction of Pr𝑊 to 𝑈; it maps into 𝑊 and is linear. Its kernel is 𝑈∩kerPr𝑊=𝑈∩𝑊⟂ (Proposition 6.4.29(a)), and its image is a subspace of 𝑊. By Theorem 4.2.11,

dim𝑈=dim(𝑈∩𝑊⟂)+dimim𝑅≤dim(𝑈∩𝑊⟂)+dim𝑊.

In words: if 𝑈 is bigger than 𝑊, then 𝑈 contains dim𝑈−dim𝑊 independent directions perpendicular to all of 𝑊.

(e) “Only if” is true. The columns of 𝐴 are 𝐚𝑗=𝐴𝐞𝑗, with ‖𝐚𝑗‖≤‖𝐞𝑗‖=1. By Hadamard’s inequality (Exercise 6.4.59(c)), |det𝐴|≤‖𝐚1‖⋯‖𝐚𝑛‖≤1. “If” is false: 𝐴=(2001/2) has det𝐴=1 but ‖𝐴𝐞1‖=2>1. The determinant measures the change of volume, and a map can stretch one direction while shrinking another.

Problem 6.8.hard Let 𝑉 be a real inner product space and 𝑓:𝑉→𝑉 a function (not assumed linear) with 𝑓(𝟎)=𝟎 and

‖𝑓(𝐱)−𝑓(𝐲)‖=‖𝐱−𝐲‖for all𝐱,𝐲∈𝑉.
  1. (a)Show that ‖𝑓(𝐱)‖=‖𝐱‖ and ⟨𝑓(𝐱),𝑓(𝐲)⟩=⟨𝐱,𝐲⟩ for all 𝐱,𝐲.
  2. (b)Show that 𝑓 is linear. Give a proof that works for every 𝑉, and, if 𝑉 is finite-dimensional, a second proof with an orthonormal basis.
  3. (c)Deduce that every distance-preserving 𝑔:ℝ𝑛→ℝ𝑛 has the form 𝑔(𝐱)=𝑄𝐱+𝐛 with 𝑄𝖳𝑄=𝐼𝑛.
  4. (d)Now let 𝑉 be a complex inner product space and 𝑓:𝑉→𝑉 satisfy the same two conditions. Show that 𝑓(𝐱+𝐲)=𝑓(𝐱)+𝑓(𝐲) and 𝑓(𝑡𝐱)=𝑡𝑓(𝐱) for real 𝑡, but that 𝑓 need not be linear over ℂ.

Solution.

Uses. Proposition 6.1.29 (Expanding a norm), Proposition 6.1.27 (Basic properties of the norm), Corollary 6.3.14 (Counting orthogonal vectors), Proposition 6.3.18 (Coordinates in an orthonormal basis), Proposition 2.3.17 (Every linear map 𝐹𝑛→𝐹𝑚 is some 𝑇𝐴), Theorem 6.3.29 (Orthonormal columns)

Techniques. Polarization (Technique 6.1.33), Show a vector is zero via its norm (Technique 6.1.36)

Hint 1. (a) Put 𝐲=𝟎, then expand ‖𝑓(𝐱)−𝑓(𝐲)‖2 and compare with ‖𝐱−𝐲‖2.
Hint 2. (b) Expand ‖𝑓(𝐱+𝐲)−𝑓(𝐱)−𝑓(𝐲)‖2 into norms and inner products of values of 𝑓, and use (a) on every term.
Hint 3. For the second proof, 𝑓(𝐞1),…,𝑓(𝐞𝑛) is orthonormal. Compute the coordinates of 𝑓(𝐱) in it. For (d), try complex conjugation on ℂ𝑛.
Sketch. (a) ‖𝑓(𝐱)‖=‖𝑓(𝐱)−𝑓(𝟎)‖=‖𝐱‖, and polarization turns equal distances and equal lengths into equal inner products. (b) ‖𝑓(𝐱+𝐲)−𝑓(𝐱)−𝑓(𝐲)‖2 expands into terms that (a) lets us replace by the same terms without 𝑓, giving ‖𝟎‖2=0; likewise for 𝑓(𝑡𝐱)−𝑡𝑓(𝐱). With an orthonormal basis: 𝑓(𝐞𝑖) is an orthonormal basis and 𝑓(𝐱)=∑𝑖⟨𝐱,𝐞𝑖⟩𝑓(𝐞𝑖). (c) Apply (b) to 𝑔−𝑔(𝟎). (d) The expansions involve only real parts, so the first proof gives real linearity; conjugation preserves distances and is not ℂ-linear.

(a) Taking 𝐲=𝟎 gives ‖𝑓(𝐱)‖=‖𝑓(𝐱)−𝑓(𝟎)‖=‖𝐱‖. By Proposition 6.1.29 over ℝ,

‖𝑓(𝐱)‖2−2⟨𝑓(𝐱),𝑓(𝐲)⟩+‖𝑓(𝐲)‖2=‖𝑓(𝐱)−𝑓(𝐲)‖2=‖𝐱−𝐲‖2=‖𝐱‖2−2⟨𝐱,𝐲⟩+‖𝐲‖2,

and the squared lengths agree, so ⟨𝑓(𝐱),𝑓(𝐲)⟩=⟨𝐱,𝐲⟩.

(b) First proof. Let 𝐱,𝐲∈𝑉 and 𝐳=𝑓(𝐱+𝐲)−𝑓(𝐱)−𝑓(𝐲). Expanding,

‖𝐳‖2=‖𝑓(𝐱+𝐲)‖2+‖𝑓(𝐱)‖2+‖𝑓(𝐲)‖2−2⟨𝑓(𝐱+𝐲),𝑓(𝐱)⟩−2⟨𝑓(𝐱+𝐲),𝑓(𝐲)⟩+2⟨𝑓(𝐱),𝑓(𝐲)⟩.

By (a), each term equals the same term with 𝑓 removed, and the result is the expansion of ‖(𝐱+𝐲)−𝐱−𝐲‖2=0. So 𝐳=𝟎 (Proposition 6.1.27). Similarly, for 𝑡∈ℝ,

‖𝑓(𝑡𝐱)−𝑡𝑓(𝐱)‖2=‖𝑓(𝑡𝐱)‖2−2𝑡⟨𝑓(𝑡𝐱),𝑓(𝐱)⟩+𝑡2‖𝑓(𝐱)‖2=‖𝑡𝐱−𝑡𝐱‖2=0.

So 𝑓 is additive and homogeneous, that is, linear. This proof works verbatim for 𝑓:𝑉→𝑊 between any two real inner product spaces.

Second proof, for dim𝑉=𝑛<∞. Let 𝐞1,…,𝐞𝑛 be an orthonormal basis. By (a), ⟨𝑓(𝐞𝑖),𝑓(𝐞𝑗)⟩=𝛿𝑖𝑗, so 𝑓(𝐞1),…,𝑓(𝐞𝑛) is an orthonormal list of length 𝑛 in 𝑉, hence an orthonormal basis (Corollary 6.3.14). By Proposition 6.3.18 and (a),

𝑓(𝐱)=∑𝑖=1𝑛⟨𝑓(𝐱),𝑓(𝐞𝑖)⟩𝑓(𝐞𝑖)=∑𝑖=1𝑛⟨𝐱,𝐞𝑖⟩𝑓(𝐞𝑖),

and each 𝐱↦⟨𝐱,𝐞𝑖⟩ is linear. This proof needs the values 𝑓(𝐞𝑖) to span the target, which is why it asks for 𝑓:𝑉→𝑉 with 𝑉 finite-dimensional; the first proof needs nothing of the kind.

(c) Let 𝑓(𝐱)=𝑔(𝐱)−𝑔(𝟎). Then 𝑓(𝟎)=𝟎 and ‖𝑓(𝐱)−𝑓(𝐲)‖=‖𝑔(𝐱)−𝑔(𝐲)‖=‖𝐱−𝐲‖, so 𝑓 is linear by (b), say 𝑓(𝐱)=𝑄𝐱 (Proposition 2.3.17). By (a), (𝑄𝐞𝑗)⋅(𝑄𝐞𝑖)=𝛿𝑖𝑗, so the columns of 𝑄 are orthonormal and 𝑄𝖳𝑄=𝐼𝑛 (Theorem 6.3.29). With 𝐛=𝑔(𝟎), 𝑔(𝐱)=𝑄𝐱+𝐛.

(d) Over ℂ, Proposition 6.1.29 contains 2Re⟨⋅,⋅⟩ instead of 2⟨⋅,⋅⟩, so (a) becomes Re⟨𝑓(𝐱),𝑓(𝐲)⟩=Re⟨𝐱,𝐲⟩, and the expansions in the first proof of (b) involve only lengths and real parts of inner products (for the second one, with 𝑡 real). So they go through unchanged and show that 𝑓 is additive and 𝑓(𝑡𝐱)=𝑡𝑓(𝐱) for 𝑡∈ℝ. But 𝑓 need not be ℂ-linear: on ℂ𝑛 with the dot product, let 𝑓 conjugate every entry. Then 𝑓(𝟎)=𝟎 and ‖𝑓(𝐱)−𝑓(𝐲)‖=‖𝐱−𝐲‖=‖𝐱−𝐲‖, while 𝑓(𝑖𝐞1)=−𝑖𝐞1≠𝑖𝑓(𝐞1).

For surjective distance-preserving maps between real normed spaces, the conclusion of (b) still holds (the Mazur–Ulam theorem), but the proof is much harder: without an inner product there is no polarization.

Problem 6.9.hard Let 𝑉,𝑊 be inner product spaces over 𝔽, and let 𝐯1,…,𝐯𝑘∈𝑉 and 𝐰1,…,𝐰𝑘∈𝑊 have the same Gram matrix: ⟨𝐯𝑗,𝐯𝑖⟩=⟨𝐰𝑗,𝐰𝑖⟩ for all 𝑖,𝑗.

  1. (a)Show that ‖𝑐1𝐯1+⋯+𝑐𝑘𝐯𝑘‖=‖𝑐1𝐰1+⋯+𝑐𝑘𝐰𝑘‖ for all 𝑐1,…,𝑐𝑘∈𝔽. Deduce that ∑𝑖𝑐𝑖𝐯𝑖=𝟎 if and only if ∑𝑖𝑐𝑖𝐰𝑖=𝟎.
  2. (b)Show that there is exactly one linear map 𝑆:span(𝐯1,…,𝐯𝑘)→span(𝐰1,…,𝐰𝑘) with 𝑆𝐯𝑖=𝐰𝑖 for all 𝑖, and that 𝑆 is bijective with ⟨𝑆𝐱,𝑆𝐲⟩=⟨𝐱,𝐲⟩ for all 𝐱,𝐲.
  3. (c)Let 𝐴,𝐵∈𝔽𝑚×𝑛. Show that 𝐴∗𝐴=𝐵∗𝐵 if and only if 𝐵=𝑈𝐴 for some unitary 𝑈∈𝔽𝑚×𝑚.

Solution.

Uses. Proposition 6.3.30 (Gram matrices detect independence), Proposition 6.1.27 (Basic properties of the norm), Corollary 2.2.6 (Agreeing on a spanning list), Theorem 6.3.29 (Orthonormal columns), Theorem 6.4.20 (Orthonormal bases exist), Corollary 6.4.25 (Dimension of the orthogonal complement), Corollary 6.3.14 (Counting orthogonal vectors), Definition 6.3.33 (Unitary and orthogonal matrices), Exercise 6.3.37

Techniques. Gram matrices (Technique 6.3.31), Show a vector is zero via its norm (Technique 6.1.36)

Hint 1. (a) is Proposition 6.3.30(a) applied to both lists. Then use Technique 6.1.36.
Hint 2. (b) Define 𝑆(∑𝑖𝑐𝑖𝐯𝑖)=∑𝑖𝑐𝑖𝐰𝑖. Why is this well defined?
Hint 3. (c) The columns of 𝐴 and of 𝐵 have the same Gram matrix. Extend the map 𝑆 of (b) from im𝐴 to all of 𝔽𝑚 by matching orthonormal bases of (im𝐴)⟂ and (im𝐵)⟂.
Sketch. (a) Both squared norms equal 𝐜∗𝐺𝐜. (b) Well defined because two expressions of the same vector differ by a relation, which (a) transports; inner products are preserved because they are computed from 𝐺; injective by (a). (c) 𝐴∗𝐴 is the Gram matrix of the columns. The isometry 𝑆:im𝐴→im𝐵 sends an orthonormal basis 𝐮1,…,𝐮𝑟 of im𝐴 to one of im𝐵; completing both with orthonormal bases of the complements (both of dimension 𝑚−𝑟) gives two unitary matrices 𝑈1,𝑈2, and 𝑈=𝑈2𝑈1∗ agrees with 𝑆 on im𝐴, so 𝑈𝐴=𝐵.

(a) Let 𝐺 be the common Gram matrix and 𝐜=(𝑐1,…,𝑐𝑘). By Proposition 6.3.30(a), ‖∑𝑖𝑐𝑖𝐯𝑖‖2=𝐜∗𝐺𝐜=‖∑𝑖𝑐𝑖𝐰𝑖‖2. Since a vector is 𝟎 exactly when its norm is 0 (Proposition 6.1.27), the second statement follows.

(b) Uniqueness. A linear map on span(𝐯1,…,𝐯𝑘) is determined by its values on the spanning list 𝐯1,…,𝐯𝑘 (Corollary 2.2.6).

Existence. Every vector of span(𝐯1,…,𝐯𝑘) is ∑𝑖𝑐𝑖𝐯𝑖 for some scalars, and we set 𝑆(∑𝑖𝑐𝑖𝐯𝑖)=∑𝑖𝑐𝑖𝐰𝑖. If ∑𝑖𝑐𝑖𝐯𝑖=∑𝑖𝑑𝑖𝐯𝑖, then ∑𝑖(𝑐𝑖−𝑑𝑖)𝐯𝑖=𝟎, so ∑𝑖(𝑐𝑖−𝑑𝑖)𝐰𝑖=𝟎 by (a), and the two definitions agree. So 𝑆 is well defined, and it is linear because ∑𝑖𝑐𝑖𝐯𝑖+𝑎∑𝑖𝑑𝑖𝐯𝑖=∑𝑖(𝑐𝑖+𝑎𝑑𝑖)𝐯𝑖 is sent to ∑𝑖(𝑐𝑖+𝑎𝑑𝑖)𝐰𝑖. Clearly 𝑆𝐯𝑖=𝐰𝑖.

𝑆 preserves inner products. For 𝐱=∑𝑗𝑐𝑗𝐯𝑗 and 𝐲=∑𝑖𝑑𝑖𝐯𝑖,

⟨𝑆𝐱,𝑆𝐲⟩=∑𝑖,𝑗𝑐𝑗𝑑𝑖⟨𝐰𝑗,𝐰𝑖⟩=∑𝑖,𝑗𝑐𝑗𝑑𝑖⟨𝐯𝑗,𝐯𝑖⟩=⟨𝐱,𝐲⟩.

𝑆 is bijective. If 𝑆𝐱=𝟎, then ‖𝐱‖=‖𝑆𝐱‖=0, so 𝑆 is injective. Its image contains every 𝐰𝑖, hence their span, so 𝑆 is surjective.

(c) If 𝐵=𝑈𝐴 with 𝑈∗𝑈=𝐼𝑚, then 𝐵∗𝐵=𝐴∗𝑈∗𝑈𝐴=𝐴∗𝐴.

Conversely, suppose 𝐴∗𝐴=𝐵∗𝐵. By Theorem 6.3.29, 𝐴∗𝐴 is the Gram matrix of the columns 𝐚1,…,𝐚𝑛 of 𝐴, and 𝐵∗𝐵 that of the columns 𝐛1,…,𝐛𝑛 of 𝐵. By (b) there is a bijective linear 𝑆:im𝐴→im𝐵 with 𝑆𝐚𝑗=𝐛𝑗 that preserves inner products. In particular 𝑟=dimim𝐴=dimim𝐵.

Choose an orthonormal basis 𝐮1,…,𝐮𝑟 of im𝐴 (Theorem 6.4.20). Then 𝑆𝐮1,…,𝑆𝐮𝑟 is orthonormal in im𝐵, hence an orthonormal basis of it (Corollary 6.3.14). By Corollary 6.4.25, (im𝐴)⟂ and (im𝐵)⟂ both have dimension 𝑚−𝑟; choose orthonormal bases 𝐮𝑟+1,…,𝐮𝑚 and 𝐮𝑟+1′,…,𝐮𝑚′ of them. Vectors of im𝐴 are orthogonal to vectors of (im𝐴)⟂, so 𝐮1,…,𝐮𝑚 is an orthonormal list of length 𝑚, hence an orthonormal basis of 𝔽𝑚, and likewise for 𝑆𝐮1,…,𝑆𝐮𝑟,𝐮𝑟+1′,…,𝐮𝑚′. Let 𝑈1 and 𝑈2 be the unitary matrices with these columns (Definition 6.3.33), and 𝑈=𝑈2𝑈1∗, which is unitary (Exercise 6.3.37). Since 𝑈1∗𝑈1=𝐼𝑚, 𝑈1∗𝐮𝑖=𝐞𝑖, so 𝑈𝐮𝑖=𝑈2𝐞𝑖=𝑆𝐮𝑖 for 𝑖≤𝑟. The linear maps 𝐱↦𝑈𝐱 and 𝑆 agree on a basis of im𝐴, so they agree on im𝐴, and 𝑈𝐚𝑗=𝑆𝐚𝑗=𝐛𝑗 for every 𝑗. That is, 𝑈𝐴=𝐵.

Over ℝ, (c) says that two lists of vectors in ℝ𝑚 with the same lengths and the same pairwise angles differ by an orthogonal matrix. The unitary 𝑈 is not unique when 𝑟<𝑚: it can be changed freely on (im𝐴)⟂.

Problem 6.10.hard Let 𝑉 be a finite-dimensional inner product space, and let 𝑈,𝑊 be subspaces with dim𝑈=dim𝑊. Give 𝑈 and 𝑊 the restricted inner products, and define 𝐴:𝑈→𝑊 and 𝐵:𝑊→𝑈 by 𝐴𝐮=Pr𝑊(𝐮) and 𝐵𝐰=Pr𝑈(𝐰).

  1. (a)Show that ⟨𝐴𝐮,𝐰⟩=⟨𝐮,𝐰⟩=⟨𝐮,𝐵𝐰⟩ for all 𝐮∈𝑈 and 𝐰∈𝑊. Conclude that 𝐵=𝐴∗.
  2. (b)Show that the following are equivalent:
    1. (i)𝑈∩𝑊⟂={𝟎};
    2. (ii)𝑊∩𝑈⟂={𝟎};
    3. (iii)𝐴 is bijective;
    4. (iv)𝐵 is bijective.
  3. (c)Show by an example that (i) and (ii) need not be equivalent when dim𝑈≠dim𝑊.

Solution.

Uses. Proposition 6.4.29 (The orthogonal projection as a linear map), Proposition 6.6.9 (Adjoints are unique and linear), Definition 6.6.8 (Adjoint), Corollary 6.6.22 (𝑇 and 𝑇∗ have the same rank), Corollary 4.2.18 (Injective if and only if surjective)

Techniques. Move an operator across the inner product (Technique 6.6.20), Dimension counting (Technique 4.2.24)

Hint 1. For (a), move Pr𝑊 across: ⟨Pr𝑊𝐮,𝐰⟩=⟨𝐮,Pr𝑊𝐰⟩, and Pr𝑊𝐰=𝐰.
Hint 2. For (b), compute ker𝐴. Then compare the ranks of 𝐴 and 𝐴∗.
Sketch. (a) ⟨Pr𝑊𝐮,𝐰⟩=⟨𝐮,Pr𝑊𝐰⟩=⟨𝐮,𝐰⟩, and symmetrically with 𝑈. So 𝐵 satisfies the defining identity of 𝐴∗. (b) ker𝐴=𝑈∩𝑊⟂ and ker𝐵=𝑊∩𝑈⟂; with dim𝑈=dim𝑊=𝑘, injective means bijective. rank𝐴∗=rank𝐴, so 𝐴 is bijective iff 𝐵 is. (c) 𝑈=span(𝐞1) and 𝑊=ℝ2.

(a) By Proposition 6.4.29(c) and (b), ⟨Pr𝑊𝐮,𝐰⟩=⟨𝐮,Pr𝑊𝐰⟩=⟨𝐮,𝐰⟩, since 𝐰∈𝑊. In the same way ⟨𝐮,Pr𝑈𝐰⟩=⟨Pr𝑈𝐮,𝐰⟩=⟨𝐮,𝐰⟩, since 𝐮∈𝑈. So ⟨𝐴𝐮,𝐰⟩=⟨𝐮,𝐵𝐰⟩ for all 𝐮∈𝑈 and 𝐰∈𝑊, which says that 𝐵 is an adjoint of 𝐴 (Definition 6.6.8); by Proposition 6.6.9, 𝐵=𝐴∗.

(b) Let 𝑘=dim𝑈=dim𝑊. By Proposition 6.4.29(a), kerPr𝑊=𝑊⟂, so ker𝐴=𝑈∩𝑊⟂; likewise ker𝐵=𝑊∩𝑈⟂. So (i) says that 𝐴 is injective, and (ii) that 𝐵 is injective. Since 𝐴 maps between spaces of the same dimension 𝑘, it is injective if and only if it is bijective (Corollary 4.2.18), and the same holds for 𝐵. So (i) ⟺ (iii) and (ii) ⟺ (iv). Finally, by (a) and Corollary 6.6.22, rank𝐵=rank𝐴∗=rank𝐴, and a map between 𝑘-dimensional spaces is bijective exactly when its rank is 𝑘. So (iii) ⟺ (iv).

(c) In 𝑉=ℝ2, let 𝑈=span(𝐞1) and 𝑊=ℝ2. Then 𝑊⟂={𝟎}, so 𝑈∩𝑊⟂={𝟎}, but 𝑊∩𝑈⟂=span(𝐞2)≠{𝟎}.

Condition (i) says that no nonzero vector of 𝑈 is perpendicular to all of 𝑊. Part (b) says that for subspaces of equal dimension this relation is symmetric, which is not obvious from the definition; the proof gets the symmetry from rank𝐴∗=rank𝐴. For two lines in ℝ3, both conditions say that the lines are not perpendicular. In orthonormal bases of 𝑈 and 𝑊, the matrix of 𝐴 has entries ⟨𝐮𝑗,𝐰𝑖⟩, and its singular values (Section 9.1) are the cosines of the principal angles between 𝑈 and 𝑊.

Problem 6.11.hard Give 𝔽𝑛×𝑛 the Frobenius inner product ⟨𝑋,𝑌⟩=tr(𝑌∗𝑋) (Proposition 6.1.16). Let 𝐶 be the span of all commutators 𝑋𝑌−𝑌𝑋 with 𝑋,𝑌∈𝔽𝑛×𝑛, and let 𝑍={𝐴∈𝔽𝑛×𝑛|tr𝐴=0}.

  1. (a)Show that 𝐶⊆𝑍 and that 𝑍=span(𝐼𝑛)⟂.
  2. (b)Show that ⟨𝑋𝑌−𝑌𝑋,𝑀⟩=⟨𝑌,𝑋∗𝑀−𝑀𝑋∗⟩ for all 𝑋,𝑌,𝑀. Deduce that every 𝑀∈𝐶⟂ commutes with every matrix.
  3. (c)Deduce that 𝐶=𝑍: every matrix of trace 0 is a sum of commutators.
  4. (d)Give a second proof of 𝐶=𝑍, valid over every field 𝐹, by writing each matrix in the spanning list of 𝑍 found in Example 2.6.28 as a commutator of matrix units.

Solution.

Uses. Proposition 2.4.28 (Cyclicity of the trace), Proposition 6.3.9 (Properties of 𝐴⟂), Proposition 6.3.27 (Properties of the conjugate transpose), Proposition 6.1.37 (Inner products distinguish vectors), Exercise 2.4.43, Theorem 6.4.26 (The double complement), Lemma 2.4.24 (Matrix units), Example 2.6.28 (The trace)

Techniques. Cyclicity of trace (Technique 2.4.29), Show a vector is zero via its norm (Technique 6.1.36)

Hint 1. (a) tr(𝑋𝑌)=tr(𝑌𝑋), and ⟨𝐴,𝐼𝑛⟩=tr𝐴.
Hint 2. (b) Write ⟨𝑋𝑌−𝑌𝑋,𝑀⟩=tr(𝑀∗𝑋𝑌)−tr(𝑀∗𝑌𝑋) and move 𝑋 cyclically in the second term. If the result vanishes for every 𝑌, test with 𝑌=𝑋∗𝑀−𝑀𝑋∗.
Hint 3. (c) (b) shows 𝐶⟂⊆span(𝐼𝑛). Take perps. (d) 𝑈𝑖𝑗=𝑈𝑖𝑖𝑈𝑖𝑗−𝑈𝑖𝑗𝑈𝑖𝑖 for 𝑖≠𝑗.
Sketch. (a) Commutators have trace 0, and tr𝐴=⟨𝐴,𝐼𝑛⟩. (b) By cyclicity, ⟨𝑋𝑌−𝑌𝑋,𝑀⟩=tr((𝑀∗𝑋−𝑋𝑀∗)𝑌)=⟨𝑌,𝑋∗𝑀−𝑀𝑋∗⟩; for 𝑀∈𝐶⟂, choosing 𝑌=𝑋∗𝑀−𝑀𝑋∗ gives 𝑋∗𝑀=𝑀𝑋∗ for all 𝑋, so 𝑀 is scalar. (c) 𝐶⟂=span(𝐼𝑛), so 𝐶=(𝐶⟂)⟂=span(𝐼𝑛)⟂=𝑍. (d) 𝑈𝑖𝑗=𝑈𝑖𝑖𝑈𝑖𝑗−𝑈𝑖𝑗𝑈𝑖𝑖 and 𝑈𝑖𝑖−𝑈𝑛𝑛=𝑈𝑖𝑛𝑈𝑛𝑖−𝑈𝑛𝑖𝑈𝑖𝑛.

(a) By Proposition 2.4.28, tr(𝑋𝑌−𝑌𝑋)=0, so every commutator lies in the subspace 𝑍, and so does their span 𝐶. For every 𝐴, ⟨𝐴,𝐼𝑛⟩=tr(𝐼𝑛∗𝐴)=tr𝐴, so 𝑍={𝐼𝑛}⟂=span(𝐼𝑛)⟂ (Proposition 6.3.9(c)).

(b) By Proposition 2.4.28, tr(𝑀∗𝑌𝑋)=tr(𝑋𝑀∗𝑌), so

⟨𝑋𝑌−𝑌𝑋,𝑀⟩=tr(𝑀∗𝑋𝑌)−tr(𝑋𝑀∗𝑌)=tr((𝑀∗𝑋−𝑋𝑀∗)𝑌).

Let 𝑁=𝑋∗𝑀−𝑀𝑋∗. By Proposition 6.3.27, 𝑁∗=𝑀∗𝑋−𝑋𝑀∗, so the right side is tr(𝑁∗𝑌)=⟨𝑌,𝑁⟩, as claimed.

Now let 𝑀∈𝐶⟂ and fix 𝑋. Then ⟨𝑌,𝑁⟩=0 for every 𝑌, and 𝑌=𝑁 gives 𝑁=0 (Proposition 6.1.37), that is, 𝑋∗𝑀=𝑀𝑋∗. As 𝑋 runs over 𝔽𝑛×𝑛 so does 𝑋∗, since 𝑋=(𝑋∗)∗. So 𝑀 commutes with every matrix.

(c) By (b) and Exercise 2.4.43 (a matrix that commutes with every upper triangular matrix is a scalar multiple of 𝐼𝑛; for 𝑛=1 every matrix is), 𝐶⟂⊆span(𝐼𝑛). Conversely 𝐼𝑛∈𝐶⟂, since ⟨𝑋𝑌−𝑌𝑋,𝐼𝑛⟩=tr(𝑋𝑌−𝑌𝑋)=0. So 𝐶⟂=span(𝐼𝑛), and by Theorem 6.4.26 and (a),

𝐶=(𝐶⟂)⟂=span(𝐼𝑛)⟂=𝑍.

(d) Write 𝑈𝑖𝑗=𝐞𝑖𝐞𝑗𝖳, so that 𝑈𝑖𝑗𝑈𝑘𝑙=𝛿𝑗𝑘𝑈𝑖𝑙 (Lemma 2.4.24). For 𝑖≠𝑗,

𝑈𝑖𝑖𝑈𝑖𝑗−𝑈𝑖𝑗𝑈𝑖𝑖=𝑈𝑖𝑗−0=𝑈𝑖𝑗,

and for 𝑖≠𝑛,

𝑈𝑖𝑛𝑈𝑛𝑖−𝑈𝑛𝑖𝑈𝑖𝑛=𝑈𝑖𝑖−𝑈𝑛𝑛.

By Example 2.6.28, these matrices span 𝑍, so 𝑍⊆𝐶, and 𝐶⊆𝑍 holds over every field by Proposition 2.4.28.

The second proof is shorter and works over every field. The first illustrates a pattern: to show that a subspace 𝐶 is all of a given subspace, compute 𝐶⟂, and test a vector of 𝐶⟂ against everything. It needs an inner product, so it works only over ℝ and ℂ. (In fact every matrix of trace 0 over ℝ or ℂ is a single commutator, a theorem of Shoda that is much harder.)

Problem 6.12.hard Let 𝐴∈𝔽𝑚×𝑛.

  1. (a)Show that 𝐼𝑛+𝐴∗𝐴 is the Gram matrix of the columns 𝐜1,…,𝐜𝑛 of the matrix 𝐶∈𝔽(𝑛+𝑚)×𝑛 that has 𝐼𝑛 on top of 𝐴.
  2. (b)Show that det(𝐼𝑛+𝐴∗𝐴)≥1, with equality if and only if 𝐴=0.

Solution (by Gram–Schmidt).

Uses. Theorem 2.4.34 (Block multiplication), Theorem 6.3.29 (Orthonormal columns), Exercise 6.4.59, Theorem 6.4.15 (Gram–Schmidt is correct)

Techniques. Gram matrices (Technique 6.3.31), A sum of nonnegative terms (Technique 6.1.9)

Hint 1. For (b), Exercise 6.4.59 gives det𝐺=‖𝐟1‖2⋯‖𝐟𝑛‖2, where 𝐟𝑗 is the Gram–Schmidt residual of 𝐜𝑗.
Hint 2. 𝐟𝑗 is 𝐜𝑗 minus a combination of 𝐜1,…,𝐜𝑗−1. What is its 𝑗th coordinate?
Sketch. (a) 𝐶∗𝐶=𝐼𝑛∗𝐼𝑛+𝐴∗𝐴 by block multiplication. (b) The columns are independent. The residual 𝐟𝑗=𝐜𝑗−∑𝑖<𝑗𝛽𝑖𝐜𝑖 has 𝑗th coordinate 1, since 𝐜𝑖 has 𝑗th coordinate 0 for 𝑖<𝑗; so ‖𝐟𝑗‖≥1 and det𝐺≥1. Equality forces 𝐟𝑗=𝐞𝑗 for all 𝑗, so span(𝐜1,…,𝐜𝑛)=span(𝐞1,…,𝐞𝑛), and the lower block 𝐴 is 0.

(a) 𝐶∗=(𝐼𝑛 𝐴∗), so by Theorem 2.4.34 𝐶∗𝐶=𝐼𝑛𝐼𝑛+𝐴∗𝐴=𝐼𝑛+𝐴∗𝐴, and 𝐶∗𝐶 is the Gram matrix of the columns of 𝐶 (Theorem 6.3.29).

(b) Write 𝐜𝑗=(𝐞𝑗,𝐚𝑗), where 𝐚𝑗 is column 𝑗 of 𝐴. Coordinate 𝑖 of 𝐜𝑗 is 𝛿𝑖𝑗 for 𝑖≤𝑛, so the columns are independent. Run Gram–Schmidt on them, with residuals 𝐟1,…,𝐟𝑛. By Exercise 6.4.59(b),

det(𝐼𝑛+𝐴∗𝐴)=‖𝐟1‖2⋯‖𝐟𝑛‖2.

The residual 𝐟𝑗 is 𝐜𝑗 minus its projection onto span(𝐜1,…,𝐜𝑗−1), so 𝐟𝑗=𝐜𝑗−∑𝑖<𝑗𝛽𝑖𝐜𝑖 for some scalars 𝛽𝑖. Coordinate 𝑗 of 𝐜𝑗 is 1, and that of 𝐜𝑖 is 0 for 𝑖<𝑗, so coordinate 𝑗 of 𝐟𝑗 is 1. Since ‖𝐟𝑗‖2 is the sum of the squared moduli of its coordinates, ‖𝐟𝑗‖2≥1, and det(𝐼𝑛+𝐴∗𝐴)≥1.

If equality holds, then every ‖𝐟𝑗‖=1, so 𝐟𝑗 has no coordinate other than the 𝑗th, and 𝐟𝑗=𝐞𝑗∈𝔽𝑛+𝑚. By Theorem 6.4.15(a), span(𝐜1,…,𝐜𝑛)=span(𝐟1,…,𝐟𝑛), which consists of vectors whose last 𝑚 coordinates vanish. So every 𝐚𝑗=𝟎, and 𝐴=0. Conversely det(𝐼𝑛+0)=1.

Solution (by the Cauchy–Binet formula).Beyond 21-242

Hint 1. Apply Cauchy–Binet to 𝐶∗𝐶: it is a sum over the 𝑛-element sets 𝑆 of rows of 𝐶.
Hint 2. The set 𝑆={1,…,𝑛} contributes 1. For the equality case, find a set 𝑆 whose minor is ±𝑎𝑖𝑗.
Sketch. det(𝐶∗𝐶)=∑𝑆|det𝐶𝑆|2, where 𝐶𝑆 consists of the rows of 𝐶 indexed by 𝑆; the term 𝑆=[𝑛] is det𝐼𝑛=1. The rows [𝑛]∖{𝑗} together with row 𝑛+𝑖 give a minor ±𝑎𝑖𝑗, so equality forces 𝐴=0.

For an 𝑛-element set 𝑆⊆[𝑛+𝑚], let 𝐶𝑆 be the 𝑛×𝑛 matrix formed by the rows of 𝐶 with indices in 𝑆. The columns of 𝐶∗ with indices in 𝑆 form 𝐶𝑆∗, so by Exercise 5.5.52 and Exercise 6.3.57(a),

det(𝐶∗𝐶)=∑𝑆det(𝐶𝑆∗)det(𝐶𝑆)=∑𝑆|det𝐶𝑆|2.

The term 𝑆={1,…,𝑛} is |det𝐼𝑛|2=1, and the others are nonnegative, so det(𝐼𝑛+𝐴∗𝐴)≥1. For equality, every other minor must vanish. Take 𝑆=([𝑛]∖{𝑗})∪{𝑛+𝑖}. Then 𝐶𝑆 consists of the rows 𝐞𝑘𝖳 for 𝑘≠𝑗, in order, followed by row 𝑖 of 𝐴. Moving that last row up to position 𝑗 changes det𝐶𝑆 by a sign, and gives 𝐼𝑛 with row 𝑗 replaced by row 𝑖 of 𝐴. Subtracting 𝑎𝑖𝑘 times row 𝑘 from row 𝑗 for every 𝑘≠𝑗 does not change the determinant (Corollary 5.4.15) and leaves a diagonal matrix whose only diagonal entry other than 1 is 𝑎𝑖𝑗. So det𝐶𝑆=±𝑎𝑖𝑗. So |𝑎𝑖𝑗|2 occurs in the sum, and equality forces every 𝑎𝑖𝑗=0.

The first approach is the geometric one: each column 𝐜𝑗 sticks out of the span of the previous ones by at least 1, because of its identity part. The second expands the determinant into squares, one of which is the 1 coming from 𝐼𝑛. Either way, 𝐼𝑛+𝐴∗𝐴 is invertible for every 𝐴, which Exercise 5.6.12(c) proved for real 𝐴 through the kernel; in terms of the singular values of Section 9.1, det(𝐼𝑛+𝐴∗𝐴)=∏𝑖(1+𝜎𝑖2).

Problem 6.13.hard Let 𝑉 be a real inner product space of dimension 𝑛≥1, and let 𝐯1,…,𝐯𝑚∈𝑉 be nonzero vectors with ⟨𝐯𝑖,𝐯𝑗⟩≤0 for all 𝑖≠𝑗. Show that 𝑚≤2𝑛, and give an example with 𝑚=2𝑛.

Solution.

Hint 1. Induct on 𝑛. For the step, project 𝐯1,…,𝐯𝑚−1 onto 𝐯𝑚⟂, which has dimension 𝑛−1.
Hint 2. The projections 𝐰𝑖=𝐯𝑖−(⟨𝐯𝑖,𝐯𝑚⟩/‖𝐯𝑚‖2)𝐯𝑚 still have ⟨𝐰𝑖,𝐰𝑗⟩≤0. How many of them can be 𝟎?
Sketch. For 𝑛=1, three nonzero real multiples of one vector include two of the same sign. For the step, with 𝐮=𝐯𝑚, the parts 𝐰𝑖 of 𝐯𝑖 orthogonal to 𝐮 satisfy ⟨𝐰𝑖,𝐰𝑗⟩=⟨𝐯𝑖,𝐯𝑗⟩−⟨𝐯𝑖,𝐮⟩⟨𝐯𝑗,𝐮⟩/‖𝐮‖2≤0. If two were 𝟎, the corresponding 𝐯𝑖,𝐯𝑗 would be negative multiples of 𝐮 with ⟨𝐯𝑖,𝐯𝑗⟩>0. So at least 𝑚−2 nonzero vectors in the (𝑛−1)-dimensional 𝐮⟂, and 𝑚−2≤2(𝑛−1). Example: ±𝐞1,…,±𝐞𝑛.

We induct on 𝑛.

𝑛=1. Then 𝑉=span(𝐮) for any nonzero 𝐮, and 𝐯𝑖=𝑡𝑖𝐮 with 𝑡𝑖≠0, so ⟨𝐯𝑖,𝐯𝑗⟩=𝑡𝑖𝑡𝑗‖𝐮‖2. If 𝑚≥3, two of 𝑡1,𝑡2,𝑡3 have the same sign, and their vectors have a positive inner product. So 𝑚≤2.

𝑛≥2. We may assume 𝑚≥2. Let 𝐮=𝐯𝑚, and for 𝑖<𝑚 let

𝐰𝑖=𝐯𝑖−𝜆𝑖𝐮,𝜆𝑖=⟨𝐯𝑖,𝐮⟩‖𝐮‖2≤0,

the part of 𝐯𝑖 orthogonal to 𝐮 (Technique 6.2.4). For 𝑖≠𝑗, both less than 𝑚,

⟨𝐰𝑖,𝐰𝑗⟩=⟨𝐯𝑖,𝐯𝑗⟩−𝜆𝑖⟨𝐮,𝐯𝑗⟩−𝜆𝑗⟨𝐯𝑖,𝐮⟩+𝜆𝑖𝜆𝑗‖𝐮‖2=⟨𝐯𝑖,𝐯𝑗⟩−𝜆𝑖𝜆𝑗‖𝐮‖2≤0,

since 𝜆𝑖𝜆𝑗≥0. If 𝐰𝑖=𝟎, then 𝐯𝑖=𝜆𝑖𝐮 with 𝜆𝑖<0 (it is ≤0, and nonzero because 𝐯𝑖≠𝟎). If this happened for two indices 𝑖≠𝑗, then ⟨𝐯𝑖,𝐯𝑗⟩=𝜆𝑖𝜆𝑗‖𝐮‖2>0, a contradiction. So at least 𝑚−2 of the vectors 𝐰1,…,𝐰𝑚−1 are nonzero. They lie in 𝐮⟂, a real inner product space of dimension 𝑛−1≥1 (Corollary 6.4.25), and have pairwise nonpositive inner products. By the induction hypothesis 𝑚−2≤2(𝑛−1), that is, 𝑚≤2𝑛.

Example. In ℝ𝑛, the 2𝑛 vectors ±𝐞1,…,±𝐞𝑛 have pairwise inner products 0 or −1.

With strict inequalities ⟨𝐯𝑖,𝐯𝑗⟩<0, the bound drops to 𝑛+1 (Exercise 6.4.62). The difference is visible in the proof: with strict inequalities, the projected vectors still have strictly negative inner products, and none of them can vanish once 𝑚≥3.

Problem 6.14.hardBeyond 21-242 (The kernel trick.) Let Φ∈ℝ𝑚×𝑁 have rows 𝛗1𝖳,…,𝛗𝑚𝖳 (the feature vectors of 𝑚 data points), let 𝐲∈ℝ𝑚, and let 𝐾=ΦΦ𝖳, the matrix with entries 𝛗𝑖⋅𝛗𝑗.

  1. (a)Show that the least-squares solution of minimal norm 𝐰+ of Φ𝐰=𝐲 (Proposition 6.5.27) lies in imΦ𝖳.
  2. (b)Show that for 𝛂∈ℝ𝑚, Φ𝖳𝛂 is a least-squares solution of Φ𝐰=𝐲 if and only if 𝛂 is a least-squares solution of 𝐾𝛂=𝐲. Deduce that 𝐰+=Φ𝖳𝛂 for every least-squares solution 𝛂 of 𝐾𝛂=𝐲, and that for any 𝛗∈ℝ𝑁,

    𝛗⋅𝐰+=∑𝑖=1𝑚𝛼𝑖𝛗⋅𝛗𝑖.
  3. (c)Data points 𝑡=−1,0,1 have values 𝐲=(0,1,3), and each point 𝑡 has the feature vector 𝛗(𝑡)=(1,2𝑡,𝑡2). Using only the kernel 𝑘(𝑠,𝑡)=𝛗(𝑠)⋅𝛗(𝑡), compute 𝐾, 𝛂, and the fitted function 𝑡↦𝛗(𝑡)⋅𝐰+.

Solution.

Uses. Proposition 6.5.27 (The least-squares solution of minimal norm), Theorem 6.6.21 (Kernels and images of adjoints), Example 6.6.10 (The adjoint of a matrix), Theorem 6.5.5 (The normal equations), Proposition 6.5.9 (rank(𝐴∗𝐴)=rank𝐴)

Techniques. Move an operator across the inner product (Technique 6.6.20)

Hint 1. (a) 𝐰+ lies in (kerΦ)⟂. Which subspace is that?
Hint 2. (b) Write both conditions with the normal equations: Φ𝖳(𝐾𝛂−𝐲)=𝟎 and 𝐾(𝐾𝛂−𝐲)=𝟎. Then compare kerΦ𝖳 with ker𝐾.
Hint 3. (c) 𝑘(𝑠,𝑡)=1+2𝑠𝑡+𝑠2𝑡2=(1+𝑠𝑡)2, and 𝐾 turns out to be invertible.
Sketch. (a) 𝐰+∈(kerΦ)⟂=imΦ𝖳. (b) By the normal equations the two conditions say 𝐾𝛂−𝐲∈kerΦ𝖳 and 𝐾𝛂−𝐲∈ker𝐾, and ker𝐾=kerΦ𝖳 by Proposition 6.5.9(a) for Φ𝖳. So Φ𝖳𝛂 is a least-squares solution in imΦ𝖳=(kerΦ)⟂, which is 𝐰+. (c) 𝐾=(410111014), 𝛂=(−1,4,5)/8, and ∑𝑖𝛼𝑖(1+𝑡𝑡𝑖)2=1+3𝑡/2+𝑡2/2.

(a) By Proposition 6.5.27, 𝐰+ is the only least-squares solution in (kerΦ)⟂. With dot products, Φ𝖳 is the adjoint of Φ (Example 6.6.10), so (kerΦ)⟂=imΦ𝖳 by Theorem 6.6.21(c).

(b) By Theorem 6.5.5, Φ𝖳𝛂 is a least-squares solution of Φ𝐰=𝐲 if and only if Φ𝖳(ΦΦ𝖳𝛂−𝐲)=𝟎, that is, 𝐾𝛂−𝐲∈kerΦ𝖳. Since 𝐾𝖳=𝐾, 𝛂 is a least-squares solution of 𝐾𝛂=𝐲 if and only if 𝐾(𝐾𝛂−𝐲)=𝟎, that is, 𝐾𝛂−𝐲∈ker𝐾. By Proposition 6.5.9(a) applied to Φ𝖳, ker𝐾=ker((Φ𝖳)𝖳Φ𝖳)=kerΦ𝖳. So the two conditions agree.

If 𝛂 is a least-squares solution of 𝐾𝛂=𝐲, then Φ𝖳𝛂 is a least-squares solution of Φ𝐰=𝐲 that lies in imΦ𝖳=(kerΦ)⟂, so it is 𝐰+ by the uniqueness in Proposition 6.5.27. Since Φ𝖳𝛂=∑𝑖𝛼𝑖𝛗𝑖, we get 𝛗⋅𝐰+=∑𝑖𝛼𝑖𝛗⋅𝛗𝑖.

(c) 𝑘(𝑠,𝑡)=1+2𝑠𝑡+𝑠2𝑡2=(1+𝑠𝑡)2. For 𝑡1,𝑡2,𝑡3=−1,0,1,

𝐾=(410111014),det𝐾=8,𝐾−1=18(3−41−416−41−43).

𝐾 is invertible, so the least-squares solution of 𝐾𝛂=𝐲 is 𝛂=𝐾−1𝐲=(1/8)(−1,4,5). By (b), the fitted function is

∑𝑖𝛼𝑖𝑘(𝑡,𝑡𝑖)=18(−(1−𝑡)2+4+5(1+𝑡)2)=1+32𝑡+12𝑡2,

which takes the values 0,1,3 at −1,0,1. Explicitly, 𝐰+=Φ𝖳𝛂=(1,32/4,1/2), and 𝛗(𝑡)⋅𝐰+ is the same polynomial.

The point is that 𝑁 never appeared in the computation. The fit needs the 𝑚×𝑚 matrix 𝐾 and the values 𝑘(𝛗,𝛗𝑖) only, so the feature space can be huge, or even infinite-dimensional, as long as its inner products are cheap to compute. Section 16.1 develops this.

Problem 6.15.hard For a continuous 𝑓:[0,1]→ℝ, let

𝐼(𝑓)=∫01𝑥2𝑓(𝑥)d𝑥and𝐽(𝑓)=∫01𝑥𝑓(𝑥)2d𝑥.

Find the largest value of 𝐼(𝑓)−𝐽(𝑓) over all such 𝑓, and the functions attaining it.

Solution.

Uses. Proposition 6.1.13 (Integral inner products), Lemma 6.1.14 (Nonnegative functions with zero integral), Proposition 6.1.29 (Expanding a norm)

Techniques. Apply Cauchy–Schwarz to a well-chosen inner product (Technique 6.2.21), A sum of nonnegative terms (Technique 6.1.9)

Hint 1. Find an inner product on 𝐶[0,1] for which 𝐽(𝑓)=‖𝑓‖2. Then write 𝐼(𝑓) as an inner product of 𝑓 with a fixed function.
Hint 2. With ⟨𝑓,𝑔⟩=∫01𝑥𝑓(𝑥)𝑔(𝑥)d𝑥 and ℎ(𝑥)=𝑥, 𝐼(𝑓)−𝐽(𝑓)=⟨𝑓,ℎ⟩−‖𝑓‖2. Complete the square.
Sketch. ⟨𝑓,𝑔⟩=∫01𝑥𝑓𝑔 is an inner product, 𝐽(𝑓)=‖𝑓‖2, and 𝐼(𝑓)=⟨𝑓,ℎ⟩ for ℎ(𝑥)=𝑥. Then 𝐼(𝑓)−𝐽(𝑓)=‖ℎ‖2/4−‖𝑓−ℎ/2‖2≤‖ℎ‖2/4=(1/4)∫01𝑥3d𝑥=1/16, with equality exactly for 𝑓(𝑥)=𝑥/2.

Let ⟨𝑓,𝑔⟩=∫01𝑥𝑓(𝑥)𝑔(𝑥)d𝑥 on 𝐶[0,1]. It is bilinear and symmetric, and ⟨𝑓,𝑓⟩=∫01𝑥𝑓(𝑥)2d𝑥≥0. If ⟨𝑓,𝑓⟩=0, then the continuous nonnegative function 𝑥𝑓(𝑥)2 is 0 (Lemma 6.1.14, as in the proof of Proposition 6.1.13), so 𝑓(𝑥)=0 for 0<𝑥≤1, and 𝑓(0)=0 by continuity. So this is an inner product.

With ℎ(𝑥)=𝑥, 𝐼(𝑓)=∫01𝑥⋅𝑥𝑓(𝑥)d𝑥=⟨𝑓,ℎ⟩ and 𝐽(𝑓)=‖𝑓‖2. By Proposition 6.1.29,

‖𝑓−ℎ2‖2=‖𝑓‖2−⟨𝑓,ℎ⟩+14‖ℎ‖2,

so

𝐼(𝑓)−𝐽(𝑓)=14‖ℎ‖2−‖𝑓−ℎ2‖2≤14‖ℎ‖2=14∫01𝑥3d𝑥=116,

with equality if and only if 𝑓=ℎ/2, that is, 𝑓(𝑥)=𝑥/2. The largest value is 1/16.

Pointwise, the identity is 𝑥2𝑓−𝑥𝑓2=𝑥3/4−𝑥(𝑓−𝑥/2)2, and integrating it gives the same proof without naming an inner product. The inner product explains where the identity comes from: the maximum of ⟨𝑓,ℎ⟩−‖𝑓‖2 over a whole inner product space is found by completing the square, and the weight 𝑥 in 𝐽 tells us which inner product to use. One can also use Cauchy–Schwarz, 𝐼(𝑓)≤‖𝑓‖‖ℎ‖, and then maximize 𝑠‖ℎ‖−𝑠2 over 𝑠=‖𝑓‖≥0.

This is Problem B5 of the 2006 Putnam Competition.

Problem 6.16.hard Let 𝑎,𝑏,𝑐 be positive real numbers with 𝑎𝑏𝑐=1. Show that

1𝑎3(𝑏+𝑐)+1𝑏3(𝑐+𝑎)+1𝑐3(𝑎+𝑏)≥32,

and find when equality holds.

Solution.

Hint 1. Substitute 𝑥=1/𝑎, 𝑦=1/𝑏, 𝑧=1/𝑐, so that 𝑥𝑦𝑧=1. What does the first term become?
Hint 2. The sum becomes 𝑥2/(𝑦+𝑧)+𝑦2/(𝑧+𝑥)+𝑧2/(𝑥+𝑦). Apply Corollary 6.2.26, and then show 𝑥+𝑦+𝑧≥3 when 𝑥𝑦𝑧=1.
Hint 3. For the last step, with 𝑥=𝑝3, 𝑦=𝑞3, 𝑧=𝑟3: 𝑝3+𝑞3+𝑟3−3𝑝𝑞𝑟=12(𝑝+𝑞+𝑟)((𝑝−𝑞)2+(𝑞−𝑟)2+(𝑟−𝑝)2).
Sketch. With 𝑥=1/𝑎 etc., 1/(𝑎3(𝑏+𝑐))=𝑥3𝑦𝑧/(𝑦+𝑧)=𝑥2/(𝑦+𝑧). By Engel’s form of Cauchy–Schwarz, the sum is at least (𝑥+𝑦+𝑧)2/(2(𝑥+𝑦+𝑧))=(𝑥+𝑦+𝑧)/2, and 𝑥+𝑦+𝑧≥3𝑥𝑦𝑧3=3 by the sum-of-squares identity for 𝑝3+𝑞3+𝑟3−3𝑝𝑞𝑟. Equality iff 𝑎=𝑏=𝑐=1.

Let 𝑥=1/𝑎, 𝑦=1/𝑏, 𝑧=1/𝑐, positive with 𝑥𝑦𝑧=1. Then

1𝑎3(𝑏+𝑐)=𝑥31/𝑦+1/𝑧=𝑥3𝑦𝑧𝑦+𝑧=𝑥2𝑦+𝑧,

and similarly for the other terms. By Corollary 6.2.26, with numerators 𝑥,𝑦,𝑧 and denominators 𝑦+𝑧, 𝑧+𝑥, 𝑥+𝑦,

𝑥2𝑦+𝑧+𝑦2𝑧+𝑥+𝑧2𝑥+𝑦≥(𝑥+𝑦+𝑧)22(𝑥+𝑦+𝑧)=𝑥+𝑦+𝑧2.

That is Cauchy–Schwarz for the vectors (𝑥/𝑦+𝑧,…) and (𝑦+𝑧,…), chosen so that their inner product is 𝑥+𝑦+𝑧 (Technique 6.2.21).

It remains to show 𝑥+𝑦+𝑧≥3. Let 𝑝,𝑞,𝑟>0 with 𝑝3=𝑥, 𝑞3=𝑦, 𝑟3=𝑧, so that 𝑝𝑞𝑟=1. Multiplying out,

𝑝3+𝑞3+𝑟3−3𝑝𝑞𝑟=(𝑝+𝑞+𝑟)(𝑝2+𝑞2+𝑟2−𝑝𝑞−𝑞𝑟−𝑟𝑝)=12(𝑝+𝑞+𝑟)((𝑝−𝑞)2+(𝑞−𝑟)2+(𝑟−𝑝)2),

which is ≥0, with equality only if 𝑝=𝑞=𝑟 (Technique 6.1.9). So 𝑥+𝑦+𝑧≥3𝑝𝑞𝑟=3, and the sum is at least 3/2.

If equality holds, then 𝑥+𝑦+𝑧=3, which forces 𝑝=𝑞=𝑟, hence 𝑥=𝑦=𝑧=1 and 𝑎=𝑏=𝑐=1. Conversely, at 𝑎=𝑏=𝑐=1 every term is 1/2.

This is Problem 2 of the 1995 International Mathematical Olympiad. The substitution is the real idea; after it, the problem is the same Engel-form estimate as Nesbitt’s inequality (Exercise 6.2.47).

Problem 6.17.challengeBeyond 21-242 Let 𝐺∈𝔽𝑘×𝑘 satisfy 𝐺∗=𝐺 and 𝐜∗𝐺𝐜≥0 for every 𝐜∈𝔽𝑘. For 𝐜,𝐝∈𝔽𝑘, let 𝛽(𝐜,𝐝)=𝐝∗𝐺𝐜.

  1. (a)Show that |𝛽(𝐜,𝐝)|2≤𝛽(𝐜,𝐜)𝛽(𝐝,𝐝) for all 𝐜,𝐝. (Decide which proof of Theorem 6.2.1 survives without definiteness.)
  2. (b)Show that 𝛽(𝐜,𝐜)=0 if and only if 𝐺𝐜=𝟎.
  3. (c)On the quotient space 𝑉=𝔽𝑘/ker𝐺 (Definition 4.6.20), show that ⟨[𝐜],[𝐝]⟩=𝐝∗𝐺𝐜 is well defined and is an inner product, and that 𝐺 is the Gram matrix of [𝐞1],…,[𝐞𝑘].
  4. (d)Deduce that a matrix 𝐺 with 𝐺∗=𝐺 is the Gram matrix of a list in some inner product space if and only if 𝐜∗𝐺𝐜≥0 for all 𝐜, if and only if 𝐺=𝐵∗𝐵 for some 𝐵∈𝔽𝑟×𝑘, where one can take 𝑟=rank𝐺.

Solution.

Uses. Lemma 6.2.6 (Nonnegative quadratics), Proposition 6.3.30 (Gram matrices detect independence), Theorem 6.3.22 (Parseval’s identity), Theorem 6.3.29 (Orthonormal columns), Proposition 6.5.9 (rank(𝐴∗𝐴)=rank𝐴), Theorem 6.4.20 (Orthonormal bases exist)

Techniques. A nonnegative quadratic has nonpositive discriminant (Technique 6.2.7), Pass to orthonormal coordinates (Technique 6.7.2)

Hint 1. (a) Run the second proof of Theorem 6.2.1: rotate the phase, then look at 𝛽(𝜆𝐜−𝑡𝐝,𝜆𝐜−𝑡𝐝) for real 𝑡. Treat 𝛽(𝐝,𝐝)=0 separately: a linear function of 𝑡 that is never negative is constant.
Hint 2. (b) If 𝛽(𝐜,𝐜)=0, (a) gives 𝛽(𝐜,𝐝)=0 for every 𝐝. Take 𝐝=𝐺𝐜.
Hint 3. (c) For well-definedness in the second slot, use 𝐺∗=𝐺. For (d), choose an orthonormal basis of 𝑉 and record the coordinates of the classes [𝐞𝑗].
Sketch. (a) With |𝜆|=1 and 𝜆𝛽(𝐜,𝐝)=|𝛽(𝐜,𝐝)|, 0≤𝛽(𝜆𝐜−𝑡𝐝,𝜆𝐜−𝑡𝐝)=𝛽(𝐜,𝐜)−2𝑡|𝛽(𝐜,𝐝)|+𝑡2𝛽(𝐝,𝐝) for real 𝑡; the discriminant gives (a) if 𝛽(𝐝,𝐝)>0, and a linear function bounded below gives 𝛽(𝐜,𝐝)=0 otherwise. (b) Then (𝐺𝐜)∗𝐺𝐜=0. (c) Changing representatives changes 𝐝∗𝐺𝐜 by terms with 𝐺𝐳=𝟎; definiteness is (b). (d) An orthonormal basis of 𝑉 turns [𝐞1],…,[𝐞𝑘] into the columns of 𝐵∈𝔽𝑟×𝑘 with 𝐵∗𝐵=𝐺, and 𝑟=rank𝐵=rank𝐵∗𝐵=rank𝐺.

The function 𝛽 is linear in 𝐜, and 𝛽(𝐝,𝐜)=𝐜∗𝐺𝐝=(𝐝∗𝐺∗𝐜)∗=𝛽(𝐜,𝐝), using 𝐺∗=𝐺. So 𝛽 satisfies every axiom of an inner product except possibly definiteness.

(a) The second proof of Theorem 6.2.1 uses definiteness only to know that ‖𝐲‖2>0, so we follow it and handle that case separately. Choose 𝜆∈𝔽 with |𝜆|=1 and 𝜆𝛽(𝐜,𝐝)=|𝛽(𝐜,𝐝)|. For real 𝑡, expanding as in Proposition 6.1.29,

0≤𝛽(𝜆𝐜−𝑡𝐝,𝜆𝐜−𝑡𝐝)=𝛽(𝐜,𝐜)−2𝑡|𝛽(𝐜,𝐝)|+𝑡2𝛽(𝐝,𝐝).

If 𝛽(𝐝,𝐝)>0, Lemma 6.2.6 gives |𝛽(𝐜,𝐝)|2≤𝛽(𝐜,𝐜)𝛽(𝐝,𝐝). If 𝛽(𝐝,𝐝)=0, the right side is 𝛽(𝐜,𝐜)−2𝑡|𝛽(𝐜,𝐝)|, which is nonnegative for every real 𝑡 only if |𝛽(𝐜,𝐝)|=0 (otherwise take 𝑡 large). In both cases (a) holds. (The first proof of Theorem 6.2.1 divides by ‖𝐲‖2, and the third normalizes, so neither survives as it stands.)

(b) If 𝐺𝐜=𝟎, then 𝛽(𝐜,𝐜)=𝐜∗𝐺𝐜=0. Conversely, if 𝛽(𝐜,𝐜)=0, then (a) gives 𝛽(𝐜,𝐝)=0 for every 𝐝. With 𝐝=𝐺𝐜 this reads (𝐺𝐜)∗(𝐺𝐜)=0, the squared length of 𝐺𝐜 for the dot product, so 𝐺𝐜=𝟎.

(c) Let [𝐜]=[𝐜′] and [𝐝]=[𝐝′], that is, 𝐺(𝐜−𝐜′)=𝟎 and 𝐺(𝐝−𝐝′)=𝟎. Then

𝐝∗𝐺𝐜−𝐝′∗𝐺𝐜′=𝐝∗𝐺(𝐜−𝐜′)+(𝐝−𝐝′)∗𝐺𝐜′=0+(𝐺(𝐝−𝐝′))∗𝐜′=0,

using (𝐝−𝐝′)∗𝐺=(𝐺∗(𝐝−𝐝′))∗=(𝐺(𝐝−𝐝′))∗. So the formula is well defined. Linearity in the first slot and conjugate symmetry come from 𝛽, and ⟨[𝐜],[𝐜]⟩=𝛽(𝐜,𝐜)≥0. By (b), ⟨[𝐜],[𝐜]⟩=0 if and only if 𝐜∈ker𝐺, that is, [𝐜]=𝟎. So this is an inner product on 𝑉, and ⟨[𝐞𝑗],[𝐞𝑖]⟩=𝐞𝑖∗𝐺𝐞𝑗=𝑔𝑖𝑗.

(d) If 𝐺 is the Gram matrix of 𝐯1,…,𝐯𝑘, then 𝐜∗𝐺𝐜=‖∑𝑖𝑐𝑖𝐯𝑖‖2≥0 (Proposition 6.3.30(a)). Conversely, if 𝐜∗𝐺𝐜≥0 for all 𝐜, then by (c) 𝐺 is the Gram matrix of [𝐞1],…,[𝐞𝑘] in 𝑉. These classes span 𝑉, so 𝑉 is finite-dimensional; let 𝒪︀ be an orthonormal basis (Theorem 6.4.20), 𝑟=dim𝑉, and 𝐵∈𝔽𝑟×𝑘 the matrix with columns [[𝐞𝑗]]𝒪︀. By Theorem 6.3.22, (𝐵∗𝐵)𝑖𝑗=⟨[𝐞𝑗],[𝐞𝑖]⟩=𝑔𝑖𝑗, so 𝐺=𝐵∗𝐵 (Technique 6.7.2). Finally, if 𝐺=𝐵∗𝐵 for any 𝐵, then 𝐺 is the Gram matrix of the columns of 𝐵 (Theorem 6.3.29), closing the cycle. For the 𝐵 constructed above, the columns span 𝔽𝑟 (they are the coordinates of a spanning list of 𝑉), so rank𝐵=𝑟, and rank𝐺=rank(𝐵∗𝐵)=rank𝐵=𝑟 by Proposition 6.5.9(b).

Matrices with these properties are called positive semidefinite. Section 8.3 produces the factorization 𝐺=𝐵∗𝐵 differently, with 𝐵 a square root of 𝐺, and Exercise 6.7.12 is the case 𝐺=(1−𝑥)𝐼𝑛+𝑥𝐽. The quotient construction, dividing a semi-inner product by its null vectors, is also how inner product spaces of functions are built in analysis, where functions that differ only on a negligible set are identified.

Problem 6.18.challenge Let 𝒢︀ be a finite set of invertible matrices in ℝ𝑛×𝑛 that contains 𝐼𝑛 and is closed under multiplication and inverses, and let |𝒢︀| be the number of its elements.

  1. (a)Show that ⟨𝐱,𝐲⟩𝒢︀=∑𝑀∈𝒢︀(𝑀𝐱)⋅(𝑀𝐲) is an inner product on ℝ𝑛, and that ⟨𝑁𝐱,𝑁𝐲⟩𝒢︀=⟨𝐱,𝐲⟩𝒢︀ for every 𝑁∈𝒢︀.
  2. (b)Let 𝑃=|𝒢︀|−1∑𝑀∈𝒢︀𝑀. Show that 𝑁𝑃=𝑃 for every 𝑁∈𝒢︀, that 𝑃2=𝑃, and that 𝑃 is self-adjoint for ⟨⋅,⋅⟩𝒢︀.
  3. (c)Deduce that tr𝑃=rank𝑃. Conclude that if ∑𝑀∈𝒢︀tr𝑀=0, then ∑𝑀∈𝒢︀𝑀=0.
  4. (d)Show that there is an invertible 𝑆∈ℝ𝑛×𝑛 such that 𝑆−1𝑀𝑆 is orthogonal for every 𝑀∈𝒢︀.

Solution.

Uses. Proposition 6.1.10 (The dot product is an inner product), Definition 6.6.8 (Adjoint), Proposition 6.6.9 (Adjoints are unique and linear), Proposition 6.6.18 (Properties of the adjoint), Corollary 6.6.29 (Orthogonal projections are the self-adjoint idempotents), Proposition 6.4.29 (The orthogonal projection as a linear map), Theorem 6.4.20 (Orthonormal bases exist), Corollary 6.4.25 (Dimension of the orthogonal complement), Proposition 2.4.28 (Cyclicity of the trace), Theorem 6.3.22 (Parseval’s identity), Theorem 6.3.29 (Orthonormal columns)

Techniques. Move an operator across the inner product (Technique 6.6.20), Cyclicity of trace (Technique 2.4.29)

Hint 1. (a) and (b): for fixed 𝑁∈𝒢︀, the maps 𝑀↦𝑀𝑁, 𝑀↦𝑁𝑀, and 𝑀↦𝑀−1 are bijections of 𝒢︀, so sums over 𝒢︀ can be reindexed by them.
Hint 2. For self-adjointness, first show that the adjoint of 𝑁∈𝒢︀ for ⟨⋅,⋅⟩𝒢︀ is 𝑁−1.
Hint 3. (c) 𝑃 is an orthogonal projection for ⟨⋅,⋅⟩𝒢︀. Take an orthonormal basis for that inner product whose first vectors span im𝑃, and compute the trace of 𝑃 in it. (d) Use the same kind of basis as the columns of 𝑆.
Sketch. (a) Positivity: ⟨𝐱,𝐱⟩𝒢︀≥‖𝐼𝑛𝐱‖2. Invariance: reindex by 𝑀↦𝑀𝑁. (b) 𝑁𝑃=𝑃 by reindexing with 𝑀↦𝑁𝑀, so 𝑃2=|𝒢︀|−1∑𝑁𝑁𝑃=𝑃. For 𝑁∈𝒢︀, ⟨𝑁𝐱,𝐲⟩𝒢︀=⟨𝑁𝐱,𝑁𝑁−1𝐲⟩𝒢︀=⟨𝐱,𝑁−1𝐲⟩𝒢︀, so 𝑁∗=𝑁−1 and 𝑃∗=|𝒢︀|−1∑𝑁−1=𝑃. (c) 𝑃=Prim𝑃; in an adapted orthonormal basis 𝑃 is diag(1,…,1,0,…,0), so tr𝑃=rank𝑃 by cyclicity of trace. If tr𝑃=0, then 𝑃=0. (d) The columns of 𝑆 form an orthonormal basis for ⟨⋅,⋅⟩𝒢︀; 𝑆−1𝑀𝑆 is the matrix of 𝑀 in it, and 𝑀 preserves ⟨⋅,⋅⟩𝒢︀.

Fix 𝑁∈𝒢︀. The map 𝑀↦𝑀𝑁 sends 𝒢︀ into 𝒢︀ (closure) and is injective (𝑀𝑁=𝑀′𝑁 implies 𝑀=𝑀′), so it is a bijection of the finite set 𝒢︀. The same holds for 𝑀↦𝑁𝑀 and for 𝑀↦𝑀−1, which is its own inverse. So a sum over 𝒢︀ can be reindexed by any of these maps.

(a) Each term (𝑀𝐱)⋅(𝑀𝐲) is linear in 𝐱 and symmetric, and so is the sum. Since 𝐼𝑛∈𝒢︀, ⟨𝐱,𝐱⟩𝒢︀=∑𝑀‖𝑀𝐱‖2≥‖𝐱‖2, which is positive for 𝐱≠𝟎 (Proposition 6.1.10). So ⟨⋅,⋅⟩𝒢︀ is an inner product. Reindexing by 𝑀↦𝑀𝑁,

⟨𝑁𝐱,𝑁𝐲⟩𝒢︀=∑𝑀∈𝒢︀(𝑀𝑁𝐱)⋅(𝑀𝑁𝐲)=∑𝑀′∈𝒢︀(𝑀′𝐱)⋅(𝑀′𝐲)=⟨𝐱,𝐲⟩𝒢︀.

(b) Reindexing by 𝑀↦𝑁𝑀, 𝑁𝑃=|𝒢︀|−1∑𝑀𝑁𝑀=|𝒢︀|−1∑𝑀′𝑀′=𝑃. Hence

𝑃2=|𝒢︀|−1∑𝑁∈𝒢︀𝑁𝑃=|𝒢︀|−1∑𝑁∈𝒢︀𝑃=𝑃.

For 𝑁∈𝒢︀ and all 𝐱,𝐲, by (a) applied with 𝑁,

⟨𝑁𝐱,𝐲⟩𝒢︀=⟨𝑁𝐱,𝑁(𝑁−1𝐲)⟩𝒢︀=⟨𝐱,𝑁−1𝐲⟩𝒢︀,

so the adjoint of 𝐱↦𝑁𝐱 for ⟨⋅,⋅⟩𝒢︀ is 𝐱↦𝑁−1𝐱 (Definition 6.6.8, Proposition 6.6.9). Adjoints of sums and real multiples are the sums and multiples of the adjoints (Proposition 6.6.18), so the adjoint of 𝑃 is |𝒢︀|−1∑𝑁𝑁−1, which is 𝑃 after reindexing by 𝑁↦𝑁−1.

(c) By (b) and Corollary 6.6.29, 𝑃 is the orthogonal projection onto im𝑃 for the inner product ⟨⋅,⋅⟩𝒢︀. Let 𝑟=rank𝑃. By Theorem 6.4.20 and Corollary 6.4.25, there is a basis 𝐮1,…,𝐮𝑛 of ℝ𝑛, orthonormal for ⟨⋅,⋅⟩𝒢︀, with 𝐮1,…,𝐮𝑟 a basis of im𝑃 and 𝐮𝑟+1,…,𝐮𝑛 a basis of (im𝑃)⟂=ker𝑃 (Proposition 6.4.29(a)). So 𝑃𝐮𝑖=𝐮𝑖 for 𝑖≤𝑟 and 𝑃𝐮𝑖=𝟎 for 𝑖>𝑟. Let 𝑆 be the invertible matrix with columns 𝐮1,…,𝐮𝑛. Then 𝑃𝑆=𝑆𝐷 with 𝐷=diag(1,…,1,0,…,0) (𝑟 ones), so 𝑃=𝑆𝐷𝑆−1 and, by Proposition 2.4.28, tr𝑃=tr(𝐷𝑆−1𝑆)=tr𝐷=𝑟.

If ∑𝑀tr𝑀=0, then tr𝑃=|𝒢︀|−1∑𝑀tr𝑀=0, so rank𝑃=0, 𝑃=0, and ∑𝑀𝑀=|𝒢︀|𝑃=0.

(d) Take 𝑆 with columns 𝐮1,…,𝐮𝑛 forming any basis that is orthonormal for ⟨⋅,⋅⟩𝒢︀, as in (c). For 𝐱∈ℝ𝑛, 𝑆−1𝐱 is the coordinate vector of 𝐱 in this basis, since 𝑆(𝑆−1𝐱)=𝐱. By Theorem 6.3.22, ⟨𝐱,𝐲⟩𝒢︀=(𝑆−1𝐱)⋅(𝑆−1𝐲). Let 𝑀∈𝒢︀ and 𝑄=𝑆−1𝑀𝑆. Then for all 𝐚,𝐛∈ℝ𝑛, with 𝐱=𝑆𝐚 and 𝐲=𝑆𝐛,

(𝑄𝐚)⋅(𝑄𝐛)=(𝑆−1𝑀𝐱)⋅(𝑆−1𝑀𝐲)=⟨𝑀𝐱,𝑀𝐲⟩𝒢︀=⟨𝐱,𝐲⟩𝒢︀=𝐚⋅𝐛.

With 𝐚=𝐞𝑗 and 𝐛=𝐞𝑖, the columns of 𝑄 are orthonormal, so 𝑄 is orthogonal (Theorem 6.3.29).

By (c), 𝑃 is the orthogonal projection onto the vectors fixed by all of 𝒢︀: if 𝑀𝐱=𝐱 for all 𝑀 then 𝑃𝐱=𝐱, and conversely 𝑀𝑃𝐲=𝑃𝐲 by (b). The idempotence 𝑃2=𝑃 alone already gives tr𝑃=rank𝑃, by the decomposition ℝ𝑛=im𝑃⊕ker𝑃 of Section 4.4, so the inner product is not needed for the conclusion of (c). It explains what 𝑃 is, and it gives (d): every finite group of real matrices is conjugate to a group of orthogonal matrices. Averaging over the group in this way is the basic tool of the representation theory of finite groups.

This is Problem B6 of the 1985 Putnam Competition, in a slightly restricted form: the original allows any finite set of real matrices that forms a group under multiplication, whose identity element need not be 𝐼𝑛.