6.3 Orthogonality and orthonormal bases

For nonzero $𝐯, 𝐰 \in ℝ^{2}$ , $𝐯 \cdot 𝐰 = 0$ exactly when $𝐯$ and $𝐰$ are perpendicular ((6.1.1)), and in every real inner product space the angle between nonzero vectors (Definition 6.2.16) is a right angle exactly when $⟨ 𝐯, 𝐰 ⟩ = 0$ (Proposition 6.2.17). This section takes the condition $⟨ 𝐯, 𝐰 ⟩ = 0$ as the definition of perpendicularity, now over $ℝ$ and $ℂ$ alike, and studies bases made of perpendicular unit vectors. For such a basis, finding the coordinates of a vector requires no linear system: each coordinate is a single inner product, computed without reference to the others. Once the coordinates are known, lengths and inner products are computed from them exactly as in $𝔽^{𝑛}$ with the dot product. In $𝔽^{𝑛}$ these bases are the columns of the matrices $𝑈$ with $𝑈^{*} 𝑈 = 𝐼$ , and we end with the most important example after the standard basis, the Fourier basis of $ℂ^{𝑛}$ .

Throughout, $𝑉$ is an inner product space over $𝔽$ , where $𝔽$ is $ℝ$ or $ℂ$ (Notation 6.1.1).

6.3.1Orthogonality

Definition 6.3.1 (Orthogonality). Let

𝑉

be an inner product space. Vectors

𝐮, 𝐯 \in 𝑉

are orthogonal, written

𝐮 ⟂ 𝐯

, if

⟨ 𝐮, 𝐯 ⟩ = 0

. A list

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

𝑉

is orthogonal if

𝐯_{𝑖} ⟂ 𝐯_{𝑗}

whenever

𝑖 \neq 𝑗

Orthogonality is symmetric: $⟨ 𝐯, 𝐮 ⟩ = ⟨ 𝐮, 𝐯 ⟩$ , and a complex number vanishes exactly when its conjugate does. By Proposition 6.1.4(b), $𝟎$ is orthogonal to every vector, itself included, and by definiteness it is the only vector orthogonal to itself. It is also the only vector orthogonal to every vector of $𝑉$ : if $𝐯 ⟂ 𝐱$ for all $𝐱$ , take $𝐱 = 𝐯$ . (This is Proposition 6.1.37 with $𝐰 = 𝟎$ .)

In the definition of an orthogonal list only entries in different positions are compared. So a list of length $0$ or $1$ is orthogonal, an orthogonal list may contain $𝟎$ any number of times, and a nonzero vector cannot occur twice in an orthogonal list, since $⟨ 𝐯, 𝐯 ⟩ \neq 0$ .

Example 6.3.2 (Orthogonal vectors).

(a)In $ℝ^{2}$ , $(𝑎, 𝑏) ⟂ (- 𝑏, 𝑎)$ for all $𝑎, 𝑏$ , since $𝑎 (- 𝑏) + 𝑏 𝑎 = 0$ . The second vector is the first rotated by $𝜋 / 2$ . For instance $(1, 2) ⟂ (- 2, 1)$ .
(b)In $ℂ^{2}$ , $(1, 𝑖) \cdot$ $(1, - 𝑖) =$ $1 \cdot$ $1 +$ $𝑖 \cdot$ $- 𝑖 =$ $1 +$ $𝑖 \cdot$ $𝑖 =$ $0$ , so $(1, 𝑖) ⟂ (1, - 𝑖)$ . Forgetting the conjugate gives $1 + 𝑖 (- 𝑖) = 2$ instead.
(c)Give $𝐶 [- 1, 1]$ the inner product $⟨ 𝑓, 𝑔 ⟩ =$ $\int_{- 1}^{1} 𝑓 (𝑡) 𝑔 (𝑡) d 𝑡$ (Proposition 6.1.13, on $[- 1, 1]$ ). If $𝑓$ is even and $𝑔$ is odd, then $𝑓 𝑔$ is odd, so $⟨ 𝑓, 𝑔 ⟩ = 0$ . For instance $1 ⟂ 𝑡$ and $𝑡 ⟂ 𝑡^{2}$ . On the other hand $⟨ 1, 𝑡^{2} ⟩ = 2 / 3 \neq 0$ .

Orthogonality depends on the inner product as well as on the vectors. For the inner product $⟨ 𝐱, 𝐲 ⟩ = 𝐲^{𝖳} 𝑀 𝐱$ on $ℝ^{2}$ with $𝑀 = (\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix})$ (Example 6.1.23), $⟨ 𝐞_{1}, 𝐞_{2} ⟩ = 𝑚_{21} = 1$ , so $𝐞_{1}$ and $𝐞_{2}$ are not orthogonal. The vectors $(1, 1)$ and $(1, - 1)$ are orthogonal for both inner products: $𝑀 (1, 1) = (3, 3)$ , and $(1, - 1) \cdot (3, 3) = 0$ .

Over $ℂ$ , orthogonality is more demanding than perpendicularity of arrows. In $ℂ = ℂ^{1}$ with $⟨ 𝑧, 𝑤 ⟩ = 𝑧 𝑤$ , the numbers $1$ and $𝑖$ are perpendicular as arrows in the plane, but $⟨ 1, 𝑖 ⟩ = 𝑖 = - 𝑖 \neq 0$ . They are not orthogonal, and they should not be, since $𝑖 = 𝑖 \cdot 1$ is a scalar multiple of $1$ . As we saw at the end of Section 6.2.3, $⟨ 𝐮, 𝐯 ⟩ = 0$ says that $𝐯$ is perpendicular, in the real sense, to $𝜆 𝐮$ for every $𝜆$ with $| 𝜆 | = 1$ .

The Pythagorean theorem

Theorem 6.3.3 (Pythagorean theorem). Let $𝐮, 𝐯 \in 𝑉$ .

(a)If $𝐮 ⟂ 𝐯$ , then ${‖ 𝐮 + 𝐯 ‖}^{2} =$ ${‖ 𝐮 ‖}^{2} +$ ${‖ 𝐯 ‖}^{2}$ .
(b)If $𝔽 = ℝ$ , the converse holds: if ${‖ 𝐮 + 𝐯 ‖}^{2} =$ ${‖ 𝐮 ‖}^{2} +$ ${‖ 𝐯 ‖}^{2}$ , then $𝐮 ⟂ 𝐯$ .

Proof.routine

Uses. Proposition 6.1.29 (Expanding a norm), Definition 6.3.1 (Orthogonality)

Hint 1. Expand

{‖ 𝐮 + 𝐯 ‖}^{2}

with Proposition 6.1.29. Which term has to vanish?

Hint 2. The identity holds if and only if

Re ⟨ 𝐮, 𝐯 ⟩ = 0

. Over

ℝ

, what is

Re ⟨ 𝐮, 𝐯 ⟩

Sketch. By Proposition 6.1.29,

{‖ 𝐮 + 𝐯 ‖}^{2} -

{‖ 𝐮 ‖}^{2} -

{‖ 𝐯 ‖}^{2} =

2 Re ⟨ 𝐮, 𝐯 ⟩

. So the identity holds exactly when

Re ⟨ 𝐮, 𝐯 ⟩ = 0

. This follows from

⟨ 𝐮, 𝐯 ⟩ = 0

, and over

ℝ

, where

⟨ 𝐮, 𝐯 ⟩

is real, it is equivalent to it.

By Proposition 6.1.29,

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

(6.3.1)

so the identity ${‖ 𝐮 + 𝐯 ‖}^{2} =$ ${‖ 𝐮 ‖}^{2} +$ ${‖ 𝐯 ‖}^{2}$ holds if and only if $Re ⟨ 𝐮, 𝐯 ⟩ = 0$ .

(a) If $𝐮 ⟂ 𝐯$ , then $⟨ 𝐮, 𝐯 ⟩ = 0$ , so its real part is $0$ .

(b) If $𝔽 = ℝ$ , then $⟨ 𝐮, 𝐯 ⟩$ is real and equals its real part. So $Re ⟨ 𝐮, 𝐯 ⟩ = 0$ says that $𝐮 ⟂ 𝐯$ . □

In $ℝ^{2}$ with the dot product, (a) is the theorem about the right triangle with legs $𝐮$ , $𝐯$ and hypotenuse $𝐮 + 𝐯$ , and (b) is its converse. In other spaces it says new things. In $𝐶 [- 1, 1]$ , $1 ⟂ 𝑡$ by Example 6.3.2(c), so

\int_{- 1}^{1} {(1 + 𝑡)}^{2} d 𝑡 = {‖ 1 ‖}^{2} + {‖ 𝑡 ‖}^{2} = 2 + \frac{2}{3} = \frac{8}{3},

which agrees with the direct computation $\int_{- 1}^{1} (1 + 2 𝑡 + 𝑡^{2}) d 𝑡 =$ $2 +$ $0 +$ $2 / 3$ .

Non-example 6.3.4 (The converse fails over $ℂ$ ). In $ℂ$ with $⟨ 𝑧, 𝑤 ⟩ = 𝑧 𝑤$ , take $𝐮 = 1$ and $𝐯 = 𝑖$ . Then ${| 1 + 𝑖 |}^{2} =$ $2 =$ ${| 1 |}^{2} +$ ${| 𝑖 |}^{2}$ , but $⟨ 1, 𝑖 ⟩ = - 𝑖 \neq 0$ . More generally, let $𝐱 \neq 𝟎$ be a vector in any complex inner product space. By Proposition 6.1.27,

{‖ 𝐱 + 𝑖 𝐱 ‖}^{2} = {| 1 + 𝑖 |}^{2} {‖ 𝐱 ‖}^{2} = 2 {‖ 𝐱 ‖}^{2} = {‖ 𝐱 ‖}^{2} + {‖ 𝑖 𝐱 ‖}^{2},

while $⟨ 𝐱, 𝑖 𝐱 ⟩ =$ $𝑖 {‖ 𝐱 ‖}^{2} =$ $- 𝑖 {‖ 𝐱 ‖}^{2} \neq$ $0$ . The proof of Theorem 6.3.3 shows what goes wrong: the Pythagorean identity only sees $Re ⟨ 𝐮, 𝐯 ⟩$ , and here $⟨ 𝐮, 𝐯 ⟩$ is purely imaginary.

The imaginary part becomes visible once $𝐯$ is multiplied by $𝑖$ . With $𝑎 = 𝑖$ , Proposition 6.1.29 gives ${‖ 𝐮 + 𝑖 𝐯 ‖}^{2} =$ ${‖ 𝐮 ‖}^{2} +$ $2 Im ⟨ 𝐮, 𝐯 ⟩ +$ ${‖ 𝐯 ‖}^{2}$ , as computed after that proposition. So over $ℂ$ two Pythagorean identities together detect orthogonality.

Proposition 6.3.5 (Orthogonality over $ℂ$ through Pythagoras). Let $𝑉$ be a complex inner product space and $𝐮, 𝐯 \in 𝑉$ . Then $𝐮 ⟂ 𝐯$ if and only if both

\begin{aligned} {‖ 𝐮 + 𝐯 ‖}^{2} & = {‖ 𝐮 ‖}^{2} + {‖ 𝐯 ‖}^{2} and \\ {‖ 𝐮 + 𝑖 𝐯 ‖}^{2} & = {‖ 𝐮 ‖}^{2} + {‖ 𝑖 𝐯 ‖}^{2} . \end{aligned}

In that case ${‖ 𝐮 + 𝑎 𝐯 ‖}^{2} =$ ${‖ 𝐮 ‖}^{2} +$ ${‖ 𝑎 𝐯 ‖}^{2}$ for every $𝑎 \in ℂ$ .

Proof.routine

Uses. Proposition 6.1.29 (Expanding a norm), Proposition 6.1.27 (Basic properties of the norm), Notation 6.1.1 (Real and complex scalars)

Techniques. Plug in clever test vectors (Technique 6.1.40)

Hint 1. Expand

{‖ 𝐮 + 𝑎 𝐯 ‖}^{2}

with Proposition 6.1.29 for a general scalar

𝑎

. The Pythagorean identity for

𝐮

and

𝑎 𝐯

says that one term vanishes.

Hint 2. For

𝑎 = 1

that term is

2 Re ⟨ 𝐮, 𝐯 ⟩

. For

𝑎 = 𝑖

it is

2 Re (- 𝑖 ⟨ 𝐮, 𝐯 ⟩)

; which part of

⟨ 𝐮, 𝐯 ⟩

is that?

Sketch. By Proposition 6.1.29 and

{‖ 𝑎 𝐯 ‖}^{2} =

{| 𝑎 |}^{2} {‖ 𝐯 ‖}^{2}

, the identity for

𝐮

and

𝑎 𝐯

holds exactly when

Re (𝑎 ⟨ 𝐮, 𝐯 ⟩) = 0

. For

𝑎 = 1

and

𝑎 = 𝑖

this says

Re ⟨ 𝐮, 𝐯 ⟩ = 0

and

Im ⟨ 𝐮, 𝐯 ⟩ = 0

, which together say

⟨ 𝐮, 𝐯 ⟩ = 0

. If

⟨ 𝐮, 𝐯 ⟩ = 0

, then

Re (𝑎 \cdot 0) = 0

for every

𝑎

Let $𝑎 \in ℂ$ . By Proposition 6.1.29 and Proposition 6.1.27,

{‖ 𝐮 + 𝑎 𝐯 ‖}^{2} - {‖ 𝐮 ‖}^{2} - {‖ 𝑎 𝐯 ‖}^{2} = 2 Re (𝑎 ⟨ 𝐮, 𝐯 ⟩) .

For $𝑎 = 1$ the right side is $2 Re ⟨ 𝐮, 𝐯 ⟩$ , and for $𝑎 = 𝑖$ it is $2 Re (- 𝑖 ⟨ 𝐮, 𝐯 ⟩) =$ $2 Im ⟨ 𝐮, 𝐯 ⟩$ (Notation 6.1.1). So the two displayed identities hold together if and only if the real and imaginary parts of $⟨ 𝐮, 𝐯 ⟩$ both vanish, that is, if and only if $𝐮 ⟂ 𝐯$ . Finally, if $⟨ 𝐮, 𝐯 ⟩ = 0$ , the right side is $0$ for every $𝑎$ . □

The last statement also follows from Theorem 6.3.3(a): if $𝐮 ⟂ 𝐯$ , then $⟨ 𝐮, 𝑎 𝐯 ⟩ =$ $𝑎 ⟨ 𝐮, 𝐯 ⟩ =$ $0$ , so $𝐮 ⟂ 𝑎 𝐯$ for every scalar $𝑎$ . Over $ℂ$ , then, orthogonality is “Pythagoras for $𝐮$ and every multiple of $𝐯$ ”, which matches the description of orthogonality through unit-modulus multiples above.

The Pythagorean theorem extends to any number of vectors, and pairwise orthogonality is all it needs.

Corollary 6.3.6 (Pythagoras for orthogonal lists). Let $𝐯_{1}, \dots, 𝐯_{𝑘}$ be an orthogonal list in $𝑉$ , and let $𝑎_{1}, \dots, 𝑎_{𝑘} \in 𝔽$ . Then

{‖ 𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑘} 𝐯_{𝑘} ‖}^{2} = {| 𝑎_{1} |}^{2} {‖ 𝐯_{1} ‖}^{2} + \dots + {| 𝑎_{𝑘} |}^{2} {‖ 𝐯_{𝑘} ‖}^{2} .

Proof (by expanding).routine

Uses. Proposition 6.1.4 (Sesquilinearity), Definition 6.1.26 (Norm), Definition 6.3.1 (Orthogonality)

Techniques. Expand by multilinearity (Technique 5.1.7)

Hint 1. Write the left side as an inner product of a sum with itself and expand both slots.

Hint 2. You get

\sum_{𝑗} \sum_{𝑙} 𝑎_{𝑗} 𝑎_{𝑙} ⟨ 𝐯_{𝑗}, 𝐯_{𝑙} ⟩

. Which terms survive?

Sketch. Expanding both slots gives

𝑘^{2}

terms

𝑎_{𝑗} 𝑎_{𝑙} ⟨ 𝐯_{𝑗}, 𝐯_{𝑙} ⟩

. Those with

𝑗 \neq 𝑙

vanish by orthogonality, and those with

𝑗 = 𝑙

are

{| 𝑎_{𝑗} |}^{2} {‖ 𝐯_{𝑗} ‖}^{2}

By linearity in the first slot and Proposition 6.1.4 in the second,

{‖ \sum_{𝑗 = 1}^{𝑘} 𝑎_{𝑗} 𝐯_{𝑗} ‖}^{2} = ⟨ \sum_{𝑗 = 1}^{𝑘} 𝑎_{𝑗} 𝐯_{𝑗}, \sum_{𝑙 = 1}^{𝑘} 𝑎_{𝑙} 𝐯_{𝑙} ⟩ = \sum_{𝑗 = 1}^{𝑘} \sum_{𝑙 = 1}^{𝑘} 𝑎_{𝑗} 𝑎_{𝑙} ⟨ 𝐯_{𝑗}, 𝐯_{𝑙} ⟩ .

For $𝑗 \neq 𝑙$ the term is $0$ because $𝐯_{𝑗} ⟂ 𝐯_{𝑙}$ . For $𝑗 = 𝑙$ it is $𝑎_{𝑗} 𝑎_{𝑗} ⟨ 𝐯_{𝑗}, 𝐯_{𝑗} ⟩ =$ ${| 𝑎_{𝑗} |}^{2} {‖ 𝐯_{𝑗} ‖}^{2}$ . Adding these gives the claim. □

Proof (by induction on $𝑘$ ).routine

Uses. Theorem 6.3.3 (Pythagorean theorem), Proposition 6.1.27 (Basic properties of the norm), Proposition 6.1.4 (Sesquilinearity)

Techniques. Induction on the length of a list (Technique 1.6.9)

Hint 1. Split off the last term:

𝐰 =

𝑎_{1} 𝐯_{1} +

\dots +

𝑎_{𝑘 - 1} 𝐯_{𝑘 - 1}

and

𝑎_{𝑘} 𝐯_{𝑘}

Hint 2. Check that

𝐰 ⟂ 𝑎_{𝑘} 𝐯_{𝑘}

by expanding

⟨ 𝐰, 𝑎_{𝑘} 𝐯_{𝑘} ⟩

, then apply Theorem 6.3.3.

Sketch. The case

𝑘 = 1

is Proposition 6.1.27. For

𝑘 \geq 2

, the vector

𝐰 =

\sum_{𝑗 < 𝑘} 𝑎_{𝑗} 𝐯_{𝑗}

satisfies

⟨ 𝐰, 𝑎_{𝑘} 𝐯_{𝑘} ⟩ =

\sum_{𝑗 < 𝑘} 𝑎_{𝑗} 𝑎_{𝑘} ⟨ 𝐯_{𝑗}, 𝐯_{𝑘} ⟩ =

0

, so Theorem 6.3.3 splits off

{| 𝑎_{𝑘} |}^{2} {‖ 𝐯_{𝑘} ‖}^{2}

, and the induction hypothesis handles

{‖ 𝐰 ‖}^{2}

We induct on $𝑘$ . For $𝑘 = 1$ the claim is ${‖ 𝑎_{1} 𝐯_{1} ‖}^{2} =$ ${| 𝑎_{1} |}^{2} {‖ 𝐯_{1} ‖}^{2}$ , which is Proposition 6.1.27. Let $𝑘 \geq 2$ and assume the claim for orthogonal lists of length $𝑘 - 1$ . Let $𝐰 =$ $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘 - 1} 𝐯_{𝑘 - 1}$ . Then

⟨ 𝐰, 𝑎_{𝑘} 𝐯_{𝑘} ⟩ = \sum_{𝑗 = 1}^{𝑘 - 1} 𝑎_{𝑗} 𝑎_{𝑘} ⟨ 𝐯_{𝑗}, 𝐯_{𝑘} ⟩ = 0,

so $𝐰 ⟂ 𝑎_{𝑘} 𝐯_{𝑘}$ , and by Theorem 6.3.3(a), Proposition 6.1.27, and the induction hypothesis applied to the orthogonal list $𝐯_{1}, \dots, 𝐯_{𝑘 - 1}$ ,

{‖ 𝐰 + 𝑎_{𝑘} 𝐯_{𝑘} ‖}^{2} = {‖ 𝐰 ‖}^{2} + {| 𝑎_{𝑘} |}^{2} {‖ 𝐯_{𝑘} ‖}^{2} = \sum_{𝑗 = 1}^{𝑘} {| 𝑎_{𝑗} |}^{2} {‖ 𝐯_{𝑗} ‖}^{2},

as desired. □

The second proof explains why pairwise orthogonality is enough: a vector orthogonal to each of $𝐯_{1}, \dots, 𝐯_{𝑘 - 1}$ is orthogonal to every linear combination of them. We record this fact in Proposition 6.3.9.

Exercise 6.3.7.routine In

ℂ^{3}

with the dot product, find all

𝑎 \in ℂ

with

(1, 𝑖, 𝑎) ⟂ (2, 1 + 𝑖, 𝑖)

. For that

𝑎

, verify Theorem 6.3.3(a) for the two vectors by computing all three norms.

Solution.

Uses. Definition 6.1.8 (Dot product), Definition 6.3.1 (Orthogonality), Proposition 6.1.10 (The dot product is an inner product)

Hint 1. Conjugate the entries of the second vector, multiply entrywise, and add. You get a linear equation in

𝑎

Hint 2. The equation is

3 + 𝑖 - 𝑖 𝑎 = 0

Sketch.

(1, 𝑖, 𝑎) \cdot

(2, 1 + 𝑖, 𝑖) =

2 +

𝑖 (1 - 𝑖) -

𝑖 𝑎 =

3 +

𝑖 -

𝑖 𝑎

, which vanishes for

𝑎 = 1 - 3 𝑖

. Then the squared norms are

12

and

7

, and the sum

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

has squared norm

9 + 5 + 5 = 19 = 12 + 7

By Definition 6.1.8,

\begin{aligned} (1, 𝑖, 𝑎) \cdot (2, 1 + 𝑖, 𝑖) & = 1 \cdot 2 + 𝑖 \cdot (1 + 𝑖) + 𝑎 \cdot 𝑖 \\ = 2 + 𝑖 (1 - 𝑖) - 𝑖 𝑎 = 3 + 𝑖 - 𝑖 𝑎 . \end{aligned}

This vanishes if and only if $𝑖 𝑎 = 3 + 𝑖$ , that is, $𝑎 =$ $(3 + 𝑖) / 𝑖 =$ $(3 + 𝑖) (- 𝑖) =$ $1 -$ $3 𝑖$ .

With $𝐮 = (1, 𝑖, 1 - 3 𝑖)$ and $𝐯 = (2, 1 + 𝑖, 𝑖)$ , Proposition 6.1.10 gives ${‖ 𝐮 ‖}^{2} = 1 + 1 + 10 = 12$ and ${‖ 𝐯 ‖}^{2} = 4 + 2 + 1 = 7$ . The sum is $𝐮 +$ $𝐯 =$ $(3, 1 + 2 𝑖, 1 - 2 𝑖)$ , with ${‖ 𝐮 + 𝐯 ‖}^{2} =$ $9 +$ $5 +$ $5 =$ $19 =$ $12 +$ $7$ , as Theorem 6.3.3 predicts.

Orthogonality to a set

We often need all vectors orthogonal to a given collection of vectors.

Definition 6.3.8 (Vectors orthogonal to a set). Let $𝐴 \subseteq 𝑉$ be any subset. A vector $𝐯 \in 𝑉$ is orthogonal to $𝐴$ , written $𝐯 ⟂ 𝐴$ , if $𝐯 ⟂ 𝐚$ for every $𝐚 \in 𝐴$ . The set of all such vectors is

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

read “ $𝐴$ perp”. For a list $ℒ︀$ , ${ℒ︀}^{⟂}$ is the perp of the set of entries of $ℒ︀$ .

When $𝐴$ is a subspace, $𝐴^{⟂}$ is called the orthogonal complement of $𝐴$ , and Section 6.4 shows that in finite dimensions it is a complement of $𝐴$ in the sense of Section 4.4. For now $𝐴$ is arbitrary.

Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ). Let $𝐴, 𝐵 \subseteq 𝑉$ .

(a) $𝐴^{⟂}$ is a subspace of $𝑉$ .
(b)If $𝐴 \subseteq 𝐵$ , then $𝐵^{⟂} \subseteq 𝐴^{⟂}$ .
(c)For a list $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ in $𝑉$ , ${span (ℒ︀)}^{⟂} = {ℒ︀}^{⟂}$ . That is, a vector is orthogonal to every linear combination of $𝐯_{1}, \dots, 𝐯_{𝑘}$ if and only if it is orthogonal to each $𝐯_{𝑗}$ .
(d) ${𝟎}^{⟂} = 𝑉$ , $𝑉^{⟂} = {𝟎}$ , and $𝐴 \cap 𝐴^{⟂} \subseteq {𝟎}$ .

Proof.routine

Uses. Theorem 1.4.3 (Subspace criterion), Proposition 6.1.4 (Sesquilinearity), Proposition 1.3.17 (A list lies in its span), Definition 1.3.10 (Span), Definition 6.1.2 (Inner product)

Techniques. Double containment (Technique 1.3.14), Fix an arbitrary element and chase it (Technique 1.3.13)

Hint 1. For (a), check the conditions of Theorem 1.4.3 using linearity in the first slot.

Hint 2. For (c), one containment is (b). For the other, take

𝐯 ⟂ 𝐯_{𝑗}

for all

𝑗

and expand

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

in the second slot.

Hint 3. For (d), a vector in

𝑉^{⟂}

or in

𝐴 \cap 𝐴^{⟂}

is orthogonal to itself.

Sketch. (a)

𝟎 \in 𝐴^{⟂}

, and

⟨ 𝑐 𝐯 + 𝐰, 𝐚 ⟩ =

𝑐 ⟨ 𝐯, 𝐚 ⟩ +

⟨ 𝐰, 𝐚 ⟩

shows closure. (b) Orthogonality to all of

𝐵

includes orthogonality to all of

𝐴

. (c)

ℒ︀ \subseteq span (ℒ︀)

gives one containment by (b); conversely

⟨ 𝐯, \sum_{𝑗} 𝑐_{𝑗} 𝐯_{𝑗} ⟩ =

\sum_{𝑗} 𝑐_{𝑗} ⟨ 𝐯, 𝐯_{𝑗} ⟩ =

0

. (d) Everything is orthogonal to

𝟎

, and a vector orthogonal to itself is

𝟎

(a) By Proposition 6.1.4(b), $⟨ 𝟎, 𝐚 ⟩ = 0$ for all $𝐚 \in 𝐴$ , so $𝟎 \in 𝐴^{⟂}$ . Let $𝐯, 𝐰 \in 𝐴^{⟂}$ and $𝑐 \in 𝔽$ . For every $𝐚 \in 𝐴$ , linearity in the first slot gives

⟨ 𝑐 𝐯 + 𝐰, 𝐚 ⟩ = 𝑐 ⟨ 𝐯, 𝐚 ⟩ + ⟨ 𝐰, 𝐚 ⟩ = 𝑐 \cdot 0 + 0 = 0,

so $𝑐 𝐯 + 𝐰 \in 𝐴^{⟂}$ . By Theorem 1.4.3, $𝐴^{⟂}$ is a subspace.

(b) If $𝐯 \in 𝐵^{⟂}$ , then $𝐯 ⟂ 𝐛$ for every $𝐛 \in 𝐵$ , in particular for every element of $𝐴 \subseteq 𝐵$ . So $𝐯 \in 𝐴^{⟂}$ .

(c) Each $𝐯_{𝑗}$ lies in $span (ℒ︀)$ (Proposition 1.3.17), so (b) gives ${span (ℒ︀)}^{⟂} \subseteq {ℒ︀}^{⟂}$ . Conversely, let $𝐯 \in {ℒ︀}^{⟂}$ , and let $𝐰 =$ $𝑐_{1} 𝐯_{1} +$ $\dots +$ $𝑐_{𝑘} 𝐯_{𝑘}$ be any element of $span (ℒ︀)$ . By Proposition 6.1.4,

⟨ 𝐯, 𝐰 ⟩ = 𝑐_{1} ⟨ 𝐯, 𝐯_{1} ⟩ + \dots + 𝑐_{𝑘} ⟨ 𝐯, 𝐯_{𝑘} ⟩ = 0,

so $⟨ 𝐰, 𝐯 ⟩ = ⟨ 𝐯, 𝐰 ⟩ = 0$ as well, and $𝐯 \in {span (ℒ︀)}^{⟂}$ .

(d) Every $𝐯 \in 𝑉$ satisfies $⟨ 𝐯, 𝟎 ⟩ = 0$ by Proposition 6.1.4(b), so ${𝟎}^{⟂} = 𝑉$ . If $𝐯 \in 𝑉^{⟂}$ , then in particular $⟨ 𝐯, 𝐯 ⟩ = 0$ , so $𝐯 = 𝟎$ by definiteness; and $𝟎 \in 𝑉^{⟂}$ by (a). Finally, if $𝐯 \in 𝐴 \cap 𝐴^{⟂}$ , then $𝐯 ⟂ 𝐯$ , so $𝐯 = 𝟎$ . □

Part (c) is how $𝐴^{⟂}$ is computed in practice: to test orthogonality to a subspace, test it on a spanning list. The same argument shows $𝐴^{⟂} = {span (𝐴)}^{⟂}$ for an arbitrary subset $𝐴$ , with $span (𝐴)$ as in Aside (Spans of infinite sets). Part (a) holds even when $𝐴$ itself is not a subspace.

Example 6.3.10 (Perps are solution sets).

(a)In $ℝ^{3}$ , ${(1, 1, 1)}^{⟂} =$ ${𝐱 \in ℝ^{3} | 𝑥_{1} + 𝑥_{2} + 𝑥_{3} = 0}$ , the plane through $𝟎$ with normal vector $(1, 1, 1)$ .
(b)Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ . The $𝑖$ th entry of $𝐴 𝐱$ is $\sum_{𝑗} 𝑎_{𝑖 𝑗} 𝑥_{𝑗} =$ $𝐱 \cdot$ $𝐫_{𝑖}$ , where $𝐫_{𝑖} =$ $(𝑎_{𝑖 1}, \dots, 𝑎_{𝑖 𝑛}) \in$ $𝔽^{𝑛}$ is the $𝑖$ th row of $𝐴$ with its entries conjugated. So
$ker 𝐴 = {𝐫_{1}, \dots, 𝐫_{𝑚}}^{⟂} .$
Over $ℝ$ , $𝐫_{𝑖}$ is just the $𝑖$ th row of $𝐴$ , and solving a homogeneous system means finding all vectors orthogonal to the rows of its coefficient matrix. For instance, for $𝐴 = (\begin{matrix} 1 & 2 & 0 \\ 0 & 1 & - 1 \end{matrix})$ , solving $𝐴 𝐱 = 𝟎$ gives $ker 𝐴 =$ $span ((- 2, 1, 1))$ , and indeed $(- 2, 1, 1)$ is orthogonal to $(1, 2, 0)$ and to $(0, 1, - 1)$ . The vectors $𝐫_{𝑖}$ are the columns of the matrix $𝐴^{*}$ of Definition 6.3.26 below, so by Proposition 6.3.9(c) this says $ker 𝐴 = {(im 𝐴^{*})}^{⟂}$ ; Section 6.6 proves the analogous statement for linear maps.

Exercise 6.3.11.routine Let

𝐴, 𝐵 \subseteq 𝑉

. Show that

{(𝐴 \cup 𝐵)}^{⟂} = 𝐴^{⟂} \cap 𝐵^{⟂}

and that

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

. Give an example with

𝐴 \neq {(𝐴^{⟂})}^{⟂}

Solution.

Uses. Definition 6.3.8 (Vectors orthogonal to a set), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ )

Techniques. Double containment (Technique 1.3.14)

Hint 1. For the first identity, unwind the definitions: being orthogonal to every element of

𝐴 \cup 𝐵

means being orthogonal to every element of

𝐴

and to every element of

𝐵

Hint 2. For

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

, take

𝐚 \in 𝐴

and

𝐯 \in 𝐴^{⟂}

, and compute

⟨ 𝐚, 𝐯 ⟩

using symmetry of orthogonality.

Hint 3.

{(𝐴^{⟂})}^{⟂}

is always a subspace, by Proposition 6.3.9(a).

Sketch.

𝐯 ⟂ (𝐴 \cup 𝐵)

if and only if

𝐯 ⟂ 𝐴

and

𝐯 ⟂ 𝐵

. If

𝐚 \in 𝐴

and

𝐯 \in 𝐴^{⟂}

, then

⟨ 𝐚, 𝐯 ⟩ = ⟨ 𝐯, 𝐚 ⟩ = 0

, so

𝐚 \in {(𝐴^{⟂})}^{⟂}

. For

𝐴 = {(1, 0)}

ℝ^{2}

{(𝐴^{⟂})}^{⟂}

is a subspace, so it is not

𝐴

A vector $𝐯$ lies in ${(𝐴 \cup 𝐵)}^{⟂}$ if and only if $⟨ 𝐯, 𝐜 ⟩ = 0$ for every $𝐜$ in $𝐴$ or in $𝐵$ , that is, if and only if $𝐯 \in 𝐴^{⟂}$ and $𝐯 \in 𝐵^{⟂}$ . So ${(𝐴 \cup 𝐵)}^{⟂} = 𝐴^{⟂} \cap 𝐵^{⟂}$ .

Let $𝐚 \in 𝐴$ . For every $𝐯 \in 𝐴^{⟂}$ , $⟨ 𝐚, 𝐯 ⟩ =$ $⟨ 𝐯, 𝐚 ⟩ =$ $0 =$ $0$ . So $𝐚$ is orthogonal to every vector of $𝐴^{⟂}$ , that is, $𝐚 \in {(𝐴^{⟂})}^{⟂}$ .

For $𝐴 = {(1, 0)}$ in $ℝ^{2}$ with the dot product, ${(𝐴^{⟂})}^{⟂}$ is a subspace by Proposition 6.3.9(a), so it contains $𝟎 \notin 𝐴$ . In fact $𝐴^{⟂} = span ((0, 1))$ and ${(𝐴^{⟂})}^{⟂} =$ $span ((1, 0))$ . (Section 6.4 shows that ${(𝑊^{⟂})}^{⟂} = 𝑊$ when $𝑊$ is a finite-dimensional subspace.)

6.3.2Orthonormal lists and bases

Orthogonal lists are independent

Three mutually perpendicular nonzero arrows in $ℝ^{3}$ cannot lie in a common plane, so they are linearly independent. To prove the general version, start from a linear relation $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} =$ $𝟎$ among orthogonal vectors and try to show that one coefficient, say $𝑎_{𝑗}$ , is $0$ . The inner product with $𝐯_{𝑗}$ is the natural thing to apply: it is linear, so it can be applied term by term, and it annihilates every $𝐯_{𝑙}$ with $𝑙 \neq 𝑗$ . This move is used throughout the rest of the book.

Technique 6.3.12 (Take an inner product to isolate a coefficient). If a vector is written as a combination $𝐰 =$ $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘}$ of an orthogonal list, take the inner product of both sides with $𝐯_{𝑗}$ . Linearity in the first slot distributes it over the sum, and orthogonality removes every term except the $𝑗$ th:

⟨ 𝐰, 𝐯_{𝑗} ⟩ = \sum_{𝑙 = 1}^{𝑘} 𝑎_{𝑙} ⟨ 𝐯_{𝑙}, 𝐯_{𝑗} ⟩ = 𝑎_{𝑗} {‖ 𝐯_{𝑗} ‖}^{2} .

So each coefficient is determined by one inner product, with no reference to the other coefficients. Put $𝐯_{𝑗}$ in the second slot; in the first slot it produces $⟨ 𝐯_{𝑗}, 𝐰 ⟩ =$ $𝑎_{𝑗} {‖ 𝐯_{𝑗} ‖}^{2}$ , the conjugate.

Reach for it when a vector or a linear relation is expressed through an orthogonal list and you need the coefficients, or need to show that they vanish. It is the inner-product form of Technique 4.1.25: the linear map $𝐱 \mapsto ⟨ 𝐱, 𝐯_{𝑗} ⟩$ from $𝑉$ to $𝔽$ kills every $𝐯_{𝑙}$ with $𝑙 \neq 𝑗$ . The canonical example is Proposition 6.3.13. The coordinate formula Proposition 6.3.18, the Fourier inversion formula (Proposition 6.3.41), and Gram–Schmidt (Algorithm 6.4.14) use it again.

Used in 13 places and 1 practice exercise

Proposition 6.3.13, Proposition 6.3.18, Corollary 6.3.21, Theorem 6.3.24, Proposition 6.4.4, Theorem 6.4.6, Corollary 6.4.25, Exercise 6.4.55, Theorem 6.6.3, Theorem 6.6.15, Exercise 6.7.7, Problem 6.5, Lemma 8.4.23; 1 practice exercise.

Proposition 6.3.13 (Orthogonal lists are independent). An orthogonal list of nonzero vectors is linearly independent.

Proof (by isolating coefficients).routine

Uses. Theorem 1.5.5 (Independence is decided at zero), Definition 6.3.1 (Orthogonality), 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. Start from a linear relation

𝑎_{1} 𝐯_{1} +

\dots +

𝑎_{𝑘} 𝐯_{𝑘} =

𝟎

. You must show that every

𝑎_{𝑗}

0

Hint 2. Fix

𝑗

and take the inner product of both sides with

𝐯_{𝑗}

Hint 3. You get

𝑎_{𝑗} {‖ 𝐯_{𝑗} ‖}^{2} = 0

. Why is

‖ 𝐯_{𝑗} ‖ \neq 0

Sketch. If

\sum_{𝑙} 𝑎_{𝑙} 𝐯_{𝑙} = 𝟎

, then for each

𝑗

0 =

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

𝑎_{𝑗} {‖ 𝐯_{𝑗} ‖}^{2}

by orthogonality. Since

𝐯_{𝑗} \neq 𝟎

{‖ 𝐯_{𝑗} ‖}^{2} > 0

, so

𝑎_{𝑗} = 0

. Only the trivial relation exists.

Let $𝐯_{1}, \dots, 𝐯_{𝑘}$ be an orthogonal list of nonzero vectors, and suppose $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} =$ $𝟎$ . Fix $𝑗 \in {1, \dots, 𝑘}$ . By Proposition 6.1.4(b) and linearity in the first slot,

\begin{aligned} 0 = ⟨ 𝟎, 𝐯_{𝑗} ⟩ & = ⟨ \sum_{𝑙 = 1}^{𝑘} 𝑎_{𝑙} 𝐯_{𝑙}, 𝐯_{𝑗} ⟩ = \sum_{𝑙 = 1}^{𝑘} 𝑎_{𝑙} ⟨ 𝐯_{𝑙}, 𝐯_{𝑗} ⟩ \\ = 𝑎_{𝑗} ⟨ 𝐯_{𝑗}, 𝐯_{𝑗} ⟩ = 𝑎_{𝑗} {‖ 𝐯_{𝑗} ‖}^{2}, \end{aligned}

where the fourth step uses $⟨ 𝐯_{𝑙}, 𝐯_{𝑗} ⟩ = 0$ for $𝑙 \neq 𝑗$ . Since $𝐯_{𝑗} \neq 𝟎$ , ${‖ 𝐯_{𝑗} ‖}^{2} > 0$ by Proposition 6.1.27, so $𝑎_{𝑗} = 0$ . As $𝑗$ was arbitrary, the only linear relation among $𝐯_{1}, \dots, 𝐯_{𝑘}$ is the trivial one, and the list is independent by Theorem 1.5.5. □

Proof (by Pythagoras).routine

Uses. Corollary 6.3.6 (Pythagoras for orthogonal lists), Theorem 1.5.5 (Independence is decided at zero), Proposition 6.1.27 (Basic properties of the norm)

Techniques. A sum of nonnegative terms (Technique 6.1.9)

Hint 1. Take the squared norm of both sides of a relation

\sum_{𝑙} 𝑎_{𝑙} 𝐯_{𝑙} = 𝟎

Hint 2. Corollary 6.3.6 turns the left side into a sum of nonnegative terms.

Sketch. If

\sum_{𝑙} 𝑎_{𝑙} 𝐯_{𝑙} = 𝟎

, then

0 =

{‖ \sum_{𝑙} 𝑎_{𝑙} 𝐯_{𝑙} ‖}^{2} =

\sum_{𝑙} {| 𝑎_{𝑙} |}^{2} {‖ 𝐯_{𝑙} ‖}^{2}

. A sum of nonnegative terms vanishes only if each does, and

‖ 𝐯_{𝑙} ‖ > 0

, so every

𝑎_{𝑙} = 0

Suppose $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐯_{𝑘} =$ $𝟎$ . By Corollary 6.3.6,

0 = {‖ 𝟎 ‖}^{2} = {| 𝑎_{1} |}^{2} {‖ 𝐯_{1} ‖}^{2} + \dots + {| 𝑎_{𝑘} |}^{2} {‖ 𝐯_{𝑘} ‖}^{2} .

Each term is a nonnegative real number, so each term is $0$ . Since ${‖ 𝐯_{𝑙} ‖}^{2} > 0$ for every $𝑙$ , it follows that ${| 𝑎_{𝑙} |}^{2} = 0$ , that is, $𝑎_{𝑙} = 0$ , for every $𝑙$ . By Theorem 1.5.5 the list is independent. □

The first proof extracts the coefficients one at a time; the second shows with a single number that they all vanish. The second also says more: by Corollary 6.3.6, a combination of orthogonal unit vectors has length ${(\sum_{𝑙} {| 𝑎_{𝑙} |}^{2})}^{1 / 2}$ , so it is short only when all its coefficients are small. Both proofs use that ${‖ 𝐯_{𝑗} ‖}^{2} \neq 0$ for $𝐯_{𝑗} \neq 𝟎$ . For the “dot product” $\sum_{𝑘} 𝑥_{𝑘} 𝑦_{𝑘}$ on $𝔽_{2}^{𝑛}$ with $𝑛 \geq 2$ , which is not an inner product, this fails, and so does the proposition (Exercise 6.3.47). The hypothesis that the vectors are nonzero is needed too, since the orthogonal list $𝐯, 𝟎$ is dependent.

Corollary 6.3.14 (Counting orthogonal vectors). Let

𝑉

be finite-dimensional with

dim 𝑉 = 𝑛

. An orthogonal list of nonzero vectors in

𝑉

has length at most

𝑛

, and if its length is exactly

𝑛

, it is a basis of

𝑉

Proof.routine

Uses. Proposition 6.3.13 (Orthogonal lists are independent), Theorem 4.1.10 (Independent lists are short), an independent list of length $dim 𝑉$ is a basis (Section 4.1)

Hint 1. By Proposition 6.3.13, such a list is independent. What does Section 4.1 say about independent lists?

Hint 2. Independent lists have length at most

dim 𝑉

, and an independent list of length

dim 𝑉

is a basis.

Sketch. The list is independent by Proposition 6.3.13. Independent lists in

𝑉

have length at most

𝑛

, and independent lists of length

𝑛

are bases.

By Proposition 6.3.13 the list is linearly independent. By Theorem 4.1.10 its length is at most

𝑛

, and an independent list of length

𝑛 = dim 𝑉

is a basis of

𝑉

(Section 4.1). □

So $ℝ^{𝑛}$ contains at most $𝑛$ mutually orthogonal nonzero vectors, and to check that $𝑛$ of them form a basis it suffices to check orthogonality.

Orthonormal lists

Definition 6.3.15 (Orthonormal list, orthonormal basis). A list $𝐮_{1}, \dots, 𝐮_{𝑘}$ in $𝑉$ is orthonormal if it is orthogonal and every $𝐮_{𝑗}$ is a unit vector. That is,

⟨ 𝐮_{𝑖}, 𝐮_{𝑗} ⟩ = 𝛿_{𝑖 𝑗} for all 𝑖, 𝑗 \in {1, \dots, 𝑘},

with the Kronecker delta of Notation 2.4.7. An orthonormal basis of $𝑉$ is an orthonormal list that is a basis of $𝑉$ .

Unit vectors are nonzero, so an orthonormal list is linearly independent by Proposition 6.3.13, and by Corollary 6.3.14 an orthonormal list in an $𝑛$ -dimensional space is an orthonormal basis exactly when its length is $𝑛$ . An orthogonal list of nonzero vectors $𝐯_{1}, \dots, 𝐯_{𝑘}$ becomes orthonormal after normalizing (Section 6.1.4): the vectors $𝐯_{𝑗} / ‖ 𝐯_{𝑗} ‖$ are unit vectors, and scaling does not affect orthogonality, as $⟨ 𝑎 𝐯, 𝑏 𝐰 ⟩ =$ $𝑎 𝑏 ⟨ 𝐯, 𝐰 ⟩$ . We write $𝒪︀$ for orthonormal lists, as the lecture does.

Example 6.3.16 (Orthonormal bases).

(a)The standard basis $𝐞_{1}, \dots, 𝐞_{𝑛}$ is an orthonormal basis of $𝔽^{𝑛}$ with the dot product, since $𝐞_{𝑖} \cdot 𝐞_{𝑗} = 𝛿_{𝑖 𝑗}$ .
(b)For every $𝜃 \in ℝ$ , $𝐮_{1} = (cos 𝜃, sin 𝜃)$ , $𝐮_{2} =$ $(- sin 𝜃, cos 𝜃)$ is an orthonormal basis of $ℝ^{2}$ : the standard basis rotated by $𝜃$ .
(c)In $ℝ^{3}$ , let
$𝐮_{1} = \frac{1}{3} (1, 2, 2), 𝐮_{2} = \frac{1}{3} (2, 1, - 2), 𝐮_{3} = \frac{1}{3} (2, - 2, 1) .$
Each has squared norm $(1 + 4 + 4) / 9 = 1$ , and $𝐮_{1} \cdot$ $𝐮_{2} =$ $(2 + 2 - 4) / 9 =$ $0$ , $𝐮_{1} \cdot$ $𝐮_{3} =$ $(2 - 4 + 2) / 9 =$ $0$ , $𝐮_{2} \cdot$ $𝐮_{3} =$ $(4 - 2 - 2) / 9 =$ $0$ . So this is an orthonormal list of length $3 = dim ℝ^{3}$ , hence an orthonormal basis.
(d)In $ℂ^{2}$ , $𝐮_{1} = \frac{1}{\sqrt{2}} (1, 𝑖)$ and $𝐮_{2} = \frac{1}{\sqrt{2}} (1, - 𝑖)$ form an orthonormal basis: ${‖ 𝐮_{𝑗} ‖}^{2} = (1 + 1) / 2 = 1$ , and $𝐮_{1} \cdot 𝐮_{2} = 0$ by Example 6.3.2(b).
(e)With the Frobenius inner product (Proposition 6.1.16), the matrix units $𝐸_{𝑖 𝑗}$ , which have entry $1$ in position $(𝑖, 𝑗)$ and $0$ elsewhere, form an orthonormal basis of $𝔽^{𝑚 \times 𝑛}$ : $⟨ 𝐸_{𝑖 𝑗}, 𝐸_{𝑘 𝑙} ⟩$ is the sum of the products of corresponding entries, which is $1$ if $(𝑖, 𝑗) = (𝑘, 𝑙)$ and $0$ otherwise.

Example 6.3.17 (Orthogonal polynomials). Give ${ℝ [𝑥]}_{\leq 2}$ the inner product $⟨ 𝑝, 𝑞 ⟩ =$ $\int_{- 1}^{1} 𝑝 (𝑡) 𝑞 (𝑡) d 𝑡$ . (Definiteness: if $\int_{- 1}^{1} {𝑝 (𝑡)}^{2} d 𝑡 = 0$ , then $𝑝$ vanishes on $[- 1, 1]$ by Lemma 6.1.14, so it has infinitely many roots and $𝑝 = 𝟎$ by Proposition 7.1.22.) The monomials $1, 𝑥, 𝑥^{2}$ are not orthogonal, since $⟨ 1, 𝑥^{2} ⟩ = 2 / 3$ . But $1, 𝑥, 𝑥^{2} - 1 / 3$ is an orthogonal list: $⟨ 1, 𝑥 ⟩ = 0$ and $⟨ 𝑥, 𝑥^{2} - 1 / 3 ⟩ = 0$ because the integrands are odd, and

⟨ 1, 𝑥^{2} - \frac{1}{3} ⟩ = \int_{- 1}^{1} (𝑡^{2} - \frac{1}{3}) d 𝑡 = \frac{2}{3} - \frac{2}{3} = 0 .

The squared norms are ${‖ 1 ‖}^{2} = 2$ , ${‖ 𝑥 ‖}^{2} = 2 / 3$ , and

{‖ 𝑥^{2} - \frac{1}{3} ‖}^{2} = \int_{- 1}^{1} (𝑡^{4} - \frac{2}{3} 𝑡^{2} + \frac{1}{9}) d 𝑡 = \frac{2}{5} - \frac{4}{9} + \frac{2}{9} = \frac{8}{45} .

So $\frac{1}{\sqrt{2}},$ $\sqrt{3 / 2} 𝑥,$ $\sqrt{45 / 8} (𝑥^{2} - 1 / 3)$ is an orthonormal basis of ${ℝ [𝑥]}_{\leq 2}$ , by Corollary 6.3.14. Up to scaling these are the first three Legendre polynomials. Section 6.4 explains how to produce them from $1, 𝑥, 𝑥^{2}$ systematically.

Coordinates are inner products

Intuition (Why orthonormal coordinates come for free). For a general basis $ℬ︀ = 𝐛_{1}, \dots, 𝐛_{𝑛}$ of $𝑉$ , finding ${[𝐯]}_{ℬ︀}$ means solving $𝐯 =$ $𝑎_{1} 𝐛_{1} +$ $\dots +$ $𝑎_{𝑛} 𝐛_{𝑛}$ for $𝑎_{1}, \dots, 𝑎_{𝑛}$ . In $𝔽^{𝑛}$ this is a linear system of $𝑛$ equations in which, in general, every equation involves every unknown, solved by row reducing the augmented matrix with columns $𝐛_{1}, \dots, 𝐛_{𝑛}, 𝐯$ . Geometrically, in $ℝ^{2}$ the coordinate $𝑎_{1}$ is found by drawing the line through the tip of $𝐯$ parallel to $𝐛_{2}$ and seeing where it meets the line through $𝐛_{1}$ (Figure 6.3.1(a)). So $𝑎_{1}$ depends on $𝐛_{2}$ as well as on $𝐛_{1}$ : tilting $𝐛_{2}$ moves the point of intersection.

For an orthonormal basis $𝐮_{1}, 𝐮_{2}$ , the line through the tip of $𝐯$ parallel to $𝐮_{2}$ is perpendicular to $𝐮_{1}$ , so $𝑎_{1} 𝐮_{1}$ is the foot of the perpendicular from $𝐯$ to the line through $𝐮_{1}$ (Figure 6.3.1(b)). That foot is the shadow of Technique 6.2.4, $𝑐 𝐮_{1}$ with $𝑐 =$ $⟨ 𝐯, 𝐮_{1} ⟩ / {‖ 𝐮_{1} ‖}^{2} =$ $⟨ 𝐯, 𝐮_{1} ⟩$ . So each coordinate is one inner product. It does not involve the other basis vectors, and computing it involves no system at all.

Figure 6.3.1. Reading off coordinates. (a) For a general basis,

𝑎_{1} 𝐛_{1}

is found by moving from the tip of

𝐯

parallel to

𝐛_{2}

, so it depends on both basis vectors. (b) For an orthonormal basis,

𝑎_{𝑗} 𝐮_{𝑗}

is the foot of the perpendicular from

𝐯

to the line through

𝐮_{𝑗}

, and

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

Proposition 6.3.18 (Coordinates in an orthonormal basis). Let $𝒪︀ = 𝐮_{1}, \dots, 𝐮_{𝑘}$ be an orthonormal list in $𝑉$ .

(a)If $𝐯 \in span (𝒪︀)$ , then
$𝐯 = ⟨ 𝐯, 𝐮_{1} ⟩ 𝐮_{1} + \dots + ⟨ 𝐯, 𝐮_{𝑘} ⟩ 𝐮_{𝑘} .$
(b)In particular, if $𝒪︀ = 𝐮_{1}, \dots, 𝐮_{𝑛}$ is an orthonormal basis of $𝑉$ , then every $𝐯 \in 𝑉$ satisfies (a), that is,
${[𝐯]}_{𝒪︀} = (⟨ 𝐯, 𝐮_{1} ⟩, \dots, ⟨ 𝐯, 𝐮_{𝑛} ⟩) .$

Proof.routine

Uses. Definition 1.3.10 (Span), Definition 6.3.15 (Orthonormal list, orthonormal basis), Definition 1.6.14 (Coordinates)

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

Hint 1. Since

𝐯 \in span (𝒪︀)

, write

𝐯 =

𝑎_{1} 𝐮_{1} +

\dots +

𝑎_{𝑘} 𝐮_{𝑘}

. You need to identify

𝑎_{𝑗}

Hint 2. Take the inner product of both sides with

𝐮_{𝑗}

, with

𝐮_{𝑗}

in the second slot.

Sketch. Write

𝐯 = \sum_{𝑙} 𝑎_{𝑙} 𝐮_{𝑙}

. Then

⟨ 𝐯, 𝐮_{𝑗} ⟩ =

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

\sum_{𝑙} 𝑎_{𝑙} 𝛿_{𝑙 𝑗} =

𝑎_{𝑗}

, so the coefficients are the inner products. For (b),

span (𝒪︀) = 𝑉

and coordinates are the unique coefficients.

(a) Since $𝐯 \in span (𝒪︀)$ , there are scalars with $𝐯 =$ $𝑎_{1} 𝐮_{1} +$ $\dots +$ $𝑎_{𝑘} 𝐮_{𝑘}$ . For each $𝑗$ , linearity in the first slot gives

⟨ 𝐯, 𝐮_{𝑗} ⟩ = \sum_{𝑙 = 1}^{𝑘} 𝑎_{𝑙} ⟨ 𝐮_{𝑙}, 𝐮_{𝑗} ⟩ = \sum_{𝑙 = 1}^{𝑘} 𝑎_{𝑙} 𝛿_{𝑙 𝑗} = 𝑎_{𝑗} .

Substituting $𝑎_{𝑗} = ⟨ 𝐯, 𝐮_{𝑗} ⟩$ into $𝐯 = \sum_{𝑗} 𝑎_{𝑗} 𝐮_{𝑗}$ gives (a).

(b) If $𝒪︀$ is a basis, then $span (𝒪︀) = 𝑉$ , so (a) applies to every $𝐯 \in 𝑉$ . The coordinates ${[𝐯]}_{𝒪︀}$ are the unique coefficients $𝑎_{1}, \dots, 𝑎_{𝑛}$ with $𝐯 = \sum_{𝑗} 𝑎_{𝑗} 𝐮_{𝑗}$ (Definition 1.6.14), and we have just seen that $𝑎_{𝑗} = ⟨ 𝐯, 𝐮_{𝑗} ⟩$ . □

Remark 6.3.19 (Which slot). The coefficient of $𝐮_{𝑗}$ is $⟨ 𝐯, 𝐮_{𝑗} ⟩$ , with $𝐯$ in the first slot, the slot in which the inner product is linear. The other order gives $⟨ 𝐮_{𝑗}, 𝐯 ⟩ =$ $⟨ 𝐯, 𝐮_{𝑗} ⟩$ . Over $ℝ$ the two agree, but over $ℂ$ the conjugated numbers are the wrong coordinates. Take the orthonormal basis $𝐮_{1} = (1, 𝑖) / \sqrt{2}$ , $𝐮_{2} = (1, - 𝑖) / \sqrt{2}$ of Example 6.3.16(d) and $𝐯 = (0, 1)$ . Then

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

and indeed $(- 𝑖 / 2) (1, 𝑖) +$ $(𝑖 / 2) (1, - 𝑖) =$ $(0, 1)$ . The conjugated coefficients give $(𝑖 / 2) (1, 𝑖) -$ $(𝑖 / 2) (1, - 𝑖) =$ $(0, - 1)$ instead. Texts that make inner products linear in the second slot, as in Non-example 6.1.25(b), write the coefficient as $⟨ 𝐮_{𝑗}, 𝐯 ⟩$ ; it is the same number.

Example 6.3.20 (Coordinates without a linear system). Take the orthonormal basis $𝒪︀ = 𝐮_{1}, 𝐮_{2}, 𝐮_{3}$ of $ℝ^{3}$ from Example 6.3.16(c) and $𝐯 = (1, 2, 3)$ . By Proposition 6.3.18,

\begin{aligned} ⟨ 𝐯, 𝐮_{1} ⟩ & = \frac{1 + 4 + 6}{3} = \frac{11}{3}, \\ ⟨ 𝐯, 𝐮_{2} ⟩ & = \frac{2 + 2 - 6}{3} = - \frac{2}{3}, \\ ⟨ 𝐯, 𝐮_{3} ⟩ & = \frac{2 - 4 + 3}{3} = \frac{1}{3}, \end{aligned}

so ${[𝐯]}_{𝒪︀} =$ $(11 / 3, - 2 / 3, 1 / 3)$ . Check:

\begin{aligned} \frac{11}{9} (1, 2, 2) - \frac{2}{9} (2, 1, - 2) + \frac{1}{9} (2, - 2, 1) \\ = \frac{1}{9} (9, 18, 27) = (1, 2, 3) . \end{aligned}

Three dot products replaced the row reduction of a $3 \times 4$ augmented matrix.

The same isolation works for orthogonal bases that are not normalized; each coefficient just picks up the factor $1 / {‖ 𝐯_{𝑗} ‖}^{2}$ .

Corollary 6.3.21 (Coordinates in an orthogonal basis). Let $𝐯_{1}, \dots, 𝐯_{𝑛}$ be an orthogonal basis of $𝑉$ , that is, an orthogonal list of nonzero vectors that is a basis. Then every $𝐯 \in 𝑉$ satisfies

𝐯 = \sum_{𝑗 = 1}^{𝑛} \frac{⟨ 𝐯, 𝐯_{𝑗} ⟩}{{‖ 𝐯_{𝑗} ‖}^{2}} 𝐯_{𝑗} .

Proof.routine

Uses. Definition 1.6.1 (Basis), Definition 6.3.1 (Orthogonality)

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

Hint 1. Write

𝐯 = \sum_{𝑙} 𝑎_{𝑙} 𝐯_{𝑙}

and take the inner product with

𝐯_{𝑗}

Hint 2. You get

⟨ 𝐯, 𝐯_{𝑗} ⟩ =

𝑎_{𝑗} {‖ 𝐯_{𝑗} ‖}^{2}

, and

‖ 𝐯_{𝑗} ‖ \neq 0

Sketch. With

𝐯 = \sum_{𝑙} 𝑎_{𝑙} 𝐯_{𝑙}

, isolating coefficients gives

⟨ 𝐯, 𝐯_{𝑗} ⟩ =

𝑎_{𝑗} {‖ 𝐯_{𝑗} ‖}^{2}

; divide by

{‖ 𝐯_{𝑗} ‖}^{2} > 0

Since $𝐯_{1}, \dots, 𝐯_{𝑛}$ is a basis, $𝐯 =$ $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑛} 𝐯_{𝑛}$ for some scalars. Taking the inner product with $𝐯_{𝑗}$ and using orthogonality,

⟨ 𝐯, 𝐯_{𝑗} ⟩ = \sum_{𝑙 = 1}^{𝑛} 𝑎_{𝑙} ⟨ 𝐯_{𝑙}, 𝐯_{𝑗} ⟩ = 𝑎_{𝑗} {‖ 𝐯_{𝑗} ‖}^{2} .

As $𝐯_{𝑗} \neq 𝟎$ , we may divide by ${‖ 𝐯_{𝑗} ‖}^{2} > 0$ , which gives $𝑎_{𝑗} =$ $⟨ 𝐯, 𝐯_{𝑗} ⟩ / {‖ 𝐯_{𝑗} ‖}^{2}$ . □

Each term $⟨ 𝐯, 𝐯_{𝑗} ⟩ / {‖ 𝐯_{𝑗} ‖}^{2} 𝐯_{𝑗}$ is the shadow of $𝐯$ on the line through $𝐯_{𝑗}$ (Technique 6.2.4). So in an orthogonal basis a vector is the sum of its shadows on the basis lines. For a basis that is not orthogonal this fails. In $ℝ^{2}$ with $𝐯_{1} = (1, 0)$ , $𝐯_{2} = (1, 1)$ , and $𝐯 = (0, 1) = - 𝐯_{1} + 𝐯_{2}$ , the shadows are $0 \cdot 𝐯_{1}$ and $(1 / 2) 𝐯_{2}$ , which add up to $(1 / 2, 1 / 2) \neq 𝐯$ .

Parseval’s identity

Coordinates with respect to an orthonormal basis do more than locate a vector. They compute lengths and inner products, by the same formulas as in $𝔽^{𝑛}$ .

Theorem 6.3.22 (Parseval’s identity). Let $𝒪︀ = 𝐮_{1}, \dots, 𝐮_{𝑛}$ be an orthonormal basis of $𝑉$ , and let $𝐯, 𝐰 \in 𝑉$ .

(a) $⟨ 𝐯, 𝐰 ⟩ =$ $\sum_{𝑗 = 1}^{𝑛} ⟨ 𝐯, 𝐮_{𝑗} ⟩ ⟨ 𝐰, 𝐮_{𝑗} ⟩$ . In coordinates,
$⟨ 𝐯, 𝐰 ⟩ = {[𝐯]}_{𝒪︀} \cdot {[𝐰]}_{𝒪︀} = {[𝐰]}_{𝒪︀}^{*} {[𝐯]}_{𝒪︀} .$
(b) ${‖ 𝐯 ‖}^{2} =$ $\sum_{𝑗 = 1}^{𝑛} {| ⟨ 𝐯, 𝐮_{𝑗} ⟩ |}^{2}$ , which is the squared norm of ${[𝐯]}_{𝒪︀}$ in $𝔽^{𝑛}$ .

Proof.routine

Uses. Proposition 6.3.18 (Coordinates in an orthonormal basis), Proposition 6.1.4 (Sesquilinearity), Definition 6.1.8 (Dot product), Notation 6.1.7 (Conjugate transpose), Proposition 6.1.10 (The dot product is an inner product)

Hint 1. It suffices to expand one of the two vectors in the basis. Which one?

Hint 2. Write

𝐰 =

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

by Proposition 6.3.18 and pull the coefficients out of the second slot, remembering the conjugates.

Sketch. Substituting

𝐰 =

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

into the second slot gives

⟨ 𝐯, 𝐰 ⟩ =

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

, which is the dot product of the coordinate vectors. Take

𝐰 = 𝐯

for (b).

(a) By Proposition 6.3.18, $𝐰 =$ $\sum_{𝑗 = 1}^{𝑛} ⟨ 𝐰, 𝐮_{𝑗} ⟩ 𝐮_{𝑗}$ . By Proposition 6.1.4,

⟨ 𝐯, 𝐰 ⟩ = ⟨ 𝐯, \sum_{𝑗 = 1}^{𝑛} ⟨ 𝐰, 𝐮_{𝑗} ⟩ 𝐮_{𝑗} ⟩ = \sum_{𝑗 = 1}^{𝑛} ⟨ 𝐰, 𝐮_{𝑗} ⟩ ⟨ 𝐯, 𝐮_{𝑗} ⟩ .

By Proposition 6.3.18(b), the $𝑗$ th entries of ${[𝐯]}_{𝒪︀}$ and ${[𝐰]}_{𝒪︀}$ are $⟨ 𝐯, 𝐮_{𝑗} ⟩$ and $⟨ 𝐰, 𝐮_{𝑗} ⟩$ , so by Definition 6.1.8 and Notation 6.1.7 this sum is ${[𝐯]}_{𝒪︀} \cdot$ ${[𝐰]}_{𝒪︀} =$ ${[𝐰]}_{𝒪︀}^{*} {[𝐯]}_{𝒪︀}$ .

(b) Take $𝐰 = 𝐯$ in (a) and use $𝑧 𝑧 = {| 𝑧 |}^{2}$ . By Proposition 6.1.10 the result is the squared norm of ${[𝐯]}_{𝒪︀}$ for the dot product. □

Part (b) is also Corollary 6.3.6 applied to $𝐯 =$ $\sum_{𝑗} ⟨ 𝐯, 𝐮_{𝑗} ⟩ 𝐮_{𝑗}$ . For the basis of Example 6.3.20, it says $(121 + 4 + 1) / 9 =$ $14 =$ ${‖ (1, 2, 3) ‖}^{2}$ , and since ${[𝐞_{3}]}_{𝒪︀} =$ $(2 / 3, - 2 / 3, 1 / 3)$ , part (a) says

𝐯 \cdot 𝐞_{3} = \frac{11}{3} \cdot \frac{2}{3} + (- \frac{2}{3}) (- \frac{2}{3}) + \frac{1}{3} \cdot \frac{1}{3} = \frac{27}{9} = 3,

which is indeed the third entry of $𝐯$ .

Intuition (An orthonormal basis turns $𝑉$ into $𝔽^{𝑛}$ ). The coordinate map $𝐯 \mapsto {[𝐯]}_{𝒪︀}$ is a linear bijection $𝑉 \to 𝔽^{𝑛}$ (Proposition 1.6.19), and Parseval’s identity says that it carries the inner product of $𝑉$ to the dot product of $𝔽^{𝑛}$ . So once an orthonormal basis is chosen, every question about lengths, angles, and orthogonality in $𝑉$ can be answered in coordinates, with the formulas of $𝔽^{𝑛}$ . Gram–Schmidt (Theorem 6.4.20) shows that every finite-dimensional inner product space has an orthonormal basis, so every $𝑛$ -dimensional inner product space looks like $𝔽^{𝑛}$ with the dot product; Section 8.4 makes “looks like” precise.

This is special to orthonormal bases. For the basis $ℬ︀ = (1, 0), (1, 1)$ of $ℝ^{2}$ , the orthogonal vectors $𝐞_{1} = (1, 0)$ and $𝐞_{2} = - (1, 0) + (1, 1)$ have coordinate vectors $(1, 0)$ and $(- 1, 1)$ , whose dot product is $- 1$ . In fact ${[𝐱]}_{ℬ︀} \cdot {[𝐲]}_{ℬ︀}$ is a different inner product on $ℝ^{2}$ , the unique one for which $ℬ︀$ is orthonormal (Exercise 6.3.51).

Exercise 6.3.23.routine Show that

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

𝐮_{2} = \frac{1}{\sqrt{3}} (1, - 1, 1)

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

is an orthonormal basis of

ℝ^{3}

. Find the coordinates of

𝐯 = (3, 1, 2)

in this basis, and check your answer with Theorem 6.3.22(b).

Solution.

Uses. Corollary 6.3.14 (Counting orthogonal vectors), Proposition 6.3.18 (Coordinates in an orthonormal basis), Theorem 6.3.22 (Parseval’s identity)

Hint 1. Check the three dot products between different vectors, and the three norms. Then use Corollary 6.3.14.

Hint 2. The

𝑗

th coordinate is

𝐯 \cdot 𝐮_{𝑗}

Sketch. The pairwise dot products of

(1, 1, 0)

(1, - 1, 1)

(- 1, 1, 2)

vanish, and the scalings make them unit vectors. The coordinates are

4 / \sqrt{2} = 2 \sqrt{2}

4 / \sqrt{3}

, and

2 / \sqrt{6}

, and

8 +

16 / 3 +

2 / 3 =

14 =

{‖ 𝐯 ‖}^{2}

The unscaled vectors $(1, 1, 0)$ , $(1, - 1, 1)$ , $(- 1, 1, 2)$ have pairwise dot products $1 - 1 + 0 = 0$ , $- 1 + 1 + 0 = 0$ , and $- 1 - 1 + 2 = 0$ , and squared norms $2$ , $3$ , $6$ . So $𝐮_{1}, 𝐮_{2}, 𝐮_{3}$ is an orthonormal list of length $3 = dim ℝ^{3}$ , hence an orthonormal basis by Corollary 6.3.14.

By Proposition 6.3.18,

\begin{aligned} 𝐯 \cdot 𝐮_{1} & = \frac{4}{\sqrt{2}} = 2 \sqrt{2}, \\ 𝐯 \cdot 𝐮_{2} & = \frac{3 - 1 + 2}{\sqrt{3}} = \frac{4}{\sqrt{3}}, \\ 𝐯 \cdot 𝐮_{3} & = \frac{- 3 + 1 + 4}{\sqrt{6}} = \frac{2}{\sqrt{6}}, \end{aligned}

so ${[𝐯]}_{𝒪︀} =$ $(2 \sqrt{2}, 4 / \sqrt{3}, 2 / \sqrt{6})$ . By Theorem 6.3.22(b), the sum of the squares of the coordinates should be ${‖ 𝐯 ‖}^{2} = 9 + 1 + 4 = 14$ , and indeed $8 +$ $16 / 3 +$ $4 / 6 =$ $8 +$ $16 / 3 +$ $2 / 3 =$ $14$ .

Bessel’s inequality

Parseval’s identity needs a basis. For an orthonormal list that does not span $𝑉$ , the sum $\sum_{𝑗} {| ⟨ 𝐯, 𝐮_{𝑗} ⟩ |}^{2}$ misses part of $𝐯$ , and an inequality remains.

Intuition (What is left over). In

ℝ^{3}

with

𝐮_{1} = 𝐞_{1}

and

𝐮_{2} = 𝐞_{2}

, the sum is

𝑣_{1}^{2} + 𝑣_{2}^{2}

, which falls short of

{‖ 𝐯 ‖}^{2}

𝑣_{3}^{2}

, the squared length of the part of

𝐯

perpendicular to the plane of

𝐮_{1}, 𝐮_{2}

. In general, split

𝐯 = 𝐩 + 𝐰

, where

𝐩 =

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

is what the formula of Proposition 6.3.18 produces and

𝐰 = 𝐯 - 𝐩

is the remainder. Isolating coefficients shows that

𝐰

is orthogonal to every

𝐮_{𝑗}

, hence to

𝐩

, and Pythagoras gives

{‖ 𝐯 ‖}^{2} = {‖ 𝐩 ‖}^{2} + {‖ 𝐰 ‖}^{2}

. For a single unit vector

𝐮_{1}

, this is the decomposition of the first proof of Theorem 6.2.1, and the inequality below is the Cauchy–Schwarz inequality

| ⟨ 𝐯, 𝐮_{1} ⟩ | \leq ‖ 𝐯 ‖

Theorem 6.3.24 (Bessel’s inequality). Let $𝐮_{1}, \dots, 𝐮_{𝑘}$ be an orthonormal list in $𝑉$ , and let $𝐯 \in 𝑉$ . Then

\sum_{𝑗 = 1}^{𝑘} {| ⟨ 𝐯, 𝐮_{𝑗} ⟩ |}^{2} \leq {‖ 𝐯 ‖}^{2},

with equality if and only if $𝐯 \in$ $span (𝐮_{1}, \dots, 𝐮_{𝑘})$ .

Proof.standard

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

Techniques. Orthogonal decomposition (Technique 6.2.4), Take an inner product to isolate a coefficient (Technique 6.3.12)

Hint 1. Let

𝐩 =

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

and

𝐰 = 𝐯 - 𝐩

. Compute

⟨ 𝐰, 𝐮_{𝑙} ⟩

for each

𝑙

Hint 2.

𝐰

is orthogonal to every

𝐮_{𝑙}

, hence to

𝐩

. Apply Theorem 6.3.3 to

𝐯 = 𝐩 + 𝐰

, and compute

{‖ 𝐩 ‖}^{2}

with Corollary 6.3.6.

Hint 3. Equality means

𝐰 = 𝟎

. For the converse, use Proposition 6.3.18(a).

Sketch. With

𝐩 =

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

and

𝐰 = 𝐯 - 𝐩

, we get

⟨ 𝐰, 𝐮_{𝑙} ⟩ =

⟨ 𝐯, 𝐮_{𝑙} ⟩ -

⟨ 𝐯, 𝐮_{𝑙} ⟩ =

0

, so

𝐰 ⟂ 𝐩

. Pythagoras gives

{‖ 𝐯 ‖}^{2} =

{‖ 𝐩 ‖}^{2} +

{‖ 𝐰 ‖}^{2} \geq

{‖ 𝐩 ‖}^{2} =

\sum_{𝑗} {| ⟨ 𝐯, 𝐮_{𝑗} ⟩ |}^{2}

. Equality holds iff

𝐰 = 𝟎

, that is,

𝐯 = 𝐩

. If

𝐯 = 𝐩

, then

𝐯

lies in the span; conversely, if

𝐯

lies in the span, then

𝐯 = 𝐩

by Proposition 6.3.18.

Let $𝐩 =$ $\sum_{𝑗 = 1}^{𝑘} ⟨ 𝐯, 𝐮_{𝑗} ⟩ 𝐮_{𝑗}$ and $𝐰 = 𝐯 - 𝐩$ . For each $𝑙$ ,

\begin{aligned} ⟨ 𝐰, 𝐮_{𝑙} ⟩ & = ⟨ 𝐯, 𝐮_{𝑙} ⟩ - \sum_{𝑗 = 1}^{𝑘} ⟨ 𝐯, 𝐮_{𝑗} ⟩ ⟨ 𝐮_{𝑗}, 𝐮_{𝑙} ⟩ \\ = ⟨ 𝐯, 𝐮_{𝑙} ⟩ - ⟨ 𝐯, 𝐮_{𝑙} ⟩ = 0 . \end{aligned}

So $𝐰 \in$ ${𝐮_{1}, \dots, 𝐮_{𝑘}}^{⟂} =$ ${span (𝐮_{1}, \dots, 𝐮_{𝑘})}^{⟂}$ by Proposition 6.3.9(c), and in particular $𝐰 ⟂ 𝐩$ . By Theorem 6.3.3(a) applied to $𝐯 = 𝐩 + 𝐰$ , and Corollary 6.3.6 applied to $𝐩$ ,

{‖ 𝐯 ‖}^{2} = {‖ 𝐩 ‖}^{2} + {‖ 𝐰 ‖}^{2} = \sum_{𝑗 = 1}^{𝑘} {| ⟨ 𝐯, 𝐮_{𝑗} ⟩ |}^{2} + {‖ 𝐰 ‖}^{2} .

(6.3.2)

Since ${‖ 𝐰 ‖}^{2} \geq 0$ , the inequality follows.

By (6.3.2), equality holds if and only if $‖ 𝐰 ‖ = 0$ , that is (Proposition 6.1.27), if and only if $𝐯 = 𝐩$ . If $𝐯 = 𝐩$ , then $𝐯$ is a linear combination of $𝐮_{1}, \dots, 𝐮_{𝑘}$ . Conversely, if $𝐯 \in$ $span (𝐮_{1}, \dots, 𝐮_{𝑘})$ , then $𝐯 = 𝐩$ by Proposition 6.3.18(a). □

The space $𝑉$ need not be finite-dimensional here. The vector $𝐩$ is the orthogonal projection of $𝐯$ onto $span (𝐮_{1}, \dots, 𝐮_{𝑘})$ , the subject of Section 6.4, where we will also see that $‖ 𝐰 ‖ = ‖ 𝐯 - 𝐩 ‖$ is the distance from $𝐯$ to that span (Theorem 6.4.33). Bessel’s inequality says that projecting onto a subspace cannot increase length, and its equality case gives a membership test: $𝐯$ lies in the span of an orthonormal list exactly when the list captures all of ${‖ 𝐯 ‖}^{2}$ .

Example 6.3.25 (Bessel in $ℝ^{3}$ ). Keep $𝐯 = (1, 2, 3)$ and the vectors $𝐮_{1}, 𝐮_{2}$ of Example 6.3.16(c), but drop $𝐮_{3}$ . Then

{| ⟨ 𝐯, 𝐮_{1} ⟩ |}^{2} + {| ⟨ 𝐯, 𝐮_{2} ⟩ |}^{2} = \frac{121}{9} + \frac{4}{9} = \frac{125}{9} < 14,

and the deficit $1 / 9 = {⟨ 𝐯, 𝐮_{3} ⟩}^{2}$ is the part that $𝐮_{3}$ would have contributed. So $(1, 2, 3) \notin$ $span (𝐮_{1}, 𝐮_{2})$ . On the other hand $𝐱 = (1, 1, 0)$ has $⟨ 𝐱, 𝐮_{1} ⟩ =$ $⟨ 𝐱, 𝐮_{2} ⟩ =$ $1$ , so the sum is $2 = {‖ 𝐱 ‖}^{2}$ , and therefore $𝐱 \in span (𝐮_{1}, 𝐮_{2})$ ; indeed $𝐱 = 𝐮_{1} + 𝐮_{2}$ .

Aside (Fourier coefficients).Beyond 21-242 Bessel’s inequality matters most in infinite-dimensional spaces, where an orthonormal list can never be a basis. On $𝐶 ([0, 2 𝜋], ℂ)$ , take the inner product $⟨ 𝑓, 𝑔 ⟩ =$ $\frac{1}{2 𝜋} \int_{0}^{2 𝜋} 𝑓 (𝑡) 𝑔 (𝑡) d 𝑡$ (Proposition 6.1.13 on $[0, 2 𝜋]$ , scaled by a positive constant), and let $𝑒_{𝑘} (𝑡) =$ $cos 𝑘 𝑡 +$ $𝑖 sin 𝑘 𝑡$ for $𝑘 \in ℤ$ . The angle subtraction formulas give $𝑒_{𝑗} 𝑒_{𝑘} = 𝑒_{𝑗 - 𝑘}$ , and $\int_{0}^{2 𝜋} cos 𝑚 𝑡 d 𝑡 =$ $\int_{0}^{2 𝜋} sin 𝑚 𝑡 d 𝑡 =$ $0$ for $𝑚 \neq 0$ , so $⟨ 𝑒_{𝑗}, 𝑒_{𝑘} ⟩ =$ $𝛿_{𝑗 𝑘}$ . Bessel’s inequality for the orthonormal list $𝑒_{- 𝑁}, \dots, 𝑒_{𝑁}$ says that the Fourier coefficients $𝑐_{𝑘} = ⟨ 𝑓, 𝑒_{𝑘} ⟩$ of $𝑓$ satisfy

\sum_{𝑘 = - 𝑁}^{𝑁} {| 𝑐_{𝑘} |}^{2} \leq \frac{1}{2 𝜋} \int_{0}^{2 𝜋} {| 𝑓 (𝑡) |}^{2} d 𝑡 for every 𝑁 .

The bound does not depend on $𝑁$ , so the series $\sum_{𝑘} {| 𝑐_{𝑘} |}^{2}$ converges, and in particular $𝑐_{𝑘} \to 0$ as $| 𝑘 | \to \infty$ . Parseval’s identity, with equality, also holds for the full infinite sum, but proving it takes analysis (Section 15.3). Both names come from this setting: the identity and the inequality were first found for Fourier series.

6.3.3Matrices with orthonormal columns

In $𝔽^{𝑚}$ with the dot product, a list of $𝑛$ vectors is the same thing as an $𝑚 \times 𝑛$ matrix, whose columns are the vectors. Orthonormality of the list is a statement about the dot products of the columns with each other, and these are the entries of a single matrix product.

Definition 6.3.26 (Conjugate transpose). Let $𝐴 =$ $(𝑎_{𝑖 𝑗}) \in$ $𝔽^{𝑚 \times 𝑛}$ . The conjugate transpose of $𝐴$ is the matrix $𝐴^{*} \in 𝔽^{𝑛 \times 𝑚}$ with entries

{(𝐴^{*})}_{𝑖 𝑗} = 𝑎_{𝑗 𝑖} (1 \leq 𝑖 \leq 𝑛, 1 \leq 𝑗 \leq 𝑚) .

That is, $𝐴^{*} = 𝐴^{𝖳}$ , where $𝐴 = (𝑎_{𝑖 𝑗})$ conjugates every entry (Definition 2.4.21). If $𝐴$ is real, $𝐴^{*} = 𝐴^{𝖳}$ . A square matrix $𝐴$ with $𝐴^{*} = 𝐴$ is called Hermitian; a real Hermitian matrix is a symmetric matrix.

This is the matrix of Notation 6.1.7. In particular, for $𝐰 \in 𝔽^{𝑛}$ , $𝐰^{*}$ is the row $(𝑤_{1}, \dots, 𝑤_{𝑛})$ , and $𝐰^{*} 𝐯 = 𝐯 \cdot 𝐰$ for $𝐯 \in 𝔽^{𝑛}$ (Definition 6.1.8). For example,

{(\begin{matrix} 1 & 𝑖 & 2 \\ 0 & 1 - 𝑖 & 3 𝑖 \end{matrix})}^{*} = (\begin{matrix} 1 & 0 \\ - 𝑖 & 1 + 𝑖 \\ 2 & - 3 𝑖 \end{matrix}) .

Proposition 6.3.27 (Properties of the conjugate transpose). Let $𝐴, 𝐴^{'} \in 𝔽^{𝑚 \times 𝑛}$ , $𝐵 \in 𝔽^{𝑛 \times 𝑝}$ , and $𝑐 \in 𝔽$ .

(a) ${(𝐴^{*})}^{*} = 𝐴$ and ${(𝑐 𝐴 + 𝐴^{'})}^{*} =$ $𝑐 𝐴^{*} +$ $𝐴^{' *}$ .
(b) ${(𝐴 𝐵)}^{*} = 𝐵^{*} 𝐴^{*}$ .
(c)If $𝑚 = 𝑛$ and $𝐴$ is invertible, then $𝐴^{*}$ is invertible and ${(𝐴^{*})}^{- 1} = {(𝐴^{- 1})}^{*}$ .
(d) $(𝐴 𝐱) \cdot$ $𝐲 =$ $𝐱 \cdot$ $(𝐴^{*} 𝐲)$ for all $𝐱 \in 𝔽^{𝑛}$ and $𝐲 \in 𝔽^{𝑚}$ .

Proof.routine

Uses. Definition 6.3.26 (Conjugate transpose), Proposition 2.4.22 (Transpose is a linear involution), Proposition 2.4.23 (Transpose of a product), Proposition 2.4.14 (Algebra of matrices), Definition 2.5.12 (Invertible), Definition 6.1.8 (Dot product), Notation 6.1.1 (Real and complex scalars)

Techniques. Compute entry by entry (Technique 2.4.15)

Hint 1. (a) is entrywise. For (b), first show

𝐴 𝐵 = 𝐴 𝐵

entry by entry, then transpose with Proposition 2.4.23.

Hint 2. For (c), apply

*

𝐴 𝐴^{- 1} = 𝐼

and

𝐴^{- 1} 𝐴 = 𝐼

using (b).

Hint 3. For (d), write both sides as matrix products:

(𝐴 𝐱) \cdot

𝐲 =

𝐲^{*} (𝐴 𝐱)

. Regroup and use (a) and (b) to recognize

𝐲^{*} 𝐴

{(𝐴^{*} 𝐲)}^{*}

Sketch. (a) Conjugating twice and transposing twice undo themselves, and conjugation respects sums and products. (b)

𝐴 𝐵 = 𝐴 𝐵

entrywise, and

{(𝐴 𝐵)}^{𝖳} = 𝐵^{𝖳} 𝐴^{𝖳}

. (c)

𝐴^{*} {(𝐴^{- 1})}^{*} =

{(𝐴^{- 1} 𝐴)}^{*} =

𝐼^{*} =

𝐼

, and similarly on the other side. (d)

(𝐴 𝐱) \cdot

𝐲 =

𝐲^{*} 𝐴 𝐱 =

{(𝐴^{*} 𝐲)}^{*} 𝐱 =

𝐱 \cdot

(𝐴^{*} 𝐲)

(a) The $(𝑖, 𝑗)$ entry of ${(𝐴^{*})}^{*}$ is ${(𝐴^{*})}_{𝑗 𝑖} =$ $𝑎_{𝑖 𝑗} =$ $𝑎_{𝑖 𝑗}$ . The $(𝑖, 𝑗)$ entry of ${(𝑐 𝐴 + 𝐴^{'})}^{*}$ is $𝑐 𝑎_{𝑗 𝑖} + 𝑎_{𝑗 𝑖}^{'} =$ $𝑐 𝑎_{𝑗 𝑖} +$ $𝑎_{𝑗 𝑖}^{'}$ , the $(𝑖, 𝑗)$ entry of $𝑐 𝐴^{*} + 𝐴^{' *}$ .

(b) Since conjugation respects sums and products (Notation 6.1.1), the $(𝑖, 𝑗)$ entry of $𝐴 𝐵$ is $\sum_{𝑙} 𝑎_{𝑖 𝑙} 𝑏_{𝑙 𝑗} =$ $\sum_{𝑙} 𝑎_{𝑖 𝑙} 𝑏_{𝑙 𝑗}$ , the $(𝑖, 𝑗)$ entry of $𝐴 𝐵$ . So $𝐴 𝐵 = 𝐴 𝐵$ , and by Proposition 2.4.23,

{(𝐴 𝐵)}^{*} = {(𝐴 𝐵)}^{𝖳} = 𝐵^{𝖳} 𝐴^{𝖳} = 𝐵^{*} 𝐴^{*} .

(c) By (b), $𝐴^{*} {(𝐴^{- 1})}^{*} =$ ${(𝐴^{- 1} 𝐴)}^{*} =$ $𝐼^{*} =$ $𝐼$ and ${(𝐴^{- 1})}^{*} 𝐴^{*} =$ ${(𝐴 𝐴^{- 1})}^{*} =$ $𝐼^{*} =$ $𝐼$ , since $𝐼$ is real and symmetric. So ${(𝐴^{- 1})}^{*}$ is a two-sided inverse of $𝐴^{*}$ (Definition 2.5.12).

(d) Identifying $1 \times 1$ matrices with scalars, $(𝐴 𝐱) \cdot$ $𝐲 =$ $𝐲^{*} (𝐴 𝐱) =$ $(𝐲^{*} 𝐴) 𝐱$ by associativity (Proposition 2.4.14). By (b) and (a), ${(𝐴^{*} 𝐲)}^{*} =$ $𝐲^{*} {(𝐴^{*})}^{*} =$ $𝐲^{*} 𝐴$ . Hence $(𝐴 𝐱) \cdot$ $𝐲 =$ ${(𝐴^{*} 𝐲)}^{*} 𝐱 =$ $𝐱 \cdot$ $(𝐴^{*} 𝐲)$ . □

Part (d) is what makes $𝐴^{*}$ useful: it moves a matrix from one side of the dot product to the other, at the price of a star. Section 6.6 turns this property into the definition of the adjoint of a linear map.

Gram matrices

All the inner products among the vectors of a list fit into one matrix.

Definition 6.3.28 (Gram matrix). The Gram matrix of a list $𝐯_{1}, \dots, 𝐯_{𝑘}$ in $𝑉$ is the matrix $𝐺 \in 𝔽^{𝑘 \times 𝑘}$ with entries

𝑔_{𝑖 𝑗} = ⟨ 𝐯_{𝑗}, 𝐯_{𝑖} ⟩ .

The order of the indices, with $𝑗$ in the first slot, matches Proposition 6.1.22 and keeps conjugates out of the next results. By conjugate symmetry $𝐺^{*} = 𝐺$ , and the diagonal entries are the squared norms ${‖ 𝐯_{𝑖} ‖}^{2}$ . The list is orthogonal if and only if $𝐺$ is diagonal, and orthonormal if and only if $𝐺 = 𝐼_{𝑘}$ .

Theorem 6.3.29 (Orthonormal columns). Let $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ have columns $𝐚_{1}, \dots, 𝐚_{𝑛}$ . Then

{(𝐴^{*} 𝐴)}_{𝑖 𝑗} = 𝐚_{𝑗} \cdot 𝐚_{𝑖} (1 \leq 𝑖, 𝑗 \leq 𝑛),

so $𝐴^{*} 𝐴$ is the Gram matrix of the columns of $𝐴$ . In particular, the columns of $𝐴$ are orthonormal if and only if $𝐴^{*} 𝐴 = 𝐼_{𝑛}$ , and orthogonal if and only if $𝐴^{*} 𝐴$ is diagonal.

Proof.routine

Uses. Proposition 2.4.8 (Four views of the product), Definition 6.3.26 (Conjugate transpose), Definition 6.1.8 (Dot product), Definition 6.3.28 (Gram matrix), Definition 6.3.15 (Orthonormal list, orthonormal basis), Definition 2.3.5 (Identity matrix)

Hint 1. Compute the

(𝑖, 𝑗)

entry of

𝐴^{*} 𝐴

as row

𝑖

𝐴^{*}

times column

𝑗

𝐴

Hint 2. Row

𝑖

𝐴^{*}

𝐚_{𝑖}^{*}

. What is

𝐚_{𝑖}^{*} 𝐚_{𝑗}

Sketch. Row

𝑖

𝐴^{*}

𝐚_{𝑖}^{*}

and column

𝑗

𝐴

𝐚_{𝑗}

, so

{(𝐴^{*} 𝐴)}_{𝑖 𝑗} =

𝐚_{𝑖}^{*} 𝐚_{𝑗} =

𝐚_{𝑗} \cdot

𝐚_{𝑖}

. Orthonormality says

𝐚_{𝑗} \cdot 𝐚_{𝑖} = 𝛿_{𝑖 𝑗}

, which is the statement

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

By Definition 6.3.26, row $𝑖$ of $𝐴^{*}$ is $(𝑎_{1 𝑖}, \dots, 𝑎_{𝑚 𝑖}) =$ $𝐚_{𝑖}^{*}$ . By Proposition 2.4.8(a),

{(𝐴^{*} 𝐴)}_{𝑖 𝑗} = 𝐚_{𝑖}^{*} 𝐚_{𝑗} = \sum_{𝑙 = 1}^{𝑚} 𝑎_{𝑙 𝑗} 𝑎_{𝑙 𝑖} = 𝐚_{𝑗} \cdot 𝐚_{𝑖},

which is the $(𝑖, 𝑗)$ entry of the Gram matrix of $𝐚_{1}, \dots, 𝐚_{𝑛}$ for the dot product. The columns are orthonormal if and only if $𝐚_{𝑗} \cdot 𝐚_{𝑖} = 𝛿_{𝑖 𝑗}$ for all $𝑖, 𝑗$ (Definition 6.3.15), that is, if and only if $𝐴^{*} 𝐴 =$ $(𝛿_{𝑖 𝑗}) =$ $𝐼_{𝑛}$ (Definition 2.3.5). Similarly, they are orthogonal if and only if every off-diagonal entry of $𝐴^{*} 𝐴$ is $0$ . □

For example, the matrix with the columns $𝐮_{1} = (1, 𝑖) / \sqrt{2}$ and $𝐮_{2} = (1, - 𝑖) / \sqrt{2}$ of Example 6.3.16(d) satisfies

\frac{1}{\sqrt{2}} (\begin{matrix} 1 & - 𝑖 \\ 1 & 𝑖 \end{matrix}) \cdot \frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 𝑖 & - 𝑖 \end{matrix}) = \frac{1}{2} (\begin{matrix} 1 + 1 & 1 - 1 \\ 1 - 1 & 1 + 1 \end{matrix}) = 𝐼_{2} .

The condition $𝐴^{*} 𝐴 = 𝐼_{𝑛}$ does not require $𝐴$ to be square. The $3 \times 2$ matrix with columns $𝐮_{1}, 𝐮_{2}$ from Example 6.3.16(c) has $𝐴^{*} 𝐴 = 𝐼_{2}$ . But $𝐴 𝐴^{*} \neq 𝐼_{3}$ , since $𝐴 𝐴^{*}$ has rank at most $2$ (Theorem 4.3.3); Section 6.4 identifies $𝐴 𝐴^{*}$ as the projection onto the plane spanned by the columns.

Gram matrices are useful beyond orthonormality. They detect linear independence of any list.

Proposition 6.3.30 (Gram matrices detect independence). Let $𝐺$ be the Gram matrix of a list $𝐯_{1}, \dots, 𝐯_{𝑘}$ in $𝑉$ , and let $𝐜 =$ $(𝑐_{1}, \dots, 𝑐_{𝑘}) \in$ $𝔽^{𝑘}$ . Then:

(a) $𝐜^{*} 𝐺 𝐜 =$ ${‖ 𝑐_{1} 𝐯_{1} + \dots + 𝑐_{𝑘} 𝐯_{𝑘} ‖}^{2}$ ;
(b) $𝐺 𝐜 = 𝟎$ if and only if $𝑐_{1} 𝐯_{1} +$ $\dots +$ $𝑐_{𝑘} 𝐯_{𝑘} =$ $𝟎$ .

Consequently, $𝐺$ is invertible if and only if $𝐯_{1}, \dots, 𝐯_{𝑘}$ is linearly independent.

Proof.standard

Uses. Definition 6.3.28 (Gram matrix), Definition 2.3.8 (Matrix–vector product), Proposition 6.1.4 (Sesquilinearity), Definition 6.1.2 (Inner product), Theorem 1.5.5 (Independence is decided at zero), a square matrix whose kernel is ${𝟎}$ is invertible (Section 3.5)

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

Hint 1. Let

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

. Show that the

𝑖

th entry of

𝐺 𝐜

⟨ 𝐰, 𝐯_{𝑖} ⟩

Hint 2. For (a),

𝐜^{*} 𝐺 𝐜 =

\sum_{𝑖} 𝑐_{𝑖} {(𝐺 𝐜)}_{𝑖}

; recognize this as

⟨ 𝐰, \sum_{𝑖} 𝑐_{𝑖} 𝐯_{𝑖} ⟩

Hint 3. For (b), one direction is immediate from the formula for

{(𝐺 𝐜)}_{𝑖}

. For the other, use (a) and definiteness.

Sketch. With

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

{(𝐺 𝐜)}_{𝑖} =

\sum_{𝑗} ⟨ 𝐯_{𝑗}, 𝐯_{𝑖} ⟩ 𝑐_{𝑗} =

⟨ 𝐰, 𝐯_{𝑖} ⟩

, and then

𝐜^{*} 𝐺 𝐜 =

\sum_{𝑖} 𝑐_{𝑖} ⟨ 𝐰, 𝐯_{𝑖} ⟩ =

⟨ 𝐰, 𝐰 ⟩

. If

𝐰 = 𝟎

, then

𝐺 𝐜 = 𝟎

; if

𝐺 𝐜 = 𝟎

, then

{‖ 𝐰 ‖}^{2} = 𝐜^{*} 𝟎 = 0

. So

ker 𝐺

is the set of coefficient vectors of linear relations, which is

{𝟎}

exactly when the list is independent.

Let $𝐰 =$ $𝑐_{1} 𝐯_{1} +$ $\dots +$ $𝑐_{𝑘} 𝐯_{𝑘}$ . By Definition 2.3.8 and linearity in the first slot,

{(𝐺 𝐜)}_{𝑖} = \sum_{𝑗 = 1}^{𝑘} 𝑔_{𝑖 𝑗} 𝑐_{𝑗} = \sum_{𝑗 = 1}^{𝑘} 𝑐_{𝑗} ⟨ 𝐯_{𝑗}, 𝐯_{𝑖} ⟩ = ⟨ 𝐰, 𝐯_{𝑖} ⟩ .

(a) By the formula above and Proposition 6.1.4,

\begin{aligned} 𝐜^{*} 𝐺 𝐜 & = \sum_{𝑖 = 1}^{𝑘} 𝑐_{𝑖} {(𝐺 𝐜)}_{𝑖} = \sum_{𝑖 = 1}^{𝑘} 𝑐_{𝑖} ⟨ 𝐰, 𝐯_{𝑖} ⟩ \\ = ⟨ 𝐰, \sum_{𝑖 = 1}^{𝑘} 𝑐_{𝑖} 𝐯_{𝑖} ⟩ = {‖ 𝐰 ‖}^{2} . \end{aligned}

(b) If $𝐰 = 𝟎$ , every entry $⟨ 𝐰, 𝐯_{𝑖} ⟩$ of $𝐺 𝐜$ is $0$ . Conversely, if $𝐺 𝐜 = 𝟎$ , then by (a), ${‖ 𝐰 ‖}^{2} = 𝐜^{*} 𝟎 = 0$ , so $𝐰 = 𝟎$ by definiteness.

By (b), $ker 𝐺$ consists of the coefficient vectors of linear relations among $𝐯_{1}, \dots, 𝐯_{𝑘}$ . So $ker 𝐺 = {𝟎}$ if and only if the list is linearly independent (Theorem 1.5.5). Since $𝐺$ is square, $ker 𝐺 = {𝟎}$ if and only if $𝐺$ is invertible (Section 3.5). □

Technique 6.3.31 (Gram matrices). To study a list $𝐯_{1}, \dots, 𝐯_{𝑘}$ in an inner product space, record all the inner products $⟨ 𝐯_{𝑗}, 𝐯_{𝑖} ⟩$ in its Gram matrix $𝐺$ . Questions about the list become questions about one matrix: the list is orthonormal if and only if $𝐺 = 𝐼$ , orthogonal if and only if $𝐺$ is diagonal, and independent if and only if $𝐺$ is invertible, and the combination with coefficient vector $𝐜$ has squared length $𝐜^{*} 𝐺 𝐜$ . When the vectors are the columns of $𝐴 \in 𝔽^{𝑚 \times 𝑛}$ , $𝐺 = 𝐴^{*} 𝐴$ , so these become statements about $𝐴^{*} 𝐴$ .

Reach for it when the hypotheses are about inner products among the vectors of a list (lengths, angles, orthogonality) and the conclusion is about the list itself, or when the product $𝐴^{*} 𝐴$ appears. The canonical example is Proposition 6.3.30. In Section 6.5 the normal equations have the coefficient matrix $𝐴^{*} 𝐴$ , and Proposition 6.3.30 shows that they have a unique solution exactly when the columns of $𝐴$ are independent.

Used in 15 places and 6 practice exercises

Proposition 6.3.41, Exercise 6.3.54, Exercise 6.3.56, Exercise 6.4.59, Proposition 6.5.23, Exercise 6.5.43, Exercise 6.6.46, Exercise 6.7.11, Problem 6.4, Problem 6.9, Problem 6.12, Theorem 8.3.5, Proposition 8.3.15, Exercise 8.3.32, Exercise 8.3.35; 6 practice exercises.

Example 6.3.32 (A relation read off from a Gram matrix). In $ℝ^{3}$ , let $𝐯_{1} = (1, 0, 1)$ , $𝐯_{2} = (0, 1, 1)$ , $𝐯_{3} = (1, - 1, 0)$ . Their Gram matrix is

𝐺 = (\begin{matrix} 2 & 1 & 1 \\ 1 & 2 & - 1 \\ 1 & - 1 & 2 \end{matrix}),

and $𝐺 (1, - 1, - 1) =$ $(2 - 1 - 1, 1 - 2 + 1, 1 + 1 - 2) =$ $𝟎$ . By Proposition 6.3.30(b), $𝐯_{1} - 𝐯_{2} - 𝐯_{3} = 𝟎$ , which is easily checked. So the list is dependent, and $𝐺$ is not invertible.

Unitary and orthogonal matrices

Definition 6.3.33 (Unitary and orthogonal matrices). A square matrix

𝑈 \in 𝔽^{𝑛 \times 𝑛}

is unitary if

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

, that is (Theorem 6.3.29), if its columns form an orthonormal basis of

𝔽^{𝑛}

. A real unitary matrix, that is, a matrix

𝑄 \in ℝ^{𝑛 \times 𝑛}

with

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

, is called orthogonal.

An $𝑛 \times 𝑛$ matrix has $𝑛$ columns, so by Corollary 6.3.14 its columns are an orthonormal basis of $𝔽^{𝑛}$ as soon as they are orthonormal. The name “orthogonal matrix” is traditional but misleading: the columns of an orthogonal matrix are orthonormal, not merely orthogonal. The matrix $(\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix})$ has orthogonal columns of length $\sqrt{2}$ and is not orthogonal; dividing it by $\sqrt{2}$ makes it orthogonal.

Proposition 6.3.34 (Characterizations of unitary matrices). For

𝑈 \in 𝔽^{𝑛 \times 𝑛}

, the following are equivalent:

(i) $𝑈^{*} 𝑈 = 𝐼_{𝑛}$ , that is, the columns of $𝑈$ are orthonormal;
(ii) $𝑈$ is invertible and $𝑈^{- 1} = 𝑈^{*}$ ;
(iii) $𝑈 𝑈^{*} = 𝐼_{𝑛}$ , that is, the rows of $𝑈$ , read as vectors of $𝔽^{𝑛}$ , are orthonormal;
(iv) $𝑈^{*}$ is unitary.

Proof.routine

Uses. Theorem 3.5.23 (One-sided inverses of square matrices), Proposition 6.3.27 (Properties of the conjugate transpose), Theorem 6.3.29 (Orthonormal columns), Definition 2.5.12 (Invertible), Definition 6.1.8 (Dot product)

Techniques. Proving TFAE (Technique 2.7.1)

Hint 1. (i) says that

𝑈^{*}

is a left inverse of the square matrix

𝑈

. What do you know about one-sided inverses of square matrices?

Hint 2. Prove (i)

\Rightarrow

(ii)

\Rightarrow

(iii)

\Rightarrow

(i), then compare (iii) and (iv) using

{(𝑈^{*})}^{*} = 𝑈

Hint 3. For the reading of (iii), compute the

(𝑖, 𝑗)

entry of

𝑈 𝑈^{*}

as a dot product of two rows.

Sketch. For a square matrix a one-sided inverse is two-sided, so

𝑈^{*} 𝑈 = 𝐼

and

𝑈 𝑈^{*} = 𝐼

each imply

𝑈^{- 1} = 𝑈^{*}

, which implies both. Statement (iv) says

{(𝑈^{*})}^{*} 𝑈^{*} = 𝐼

, which is

𝑈 𝑈^{*} = 𝐼

. Finally

{(𝑈 𝑈^{*})}_{𝑖 𝑗} =

\sum_{𝑙} 𝑢_{𝑖 𝑙} 𝑢_{𝑗 𝑙}

is the dot product of rows

𝑖

and

𝑗

We prove (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (i) and (iii) $\Leftrightarrow$ (iv).

(i) $\Rightarrow$ (ii). $𝑈^{*}$ is a left inverse of the square matrix $𝑈$ , so it is a two-sided inverse by Theorem 3.5.23. That is, $𝑈$ is invertible with $𝑈^{- 1} = 𝑈^{*}$ .

(ii) $\Rightarrow$ (iii). $𝑈 𝑈^{*} = 𝑈 𝑈^{- 1} = 𝐼_{𝑛}$ .

(iii) $\Rightarrow$ (i). $𝑈^{*}$ is a right inverse of the square matrix $𝑈$ , so again it is a two-sided inverse by Theorem 3.5.23, and $𝑈^{*} 𝑈 = 𝐼_{𝑛}$ .

(iii) $\Leftrightarrow$ (iv). By Proposition 6.3.27(a), ${(𝑈^{*})}^{*} 𝑈^{*} = 𝑈 𝑈^{*}$ , so $𝑈^{*}$ is unitary exactly when $𝑈 𝑈^{*} = 𝐼_{𝑛}$ .

Finally, the $(𝑖, 𝑗)$ entry of $𝑈 𝑈^{*}$ is $\sum_{𝑙} 𝑢_{𝑖 𝑙} 𝑢_{𝑗 𝑙}$ , which is the dot product of $𝐫_{𝑖} =$ $(𝑢_{𝑖 1}, \dots, 𝑢_{𝑖 𝑛})$ with $𝐫_{𝑗}$ (Definition 6.1.8). So $𝑈 𝑈^{*} = 𝐼_{𝑛}$ says that $𝐫_{𝑖} \cdot 𝐫_{𝑗} = 𝛿_{𝑖 𝑗}$ , that is, the rows are orthonormal. □

That the rows of a square matrix are orthonormal whenever its columns are is not visible from either list by itself; it comes from the fact that one-sided inverses of square matrices are two-sided. For non-square matrices it fails: the columns of $(\begin{matrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix})$ are orthonormal, but its rows $(1, 0)$ , $(0, 1)$ , $(0, 0)$ are not.

Example 6.3.35 (Unitary and orthogonal matrices).

(a)For every $𝜃 \in ℝ$ , the rotation and the reflection
$𝑅_{𝜃} = (\begin{matrix} cos 𝜃 & - sin 𝜃 \\ sin 𝜃 & cos 𝜃 \end{matrix}), 𝑆_{𝜃} = (\begin{matrix} cos 𝜃 & sin 𝜃 \\ sin 𝜃 & - cos 𝜃 \end{matrix})$
are orthogonal. The columns of $𝑅_{𝜃}$ are the orthonormal basis of Example 6.3.16(b), and those of $𝑆_{𝜃}$ are the same two vectors up to the sign of the second.
(b)Every permutation matrix (Definition 5.2.29) is orthogonal, since its columns are the standard basis vectors in some order.
(c)A diagonal matrix $diag (𝜆_{1}, \dots, 𝜆_{𝑛})$ is unitary if and only if $| 𝜆_{𝑗} | = 1$ for every $𝑗$ , since its columns $𝜆_{𝑗} 𝐞_{𝑗}$ are orthogonal with norms $| 𝜆_{𝑗} |$ .
(d)The matrices
$\frac{1}{\sqrt{2}} (\begin{matrix} 1 & 1 \\ 𝑖 & - 𝑖 \end{matrix}) and \frac{1}{3} (\begin{matrix} 1 & 2 & 2 \\ 2 & 1 & - 2 \\ 2 & - 2 & 1 \end{matrix})$
are unitary and orthogonal respectively, by Example 6.3.16(d) and (c).

The definition only asks for orthonormal columns. What unitary matrices do geometrically, namely preserve lengths and inner products, and what they look like (rotations and reflections, in the real case) is the subject of Section 8.4. Here we only record why they belong in this section: they are the matrices whose linear systems are solved by the method of Proposition 6.3.18.

Corollary 6.3.36 (Orthonormal coordinates in

𝔽^{𝑛}

). Let

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

be an orthonormal basis of

𝔽^{𝑛}

, and let

𝑈

be the unitary matrix with columns

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

. Then

{[𝐱]}_{𝒪︀} = 𝑈^{*} 𝐱

for every

𝐱 \in 𝔽^{𝑛}

Proof (by inner products).routine

Uses. Proposition 6.3.18 (Coordinates in an orthonormal basis), Proposition 2.4.8 (Four views of the product), Definition 6.3.26 (Conjugate transpose)

Hint 1. By Proposition 6.3.18, the

𝑗

th coordinate is

𝐱 \cdot 𝐮_{𝑗}

. Write it as a matrix product.

Hint 2.

𝐱 \cdot 𝐮_{𝑗} = 𝐮_{𝑗}^{*} 𝐱

, and

𝐮_{𝑗}^{*}

is row

𝑗

𝑈^{*}

Sketch. The

𝑗

th coordinate is

𝐱 \cdot 𝐮_{𝑗} = 𝐮_{𝑗}^{*} 𝐱

, and row

𝑗

𝑈^{*}

𝐮_{𝑗}^{*}

, so this is the

𝑗

th entry of

𝑈^{*} 𝐱

By Proposition 6.3.18(b), the

𝑗

th entry of

{[𝐱]}_{𝒪︀}

𝐱 \cdot 𝐮_{𝑗} = 𝐮_{𝑗}^{*} 𝐱

. Row

𝑗

𝑈^{*}

𝐮_{𝑗}^{*}

(Definition 6.3.26), so by Proposition 2.4.8 this is the

𝑗

th entry of

𝑈^{*} 𝐱

. □

Proof (by solving the system).routine

Uses. Definition 1.6.14 (Coordinates), Definition 2.3.8 (Matrix–vector product), Proposition 6.3.34 (Characterizations of unitary matrices)

Hint 1. The coordinate vector

𝐜 = {[𝐱]}_{𝒪︀}

is the unique solution of

𝑐_{1} 𝐮_{1} +

\dots +

𝑐_{𝑛} 𝐮_{𝑛} =

𝐱

. Write this as a matrix equation.

Hint 2. The equation is

𝑈 𝐜 = 𝐱

. Solve it with

𝑈^{- 1}

Sketch.

{[𝐱]}_{𝒪︀}

is the solution of

𝑈 𝐜 = 𝐱

, and

𝑈^{- 1} = 𝑈^{*}

by Proposition 6.3.34, so

𝐜 = 𝑈^{*} 𝐱

By Definition 1.6.14 and Definition 2.3.8,

𝐜 = {[𝐱]}_{𝒪︀}

is the unique vector with

𝑈 𝐜 =

𝑐_{1} 𝐮_{1} +

\dots +

𝑐_{𝑛} 𝐮_{𝑛} =

𝐱

. By Proposition 6.3.34,

𝑈

is invertible with

𝑈^{- 1} = 𝑈^{*}

, so

𝐜 = 𝑈^{- 1} 𝐱 = 𝑈^{*} 𝐱

. □

The first proof computes the coordinates one at a time as inner products. The second says that the linear system $𝑈 𝐜 = 𝐱$ , which computing coordinates always requires, is solved for unitary $𝑈$ by a single multiplication by $𝑈^{*}$ , with no elimination. In the notation of Section 4.5, $𝑈 = {[id]}_{ℰ︀ 𝒪︀}$ and $𝑈^{*} = {[id]}_{𝒪︀ ℰ︀}$ , and the general fact that these two change-of-coordinates matrices are inverse to each other becomes $𝑈^{- 1} = 𝑈^{*}$ .

Exercise 6.3.37.routine Let

𝑈, 𝑊 \in 𝔽^{𝑛 \times 𝑛}

be unitary. Show that

𝑈 𝑊

and

𝑈^{- 1}

are unitary, and that

(𝑈 𝐱) \cdot

(𝑈 𝐲) =

𝐱 \cdot

𝐲

and

‖ 𝑈 𝐱 ‖ = ‖ 𝐱 ‖

for all

𝐱, 𝐲 \in 𝔽^{𝑛}

Solution.

Uses. Definition 6.3.33 (Unitary and orthogonal matrices), Proposition 6.3.27 (Properties of the conjugate transpose), Proposition 6.3.34 (Characterizations of unitary matrices), Proposition 2.4.14 (Algebra of matrices)

Hint 1. Compute

{(𝑈 𝑊)}^{*} (𝑈 𝑊)

with Proposition 6.3.27(b).

Hint 2.

𝑈^{- 1} = 𝑈^{*}

, and Proposition 6.3.34(iv). For the dot products, move

𝑈

across with Proposition 6.3.27(d).

Sketch.

{(𝑈 𝑊)}^{*} 𝑈 𝑊 =

𝑊^{*} 𝑈^{*} 𝑈 𝑊 =

𝑊^{*} 𝑊 =

𝐼

𝑈^{- 1} = 𝑈^{*}

is unitary by Proposition 6.3.34. And

(𝑈 𝐱) \cdot

(𝑈 𝐲) =

𝐱 \cdot

(𝑈^{*} 𝑈 𝐲) =

𝐱 \cdot

𝐲

; take

𝐲 = 𝐱

for the norms.

By Proposition 6.3.27(b) and associativity,

{(𝑈 𝑊)}^{*} (𝑈 𝑊) = 𝑊^{*} (𝑈^{*} 𝑈) 𝑊 = 𝑊^{*} 𝐼_{𝑛} 𝑊 = 𝑊^{*} 𝑊 = 𝐼_{𝑛},

so $𝑈 𝑊$ is unitary. By Proposition 6.3.34, $𝑈^{- 1} = 𝑈^{*}$ , and $𝑈^{*}$ is unitary by (iv) of the same proposition.

By Proposition 6.3.27(d) with $𝐴 = 𝑈$ and the vector $𝑈 𝐲$ in place of $𝐲$ ,

(𝑈 𝐱) \cdot (𝑈 𝐲) = 𝐱 \cdot (𝑈^{*} 𝑈 𝐲) = 𝐱 \cdot 𝐲 .

Taking $𝐲 = 𝐱$ gives ${‖ 𝑈 𝐱 ‖}^{2} = {‖ 𝐱 ‖}^{2}$ , and norms are nonnegative, so $‖ 𝑈 𝐱 ‖ = ‖ 𝐱 ‖$ . (Section 8.4 shows that, conversely, a square matrix with $‖ 𝐴 𝐱 ‖ = ‖ 𝐱 ‖$ for all $𝐱$ is unitary.)

Exercise 6.3.38.routine Find all

𝑎, 𝑏 \in ℂ

for which

\frac{1}{\sqrt{2}} (\begin{matrix} 1 & 𝑎 \\ 𝑖 & 𝑏 \end{matrix})

is unitary.

Solution.

Uses. Definition 6.3.33 (Unitary and orthogonal matrices), Theorem 6.3.29 (Orthonormal columns), Definition 6.1.8 (Dot product)

Hint 1. The first column

(1, 𝑖) / \sqrt{2}

is already a unit vector. Write the two remaining conditions on the second column.

Hint 2. Orthogonality to the first column gives one linear equation; the norm gives

{| 𝑎 |}^{2} + {| 𝑏 |}^{2} = 2

Sketch. Orthogonality:

(𝑎, 𝑏) \cdot

(1, 𝑖) =

𝑎 -

𝑖 𝑏 =

0

, so

𝑎 = 𝑖 𝑏

. Unit length:

{| 𝑎 |}^{2} +

{| 𝑏 |}^{2} =

2 {| 𝑏 |}^{2} =

2

. So

(𝑎, 𝑏) = (𝑖 𝑏, 𝑏)

with

| 𝑏 | = 1

By Theorem 6.3.29 the matrix is unitary if and only if its columns $𝐜_{1} = (1, 𝑖) / \sqrt{2}$ and $𝐜_{2} = (𝑎, 𝑏) / \sqrt{2}$ are orthonormal. Here ${‖ 𝐜_{1} ‖}^{2} = (1 + 1) / 2 = 1$ . Next,

𝐜_{2} \cdot 𝐜_{1} = \frac{1}{2} (𝑎 \cdot 1 + 𝑏 \cdot 𝑖) = \frac{1}{2} (𝑎 - 𝑖 𝑏),

which vanishes if and only if $𝑎 = 𝑖 𝑏$ . Then ${‖ 𝐜_{2} ‖}^{2} =$ $({| 𝑎 |}^{2} + {| 𝑏 |}^{2}) / 2 =$ ${| 𝑏 |}^{2}$ , which is $1$ if and only if $| 𝑏 | = 1$ . So the matrix is unitary exactly when $𝑎 = 𝑖 𝑏$ with $| 𝑏 | = 1$ . For $𝑏 = - 𝑖$ we recover the first matrix of Example 6.3.35(d).

6.3.4The discrete Fourier basis

After the standard basis, the most useful orthonormal basis of $ℂ^{𝑛}$ consists of sampled waves. Computing coordinates in it is the discrete Fourier transform of signal processing. Its orthogonality rests on one computation with roots of unity.

Fix $𝑛 \geq 1$ and let

𝜔 = cos \frac{2 𝜋}{𝑛} + 𝑖 sin \frac{2 𝜋}{𝑛} .

By de Moivre’s formula (Section B.1), $𝜔^{𝑚} =$ $cos (2 𝜋 𝑚 / 𝑛) +$ $𝑖 sin (2 𝜋 𝑚 / 𝑛)$ for every integer $𝑚$ . So $| 𝜔 | = 1$ , which gives $𝜔^{𝑚} = 𝜔^{- 𝑚}$ , and $𝜔^{𝑚} = 1$ if and only if $𝑚 / 𝑛$ is an integer, that is, $𝑛 | 𝑚$ . In particular $𝜔^{𝑛} = 1$ , so $𝜔^{𝑚}$ depends only on the remainder of $𝑚$ modulo $𝑛$ .

Lemma 6.3.39 (Sums of roots of unity). For every integer $𝑚$ ,

\sum_{𝑗 = 0}^{𝑛 - 1} 𝜔^{𝑗 𝑚} = {\begin{cases} 𝑛 & if 𝑛 | 𝑚 \\ 0 & if 𝑛 ∤ 𝑚 . \end{cases}

Intuition. The numbers

𝜔^{𝑗 𝑚}

𝑗 = 0, \dots, 𝑛 - 1

, go around the unit circle in equal steps, and when

𝑛 ∤ 𝑚

they are spread evenly around it. Rotating them all by the step

𝑧 = 𝜔^{𝑚}

permutes them, so their sum

𝑆

satisfies

𝑧 𝑆 = 𝑆

; as

𝑧 \neq 1

, this forces

𝑆 = 0

. When

𝑛 | 𝑚

every step is a full turn, and all

𝑛

terms are

1

Proof.routine

Uses. $𝜔^{𝑚} = 1$ if and only if $𝑛 | 𝑚$ , Proposition 1.1.17 (No zero divisors)

Hint 1. If

𝑛 | 𝑚

, what is each term? If not, let

𝑧 = 𝜔^{𝑚} \neq 1

and

𝑆 = \sum_{𝑗 = 0}^{𝑛 - 1} 𝑧^{𝑗}

. Compare

𝑧 𝑆

with

𝑆

Hint 2.

𝑧 𝑆 =

𝑧 +

𝑧^{2} +

\dots +

𝑧^{𝑛}

, and

𝑧^{𝑛} = {(𝜔^{𝑛})}^{𝑚} = 1

Sketch. If

𝑛 | 𝑚

, every term is

1

. Otherwise

𝑧 = 𝜔^{𝑚} \neq 1

, and

𝑧 𝑆 =

\sum_{𝑗 = 1}^{𝑛} 𝑧^{𝑗} =

𝑆

because

𝑧^{𝑛} = 1 = 𝑧^{0}

. So

(𝑧 - 1) 𝑆 = 0

with

𝑧 - 1 \neq 0

, and

𝑆 = 0

. (Equivalently, sum the geometric series:

𝑆 =

(𝑧^{𝑛} - 1) / (𝑧 - 1) =

0

If $𝑛 | 𝑚$ , then $𝜔^{𝑚} = 1$ , so $𝜔^{𝑗 𝑚} = {(𝜔^{𝑚})}^{𝑗} = 1$ for every $𝑗$ , and the sum is $𝑛$ . Suppose $𝑛 ∤ 𝑚$ , and let $𝑧 = 𝜔^{𝑚}$ , so $𝑧 \neq 1$ and $𝑧^{𝑛} = {(𝜔^{𝑛})}^{𝑚} = 1$ . Let $𝑆 = \sum_{𝑗 = 0}^{𝑛 - 1} 𝑧^{𝑗}$ . Then

\begin{aligned} 𝑧 𝑆 & = 𝑧 + 𝑧^{2} + \dots + 𝑧^{𝑛 - 1} + 𝑧^{𝑛} \\ = 𝑧 + 𝑧^{2} + \dots + 𝑧^{𝑛 - 1} + 1 = 𝑆 . \end{aligned}

So $(𝑧 - 1) 𝑆 = 0$ , and since $𝑧 - 1 \neq 0$ , Proposition 1.1.17 gives $𝑆 = 0$ . □

Definition 6.3.40 (Fourier matrix). The $𝑛 \times 𝑛$ Fourier matrix is the matrix $Φ_{𝑛} \in ℂ^{𝑛 \times 𝑛}$ with entries

{(Φ_{𝑛})}_{𝑗 𝑘} = 𝜔^{𝑗 𝑘},

where, unlike elsewhere in the book, rows and columns are indexed by $𝑗, 𝑘 = 0, 1, \dots, 𝑛 - 1$ . Its columns are $𝐟_{0}, \dots, 𝐟_{𝑛 - 1} \in ℂ^{𝑛}$ , where

𝐟_{𝑘} = (1, 𝜔^{𝑘}, 𝜔^{2 𝑘}, \dots, 𝜔^{(𝑛 - 1) 𝑘}) .

For example, $Φ_{1} = (1)$ , $Φ_{2} = (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix})$ , and since $𝜔 = 𝑖$ for $𝑛 = 4$ ,

Φ_{4} = (\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 𝑖 & - 1 & - 𝑖 \\ 1 & - 1 & 1 & - 1 \\ 1 & - 𝑖 & - 1 & 𝑖 \end{matrix}) .

Since $𝑗 𝑘 = 𝑘 𝑗$ , $Φ_{𝑛}$ is symmetric, so its rows are also $𝐟_{0}, \dots, 𝐟_{𝑛 - 1}$ .

Intuition (The columns are waves). The

𝑗

th entry of

𝐟_{𝑘}

𝜔^{𝑗 𝑘} =

cos (2 𝜋 𝑘 𝑗 / 𝑛) +

𝑖 sin (2 𝜋 𝑘 𝑗 / 𝑛)

. So

𝐟_{𝑘}

records the values of

𝑡 \mapsto

cos (2 𝜋 𝑘 𝑡) +

𝑖 sin (2 𝜋 𝑘 𝑡)

, which winds

𝑘

times around the unit circle as

𝑡

runs over

[0, 1]

, at the

𝑛

sample points

𝑡 = 𝑗 / 𝑛

. Its real part samples a cosine wave with

𝑘

full periods (Figure 6.3.2). The coordinate of a vector

𝐱 \in ℂ^{𝑛}

along

𝐟_{𝑘}

measures how much of the wave of frequency

𝑘

the data

𝐱

contains. Since

𝜔^{𝑗 (𝑛 - 𝑘)} =

𝜔^{- 𝑗 𝑘}

, we have

𝐟_{𝑛 - 𝑘} = 𝐟_{𝑘}

: at only

𝑛

sample points, frequency

𝑛 - 𝑘

looks exactly like frequency

- 𝑘

Figure 6.3.2. Real parts of four columns

𝐟_{𝑘}

Φ_{8}

: the samples

cos (2 𝜋 𝑘 𝑗 / 8)

𝑗 = 0, \dots, 7

, joined by the curve

𝑠 \mapsto cos (2 𝜋 𝑘 𝑠 / 8)

. Frequency

4

is the fastest oscillation that

8

samples can show. The samples for

𝑘 = 7

coincide with those for

𝑘 = 1

, because

𝐟_{7} = 𝐟_{1}

has the same real part as

𝐟_{1}

Proposition 6.3.41 (The Fourier basis). The columns $𝐟_{0}, \dots, 𝐟_{𝑛 - 1}$ of $Φ_{𝑛}$ are orthogonal, and ${‖ 𝐟_{𝑘} ‖}^{2} = 𝑛$ for every $𝑘$ . Consequently:

(a) $Φ_{𝑛}^{*} Φ_{𝑛} = 𝑛 𝐼_{𝑛}$ , and $Φ_{𝑛} / \sqrt{𝑛}$ is unitary;
(b) $Φ_{𝑛}$ is invertible, with $Φ_{𝑛}^{- 1} =$ $\frac{1}{𝑛} Φ_{𝑛}^{*} =$ $\frac{1}{𝑛} Φ_{𝑛}$ ;
(c)every $𝐱 \in ℂ^{𝑛}$ satisfies
$𝐱 = \frac{1}{𝑛} \sum_{𝑘 = 0}^{𝑛 - 1} ⟨ 𝐱, 𝐟_{𝑘} ⟩ 𝐟_{𝑘}, where ⟨ 𝐱, 𝐟_{𝑘} ⟩ = \sum_{𝑗 = 0}^{𝑛 - 1} 𝑥_{𝑗} 𝜔^{- 𝑗 𝑘};$
(d)every $𝐱 \in ℂ^{𝑛}$ satisfies $\sum_{𝑗 = 0}^{𝑛 - 1} {| 𝑥_{𝑗} |}^{2} =$ $\frac{1}{𝑛} \sum_{𝑘 = 0}^{𝑛 - 1} {| ⟨ 𝐱, 𝐟_{𝑘} ⟩ |}^{2}$ .

Proof.standard

Uses. Lemma 6.3.39 (Sums of roots of unity), Theorem 6.3.29 (Orthonormal columns), Proposition 6.3.34 (Characterizations of unitary matrices), Corollary 6.3.21 (Coordinates in an orthogonal basis), Theorem 6.3.22 (Parseval’s identity), Corollary 6.3.14 (Counting orthogonal vectors)

Techniques. Gram matrices (Technique 6.3.31)

Hint 1. Compute

𝐟_{𝑘} \cdot 𝐟_{𝑙}

using

𝜔^{𝑗 𝑙} = 𝜔^{- 𝑗 𝑙}

. You get a sum of the kind in Lemma 6.3.39.

Hint 2. The sum is

\sum_{𝑗} 𝜔^{𝑗 (𝑘 - 𝑙)}

. For

0 \leq 𝑘, 𝑙 \leq 𝑛 - 1

, when does

𝑛

divide

𝑘 - 𝑙

Hint 3. For (a), use Theorem 6.3.29. For (c) and (d),

𝐟_{0}, \dots, 𝐟_{𝑛 - 1}

is an orthogonal basis; apply Corollary 6.3.21 and Theorem 6.3.22 to

𝐟_{𝑘} / \sqrt{𝑛}

Sketch.

𝐟_{𝑘} \cdot

𝐟_{𝑙} =

\sum_{𝑗} 𝜔^{𝑗 𝑘} 𝜔^{- 𝑗 𝑙} =

\sum_{𝑗} 𝜔^{𝑗 (𝑘 - 𝑙)}

, which is

𝑛

𝑘 = 𝑙

and

0

otherwise by Lemma 6.3.39, as

| 𝑘 - 𝑙 | < 𝑛

. So

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

by Theorem 6.3.29,

Φ_{𝑛} / \sqrt{𝑛}

is unitary, and its inverse is its conjugate transpose. The vectors

𝐟_{𝑘}

form an orthogonal basis with

{‖ 𝐟_{𝑘} ‖}^{2} = 𝑛

, which gives (c) by Corollary 6.3.21, and (d) is Parseval for the orthonormal basis

𝐟_{𝑘} / \sqrt{𝑛}

For $0 \leq 𝑘, 𝑙 \leq 𝑛 - 1$ , since $𝜔^{𝑗 𝑙} = 𝜔^{- 𝑗 𝑙}$ ,

𝐟_{𝑘} \cdot 𝐟_{𝑙} = \sum_{𝑗 = 0}^{𝑛 - 1} 𝜔^{𝑗 𝑘} 𝜔^{𝑗 𝑙} = \sum_{𝑗 = 0}^{𝑛 - 1} 𝜔^{𝑗 (𝑘 - 𝑙)} .

Since $| 𝑘 - 𝑙 | \leq 𝑛 - 1$ , $𝑛 | (𝑘 - 𝑙)$ only when $𝑘 = 𝑙$ . By Lemma 6.3.39, $𝐟_{𝑘} \cdot 𝐟_{𝑙} = 𝑛$ if $𝑘 = 𝑙$ and $0$ otherwise. So the columns are orthogonal with ${‖ 𝐟_{𝑘} ‖}^{2} = 𝑛$ .

(a) By Theorem 6.3.29, ${(Φ_{𝑛}^{*} Φ_{𝑛})}_{𝑘 𝑙} =$ $𝐟_{𝑙} \cdot$ $𝐟_{𝑘} =$ $𝑛 𝛿_{𝑘 𝑙}$ , so $Φ_{𝑛}^{*} Φ_{𝑛} = 𝑛 𝐼_{𝑛}$ . Hence ${(Φ_{𝑛} / \sqrt{𝑛})}^{*} (Φ_{𝑛} / \sqrt{𝑛}) =$ $(1 / 𝑛) Φ_{𝑛}^{*} Φ_{𝑛} =$ $𝐼_{𝑛}$ (Proposition 6.3.27(a)), and $Φ_{𝑛} / \sqrt{𝑛}$ is unitary.

(b) By Proposition 6.3.34, $Φ_{𝑛} / \sqrt{𝑛}$ is invertible with inverse ${(Φ_{𝑛} / \sqrt{𝑛})}^{*} = Φ_{𝑛}^{*} / \sqrt{𝑛}$ . So $Φ_{𝑛}$ is invertible, and $Φ_{𝑛}^{- 1} = (1 / 𝑛) Φ_{𝑛}^{*}$ . Since $Φ_{𝑛}$ is symmetric, $Φ_{𝑛}^{*} = {Φ_{𝑛}}^{𝖳} = Φ_{𝑛}$ .

(c) The vectors $𝐟_{0}, \dots, 𝐟_{𝑛 - 1}$ are $𝑛$ orthogonal nonzero vectors in $ℂ^{𝑛}$ , hence an orthogonal basis (Corollary 6.3.14). By Corollary 6.3.21, $𝐱 =$ $\sum_{𝑘} ⟨ 𝐱, 𝐟_{𝑘} ⟩ / {‖ 𝐟_{𝑘} ‖}^{2} 𝐟_{𝑘}$ , and ${‖ 𝐟_{𝑘} ‖}^{2} = 𝑛$ . Finally $⟨ 𝐱, 𝐟_{𝑘} ⟩ =$ $𝐱 \cdot$ $𝐟_{𝑘} =$ $\sum_{𝑗} 𝑥_{𝑗} 𝜔^{𝑗 𝑘} =$ $\sum_{𝑗} 𝑥_{𝑗} 𝜔^{- 𝑗 𝑘}$ .

(d) The vectors $𝐟_{𝑘} / \sqrt{𝑛}$ form an orthonormal basis of $ℂ^{𝑛}$ , so by Theorem 6.3.22(b),

{‖ 𝐱 ‖}^{2} = \sum_{𝑘 = 0}^{𝑛 - 1} {| ⟨ 𝐱, \frac{𝐟_{𝑘}}{\sqrt{𝑛}} ⟩ |}^{2} = \frac{1}{𝑛} \sum_{𝑘 = 0}^{𝑛 - 1} {| ⟨ 𝐱, 𝐟_{𝑘} ⟩ |}^{2},

using that $1 / \sqrt{𝑛}$ is real. □

The vector $\hat{𝐱} =$ $Φ_{𝑛}^{*} 𝐱 =$ $(⟨ 𝐱, 𝐟_{0} ⟩, \dots, ⟨ 𝐱, 𝐟_{𝑛 - 1} ⟩)$ is called the discrete Fourier transform of $𝐱$ . (Conventions differ in where the factor $1 / 𝑛$ goes and in the sign of the exponent.) Part (c) is the inversion formula $𝐱 = (1 / 𝑛) Φ_{𝑛} \hat{𝐱}$ , and (d) is Parseval’s identity for the transform. Both are instances of what we proved for general orthogonal bases; the only computation specific to $Φ_{𝑛}$ is Lemma 6.3.39.

Example 6.3.42 (A transform with $𝑛 = 4$ ). Let $𝐱 = (1, 2, 3, 4)$ . With $𝜔 = 𝑖$ , $⟨ 𝐱, 𝐟_{𝑘} ⟩ =$ $\sum_{𝑗} 𝑥_{𝑗} 𝑖^{- 𝑗 𝑘}$ :

\begin{aligned} ⟨ 𝐱, 𝐟_{0} ⟩ & = 1 + 2 + 3 + 4 = 10, \\ ⟨ 𝐱, 𝐟_{1} ⟩ & = 1 - 2 𝑖 - 3 + 4 𝑖 = - 2 + 2 𝑖, \\ ⟨ 𝐱, 𝐟_{2} ⟩ & = 1 - 2 + 3 - 4 = - 2, \\ ⟨ 𝐱, 𝐟_{3} ⟩ & = 1 + 2 𝑖 - 3 - 4 𝑖 = - 2 - 2 𝑖 . \end{aligned}

By Proposition 6.3.41(c),

𝐱 = \frac{1}{4} (10 𝐟_{0} + (- 2 + 2 𝑖) 𝐟_{1} - 2 𝐟_{2} + (- 2 - 2 𝑖) 𝐟_{3}) .

The first term is the constant vector $(5 / 2) 𝐟_{0}$ whose entries are the mean of the entries of $𝐱$ , and the other three terms add up to the deviations $(- 3 / 2, - 1 / 2, 1 / 2, 3 / 2)$ from the mean. Since $𝐱$ is real, $⟨ 𝐱, 𝐟_{3} ⟩ =$ $⟨ 𝐱, 𝐟_{1} ⟩ =$ $⟨ 𝐱, 𝐟_{1} ⟩$ . As a check of (d), $1 + 4 + 9 + 16 = 30$ and $(100 + 8 + 4 + 8) / 4 = 30$ .

The invertibility of $Φ_{𝑛}$ can also be proved without orthogonality, and comparing the two proofs shows what orthogonality buys.

Corollary 6.3.43 (

Φ_{𝑛}

is invertible). The Fourier matrix

Φ_{𝑛}

is invertible.

Proof (by orthogonality).routine

Uses. Proposition 6.3.41 (The Fourier basis)

Hint 1. Use Proposition 6.3.41(b).

Hint 2. It even gives the inverse.

Sketch.

(1 / 𝑛) Φ_{𝑛}

is a two-sided inverse, by Proposition 6.3.41(b).

This is Proposition 6.3.41(b):

Φ_{𝑛}^{- 1} = (1 / 𝑛) Φ_{𝑛}

. □

Proof (by the Vandermonde determinant).standard

Uses. Theorem 5.5.21 (The Vandermonde determinant), Theorem 5.4.7 (Invertibility and the determinant), $𝜔^{𝑚} = 1$ if and only if $𝑛 | 𝑚$

Hint 1. Row

𝑗

Φ_{𝑛}

(1, 𝑧_{𝑗}, 𝑧_{𝑗}^{2}, \dots, 𝑧_{𝑗}^{𝑛 - 1})

with

𝑧_{𝑗} = 𝜔^{𝑗}

. What kind of matrix is that?

Hint 2.

Φ_{𝑛}

is a Vandermonde matrix. Its determinant is nonzero when the nodes

𝑧_{0}, \dots, 𝑧_{𝑛 - 1}

are distinct; check that they are.

Sketch.

Φ_{𝑛}

is the Vandermonde matrix of the nodes

1, 𝜔, \dots, 𝜔^{𝑛 - 1}

(it is symmetric, so the orientation does not matter). These are distinct, since

𝜔^{𝑗} = 𝜔^{𝑗^{'}}

with

0 \leq 𝑗 < 𝑗^{'} \leq 𝑛 - 1

would give

𝜔^{𝑗^{'} - 𝑗} = 1

with

0 < 𝑗^{'} - 𝑗 < 𝑛

. So

det Φ_{𝑛} \neq 0

, and

Φ_{𝑛}

is invertible.

Let

𝑧_{𝑗} = 𝜔^{𝑗}

for

𝑗 = 0, \dots, 𝑛 - 1

. The entry of

Φ_{𝑛}

in row

𝑗

and column

𝑘

𝜔^{𝑗 𝑘} = 𝑧_{𝑗}^{𝑘}

, so

Φ_{𝑛}

is the Vandermonde matrix of the nodes

𝑧_{0}, \dots, 𝑧_{𝑛 - 1}

; since

Φ_{𝑛}

is symmetric, this holds whichever of rows or columns carries the powers in Theorem 5.5.21. The nodes are distinct: if

𝑧_{𝑗} = 𝑧_{𝑗^{'}}

with

0 \leq 𝑗 < 𝑗^{'} \leq 𝑛 - 1

, then

𝜔^{𝑗^{'} - 𝑗} = 1

with

0 < 𝑗^{'} - 𝑗 < 𝑛

, which is impossible since

𝑛 ∤ (𝑗^{'} - 𝑗)

. By Theorem 5.5.21,

det Φ_{𝑛} =

\prod_{0 \leq 𝑗 < 𝑗^{'} \leq 𝑛 - 1} (𝑧_{𝑗^{'}} - 𝑧_{𝑗}) \neq

0

, and by Theorem 5.4.7,

Φ_{𝑛}

is invertible. □

The Vandermonde proof uses only that the nodes $𝜔^{𝑗}$ are distinct, so it applies to any distinct nodes, but it says nothing about the inverse. The orthogonality proof uses the special position of the nodes on the unit circle, and in return it produces the inverse $(1 / 𝑛) Φ_{𝑛}$ , the inversion formula, and Parseval’s identity. It also shows that $| det Φ_{𝑛} | = 𝑛^{𝑛 / 2}$ (Exercise 6.3.60), which the product formula for the Vandermonde determinant hides.

Exercises

Exercise 6.3.44.routine In $ℂ^{2}$ with the dot product, let $𝐮_{1} = \frac{1}{\sqrt{3}} (1, 1 + 𝑖)$ and $𝐮_{2} = \frac{1}{\sqrt{3}} (- 1 + 𝑖, 1)$ .

(a)Show that $𝒪︀ = 𝐮_{1}, 𝐮_{2}$ is an orthonormal basis of $ℂ^{2}$ .
(b)Find ${[𝐯]}_{𝒪︀}$ for $𝐯 = (2, 3 𝑖)$ , and check your answer with Theorem 6.3.22(b).
(c)Compute $⟨ 𝐮_{1}, 𝐯 ⟩ 𝐮_{1} +$ $⟨ 𝐮_{2}, 𝐯 ⟩ 𝐮_{2}$ , with the slots exchanged, and compare it with $𝐯$ .

Solution.

Uses. Definition 6.1.8 (Dot product), Corollary 6.3.14 (Counting orthogonal vectors), Proposition 6.3.18 (Coordinates in an orthonormal basis), Theorem 6.3.22 (Parseval’s identity), Remark 6.3.19 (Which slot)

Hint 1. For (a), compute both squared norms and one dot product; then count.

Hint 2. For (b), the coordinates are

𝐯 \cdot 𝐮_{1}

and

𝐯 \cdot 𝐮_{2}

. Conjugate the entries of

𝐮_{𝑗}

Hint 3. For (c), the coefficients are the conjugates of those in (b).

Sketch. (a)

{‖ (1, 1 + 𝑖) ‖}^{2} =

{‖ (- 1 + 𝑖, 1) ‖}^{2} =

3

and

(1, 1 + 𝑖) \cdot

(- 1 + 𝑖, 1) =

(- 1 - 𝑖) +

(1 + 𝑖) =

0

. (b)

{[𝐯]}_{𝒪︀} =

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

, and

(34 + 5) / 3 = 13 = {‖ 𝐯 ‖}^{2}

. (c) The conjugated coefficients give

((8 - 4 𝑖) / 3, (6 + 𝑖) / 3) \neq

𝐯

(a) ${‖ (1, 1 + 𝑖) ‖}^{2} = 1 + 2 = 3$ and ${‖ (- 1 + 𝑖, 1) ‖}^{2} =$ $2 +$ $1 =$ $3$ , so $𝐮_{1}$ and $𝐮_{2}$ are unit vectors. Also

\begin{aligned} (1, 1 + 𝑖) \cdot (- 1 + 𝑖, 1) & = 1 \cdot (- 1 + 𝑖) + (1 + 𝑖) \cdot 1 \\ = (- 1 - 𝑖) + (1 + 𝑖) = 0 . \end{aligned}

So $𝒪︀$ is an orthonormal list of length $2 = dim ℂ^{2}$ , hence an orthonormal basis by Corollary 6.3.14.

(b) By Proposition 6.3.18,

\begin{aligned} ⟨ 𝐯, 𝐮_{1} ⟩ & = \frac{1}{\sqrt{3}} (2 \cdot 1 + 3 𝑖 \cdot (1 + 𝑖)) \\ = \frac{1}{\sqrt{3}} (2 + 3 𝑖 + 3) = \frac{5 + 3 𝑖}{\sqrt{3}}, \\ ⟨ 𝐯, 𝐮_{2} ⟩ & = \frac{1}{\sqrt{3}} (2 \cdot (- 1 + 𝑖) + 3 𝑖 \cdot 1) \\ = \frac{1}{\sqrt{3}} (- 2 - 2 𝑖 + 3 𝑖) = \frac{- 2 + 𝑖}{\sqrt{3}} . \end{aligned}

So ${[𝐯]}_{𝒪︀} =$ $((5 + 3 𝑖) / \sqrt{3}, (- 2 + 𝑖) / \sqrt{3})$ . Check: ${| 5 + 3 𝑖 |}^{2} / 3 +$ ${| - 2 + 𝑖 |}^{2} / 3 =$ $(34 + 5) / 3 =$ $13 =$ ${| 2 |}^{2} +$ ${| 3 𝑖 |}^{2}$ , as Theorem 6.3.22(b) requires. One can also check directly that $(5 + 3 𝑖) (1, 1 + 𝑖) / 3 +$ $(- 2 + 𝑖) (- 1 + 𝑖, 1) / 3 =$ $(6, 9 𝑖) / 3 =$ $𝐯$ , using $(5 + 3 𝑖) (1 + 𝑖) =$ $2 +$ $8 𝑖$ and $(- 2 + 𝑖) (- 1 + 𝑖) =$ $1 -$ $3 𝑖$ .

(c) The exchanged coefficients are the conjugates $⟨ 𝐮_{1}, 𝐯 ⟩ =$ $(5 - 3 𝑖) / \sqrt{3}$ and $⟨ 𝐮_{2}, 𝐯 ⟩ =$ $(- 2 - 𝑖) / \sqrt{3}$ . Since $(5 - 3 𝑖) (1 + 𝑖) =$ $8 +$ $2 𝑖$ and $(- 2 - 𝑖) (- 1 + 𝑖) =$ $3 -$ $𝑖$ ,

\begin{aligned} \frac{1}{3} ((5 - 3 𝑖) (1, 1 + 𝑖) + (- 2 - 𝑖) (- 1 + 𝑖, 1)) \\ = \frac{1}{3} (5 - 3 𝑖 + 3 - 𝑖, 8 + 2 𝑖 - 2 - 𝑖) = (\frac{8 - 4 𝑖}{3}, \frac{6 + 𝑖}{3}), \end{aligned}

which is not $𝐯$ . Over $ℂ$ the vector belongs in the first slot (Remark 6.3.19).

Exercise 6.3.45.routine Find all unit vectors

𝐱 \in ℝ^{3}

that are orthogonal to both

(1, 2, 2)

and

(2, 1, - 2)

. Then find all

3 \times 3

orthogonal matrices whose first two columns are

\frac{1}{3} (1, 2, 2)

and

\frac{1}{3} (2, 1, - 2)

Solution.

Uses. Example 6.3.10 (Perps are solution sets), Theorem 6.3.29 (Orthonormal columns), Definition 6.3.33 (Unitary and orthogonal matrices)

Hint 1. By Example 6.3.10, the vectors orthogonal to both are the solutions of a homogeneous system with these two rows.

Hint 2. Solve

𝑥_{1} + 2 𝑥_{2} + 2 𝑥_{3} = 0

2 𝑥_{1} + 𝑥_{2} - 2 𝑥_{3} = 0

, then normalize. For the matrices, the third column must be one of the vectors you found.

Sketch. Adding the equations gives

𝑥_{2} = - 𝑥_{1}

, and then

𝑥_{3} = 𝑥_{1} / 2

, so the solutions are

𝑡 (2, - 2, 1)

, and the unit ones are

\pm \frac{1}{3} (2, - 2, 1)

. A

3 \times 3

matrix is orthogonal exactly when its columns are orthonormal, so the third column must be one of these two vectors: there are exactly two such matrices.

By Example 6.3.10, $𝐱$ is orthogonal to both vectors if and only if

𝑥_{1} + 2 𝑥_{2} + 2 𝑥_{3} = 0, 2 𝑥_{1} + 𝑥_{2} - 2 𝑥_{3} = 0 .

Adding the equations gives $3 𝑥_{1} + 3 𝑥_{2} = 0$ , so $𝑥_{2} = - 𝑥_{1}$ , and then the first equation gives $- 𝑥_{1} + 2 𝑥_{3} = 0$ , so $𝑥_{3} = 𝑥_{1} / 2$ . Conversely, every $𝐱 = 𝑡 (2, - 2, 1)$ satisfies both equations. Since $‖ (2, - 2, 1) ‖ = 3$ , the unit vectors among these are $𝐱 = \pm \frac{1}{3} (2, - 2, 1)$ .

By Theorem 6.3.29 and Definition 6.3.33, a real $3 \times 3$ matrix is orthogonal if and only if its columns are orthonormal. The first two given columns are orthonormal (Example 6.3.16(c)), so the matrix is orthogonal exactly when its third column is a unit vector orthogonal to both, that is, $\pm \frac{1}{3} (2, - 2, 1)$ . So there are exactly two such matrices,

\frac{1}{3} (\begin{matrix} 1 & 2 & 2 \\ 2 & 1 & - 2 \\ 2 & - 2 & 1 \end{matrix}) and \frac{1}{3} (\begin{matrix} 1 & 2 & - 2 \\ 2 & 1 & 2 \\ 2 & - 2 & - 1 \end{matrix}) .

Exercise 6.3.46.standard Let $𝑉$ be an inner product space. Prove or disprove each statement.

(a)If $𝐮 ⟂ 𝐯$ and $𝐯 ⟂ 𝐰$ , then $𝐮 ⟂ 𝐰$ .
(b)If $𝐯_{1}, 𝐯_{2}, 𝐯_{3}$ are nonzero with $𝐯_{1} ⟂ 𝐯_{2}$ and $𝐯_{2} ⟂ 𝐯_{3}$ , then $𝐯_{1}, 𝐯_{2}, 𝐯_{3}$ is linearly independent.
(c)If $𝐯_{1}, \dots, 𝐯_{𝑘}$ is orthogonal and $𝑐_{1}, \dots, 𝑐_{𝑘} \in 𝔽$ , then $𝑐_{1} 𝐯_{1}, \dots, 𝑐_{𝑘} 𝐯_{𝑘}$ is orthogonal.
(d)If ${‖ 𝐮 + 𝐯 ‖}^{2} =$ ${‖ 𝐮 ‖}^{2} +$ ${‖ 𝐯 ‖}^{2}$ and ${‖ 𝐮 - 𝐯 ‖}^{2} =$ ${‖ 𝐮 ‖}^{2} +$ ${‖ 𝐯 ‖}^{2}$ , then $𝐮 ⟂ 𝐯$ .
(e)If $𝐯_{1}, \dots, 𝐯_{𝑘}$ spans $𝑉$ and $𝐱 ⟂ 𝐯_{𝑗}$ for every $𝑗$ , then $𝐱 = 𝟎$ .

Solution.

Uses. Definition 6.3.1 (Orthogonality), Proposition 6.1.4 (Sesquilinearity), Proposition 6.1.29 (Expanding a norm), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ), Non-example 6.3.4 (The converse fails over $ℂ$ )

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. For (a) and (b), look for counterexamples in which a vector is repeated.

Hint 2. For (d), expand both norms with Proposition 6.1.29. Do the two hypotheses say different things?

Hint 3. For (e), combine (c) and (d) of Proposition 6.3.9.

Sketch. (a) False:

𝐮 = 𝐰 = 𝐞_{1}

𝐯 = 𝐞_{2}

. (b) False: in

ℝ^{3}

𝐯_{1} = 𝐯_{3} = 𝐞_{1}

𝐯_{2} = 𝐞_{2}

. (c) True:

⟨ 𝑐_{𝑖} 𝐯_{𝑖}, 𝑐_{𝑗} 𝐯_{𝑗} ⟩ =

𝑐_{𝑖} 𝑐_{𝑗} ⟨ 𝐯_{𝑖}, 𝐯_{𝑗} ⟩

. (d) Both hypotheses say

Re ⟨ 𝐮, 𝐯 ⟩ = 0

; true over

ℝ

, false over

ℂ

(

𝐮 = 1

𝐯 = 𝑖

). (e) True:

𝐱 \in

{ℒ︀}^{⟂} =

{span (ℒ︀)}^{⟂} =

𝑉^{⟂} =

{𝟎}

(a) False. In $ℝ^{2}$ , take $𝐮 = 𝐰 = 𝐞_{1}$ and $𝐯 = 𝐞_{2}$ . Then $𝐮 ⟂ 𝐯$ and $𝐯 ⟂ 𝐰$ , but $⟨ 𝐮, 𝐰 ⟩ = 1$ .

(b) False. In $ℝ^{3}$ , take $𝐯_{1} = 𝐯_{3} = 𝐞_{1}$ and $𝐯_{2} = 𝐞_{2}$ . The hypotheses hold, but $𝐯_{1} - 𝐯_{3} = 𝟎$ . The hypothesis says nothing about the pair $𝐯_{1}, 𝐯_{3}$ , so the list need not be orthogonal, and Proposition 6.3.13 does not apply. (The space is $ℝ^{3}$ so that the dependence is not merely forced by the dimension.)

(c) True. For $𝑖 \neq 𝑗$ , Proposition 6.1.4 gives $⟨ 𝑐_{𝑖} 𝐯_{𝑖}, 𝑐_{𝑗} 𝐯_{𝑗} ⟩ =$ $𝑐_{𝑖} 𝑐_{𝑗} ⟨ 𝐯_{𝑖}, 𝐯_{𝑗} ⟩ =$ $0$ .

(d) True over $ℝ$ and false over $ℂ$ . By Proposition 6.1.29,

{‖ 𝐮 \pm 𝐯 ‖}^{2} = {‖ 𝐮 ‖}^{2} \pm 2 Re ⟨ 𝐮, 𝐯 ⟩ + {‖ 𝐯 ‖}^{2},

so each hypothesis says exactly that $Re ⟨ 𝐮, 𝐯 ⟩ = 0$ ; the second adds nothing to the first. Over $ℝ$ this means $𝐮 ⟂ 𝐯$ (Theorem 6.3.3(b)). Over $ℂ$ , $𝐮 = 1$ and $𝐯 = 𝑖$ in $ℂ$ satisfy both, since ${| 1 \pm 𝑖 |}^{2} = 2$ , but $⟨ 1, 𝑖 ⟩ = - 𝑖 \neq 0$ (Non-example 6.3.4).

(e) True. Let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ . By Proposition 6.3.9(c) and (d), $𝐱 \in$ ${ℒ︀}^{⟂} =$ ${span (ℒ︀)}^{⟂} =$ $𝑉^{⟂} =$ ${𝟎}$ .

Exercise 6.3.47.standard On $𝔽_{2}^{4}$ , let $𝐱 \cdot$ $𝐲 =$ $𝑥_{1} 𝑦_{1} +$ $𝑥_{2} 𝑦_{2} +$ $𝑥_{3} 𝑦_{3} +$ $𝑥_{4} 𝑦_{4}$ . This formula is linear in each slot and symmetric, but it is not an inner product, since the scalars are not real or complex. Call $𝐱$ and $𝐲$ orthogonal if $𝐱 \cdot 𝐲 = 0$ .

(a)Find a nonzero $𝐱 \in 𝔽_{2}^{4}$ with $𝐱 \cdot 𝐱 = 0$ .
(b)Find three nonzero vectors in $𝔽_{2}^{4}$ that are pairwise orthogonal but linearly dependent. Which step of the first proof of Proposition 6.3.13 fails?
(c)Let $𝑊 =$ $span ((1, 1, 0, 0), (0, 0, 1, 1))$ . Show that ${𝐱 \in 𝔽_{2}^{4} | 𝐱 \cdot 𝐰 = 0 for all 𝐰 \in 𝑊} =$ $𝑊$ . Which part of Proposition 6.3.9 fails?

Solution.

Uses. Proposition 6.3.13 (Orthogonal lists are independent), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ), Definition 6.1.2 (Inner product)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. In

𝔽_{2}

1 + 1 = 0

. A vector with an even number of entries

1

is orthogonal to itself.

Hint 2. Try

(1, 1, 0, 0)

(0, 0, 1, 1)

, and their sum.

Hint 3. For (c), as in Proposition 6.3.9(c), it suffices to test orthogonality to the two spanning vectors.

Sketch. (a)

(1, 1, 0, 0)

. (b)

(1, 1, 0, 0)

(0, 0, 1, 1)

(1, 1, 1, 1)

are pairwise orthogonal and the third is the sum of the first two; the step “

𝑎_{𝑗} 𝐯_{𝑗} \cdot 𝐯_{𝑗} = 0

forces

𝑎_{𝑗} = 0

” fails because

𝐯_{𝑗} \cdot 𝐯_{𝑗} = 0

. (c) The conditions are

𝑥_{1} = 𝑥_{2}

and

𝑥_{3} = 𝑥_{4}

, which describe

𝑊

. So

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

, against Proposition 6.3.9(d), whose proof used definiteness.

(a) $𝐱 = (1, 1, 0, 0)$ has $𝐱 \cdot 𝐱 = 1 + 1 = 0$ in $𝔽_{2}$ .

(b) Let $𝐯_{1} = (1, 1, 0, 0)$ , $𝐯_{2} = (0, 0, 1, 1)$ , $𝐯_{3} = (1, 1, 1, 1)$ . Then $𝐯_{1} \cdot 𝐯_{2} = 0$ , $𝐯_{1} \cdot 𝐯_{3} = 1 + 1 = 0$ , and $𝐯_{2} \cdot 𝐯_{3} = 1 + 1 = 0$ . But $𝐯_{1} +$ $𝐯_{2} +$ $𝐯_{3} =$ $(2, 2, 2, 2) =$ $𝟎$ , a nontrivial relation. In the first proof of Proposition 6.3.13, taking the product with $𝐯_{𝑗}$ still gives $𝑎_{𝑗} (𝐯_{𝑗} \cdot 𝐯_{𝑗}) = 0$ , but now $𝐯_{𝑗} \cdot 𝐯_{𝑗} = 0$ , so nothing follows about $𝑎_{𝑗}$ . The proof needed $⟨ 𝐯_{𝑗}, 𝐯_{𝑗} ⟩ \neq 0$ for $𝐯_{𝑗} \neq 𝟎$ , which is definiteness.

(c) Since the formula is linear in each slot, the argument of Proposition 6.3.9(c) applies: $𝐱$ is orthogonal to every vector of $𝑊$ if and only if it is orthogonal to $(1, 1, 0, 0)$ and $(0, 0, 1, 1)$ , that is, $𝑥_{1} + 𝑥_{2} = 0$ and $𝑥_{3} + 𝑥_{4} = 0$ . In $𝔽_{2}$ these say $𝑥_{1} = 𝑥_{2}$ and $𝑥_{3} = 𝑥_{4}$ , so the set is ${(𝑠, 𝑠, 𝑡, 𝑡) | 𝑠, 𝑡 \in 𝔽_{2}} =$ $𝑊$ . So $𝑊 \cap 𝑊^{⟂} = 𝑊 \neq {𝟎}$ , and the last statement of Proposition 6.3.9(d) fails; its proof used that a vector orthogonal to itself is $𝟎$ . Forms over general fields are studied in Section 12.4.

Exercise 6.3.48.standard Give $ℝ^{𝑛 \times 𝑛}$ and $ℂ^{𝑛 \times 𝑛}$ the Frobenius inner product $⟨ 𝐴, 𝐵 ⟩ = tr (𝐵^{*} 𝐴)$ (Proposition 6.1.16).

(a)Show that every symmetric $𝑆 \in ℝ^{𝑛 \times 𝑛}$ is orthogonal to every skew-symmetric $𝐾 \in ℝ^{𝑛 \times 𝑛}$ , and deduce that ${‖ 𝐴 ‖}^{2} =$ ${‖ (𝐴 + 𝐴^{𝖳}) / 2 ‖}^{2} +$ ${‖ (𝐴 - 𝐴^{𝖳}) / 2 ‖}^{2}$ for every $𝐴 \in ℝ^{𝑛 \times 𝑛}$ .
(b)Prove or disprove: every Hermitian $𝐻 \in ℂ^{𝑛 \times 𝑛}$ is orthogonal to every $𝐾 \in ℂ^{𝑛 \times 𝑛}$ with $𝐾^{*} = - 𝐾$ . Does the identity ${‖ 𝐴 ‖}^{2} =$ ${‖ (𝐴 + 𝐴^{*}) / 2 ‖}^{2} +$ ${‖ (𝐴 - 𝐴^{*}) / 2 ‖}^{2}$ hold for every $𝐴 \in ℂ^{𝑛 \times 𝑛}$ ?

Solution.

Uses. Proposition 6.1.16 (Frobenius inner product), Proposition 2.4.28 (Cyclicity of the trace), Definition 2.4.26 (Trace), Theorem 6.3.3 (Pythagorean theorem), (6.3.1), Proposition 6.3.27 (Properties of the conjugate transpose)

Techniques. Cyclicity of trace (Technique 2.4.29)

Hint 1. For (a),

⟨ 𝑆, 𝐾 ⟩ =

tr (𝐾^{𝖳} 𝑆) =

- tr (𝐾 𝑆)

. Compute

tr (𝐾 𝑆)

a second way by transposing, and use cyclicity.

Hint 2. For (b), test

𝐻 = 𝐼_{𝑛}

and

𝐾 = 𝑖 𝐼_{𝑛}

Hint 3. For the identity in (b), only

Re ⟨ 𝐻, 𝐾 ⟩

matters ((6.3.1)). Show that

tr (𝐾 𝐻)

is purely imaginary by comparing it with its conjugate

tr ({(𝐾 𝐻)}^{*})

Sketch. (a)

tr (𝐾 𝑆) =

tr ({(𝐾 𝑆)}^{𝖳}) =

tr (𝑆^{𝖳} 𝐾^{𝖳}) =

- tr (𝑆 𝐾) =

- tr (𝐾 𝑆)

, so

⟨ 𝑆, 𝐾 ⟩ =

- tr (𝐾 𝑆) =

0

, and Pythagoras applies to

𝐴 = 𝑆 + 𝐾

. (b) False:

⟨ 𝐼, 𝑖 𝐼 ⟩ = - 𝑖 𝑛 \neq 0

. But

tr (𝐾 𝐻) =

tr (𝐻^{*} 𝐾^{*}) =

- tr (𝐾 𝐻)

, so

⟨ 𝐻, 𝐾 ⟩ = - tr (𝐾 𝐻)

is purely imaginary,

Re ⟨ 𝐻, 𝐾 ⟩ = 0

, and the identity holds by (6.3.1).

(a) Let $𝑆^{𝖳} = 𝑆$ and $𝐾^{𝖳} = - 𝐾$ . A matrix and its transpose have the same diagonal, so $tr (𝑀^{𝖳}) = tr 𝑀$ . Hence, using cyclicity (Proposition 2.4.28),

\begin{aligned} tr (𝐾 𝑆) & = tr ({(𝐾 𝑆)}^{𝖳}) = tr (𝑆^{𝖳} 𝐾^{𝖳}) \\ = tr (𝑆 (- 𝐾)) = - tr (𝑆 𝐾) = - tr (𝐾 𝑆), \end{aligned}

so $tr (𝐾 𝑆) = 0$ , and $⟨ 𝑆, 𝐾 ⟩ =$ $tr (𝐾^{𝖳} 𝑆) =$ $- tr (𝐾 𝑆) =$ $0$ . For $𝐴 \in ℝ^{𝑛 \times 𝑛}$ , $𝑆 = (𝐴 + 𝐴^{𝖳}) / 2$ is symmetric, $𝐾 = (𝐴 - 𝐴^{𝖳}) / 2$ is skew-symmetric, and $𝐴 = 𝑆 + 𝐾$ . By Theorem 6.3.3(a), ${‖ 𝐴 ‖}^{2} = {‖ 𝑆 ‖}^{2} + {‖ 𝐾 ‖}^{2}$ .

(b) False. $𝐻 = 𝐼_{𝑛}$ is Hermitian and $𝐾 = 𝑖 𝐼_{𝑛}$ satisfies $𝐾^{*} = - 𝑖 𝐼_{𝑛} = - 𝐾$ , but $⟨ 𝐻, 𝐾 ⟩ =$ $tr (𝐾^{*} 𝐻) =$ $tr (- 𝑖 𝐼_{𝑛}) =$ $- 𝑖 𝑛 \neq$ $0$ .

The identity still holds. Let $𝐻^{*} = 𝐻$ and $𝐾^{*} = - 𝐾$ . The diagonal entries of $𝑀^{*}$ are the conjugates of those of $𝑀$ , so $tr (𝑀^{*}) = tr 𝑀$ . By Proposition 6.3.27(b) and cyclicity,

\begin{aligned} tr (𝐾 𝐻) & = tr ({(𝐾 𝐻)}^{*}) = tr (𝐻^{*} 𝐾^{*}) \\ = tr (𝐻 (- 𝐾)) = - tr (𝐻 𝐾) = - tr (𝐾 𝐻) . \end{aligned}

So $tr (𝐾 𝐻)$ is purely imaginary, and so is $⟨ 𝐻, 𝐾 ⟩ =$ $tr (𝐾^{*} 𝐻) =$ $- tr (𝐾 𝐻)$ . Thus $Re ⟨ 𝐻, 𝐾 ⟩ = 0$ , and by (6.3.1), ${‖ 𝐻 + 𝐾 ‖}^{2} =$ ${‖ 𝐻 ‖}^{2} +$ ${‖ 𝐾 ‖}^{2}$ . For $𝐴 \in ℂ^{𝑛 \times 𝑛}$ , $𝐻 = (𝐴 + 𝐴^{*}) / 2$ is Hermitian and $𝐾 = (𝐴 - 𝐴^{*}) / 2$ satisfies $𝐾^{*} = - 𝐾$ (Proposition 6.3.27(a)), and $𝐴 = 𝐻 + 𝐾$ , which gives the identity. This is the situation of Non-example 6.3.4: Pythagoras holds without orthogonality.

Exercise 6.3.49.standard Give ${ℝ [𝑥]}_{\leq 3}$ the inner product $⟨ 𝑝, 𝑞 ⟩ =$ $\int_{- 1}^{1} 𝑝 (𝑡) 𝑞 (𝑡) d 𝑡$ , as in Example 6.3.17.

(a)Find the polynomial $𝑞 =$ $𝑥^{3} +$ $𝑎 𝑥^{2} +$ $𝑏 𝑥 +$ $𝑐$ that is orthogonal to $1$ , $𝑥$ , and $𝑥^{2}$ , and compute ${‖ 𝑞 ‖}^{2}$ .
(b)Show that $1, 𝑥, 𝑥^{2} - 1 / 3, 𝑞$ is an orthogonal basis of ${ℝ [𝑥]}_{\leq 3}$ .
(c)Use Corollary 6.3.21 to write $𝑝 = 1 + 𝑥 + 𝑥^{2} + 𝑥^{3}$ in this basis, and check the result.

Solution.

Uses. Example 6.3.17 (Orthogonal polynomials), Proposition 6.3.9 (Properties of $𝐴^{⟂}$ ), Corollary 6.3.14 (Counting orthogonal vectors), Corollary 6.3.21 (Coordinates in an orthogonal basis)

Techniques. Undetermined coefficients (Technique 3.1.9)

Hint 1.

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

\int_{- 1}^{1} 𝑡^{𝑗 + 𝑘} d 𝑡

2 / (𝑗 + 𝑘 + 1)

𝑗 + 𝑘

is even and

0

if it is odd. The three conditions are linear equations in

𝑎, 𝑏, 𝑐

Hint 2. You should find

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

. For (b),

𝑞 ⟂ 𝑥^{2} - 1 / 3

follows from

𝑞 ⟂ 1

and

𝑞 ⟂ 𝑥^{2}

Hint 3. For (c), you need

⟨ 𝑝, 1 ⟩

⟨ 𝑝, 𝑥 ⟩

⟨ 𝑝, 𝑥^{2} - 1 / 3 ⟩

⟨ 𝑝, 𝑞 ⟩

and the four squared norms.

Sketch. (a)

⟨ 𝑞, 1 ⟩ = 2 𝑎 / 3 + 2 𝑐

⟨ 𝑞, 𝑥 ⟩ = 2 / 5 + 2 𝑏 / 3

⟨ 𝑞, 𝑥^{2} ⟩ =

2 𝑎 / 5 +

2 𝑐 / 3

force

𝑎 = 𝑐 = 0

𝑏 = - 3 / 5

, and

{‖ 𝑞 ‖}^{2} = 8 / 175

. (b) Four nonzero orthogonal vectors in a

4

-dimensional space. (c) The coefficients are

(8 / 3) / 2 = 4 / 3

(16 / 15) / (2 / 3) = 8 / 5

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

, and

(8 / 175) / (8 / 175) = 1

Throughout, $⟨ 𝑥^{𝑗}, 𝑥^{𝑘} ⟩ =$ $\int_{- 1}^{1} 𝑡^{𝑗 + 𝑘} d 𝑡$ , which is $2 / (𝑗 + 𝑘 + 1)$ when $𝑗 + 𝑘$ is even and $0$ when $𝑗 + 𝑘$ is odd.

(a) By linearity in the first slot,

⟨ 𝑞, 1 ⟩ = \frac{2}{3} 𝑎 + 2 𝑐, ⟨ 𝑞, 𝑥 ⟩ = \frac{2}{5} + \frac{2}{3} 𝑏, ⟨ 𝑞, 𝑥^{2} ⟩ = \frac{2}{5} 𝑎 + \frac{2}{3} 𝑐 .

The second equation gives $𝑏 = - 3 / 5$ . The first gives $𝑐 = - 𝑎 / 3$ , and then the third becomes $2 𝑎 / 5 -$ $2 𝑎 / 9 =$ $8 𝑎 / 45 =$ $0$ , so $𝑎 = 𝑐 = 0$ . Hence $𝑞 = 𝑥^{3} - (3 / 5) 𝑥$ , and

\begin{aligned} {‖ 𝑞 ‖}^{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}

(b) By Example 6.3.17, $1, 𝑥, 𝑥^{2} - 1 / 3$ is orthogonal. By (a), $𝑞$ is orthogonal to $1$ and to $𝑥^{2}$ , hence to $𝑥^{2} - 1 / 3$ (Proposition 6.3.9(a)), and to $𝑥$ . So the four polynomials form an orthogonal list of nonzero vectors in the $4$ -dimensional space ${ℝ [𝑥]}_{\leq 3}$ , hence an orthogonal basis (Corollary 6.3.14).

(c) We compute $⟨ 𝑝, 𝑥^{𝑘} ⟩ =$ $\sum_{𝑗 = 0}^{3} ⟨ 𝑥^{𝑗}, 𝑥^{𝑘} ⟩$ :

\begin{aligned} ⟨ 𝑝, 1 ⟩ & = 2 + \frac{2}{3} = \frac{8}{3}, & ⟨ 𝑝, 𝑥 ⟩ & = \frac{2}{3} + \frac{2}{5} = \frac{16}{15}, \\ ⟨ 𝑝, 𝑥^{2} ⟩ & = \frac{2}{3} + \frac{2}{5} = \frac{16}{15}, & ⟨ 𝑝, 𝑥^{3} ⟩ & = \frac{2}{5} + \frac{2}{7} = \frac{24}{35} . \end{aligned}

Hence $⟨ 𝑝, 𝑥^{2} - 1 / 3 ⟩ =$ $16 / 15 -$ $8 / 9 =$ $8 / 45$ and $⟨ 𝑝, 𝑞 ⟩ =$ $24 / 35 -$ $(3 / 5) (16 / 15) =$ $24 / 35 -$ $16 / 25 =$ $8 / 175$ . The squared norms are $2$ , $2 / 3$ , $8 / 45$ (Example 6.3.17), and $8 / 175$ . By Corollary 6.3.21,

𝑝 = \frac{4}{3} \cdot 1 + \frac{8}{5} 𝑥 + 1 \cdot (𝑥^{2} - \frac{1}{3}) + 1 \cdot (𝑥^{3} - \frac{3}{5} 𝑥) .

Check: the constant term is $4 / 3 - 1 / 3 = 1$ , the coefficient of $𝑥$ is $8 / 5 - 3 / 5 = 1$ , and those of $𝑥^{2}$ and $𝑥^{3}$ are $1$ .

Exercise 6.3.50.standard The Pauli matrices are

\begin{matrix} 𝜎_{0} = 𝐼_{2}, 𝜎_{1} = (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}), \\ 𝜎_{2} = (\begin{matrix} 0 & - 𝑖 \\ 𝑖 & 0 \end{matrix}), 𝜎_{3} = (\begin{matrix} 1 & 0 \\ 0 & - 1 \end{matrix}) . \end{matrix}

Give $ℂ^{2 \times 2}$ the Frobenius inner product $⟨ 𝐴, 𝐵 ⟩ = tr (𝐵^{*} 𝐴)$ .

(a)Show that $𝜎_{0} / \sqrt{2}, \dots, 𝜎_{3} / \sqrt{2}$ is an orthonormal basis of $ℂ^{2 \times 2}$ .
(b)Deduce that every $𝐴 \in ℂ^{2 \times 2}$ satisfies $𝐴 =$ $\frac{1}{2} \sum_{𝑎 = 0}^{3} tr (𝜎_{𝑎} 𝐴) 𝜎_{𝑎}$ .
(c)Write $𝐴 = (\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix})$ in this form.

Solution.

Uses. Proposition 6.1.16 (Frobenius inner product), Proposition 2.4.28 (Cyclicity of the trace), Corollary 6.3.14 (Counting orthogonal vectors), Proposition 6.3.18 (Coordinates in an orthonormal basis)

Hint 1. Each

𝜎_{𝑎}

is Hermitian, so

⟨ 𝜎_{𝑎}, 𝜎_{𝑏} ⟩ =

tr (𝜎_{𝑏} 𝜎_{𝑎})

. Compute

𝜎_{𝑎}^{2}

and the products

𝜎_{1} 𝜎_{2}

𝜎_{2} 𝜎_{3}

𝜎_{3} 𝜎_{1}

Hint 2.

𝜎_{𝑎}^{2} = 𝐼_{2}

, and the three products are

𝑖 𝜎_{3}

𝑖 𝜎_{1}

𝑖 𝜎_{2}

, all of trace

0

. Also

tr 𝜎_{𝑎} = 0

for

𝑎 = 1, 2, 3

Hint 3. For (b), the coordinate of

𝐴

along

𝜎_{𝑎} / \sqrt{2}

⟨ 𝐴, 𝜎_{𝑎} / \sqrt{2} ⟩ =

tr (𝜎_{𝑎} 𝐴) / \sqrt{2}

Sketch. (a)

⟨ 𝜎_{𝑎}, 𝜎_{𝑏} ⟩ =

tr (𝜎_{𝑏} 𝜎_{𝑎})

2

for

𝑎 = 𝑏

and

0

otherwise, and

dim ℂ^{2 \times 2} = 4

. (b) Proposition 6.3.18 with

⟨ 𝐴, 𝜎_{𝑎} / \sqrt{2} ⟩ =

tr (𝜎_{𝑎} 𝐴) / \sqrt{2}

. (c) The traces are

5, 5, - 𝑖, - 3

, so

𝐴 =

(5 𝜎_{0} + 5 𝜎_{1} - 𝑖 𝜎_{2} - 3 𝜎_{3}) / 2

(a) Each $𝜎_{𝑎}$ satisfies $𝜎_{𝑎}^{*} = 𝜎_{𝑎}$ (for $𝜎_{2}$ : $- 𝑖 = 𝑖$ moves to position $(2, 1)$ ). So $⟨ 𝜎_{𝑎}, 𝜎_{𝑏} ⟩ =$ $tr (𝜎_{𝑏}^{*} 𝜎_{𝑎}) =$ $tr (𝜎_{𝑏} 𝜎_{𝑎})$ . Direct multiplication gives $𝜎_{1}^{2} =$ $𝜎_{2}^{2} =$ $𝜎_{3}^{2} =$ $𝐼_{2}$ and

\begin{aligned} 𝜎_{1} 𝜎_{2} & = (\begin{matrix} 𝑖 & 0 \\ 0 & - 𝑖 \end{matrix}) = 𝑖 𝜎_{3}, \\ 𝜎_{2} 𝜎_{3} & = (\begin{matrix} 0 & 𝑖 \\ 𝑖 & 0 \end{matrix}) = 𝑖 𝜎_{1}, \\ 𝜎_{3} 𝜎_{1} & = (\begin{matrix} 0 & 1 \\ - 1 & 0 \end{matrix}) = 𝑖 𝜎_{2} . \end{aligned}

So $⟨ 𝜎_{𝑎}, 𝜎_{𝑎} ⟩ =$ $tr 𝐼_{2} =$ $2$ for every $𝑎$ (including $𝑎 = 0$ ). For distinct $𝑎, 𝑏 \in {1, 2, 3}$ , $tr (𝜎_{𝑏} 𝜎_{𝑎}) =$ $tr (𝜎_{𝑎} 𝜎_{𝑏})$ (Proposition 2.4.28) is the trace of $𝑖$ times a Pauli matrix with trace $0$ , so it is $0$ . Finally $⟨ 𝜎_{𝑎}, 𝜎_{0} ⟩ =$ $tr 𝜎_{𝑎} =$ $0$ for $𝑎 = 1, 2, 3$ . Hence the $𝜎_{𝑎} / \sqrt{2}$ are orthonormal, and since $dim ℂ^{2 \times 2} = 4$ , they form an orthonormal basis (Corollary 6.3.14).

(b) By Proposition 6.3.18, $𝐴 =$ $\sum_{𝑎} ⟨ 𝐴, 𝜎_{𝑎} / \sqrt{2} ⟩ 𝜎_{𝑎} / \sqrt{2}$ , and $⟨ 𝐴, 𝜎_{𝑎} / \sqrt{2} ⟩ =$ $tr (𝜎_{𝑎}^{*} 𝐴) / \sqrt{2} =$ $tr (𝜎_{𝑎} 𝐴) / \sqrt{2}$ . Multiplying the two factors $1 / \sqrt{2}$ gives the formula.

(c) We have $tr 𝐴 = 5$ , and

\begin{matrix} 𝜎_{1} 𝐴 = (\begin{matrix} 3 & 4 \\ 1 & 2 \end{matrix}), 𝜎_{2} 𝐴 = (\begin{matrix} - 3 𝑖 & - 4 𝑖 \\ 𝑖 & 2 𝑖 \end{matrix}), \\ 𝜎_{3} 𝐴 = (\begin{matrix} 1 & 2 \\ - 3 & - 4 \end{matrix}), \end{matrix}

with traces $5$ , $- 𝑖$ , $- 3$ . So $𝐴 =$ $(5 𝜎_{0} + 5 𝜎_{1} - 𝑖 𝜎_{2} - 3 𝜎_{3}) / 2$ . Check: $5 𝜎_{0} +$ $5 𝜎_{1} -$ $𝑖 𝜎_{2} -$ $3 𝜎_{3} =$ $(\begin{matrix} 5 - 3 & 5 - 1 \\ 5 + 1 & 5 + 3 \end{matrix}) =$ $(\begin{matrix} 2 & 4 \\ 6 & 8 \end{matrix}) =$ $2 𝐴$ , since $- 𝑖 𝜎_{2} = (\begin{matrix} 0 & - 1 \\ 1 & 0 \end{matrix})$ .

Exercise 6.3.51.standard Let $𝑉$ be a vector space over $𝔽$ with a basis $ℬ︀ = 𝐛_{1}, \dots, 𝐛_{𝑛}$ .

(a)Show that ${⟨ 𝐱, 𝐲 ⟩}_{ℬ︀} =$ ${[𝐱]}_{ℬ︀} \cdot$ ${[𝐲]}_{ℬ︀}$ is an inner product on $𝑉$ for which $ℬ︀$ is orthonormal.
(b)Show that it is the only inner product on $𝑉$ for which $ℬ︀$ is orthonormal.
(c)For $𝑉 = ℝ^{2}$ and $ℬ︀ = (1, 0), (1, 1)$ , find the matrix $𝑀$ with ${⟨ 𝐱, 𝐲 ⟩}_{ℬ︀} =$ $𝐲^{𝖳} 𝑀 𝐱$ .

Solution.

Uses. Proposition 1.6.19 (Coordinates respect linear combinations), Proposition 6.1.10 (The dot product is an inner product), Definition 6.1.2 (Inner product), Theorem 6.3.22 (Parseval’s identity), Proposition 6.1.22 (Inner products on $𝔽^{𝑛}$ )

Hint 1. The coordinate map

𝐱 \mapsto {[𝐱]}_{ℬ︀}

is linear and injective. Transfer each axiom from the dot product.

Hint 2. For (b), if

ℬ︀

is orthonormal for some inner product, what does Theorem 6.3.22 say about it?

Hint 3. For (c),

{[𝐱]}_{ℬ︀} =

(𝑥_{1} - 𝑥_{2}, 𝑥_{2})

Sketch. (a) Write

𝐶 (𝐱) = {[𝐱]}_{ℬ︀}

. Conjugate symmetry, linearity in the first slot, and positivity pass from the dot product through the linear map

𝐶

, and

{⟨ 𝐱, 𝐱 ⟩}_{ℬ︀} = 0

forces

𝐶 (𝐱) = 𝟎

, so

𝐱 = 𝟎

. Since

{[𝐛_{𝑗}]}_{ℬ︀} = 𝐞_{𝑗}

ℬ︀

is orthonormal. (b) By Theorem 6.3.22(a), any inner product for which

ℬ︀

is orthonormal equals

{[𝐱]}_{ℬ︀} \cdot {[𝐲]}_{ℬ︀}

. (c)

(𝑥_{1} - 𝑥_{2}) (𝑦_{1} - 𝑦_{2}) +

𝑥_{2} 𝑦_{2}

, so

𝑀 = (\begin{matrix} 1 & - 1 \\ - 1 & 2 \end{matrix})

(a) Let $𝐶 (𝐱) = {[𝐱]}_{ℬ︀}$ . By Proposition 1.6.19, $𝐶 : 𝑉 \to 𝔽^{𝑛}$ is linear, and $𝐶 (𝐱) = 𝟎$ only for $𝐱 =$ $0 𝐛_{1} +$ $\dots +$ $0 𝐛_{𝑛} =$ $𝟎$ . Since the dot product is an inner product on $𝔽^{𝑛}$ (Proposition 6.1.10), for all $𝐱, 𝐲, 𝐳 \in 𝑉$ and $𝑎, 𝑏 \in 𝔽$ :

${⟨ 𝐲, 𝐱 ⟩}_{ℬ︀} =$ $𝐶 (𝐲) \cdot$ $𝐶 (𝐱) =$ $𝐶 (𝐱) \cdot 𝐶 (𝐲) =$ ${⟨ 𝐱, 𝐲 ⟩}_{ℬ︀}$ ;
${⟨ 𝑎 𝐱 + 𝑏 𝐲, 𝐳 ⟩}_{ℬ︀} =$ $(𝑎 𝐶 (𝐱) + 𝑏 𝐶 (𝐲)) \cdot$ $𝐶 (𝐳) =$ $𝑎 {⟨ 𝐱, 𝐳 ⟩}_{ℬ︀} +$ $𝑏 {⟨ 𝐲, 𝐳 ⟩}_{ℬ︀}$ ;
${⟨ 𝐱, 𝐱 ⟩}_{ℬ︀} =$ $𝐶 (𝐱) \cdot$ $𝐶 (𝐱) \geq$ $0$ , with equality only if $𝐶 (𝐱) = 𝟎$ , that is, $𝐱 = 𝟎$ .

So ${⟨ \cdot, \cdot ⟩}_{ℬ︀}$ is an inner product. Since ${[𝐛_{𝑗}]}_{ℬ︀} = 𝐞_{𝑗}$ , we get ${⟨ 𝐛_{𝑖}, 𝐛_{𝑗} ⟩}_{ℬ︀} =$ $𝐞_{𝑖} \cdot$ $𝐞_{𝑗} =$ $𝛿_{𝑖 𝑗}$ , so $ℬ︀$ is orthonormal.

(b) Let $⟨ \cdot, \cdot ⟩$ be an inner product on $𝑉$ for which $ℬ︀$ is orthonormal. Then $ℬ︀$ is an orthonormal basis, and by Theorem 6.3.22(a), $⟨ 𝐱, 𝐲 ⟩ =$ ${[𝐱]}_{ℬ︀} \cdot$ ${[𝐲]}_{ℬ︀} =$ ${⟨ 𝐱, 𝐲 ⟩}_{ℬ︀}$ for all $𝐱, 𝐲$ .

(c) Writing $𝐱 =$ $𝑎 (1, 0) +$ $𝑐 (1, 1) =$ $(𝑎 + 𝑐, 𝑐)$ gives $𝑐 = 𝑥_{2}$ and $𝑎 = 𝑥_{1} - 𝑥_{2}$ , so ${[𝐱]}_{ℬ︀} =$ $(𝑥_{1} - 𝑥_{2}, 𝑥_{2})$ . Hence

\begin{aligned} {⟨ 𝐱, 𝐲 ⟩}_{ℬ︀} & = (𝑥_{1} - 𝑥_{2}) (𝑦_{1} - 𝑦_{2}) + 𝑥_{2} 𝑦_{2} \\ = 𝑥_{1} 𝑦_{1} - 𝑥_{1} 𝑦_{2} - 𝑥_{2} 𝑦_{1} + 2 𝑥_{2} 𝑦_{2} \\ = 𝐲^{𝖳} (\begin{matrix} 1 & - 1 \\ - 1 & 2 \end{matrix}) 𝐱 . \end{aligned}

For instance ${⟨ 𝐞_{1}, 𝐞_{2} ⟩}_{ℬ︀} = - 1$ : the standard basis is not orthonormal for this inner product, as anticipated after Theorem 6.3.22.

Exercise 6.3.52.standard

(a)In $ℝ^{2}$ , let $𝐰_{𝑗} =$ $\sqrt{2 / 3} (cos (2 𝜋 𝑗 / 3), sin (2 𝜋 𝑗 / 3))$ for $𝑗 = 0, 1, 2$ . Show that $\sum_{𝑗 = 0}^{2} {⟨ 𝐯, 𝐰_{𝑗} ⟩}^{2} =$ ${‖ 𝐯 ‖}^{2}$ for every $𝐯 \in ℝ^{2}$ , although $𝐰_{0}, 𝐰_{1}, 𝐰_{2}$ is not orthonormal.
(b)Let $𝐯_{1}, \dots, 𝐯_{𝑘}$ be unit vectors in an inner product space $𝑉$ such that $\sum_{𝑗 = 1}^{𝑘} {| ⟨ 𝐯, 𝐯_{𝑗} ⟩ |}^{2} =$ ${‖ 𝐯 ‖}^{2}$ for every $𝐯 \in 𝑉$ . Show that $𝐯_{1}, \dots, 𝐯_{𝑘}$ is an orthonormal basis of $𝑉$ .

Solution.

Uses. Definition 6.1.8 (Dot product), Corollary 6.3.14 (Counting orthogonal vectors), Theorem 6.3.24 (Bessel’s inequality), Proposition 6.3.13 (Orthogonal lists are independent)

Techniques. Plug in clever test vectors (Technique 6.1.40), A sum of nonnegative terms (Technique 6.1.9)

Hint 1. For (a), write

𝐯 = (𝑥, 𝑦)

and expand. You need

\sum_{𝑗} {cos}^{2} 𝜃_{𝑗}

\sum_{𝑗} {sin}^{2} 𝜃_{𝑗}

, and

\sum_{𝑗} cos 𝜃_{𝑗} sin 𝜃_{𝑗}

for

𝜃_{𝑗} = 2 𝜋 𝑗 / 3

Hint 2. For (b), apply the hypothesis to

𝐯 = 𝐯_{𝑙}

. The left side contains the term

{| ⟨ 𝐯_{𝑙}, 𝐯_{𝑙} ⟩ |}^{2} = 1

Hint 3. Once the list is orthonormal, the hypothesis is the equality case of Bessel’s inequality for every

𝐯

Sketch. (a) With

cos 𝜃_{𝑗} =

1,

- 1 / 2,

- 1 / 2

and

sin 𝜃_{𝑗} =

0,

\sqrt{3} / 2,

- \sqrt{3} / 2

, the sum is

(2 / 3) (3 𝑥^{2} / 2 + 3 𝑦^{2} / 2)

. Three nonzero vectors in

ℝ^{2}

cannot be orthogonal. (b) For

𝐯 = 𝐯_{𝑙}

1 =

1 +

\sum_{𝑗 \neq 𝑙} {| ⟨ 𝐯_{𝑙}, 𝐯_{𝑗} ⟩ |}^{2}

, so the cross terms vanish. Then Bessel’s equality case puts every

𝐯

in the span.

(a) For $𝜃_{𝑗} = 2 𝜋 𝑗 / 3$ , the cosines are $1, - 1 / 2, - 1 / 2$ and the sines are $0, \sqrt{3} / 2, - \sqrt{3} / 2$ . So $\sum_{𝑗} {cos}^{2} 𝜃_{𝑗} = 3 / 2$ , $\sum_{𝑗} {sin}^{2} 𝜃_{𝑗} = 3 / 2$ , and $\sum_{𝑗} cos 𝜃_{𝑗} sin 𝜃_{𝑗} =$ $0 -$ $\sqrt{3} / 4 +$ $\sqrt{3} / 4 =$ $0$ . For $𝐯 = (𝑥, 𝑦)$ ,

\begin{aligned} \sum_{𝑗 = 0}^{2} {⟨ 𝐯, 𝐰_{𝑗} ⟩}^{2} & = \frac{2}{3} \sum_{𝑗 = 0}^{2} {(𝑥 cos 𝜃_{𝑗} + 𝑦 sin 𝜃_{𝑗})}^{2} \\ = \frac{2}{3} (\frac{3}{2} 𝑥^{2} + 0 + \frac{3}{2} 𝑦^{2}) = {‖ 𝐯 ‖}^{2} . \end{aligned}

The list is not orthonormal: each $𝐰_{𝑗}$ has norm $\sqrt{2 / 3}$ , and by Corollary 6.3.14 no three nonzero vectors in $ℝ^{2}$ are orthogonal.

(b) Fix $𝑙$ and apply the hypothesis to $𝐯 = 𝐯_{𝑙}$ . Since $‖ 𝐯_{𝑙} ‖ = 1$ ,

1 = \sum_{𝑗 = 1}^{𝑘} {| ⟨ 𝐯_{𝑙}, 𝐯_{𝑗} ⟩ |}^{2} = 1 + \sum_{𝑗 \neq 𝑙} {| ⟨ 𝐯_{𝑙}, 𝐯_{𝑗} ⟩ |}^{2} .

So the remaining sum of nonnegative terms is $0$ , and $⟨ 𝐯_{𝑙}, 𝐯_{𝑗} ⟩ = 0$ for all $𝑗 \neq 𝑙$ . Thus the list is orthonormal. Now the hypothesis says that equality holds in Bessel’s inequality (Theorem 6.3.24) for every $𝐯 \in 𝑉$ , so every $𝐯$ lies in $span (𝐯_{1}, \dots, 𝐯_{𝑘})$ . The list spans $𝑉$ and is independent (Proposition 6.3.13), so it is an orthonormal basis. Part (a) shows that the hypothesis “unit vectors” cannot be dropped.

Exercise 6.3.53.standard Let $𝐮_{1}, \dots, 𝐮_{𝑘}$ be an orthonormal list in $𝑉$ , and let $𝐱, 𝐲 \in 𝑉$ .

(a)Show that $\sum_{𝑗 = 1}^{𝑘} | ⟨ 𝐱, 𝐮_{𝑗} ⟩ | | ⟨ 𝐲, 𝐮_{𝑗} ⟩ | \leq$ $‖ 𝐱 ‖ ‖ 𝐲 ‖$ .
(b)Show that $\sum_{𝑗 = 1}^{𝑘} | ⟨ 𝐱, 𝐮_{𝑗} ⟩ | \leq$ $\sqrt{𝑘} ‖ 𝐱 ‖$ , and find when equality holds.

Solution.

Uses. Theorem 6.2.1 (Cauchy–Schwarz inequality), Theorem 6.3.24 (Bessel’s inequality), Proposition 6.2.22 (The square of a sum)

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

Hint 1. For (a), apply Cauchy–Schwarz in

ℝ^{𝑘}

to the vectors

{(| ⟨ 𝐱, 𝐮_{𝑗} ⟩ |)}_{𝑗}

and

{(| ⟨ 𝐲, 𝐮_{𝑗} ⟩ |)}_{𝑗}

, then Bessel to each norm.

Hint 2. For (b), use Proposition 6.2.22 and then Bessel. Equality requires equality in both steps.

Sketch. (a) Cauchy–Schwarz in

ℝ^{𝑘}

bounds the sum by

{(\sum_{𝑗} {| ⟨ 𝐱, 𝐮_{𝑗} ⟩ |}^{2})}^{1 / 2} {(\sum_{𝑗} {| ⟨ 𝐲, 𝐮_{𝑗} ⟩ |}^{2})}^{1 / 2}

, and Bessel bounds the factors by

‖ 𝐱 ‖

and

‖ 𝐲 ‖

. (b)

{(\sum_{𝑗} 𝑎_{𝑗})}^{2} \leq

𝑘 \sum_{𝑗} 𝑎_{𝑗}^{2} \leq

𝑘 {‖ 𝐱 ‖}^{2}

with

𝑎_{𝑗} = | ⟨ 𝐱, 𝐮_{𝑗} ⟩ |

. Equality: all

𝑎_{𝑗}

equal and

𝐱 \in

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

, that is,

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

with

| 𝑐_{1} | = \dots = | 𝑐_{𝑘} |

Write $𝑎_{𝑗} = | ⟨ 𝐱, 𝐮_{𝑗} ⟩ |$ and $𝑏_{𝑗} = | ⟨ 𝐲, 𝐮_{𝑗} ⟩ |$ , nonnegative reals.

(a) By Theorem 6.2.1 for the dot product on $ℝ^{𝑘}$ and then Theorem 6.3.24 twice,

\sum_{𝑗} 𝑎_{𝑗} 𝑏_{𝑗} \leq {(\sum_{𝑗} 𝑎_{𝑗}^{2})}^{1 / 2} {(\sum_{𝑗} 𝑏_{𝑗}^{2})}^{1 / 2} \leq ‖ 𝐱 ‖ ‖ 𝐲 ‖ .

(b) By Proposition 6.2.22 and Theorem 6.3.24,

{(\sum_{𝑗} 𝑎_{𝑗})}^{2} \leq 𝑘 \sum_{𝑗} 𝑎_{𝑗}^{2} \leq 𝑘 {‖ 𝐱 ‖}^{2},

and taking nonnegative square roots gives the inequality. Equality holds if and only if both steps are equalities: all $𝑎_{𝑗}$ are equal (Proposition 6.2.22) and $𝐱 \in$ $span (𝐮_{1}, \dots, 𝐮_{𝑘})$ (Theorem 6.3.24). By Proposition 6.3.18, this says $𝐱 =$ $𝑐_{1} 𝐮_{1} +$ $\dots +$ $𝑐_{𝑘} 𝐮_{𝑘}$ with $| 𝑐_{1} | = \dots = | 𝑐_{𝑘} |$ . For example, in $ℝ^{𝑘}$ with the standard basis, $𝐱 = (1, - 1, 1, \dots)$ gives equality.

Exercise 6.3.54.standard The $𝑛 \times 𝑛$ Hilbert matrix $𝐻_{𝑛}$ has entries $ℎ_{𝑖 𝑗} = 1 / (𝑖 + 𝑗 - 1)$ .

(a)Show that $𝐻_{𝑛}$ is the Gram matrix of $1, 𝑥, \dots, 𝑥^{𝑛 - 1}$ in ${ℝ [𝑥]}_{\leq 𝑛 - 1}$ with $⟨ 𝑝, 𝑞 ⟩ =$ $\int_{0}^{1} 𝑝 (𝑡) 𝑞 (𝑡) d 𝑡$ .
(b)Deduce that $𝐻_{𝑛}$ is invertible and that $𝐜^{𝖳} 𝐻_{𝑛} 𝐜 > 0$ for every nonzero $𝐜 \in ℝ^{𝑛}$ .

Solution.

Uses. Definition 6.3.28 (Gram matrix), Proposition 6.3.30 (Gram matrices detect independence), Example 1.5.7 (Monomials)

Techniques. Gram matrices (Technique 6.3.31)

Hint 1. Compute

⟨ 𝑥^{𝑗 - 1}, 𝑥^{𝑖 - 1} ⟩

Hint 2. The monomials are linearly independent. Apply Proposition 6.3.30.

Sketch.

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

\int_{0}^{1} 𝑡^{𝑖 + 𝑗 - 2} d 𝑡 =

1 / (𝑖 + 𝑗 - 1)

. The monomials are independent, so

𝐻_{𝑛}

is invertible, and

𝐜^{𝖳} 𝐻_{𝑛} 𝐜 =

{‖ \sum_{𝑗} 𝑐_{𝑗} 𝑥^{𝑗 - 1} ‖}^{2} >

0

because the polynomial is nonzero.

(a) The formula is an inner product on ${ℝ [𝑥]}_{\leq 𝑛 - 1}$ (see Example 6.3.17 for definiteness; the interval does not matter). The $(𝑖, 𝑗)$ entry of the Gram matrix of $𝑥^{0}, \dots, 𝑥^{𝑛 - 1}$ is

⟨ 𝑥^{𝑗 - 1}, 𝑥^{𝑖 - 1} ⟩ = \int_{0}^{1} 𝑡^{𝑖 + 𝑗 - 2} d 𝑡 = \frac{1}{𝑖 + 𝑗 - 1} = ℎ_{𝑖 𝑗} .

(b) The monomials $1, 𝑥, \dots, 𝑥^{𝑛 - 1}$ are linearly independent (Example 1.5.7), so $𝐻_{𝑛}$ is invertible by Proposition 6.3.30. For $𝐜 \neq 𝟎$ , the polynomial $𝑝 =$ $𝑐_{1} +$ $𝑐_{2} 𝑥 +$ $\dots +$ $𝑐_{𝑛} 𝑥^{𝑛 - 1}$ is nonzero, and by Proposition 6.3.30(a), $𝐜^{𝖳} 𝐻_{𝑛} 𝐜 =$ ${‖ 𝑝 ‖}^{2} >$ $0$ .

Computing $det 𝐻_{𝑛}$ directly is laborious already for $𝑛 = 4$ ; the Gram matrix point of view gives invertibility with no computation.

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

Claim. If the columns of $𝐴 \in ℝ^{𝑛 \times 𝑛}$ are orthogonal and nonzero, then the rows of $𝐴$ are orthogonal.

Argument. By Theorem 6.3.29, $𝐴^{𝖳} 𝐴 = 𝐷$ is diagonal with positive diagonal entries, so $𝐷$ is invertible. The columns are independent (Proposition 6.3.13), so $𝐴$ is invertible, and $𝐴^{𝖳} = 𝐷 𝐴^{- 1}$ . Hence $𝐴 𝐴^{𝖳} = 𝐴 𝐷 𝐴^{- 1}$ . A matrix similar to a diagonal matrix is diagonal, so $𝐴 𝐴^{𝖳}$ is diagonal, which says that the rows of $𝐴$ are orthogonal.

Solution.

Uses. Theorem 6.3.29 (Orthonormal columns), Proposition 6.3.34 (Characterizations of unitary matrices)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Check each step. Which one is a general claim about matrices that you have not seen proved?

Hint 2. Is

(\begin{matrix} 1 & 1 \\ 0 & 2 \end{matrix})

diagonal? Is it similar to a diagonal matrix? For a counterexample to the claim, try

2 \times 2

matrices with columns

(1, 1)

and

(𝑎, - 𝑎)

Sketch. The false step is “similar to a diagonal matrix implies diagonal”. The claim is false:

𝐴 = (\begin{matrix} 1 & 2 \\ 1 & - 2 \end{matrix})

has

𝐴^{𝖳} 𝐴 = diag (2, 8)

but

𝐴 𝐴^{𝖳} = (\begin{matrix} 5 & - 3 \\ - 3 & 5 \end{matrix})

. With orthonormal columns (

𝐷 = 𝐼

) the argument works and gives Proposition 6.3.34.

Every step is correct except “a matrix similar to a diagonal matrix is diagonal”. For instance $𝑃 𝐷 𝑃^{- 1}$ with $𝐷 = diag (1, 2)$ and $𝑃 = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ is $(\begin{matrix} 1 & 1 \\ 0 & 2 \end{matrix})$ , which is not diagonal. (Matrices similar to diagonal ones are the diagonalizable matrices of Section 7.4.)

The claim is false. For $𝐴 = (\begin{matrix} 1 & 2 \\ 1 & - 2 \end{matrix})$ , the columns $(1, 1)$ and $(2, - 2)$ are orthogonal and nonzero, and $𝐴^{𝖳} 𝐴 = diag (2, 8)$ . But the rows $(1, 2)$ and $(1, - 2)$ have dot product $1 - 4 = - 3$ , and indeed

𝐴 𝐴^{𝖳} = (\begin{matrix} 1 & 2 \\ 1 & - 2 \end{matrix}) (\begin{matrix} 1 & 1 \\ 2 & - 2 \end{matrix}) = (\begin{matrix} 5 & - 3 \\ - 3 & 5 \end{matrix}) .

The argument does prove something when $𝐷 = 𝐼$ , that is, when the columns are orthonormal: then $𝐴 𝐴^{𝖳} = 𝐴 𝐴^{- 1} = 𝐼$ , and the rows are orthonormal. This is (i) $\Rightarrow$ (iii) of Proposition 6.3.34.

Exercise 6.3.56.standard Let $𝐯_{1}, \dots, 𝐯_{𝑛}$ be a list in $𝑉$ with Gram matrix $𝐺$ , let $𝑆 =$ $(𝑠_{𝑖 𝑗}) \in$ $𝔽^{𝑛 \times 𝑛}$ , and let $𝐰_{𝑗} =$ $\sum_{𝑖 = 1}^{𝑛} 𝑠_{𝑖 𝑗} 𝐯_{𝑖}$ for $𝑗 = 1, \dots, 𝑛$ .

(a)Show that the Gram matrix of $𝐰_{1}, \dots, 𝐰_{𝑛}$ is $𝑆^{*} 𝐺 𝑆$ .
(b)Suppose $𝒪︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}$ is an orthonormal basis of $𝑉$ . Show that $𝐰_{1}, \dots, 𝐰_{𝑛}$ is an orthonormal basis of $𝑉$ if and only if $𝑆$ is unitary. Conclude that the change-of-coordinates matrix between two orthonormal bases (Section 4.5) is unitary.

Solution.

Uses. Definition 6.3.28 (Gram matrix), Proposition 6.1.4 (Sesquilinearity), Definition 2.4.1 (Matrix product), Definition 6.3.26 (Conjugate transpose), Definition 6.3.33 (Unitary and orthogonal matrices), Corollary 6.3.14 (Counting orthogonal vectors)

Techniques. Expand by multilinearity (Technique 5.1.7), Gram matrices (Technique 6.3.31)

Hint 1. Expand

⟨ 𝐰_{𝑗}, 𝐰_{𝑖} ⟩

in both slots. The coefficients from the second slot come out conjugated.

Hint 2.

⟨ 𝐰_{𝑗}, 𝐰_{𝑖} ⟩ =

\sum_{𝑚} \sum_{𝑙} 𝑠_{𝑚 𝑖} 𝑔_{𝑚 𝑙} 𝑠_{𝑙 𝑗}

, and

𝑠_{𝑚 𝑖}

is the

(𝑖, 𝑚)

entry of

𝑆^{*}

Hint 3. For (b),

𝐺 = 𝐼_{𝑛}

; a list is orthonormal exactly when its Gram matrix is

𝐼_{𝑛}

. Column

𝑗

𝑆

{[𝐰_{𝑗}]}_{𝒪︀}

Sketch. (a)

⟨ 𝐰_{𝑗}, 𝐰_{𝑖} ⟩ =

\sum_{𝑙, 𝑚} 𝑠_{𝑙 𝑗} 𝑠_{𝑚 𝑖} ⟨ 𝐯_{𝑙}, 𝐯_{𝑚} ⟩ =

\sum_{𝑚, 𝑙} {(𝑆^{*})}_{𝑖 𝑚} 𝑔_{𝑚 𝑙} 𝑠_{𝑙 𝑗} =

{(𝑆^{*} 𝐺 𝑆)}_{𝑖 𝑗}

. (b) With

𝐺 = 𝐼

, the

𝐰_{𝑗}

are orthonormal iff

𝑆^{*} 𝑆 = 𝐼

, and

𝑛

orthonormal vectors form a basis. Column

𝑗

𝑆

{[𝐰_{𝑗}]}_{𝒪︀}

, so

𝑆

is the change-of-coordinates matrix from the

𝐰

-basis to

𝒪︀

(a) Expanding both slots (linearity in the first, Proposition 6.1.4 in the second),

\begin{aligned} ⟨ 𝐰_{𝑗}, 𝐰_{𝑖} ⟩ & = ⟨ \sum_{𝑙} 𝑠_{𝑙 𝑗} 𝐯_{𝑙}, \sum_{𝑚} 𝑠_{𝑚 𝑖} 𝐯_{𝑚} ⟩ = \sum_{𝑚 = 1}^{𝑛} \sum_{𝑙 = 1}^{𝑛} 𝑠_{𝑚 𝑖} ⟨ 𝐯_{𝑙}, 𝐯_{𝑚} ⟩ 𝑠_{𝑙 𝑗} \\ = \sum_{𝑚 = 1}^{𝑛} \sum_{𝑙 = 1}^{𝑛} {(𝑆^{*})}_{𝑖 𝑚} 𝑔_{𝑚 𝑙} 𝑠_{𝑙 𝑗}, \end{aligned}

using $𝑔_{𝑚 𝑙} =$ $⟨ 𝐯_{𝑙}, 𝐯_{𝑚} ⟩$ and ${(𝑆^{*})}_{𝑖 𝑚} = 𝑠_{𝑚 𝑖}$ . By Definition 2.4.1, the right side is the $(𝑖, 𝑗)$ entry of $𝑆^{*} 𝐺 𝑆$ .

(b) If $𝒪︀$ is orthonormal, its Gram matrix is $𝐼_{𝑛}$ , so by (a) the Gram matrix of $𝐰_{1}, \dots, 𝐰_{𝑛}$ is $𝑆^{*} 𝑆$ . A list is orthonormal exactly when its Gram matrix is the identity, so $𝐰_{1}, \dots, 𝐰_{𝑛}$ is orthonormal if and only if $𝑆^{*} 𝑆 = 𝐼_{𝑛}$ , that is, $𝑆$ is unitary. An orthonormal list of length $𝑛 = dim 𝑉$ is an orthonormal basis (Corollary 6.3.14).

Column $𝑗$ of $𝑆$ is the coordinate vector ${[𝐰_{𝑗}]}_{𝒪︀}$ , so $𝑆$ is the change-of-coordinates matrix that converts coordinates with respect to $𝐰_{1}, \dots, 𝐰_{𝑛}$ into coordinates with respect to $𝒪︀$ . Hence if both lists are orthonormal bases, this matrix is unitary, and so is its inverse, the change of coordinates in the other direction (Exercise 6.3.37).

Exercise 6.3.57.standard

(a)Show that $det (𝐴^{*}) = det 𝐴$ for every $𝐴 \in 𝔽^{𝑛 \times 𝑛}$ . Deduce that $| det 𝑈 | = 1$ for every unitary $𝑈$ , and that $det 𝑄 = \pm 1$ for every real orthogonal $𝑄$ .
(b)Show by example that a real matrix with determinant $1$ need not be orthogonal.
(c)Show that an upper triangular unitary matrix is diagonal.

Solution.

Uses. Theorem 5.3.3 (The Leibniz formula), Theorem 5.4.14 (The transpose), Theorem 5.4.10 (Multiplicativity), Theorem 6.3.29 (Orthonormal columns), Definition 6.3.26 (Conjugate transpose)

Hint 1. Conjugation respects sums and products, so it passes through the Leibniz formula:

det 𝐴 = det 𝐴

. Then use

det (𝐵^{𝖳}) = det 𝐵

Hint 2. Take determinants of

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

Hint 3. For (c), the first column of

𝑈

𝑢_{11} 𝐞_{1}

. Orthogonality of the other columns to it kills the rest of the first row. Then repeat with the second column.

Sketch. (a)

det 𝐴^{*} =

det 𝐴^{𝖳} =

det 𝐴 =

det 𝐴

, so

1 =

det (𝑈^{*} 𝑈) =

det 𝑈 det 𝑈 =

{| det 𝑈 |}^{2}

; a real number of modulus

1

\pm 1

. (b)

diag (2, 1 / 2)

. (c) Induct on the row: if rows

1, \dots, 𝑖 - 1

vanish off the diagonal, column

𝑖

𝑢_{𝑖 𝑖} 𝐞_{𝑖}

, and orthogonality of column

𝑗 > 𝑖

to it gives

𝑢_{𝑖 𝑗} 𝑢_{𝑖 𝑖} = 0

with

| 𝑢_{𝑖 𝑖} | = 1

, so row

𝑖

vanishes off the diagonal too.

(a) By Theorem 5.3.3, $det 𝐴$ is a sum of signed products of entries of $𝐴$ , which are the conjugates of the corresponding products for $𝐴$ ; since conjugation respects sums and products, $det 𝐴 = det 𝐴$ . By Theorem 5.4.14, $det (𝐴^{*}) =$ $det (𝐴^{𝖳}) =$ $det 𝐴 =$ $det 𝐴$ .

If $𝑈$ is unitary, then by Theorem 5.4.10,

\begin{aligned} 1 = det 𝐼_{𝑛} = det (𝑈^{*} 𝑈) & = det (𝑈^{*}) det 𝑈 \\ = det 𝑈 det 𝑈 = {| det 𝑈 |}^{2}, \end{aligned}

so $| det 𝑈 | = 1$ . If $𝑄$ is real orthogonal, $det 𝑄$ is a real number with $| det 𝑄 | = 1$ , so $det 𝑄 = \pm 1$ .

(b) $𝐴 = diag (2, 1 / 2)$ has $det 𝐴 = 1$ , but its first column has norm $2$ , so $𝐴^{𝖳} 𝐴 \neq 𝐼_{2}$ .

(c) Let $𝑈$ be unitary and upper triangular, with columns $𝐜_{1}, \dots, 𝐜_{𝑛}$ ; by Theorem 6.3.29 they are orthonormal. We show by induction on $𝑖$ that $𝑢_{𝑖 𝑗} = 0$ for all $𝑗 > 𝑖$ . Suppose this holds for the rows $1, \dots, 𝑖 - 1$ . Then the entries $𝑢_{1 𝑖}, \dots, 𝑢_{𝑖 - 1, 𝑖}$ of $𝐜_{𝑖}$ vanish, and so do its entries below the diagonal, so $𝐜_{𝑖} = 𝑢_{𝑖 𝑖} 𝐞_{𝑖}$ , and $| 𝑢_{𝑖 𝑖} | = ‖ 𝐜_{𝑖} ‖ = 1$ . For $𝑗 > 𝑖$ ,

0 = 𝐜_{𝑗} \cdot 𝐜_{𝑖} = 𝑢_{𝑖 𝑗} 𝑢_{𝑖 𝑖},

and $𝑢_{𝑖 𝑖} \neq 0$ , so $𝑢_{𝑖 𝑗} = 0$ . This completes the induction (the case $𝑖 = 1$ needs no hypothesis). So $𝑈$ is diagonal, with diagonal entries of modulus $1$ .

Exercise 6.3.58.standard Show that $𝑈 \in ℂ^{2 \times 2}$ is unitary if and only if

𝑈 = (\begin{matrix} 𝑎 & - 𝜆 𝑐 \\ 𝑐 & 𝜆 𝑎 \end{matrix})

for some $𝑎, 𝑐, 𝜆 \in ℂ$ with ${| 𝑎 |}^{2} + {| 𝑐 |}^{2} = 1$ and $| 𝜆 | = 1$ , and that then $det 𝑈 = 𝜆$ .

Solution.

Uses. Theorem 6.3.29 (Orthonormal columns), Definition 6.1.8 (Dot product), Theorem 5.1.13 (The $2 \times 2$ determinant)

Hint 1. The first column

(𝑎, 𝑐)

is any unit vector. Find one unit vector orthogonal to it by inspection.

Hint 2.

(- 𝑐, 𝑎)

works. Show that every vector orthogonal to

(𝑎, 𝑐)

is a multiple of it: solve

𝑏 𝑎 + 𝑑 𝑐 = 0

, treating

𝑎 \neq 0

and

𝑎 = 0

separately.

Sketch. The given matrices have orthonormal columns by a direct check. Conversely, if

(𝑎, 𝑐)

is a unit vector, the solutions of

𝑏 𝑎 + 𝑑 𝑐 = 0

are the multiples of

(- 𝑐, 𝑎)

, which is a unit vector; so a unit second column is

𝜆 (- 𝑐, 𝑎)

with

| 𝜆 | = 1

. Then

det 𝑈 =

𝜆 ({| 𝑎 |}^{2} + {| 𝑐 |}^{2}) =

𝜆

By Theorem 6.3.29, $𝑈$ is unitary if and only if its columns are orthonormal.

Suppose $𝑈$ has the given form. The first column has squared norm ${| 𝑎 |}^{2} + {| 𝑐 |}^{2} = 1$ , the second has squared norm ${| 𝜆 |}^{2} ({| 𝑐 |}^{2} + {| 𝑎 |}^{2}) =$ $1$ , and

(- 𝜆 𝑐, 𝜆 𝑎) \cdot (𝑎, 𝑐) = - 𝜆 𝑐 𝑎 + 𝜆 𝑎 𝑐 = 0 .

So $𝑈$ is unitary.

Conversely, let $𝑈 = (\begin{matrix} 𝑎 & 𝑏 \\ 𝑐 & 𝑑 \end{matrix})$ be unitary. Then ${| 𝑎 |}^{2} + {| 𝑐 |}^{2} = 1$ , and the second column satisfies $(𝑏, 𝑑) \cdot$ $(𝑎, 𝑐) =$ $𝑏 𝑎 +$ $𝑑 𝑐 =$ $0$ . If $𝑎 \neq 0$ , then $𝑏 = - 𝑑 𝑐 / 𝑎$ , so $(𝑏, 𝑑) =$ $(𝑑 / 𝑎) (- 𝑐, 𝑎)$ . If $𝑎 = 0$ , then $| 𝑐 | = 1$ , so $𝑐 \neq 0$ and $𝑑 = 0$ , and $(𝑏, 𝑑) =$ $(𝑏, 0) =$ $(- 𝑏 / 𝑐) (- 𝑐, 𝑎)$ since $𝑎 = 0$ . Either way $(𝑏, 𝑑) =$ $𝜆 (- 𝑐, 𝑎)$ for some $𝜆 \in ℂ$ . Since ${‖ (- 𝑐, 𝑎) ‖}^{2} =$ ${| 𝑐 |}^{2} +$ ${| 𝑎 |}^{2} =$ $1$ and $(𝑏, 𝑑)$ is a unit vector, $| 𝜆 | = 1$ .

Finally, by Theorem 5.1.13, $det 𝑈 =$ $𝑎 \cdot$ $𝜆 𝑎 -$ $(- 𝜆 𝑐) 𝑐 =$ $𝜆 ({| 𝑎 |}^{2} + {| 𝑐 |}^{2}) =$ $𝜆$ . The unitary matrices with determinant $1$ are those with $𝜆 = 1$ .

Exercise 6.3.59.routine Let $𝑛 = 3$ , so that $𝜔 = - 1 / 2 + (\sqrt{3} / 2) 𝑖$ .

(a)Write down $Φ_{3}$ and $Φ_{3}^{- 1}$ .
(b)Write $𝐱 = (1, 2, 0)$ as a linear combination of $𝐟_{0}, 𝐟_{1}, 𝐟_{2}$ , and check Proposition 6.3.41(d).

Solution.

Uses. Definition 6.3.40 (Fourier matrix), Proposition 6.3.41 (The Fourier basis)

Hint 1.

𝜔^{3} = 1

, so

𝜔^{4} = 𝜔

, and

𝜔^{2} = 𝜔 = 𝜔^{- 1}

Hint 2. The coefficient of

𝐟_{𝑘}

⟨ 𝐱, 𝐟_{𝑘} ⟩ / 3

with

⟨ 𝐱, 𝐟_{𝑘} ⟩ =

\sum_{𝑗} 𝑥_{𝑗} 𝜔^{- 𝑗 𝑘}

Sketch.

Φ_{3} =

(\begin{matrix} 1 & 1 & 1 \\ 1 & 𝜔 & 𝜔^{2} \\ 1 & 𝜔^{2} & 𝜔 \end{matrix})

and

Φ_{3}^{- 1} = (1 / 3) Φ_{3}

. The transform of

𝐱

(3, - \sqrt{3} 𝑖, \sqrt{3} 𝑖)

, so

𝐱 =

𝐟_{0} +

(𝑖 / \sqrt{3}) (𝐟_{2} - 𝐟_{1})

, and

1 + 4 = (9 + 3 + 3) / 3

(a) Since $𝜔^{3} = 1$ , $𝜔^{4} = 𝜔$ , and $𝜔 = 𝜔^{2}$ ,

\begin{aligned} Φ_{3} & = (\begin{matrix} 1 & 1 & 1 \\ 1 & 𝜔 & 𝜔^{2} \\ 1 & 𝜔^{2} & 𝜔 \end{matrix}), \\ Φ_{3}^{- 1} & = \frac{1}{3} Φ_{3} = \frac{1}{3} (\begin{matrix} 1 & 1 & 1 \\ 1 & 𝜔^{2} & 𝜔 \\ 1 & 𝜔 & 𝜔^{2} \end{matrix}), \end{aligned}

by Proposition 6.3.41(b).

(b) By Proposition 6.3.41(c), with $𝜔^{- 1} = 𝜔^{2}$ and $𝜔^{- 2} = 𝜔$ ,

\begin{aligned} ⟨ 𝐱, 𝐟_{0} ⟩ & = 3, \\ ⟨ 𝐱, 𝐟_{1} ⟩ & = 1 + 2 𝜔^{2} = - \sqrt{3} 𝑖, \\ ⟨ 𝐱, 𝐟_{2} ⟩ & = 1 + 2 𝜔 = \sqrt{3} 𝑖 . \end{aligned}

So $𝐱 =$ $(1 / 3) (3 𝐟_{0} - \sqrt{3} 𝑖 𝐟_{1} + \sqrt{3} 𝑖 𝐟_{2}) =$ $𝐟_{0} +$ $(𝑖 / \sqrt{3}) (𝐟_{2} - 𝐟_{1})$ . Check: $𝐟_{2} -$ $𝐟_{1} =$ $(0, 𝜔^{2} - 𝜔, 𝜔 - 𝜔^{2}) =$ $(0, - \sqrt{3} 𝑖, \sqrt{3} 𝑖)$ , so $(𝑖 / \sqrt{3}) (𝐟_{2} - 𝐟_{1}) =$ $(0, 1, - 1)$ , and adding $𝐟_{0} = (1, 1, 1)$ gives $(1, 2, 0)$ . For (d): ${| 1 |}^{2} + {| 2 |}^{2} + 0 = 5$ and $(9 + 3 + 3) / 3 = 5$ .

Exercise 6.3.60.standard Index rows and columns by $0, \dots, 𝑛 - 1$ , as for $Φ_{𝑛}$ .

(a)Show that $Φ_{𝑛}^{2} = 𝑛 𝑃$ , where $𝑃$ has entries $𝑝_{𝑗 𝑙} = 1$ if $𝑛 | (𝑗 + 𝑙)$ and $𝑝_{𝑗 𝑙} = 0$ otherwise. Show that $𝑃$ is a permutation matrix with $𝑃^{2} = 𝐼_{𝑛}$ , and deduce that $Φ_{𝑛}^{4} = 𝑛^{2} 𝐼_{𝑛}$ .
(b)Show that $| det Φ_{𝑛} | = 𝑛^{𝑛 / 2}$ .

Solution.

Uses. Lemma 6.3.39 (Sums of roots of unity), Definition 5.2.29 (Permutation matrix), Theorem 5.4.10 (Multiplicativity), Proposition 5.3.15 (Triangular matrices)

Techniques. Compute entry by entry (Technique 2.4.15)

Hint 1.

{(Φ_{𝑛}^{2})}_{𝑗 𝑙} =

\sum_{𝑘} 𝜔^{𝑗 𝑘} 𝜔^{𝑘 𝑙}

. Apply Lemma 6.3.39 with

𝑚 = 𝑗 + 𝑙

Hint 2. For each

𝑗

there is exactly one

𝑙 \in {0, \dots, 𝑛 - 1}

with

𝑛 | (𝑗 + 𝑙)

. Which?

Hint 3. For (b), take determinants in

Φ_{𝑛}^{4} = 𝑛^{2} 𝐼_{𝑛}

Sketch. (a)

{(Φ_{𝑛}^{2})}_{𝑗 𝑙} =

\sum_{𝑘} 𝜔^{𝑘 (𝑗 + 𝑙)}

𝑛

𝑛 | (𝑗 + 𝑙)

and

0

otherwise. Each row and each column of

𝑃

has a single

1

, at

𝑙 = 𝜎 (𝑗)

where

𝜎 (𝑗)

- 𝑗

reduced mod

𝑛

, and

𝜎

is its own inverse, so

𝑃^{2} = 𝐼

and

Φ_{𝑛}^{4} = 𝑛^{2} 𝑃^{2} = 𝑛^{2} 𝐼

. (b)

{(det Φ_{𝑛})}^{4} =

det (𝑛^{2} 𝐼_{𝑛}) =

𝑛^{2 𝑛}

, so

| det Φ_{𝑛} | = 𝑛^{𝑛 / 2}

(a) By the entry formula for products and Lemma 6.3.39,

{(Φ_{𝑛}^{2})}_{𝑗 𝑙} = \sum_{𝑘 = 0}^{𝑛 - 1} 𝜔^{𝑗 𝑘} 𝜔^{𝑘 𝑙} = \sum_{𝑘 = 0}^{𝑛 - 1} 𝜔^{𝑘 (𝑗 + 𝑙)} = {\begin{cases} 𝑛 & if 𝑛 | (𝑗 + 𝑙) \\ 0 & otherwise, \end{cases}

so $Φ_{𝑛}^{2} = 𝑛 𝑃$ . For $𝑗 \in {0, \dots, 𝑛 - 1}$ , let $𝜎 (𝑗) = 0$ if $𝑗 = 0$ and $𝜎 (𝑗) = 𝑛 - 𝑗$ otherwise. Then $𝜎 (𝑗)$ is the only $𝑙 \in {0, \dots, 𝑛 - 1}$ with $𝑛 | (𝑗 + 𝑙)$ , so row $𝑗$ of $𝑃$ has its only $1$ in column $𝜎 (𝑗)$ . Also $𝜎 (𝜎 (𝑗)) = 𝑗$ , so $𝜎$ is a bijection of ${0, \dots, 𝑛 - 1}$ (its own inverse), and $𝑃$ is the permutation matrix of $𝜎$ (Definition 5.2.29). It is symmetric, since $𝑛 | (𝑗 + 𝑙)$ is symmetric in $𝑗$ and $𝑙$ . Finally

{(𝑃^{2})}_{𝑗 𝑚} = \sum_{𝑙} 𝑝_{𝑗 𝑙} 𝑝_{𝑙 𝑚} = 𝑝_{𝜎 (𝑗) 𝑚},

which is $1$ exactly when $𝑚 = 𝜎 (𝜎 (𝑗)) = 𝑗$ . So $𝑃^{2} = 𝐼_{𝑛}$ and $Φ_{𝑛}^{4} =$ ${(𝑛 𝑃)}^{2} =$ $𝑛^{2} 𝑃^{2} =$ $𝑛^{2} 𝐼_{𝑛}$ .

(b) By Theorem 5.4.10 and Proposition 5.3.15, ${(det Φ_{𝑛})}^{4} =$ $det (Φ_{𝑛}^{4}) =$ $det (𝑛^{2} 𝐼_{𝑛}) =$ $𝑛^{2 𝑛}$ . Taking moduli, ${| det Φ_{𝑛} |}^{4} = 𝑛^{2 𝑛}$ , so $| det Φ_{𝑛} | = 𝑛^{𝑛 / 2}$ . (Alternatively, $Φ_{𝑛}^{*} Φ_{𝑛} = 𝑛 𝐼_{𝑛}$ and Exercise 6.3.57(a) give ${| det Φ_{𝑛} |}^{2} = 𝑛^{𝑛}$ .)

Exercise 6.3.61.hard For $𝐜 =$ $(𝑐_{0}, \dots, 𝑐_{𝑛 - 1}) \in$ $ℂ^{𝑛}$ , the circulant matrix $𝐶$ has entries $𝐶_{𝑗 𝑙} =$ $𝑐_{(𝑗 - 𝑙) mod 𝑛}$ , with indices $0, \dots, 𝑛 - 1$ . For $𝑛 = 3$ ,

𝐶 = (\begin{matrix} 𝑐_{0} & 𝑐_{2} & 𝑐_{1} \\ 𝑐_{1} & 𝑐_{0} & 𝑐_{2} \\ 𝑐_{2} & 𝑐_{1} & 𝑐_{0} \end{matrix}) .

(a)Show that $𝐶 𝐟_{𝑘} =$ $⟨ 𝐜, 𝐟_{𝑘} ⟩ 𝐟_{𝑘}$ for $𝑘 = 0, \dots, 𝑛 - 1$ .
(b)Deduce that $𝐶 = Φ_{𝑛} 𝐷 Φ_{𝑛}^{- 1}$ , where $𝐷$ is the diagonal matrix with entries $⟨ 𝐜, 𝐟_{0} ⟩,$ $\dots,$ $⟨ 𝐜, 𝐟_{𝑛 - 1} ⟩$ . Conclude that any two $𝑛 \times 𝑛$ circulant matrices commute, and that $𝐶$ is invertible if and only if $⟨ 𝐜, 𝐟_{𝑘} ⟩ \neq 0$ for every $𝑘$ .
(c)Using (b), decide whether the following matrix is invertible, and find its determinant:
$(\begin{matrix} 2 & 0 & 1 \\ 1 & 2 & 0 \\ 0 & 1 & 2 \end{matrix}) .$

Solution.

Uses. Definition 6.3.40 (Fourier matrix), Proposition 6.3.41 (The Fourier basis), Proposition 2.4.8 (Four views of the product), Theorem 5.4.10 (Multiplicativity)

Hint 1. Write

{(𝐶 𝐟_{𝑘})}_{𝑗} =

\sum_{𝑙} 𝑐_{(𝑗 - 𝑙) mod 𝑛} 𝜔^{𝑙 𝑘}

and substitute

𝑚 = (𝑗 - 𝑙) mod 𝑛

. Since

𝜔^{𝑛} = 1

𝜔^{𝑙 𝑘} =

𝜔^{(𝑗 - 𝑚) 𝑘}

Hint 2. For (b), (a) says

𝐶 Φ_{𝑛} = Φ_{𝑛} 𝐷

column by column. Diagonal matrices commute.

Hint 3. For (c),

𝐜 = (2, 1, 0)

and

⟨ 𝐜, 𝐟_{𝑘} ⟩ = 2 + 𝜔^{- 𝑘}

Sketch. (a) Reindexing by

𝑚 = (𝑗 - 𝑙) mod 𝑛

gives

{(𝐶 𝐟_{𝑘})}_{𝑗} =

𝜔^{𝑗 𝑘} \sum_{𝑚} 𝑐_{𝑚} 𝜔^{- 𝑚 𝑘} =

⟨ 𝐜, 𝐟_{𝑘} ⟩ {(𝐟_{𝑘})}_{𝑗}

. (b) So

𝐶 Φ_{𝑛} = Φ_{𝑛} 𝐷

, and

𝐶 = Φ_{𝑛} 𝐷 Φ_{𝑛}^{- 1}

; then

𝐶 𝐶^{'} =

Φ_{𝑛} 𝐷 𝐷^{'} Φ_{𝑛}^{- 1} =

𝐶^{'} 𝐶

, and

𝐶

is invertible iff

𝐷

is. (c) The values

2 + 𝜔^{- 𝑘}

are

3

2 + 𝜔^{2}

2 + 𝜔

, all nonzero, and

det 𝐶 = 3 {| 2 + 𝜔 |}^{2} = 9

(a) Fix $𝑗$ and $𝑘$ . As $𝑙$ runs over $0, \dots, 𝑛 - 1$ , so does $𝑚 = (𝑗 - 𝑙) mod 𝑛$ , and $𝑙$ is congruent to $𝑗 - 𝑚$ modulo $𝑛$ . Since $𝜔^{𝑛} = 1$ , $𝜔^{𝑙 𝑘} =$ $𝜔^{(𝑗 - 𝑚) 𝑘}$ . Hence

\begin{aligned} {(𝐶 𝐟_{𝑘})}_{𝑗} & = \sum_{𝑙 = 0}^{𝑛 - 1} 𝑐_{(𝑗 - 𝑙) mod 𝑛} 𝜔^{𝑙 𝑘} = \sum_{𝑚 = 0}^{𝑛 - 1} 𝑐_{𝑚} 𝜔^{(𝑗 - 𝑚) 𝑘} \\ = 𝜔^{𝑗 𝑘} \sum_{𝑚 = 0}^{𝑛 - 1} 𝑐_{𝑚} 𝜔^{- 𝑚 𝑘} = ⟨ 𝐜, 𝐟_{𝑘} ⟩ {(𝐟_{𝑘})}_{𝑗}, \end{aligned}

using $⟨ 𝐜, 𝐟_{𝑘} ⟩ =$ $\sum_{𝑚} 𝑐_{𝑚} 𝜔^{- 𝑚 𝑘}$ (Proposition 6.3.41(c)).

(b) Column $𝑘$ of $𝐶 Φ_{𝑛}$ is $𝐶 𝐟_{𝑘}$ (Proposition 2.4.8), and column $𝑘$ of $Φ_{𝑛} 𝐷$ is $⟨ 𝐜, 𝐟_{𝑘} ⟩ 𝐟_{𝑘}$ . By (a), $𝐶 Φ_{𝑛} = Φ_{𝑛} 𝐷$ , and since $Φ_{𝑛}$ is invertible, $𝐶 = Φ_{𝑛} 𝐷 Φ_{𝑛}^{- 1}$ . If $𝐶^{'}$ is another circulant, with diagonal matrix $𝐷^{'}$ , then since diagonal matrices commute,

𝐶 𝐶^{'} = Φ_{𝑛} 𝐷 𝐷^{'} Φ_{𝑛}^{- 1} = Φ_{𝑛} 𝐷^{'} 𝐷 Φ_{𝑛}^{- 1} = 𝐶^{'} 𝐶 .

Finally, $𝐶$ is invertible if and only if $𝐷 = Φ_{𝑛}^{- 1} 𝐶 Φ_{𝑛}$ is, and a diagonal matrix is invertible if and only if its diagonal entries are nonzero.

(c) The matrix is the circulant with $𝐜 = (2, 1, 0)$ . With $𝜔 = - 1 / 2 + (\sqrt{3} / 2) 𝑖$ , the entries of $𝐷$ are $⟨ 𝐜, 𝐟_{𝑘} ⟩ = 2 + 𝜔^{- 𝑘}$ , namely $3$ , $2 + 𝜔^{2}$ , and $2 + 𝜔$ . The last two are $3 / 2 \mp (\sqrt{3} / 2) 𝑖 \neq 0$ , so the matrix is invertible. By Theorem 5.4.10, $det 𝐶 =$ $det 𝐷 =$ $3 (2 + 𝜔^{2}) (2 + 𝜔) =$ $3 {| 2 + 𝜔 |}^{2} =$ $3 (9 / 4 + 3 / 4) =$ $9$ , which agrees with cofactor expansion along the first row: $2 \cdot 4 - 0 + 1 \cdot 1 = 9$ .

Exercise 6.3.62.hard Let $𝑛 \geq 1$ , let $𝜔$ be as in Section 6.3.4, and let $𝑟 \in {0, \dots, 𝑛 - 1}$ .

(a)Let $𝑝 (𝑥) =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $\dots +$ $𝑎_{𝑑} 𝑥^{𝑑} \in$ $ℂ [𝑥]$ . Show that
$\sum_{0 \leq 𝑘 \leq 𝑑, 𝑛 | (𝑘 - 𝑟)} 𝑎_{𝑘} = \frac{1}{𝑛} \sum_{𝑗 = 0}^{𝑛 - 1} 𝜔^{- 𝑗 𝑟} 𝑝 (𝜔^{𝑗}) .$
(b)Compute $(\binom{12}{0}) +$ $(\binom{12}{3}) +$ $(\binom{12}{6}) +$ $(\binom{12}{9}) +$ $(\binom{12}{12})$ without adding these numbers.
(c)Show that for every $𝑚 \geq 0$ , $\sum_{𝑘 \equiv 0 (mod 3)} (\binom{𝑚}{𝑘}) =$ $(2^{𝑚} + 2 cos (𝑚 𝜋 / 3)) / 3$ .

Solution.

Uses. Lemma 6.3.39 (Sums of roots of unity), Definition 1.2.17 (Evaluation), de Moivre’s formula (Section B.1), the binomial theorem

Hint 1. Substitute

𝑝 (𝜔^{𝑗}) =

\sum_{𝑘} 𝑎_{𝑘} 𝜔^{𝑗 𝑘}

, exchange the two sums, and apply Lemma 6.3.39 with

𝑚 = 𝑘 - 𝑟

Hint 2. For (b), take

𝑝 = {(1 + 𝑥)}^{12}

𝑛 = 3

𝑟 = 0

. Write

1 + 𝜔

and

1 + 𝜔^{2}

in the form

cos 𝜃 + 𝑖 sin 𝜃

Sketch. (a)

(1 / 𝑛) \sum_{𝑗} 𝜔^{- 𝑗 𝑟} \sum_{𝑘} 𝑎_{𝑘} 𝜔^{𝑗 𝑘} =

\sum_{𝑘} 𝑎_{𝑘} (1 / 𝑛) \sum_{𝑗} 𝜔^{𝑗 (𝑘 - 𝑟)}

, and the inner average is

1

𝑛 | (𝑘 - 𝑟)

and

0

otherwise. (b) With

𝜔 = 𝜔_{3}

1 +

𝜔 =

cos (𝜋 / 3) +

𝑖 sin (𝜋 / 3)

and

1 + 𝜔^{2}

is its conjugate, so their

12

th powers are

1

, and the sum is

(2^{12} + 2) / 3 = 1366

. (c) The same computation with exponent

𝑚

gives

(2^{𝑚} + 2 cos (𝑚 𝜋 / 3)) / 3

(a) By Definition 1.2.17, $𝑝 (𝜔^{𝑗}) =$ $\sum_{𝑘 = 0}^{𝑑} 𝑎_{𝑘} 𝜔^{𝑗 𝑘}$ . Exchanging the finite sums,

\frac{1}{𝑛} \sum_{𝑗 = 0}^{𝑛 - 1} 𝜔^{- 𝑗 𝑟} 𝑝 (𝜔^{𝑗}) = \sum_{𝑘 = 0}^{𝑑} 𝑎_{𝑘} (\frac{1}{𝑛} \sum_{𝑗 = 0}^{𝑛 - 1} 𝜔^{𝑗 (𝑘 - 𝑟)}) .

By Lemma 6.3.39 the expression in parentheses is $1$ if $𝑛 | (𝑘 - 𝑟)$ and $0$ otherwise, which gives the claim.

(b) Take $𝑛 = 3$ , $𝑟 = 0$ , and $𝑝 =$ ${(1 + 𝑥)}^{12} =$ $\sum_{𝑘} (\binom{12}{𝑘}) 𝑥^{𝑘}$ . Then the left side of (a) is the requested sum, and the right side is $(𝑝 (1) + 𝑝 (𝜔) + 𝑝 (𝜔^{2})) / 3$ . Here $𝜔 = - 1 / 2 + (\sqrt{3} / 2) 𝑖$ , so

\begin{aligned} 1 + 𝜔 & = \frac{1}{2} + \frac{\sqrt{3}}{2} 𝑖 = cos \frac{𝜋}{3} + 𝑖 sin \frac{𝜋}{3}, \\ 1 + 𝜔^{2} & = 1 + 𝜔 = 1 + 𝜔 . \end{aligned}

By de Moivre’s formula, ${(1 + 𝜔)}^{12} =$ $cos 4 𝜋 +$ $𝑖 sin 4 𝜋 =$ $1$ , and ${(1 + 𝜔^{2})}^{12} =$ ${(1 + 𝜔)}^{12} =$ $1$ . So the sum is $(2^{12} + 1 + 1) / 3 =$ $4098 / 3 =$ $1366$ .

(c) With $𝑝 = {(1 + 𝑥)}^{𝑚}$ , the same computation gives ${(1 + 𝜔)}^{𝑚} =$ $cos (𝑚 𝜋 / 3) +$ $𝑖 sin (𝑚 𝜋 / 3)$ and ${(1 + 𝜔^{2})}^{𝑚}$ its conjugate, which add up to $2 cos (𝑚 𝜋 / 3)$ . So the sum is $(2^{𝑚} + 2 cos (𝑚 𝜋 / 3)) / 3$ .

Exercise 6.3.63.hard A Hadamard matrix of order $𝑛$ is a matrix $𝐻 \in ℝ^{𝑛 \times 𝑛}$ whose entries are all $\pm 1$ and whose columns are orthogonal; equivalently, $𝐻^{𝖳} 𝐻 = 𝑛 𝐼_{𝑛}$ .

(a)Show that if a Hadamard matrix of order $𝑛 \geq 3$ exists, then $4 | 𝑛$ .
(b)Show that if $𝐻$ is a Hadamard matrix of order $𝑛$ , then $(\begin{matrix} 𝐻 & 𝐻 \\ 𝐻 & - 𝐻 \end{matrix})$ is a Hadamard matrix of order $2 𝑛$ . Deduce that Hadamard matrices of order $2^{𝑘}$ exist for every $𝑘 \geq 0$ .

Solution.

Uses. Theorem 6.3.29 (Orthonormal columns), Theorem 2.4.34 (Block multiplication)

Techniques. Block decomposition (Technique 2.4.35)

Hint 1. Multiplying a row of

𝐻

- 1

, or permuting the rows, keeps the columns orthogonal. Use this to make the first column all

1

Hint 2. A

\pm 1

column orthogonal to the all-

1

s column has as many

+ 1

s as

- 1

s. Arrange the second column as

𝑛 / 2

entries

+ 1

followed by

𝑛 / 2

entries

- 1

Hint 3. Count the

+ 1

s of the third column in each half, and use its orthogonality to the first two columns.

Sketch. (a) Normalize the first column to all

1

s and sort the rows so that column

2

+ 1

in the first half and

- 1

in the second. If column

3

has

𝑎

entries

+ 1

in the first half and

𝑏

in the second, orthogonality to column

1

gives

𝑎 + 𝑏 = 𝑛 / 2

and to column

2

gives

2 𝑎 - 2 𝑏 = 0

, so

𝑎 = 𝑛 / 4

. (b) Block multiplication gives

{(\begin{matrix} 𝐻 & 𝐻 \\ 𝐻 & - 𝐻 \end{matrix})}^{𝖳} (\begin{matrix} 𝐻 & 𝐻 \\ 𝐻 & - 𝐻 \end{matrix}) =

diag (2 𝐻^{𝖳} 𝐻, 2 𝐻^{𝖳} 𝐻) =

2 𝑛 𝐼_{2 𝑛}

; start from

(1)

(a) Let $𝐻$ be a Hadamard matrix of order $𝑛 \geq 3$ , with columns $𝐡_{1}, \dots, 𝐡_{𝑛}$ , so $𝐡_{𝑘} \cdot$ $𝐡_{𝑙} =$ $\sum_{𝑗} ℎ_{𝑗 𝑘} ℎ_{𝑗 𝑙}$ . Multiplying row $𝑗$ by $- 1$ multiplies both $ℎ_{𝑗 𝑘}$ and $ℎ_{𝑗 𝑙}$ by $- 1$ , so it leaves each term $ℎ_{𝑗 𝑘} ℎ_{𝑗 𝑙}$ unchanged, and permuting the rows only reorders the sum. So both operations produce Hadamard matrices. Multiply each row whose first entry is $- 1$ by $- 1$ ; now $𝐡_{1} = (1, \dots, 1)$ .

Every other column satisfies $0 =$ $𝐡_{𝑘} \cdot$ $𝐡_{1} =$ $\sum_{𝑗} ℎ_{𝑗 𝑘}$ , so it has equally many entries $+ 1$ and $- 1$ ; in particular $𝑛$ is even. Permute the rows so that $𝐡_{2}$ has $+ 1$ in rows $1, \dots, 𝑛 / 2$ and $- 1$ in rows $𝑛 / 2 + 1, \dots, 𝑛$ . Let $𝑎$ and $𝑏$ be the numbers of entries $+ 1$ of $𝐡_{3}$ in the first and in the second half. From $𝐡_{3} \cdot 𝐡_{1} = 0$ , $𝐡_{3}$ has $𝑛 / 2$ entries $+ 1$ in total, so $𝑎 + 𝑏 = 𝑛 / 2$ . From $𝐡_{3} \cdot 𝐡_{2} = 0$ ,

0 = (𝑎 - (\frac{𝑛}{2} - 𝑎)) - (𝑏 - (\frac{𝑛}{2} - 𝑏)) = 2 𝑎 - 2 𝑏 .

So $𝑎 = 𝑏 = 𝑛 / 4$ , and since $𝑎$ is an integer, $4 | 𝑛$ .

(b) Let $𝐾 = (\begin{matrix} 𝐻 & 𝐻 \\ 𝐻 & - 𝐻 \end{matrix})$ . Its entries are $\pm 1$ , and by Theorem 2.4.34,

\begin{aligned} 𝐾^{𝖳} 𝐾 & = (\begin{matrix} 𝐻^{𝖳} & 𝐻^{𝖳} \\ 𝐻^{𝖳} & - 𝐻^{𝖳} \end{matrix}) (\begin{matrix} 𝐻 & 𝐻 \\ 𝐻 & - 𝐻 \end{matrix}) \\ = (\begin{matrix} 2 𝐻^{𝖳} 𝐻 & 0 \\ 0 & 2 𝐻^{𝖳} 𝐻 \end{matrix}) = (\begin{matrix} 2 𝑛 𝐼_{𝑛} & 0 \\ 0 & 2 𝑛 𝐼_{𝑛} \end{matrix}) = 2 𝑛 𝐼_{2 𝑛} . \end{aligned}

So $𝐾$ is a Hadamard matrix of order $2 𝑛$ (Theorem 6.3.29). Starting from the Hadamard matrix $(1)$ of order $1$ and applying this construction $𝑘$ times gives one of order $2^{𝑘}$ . The first step gives $Φ_{2} = (\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix})$ . Whether Hadamard matrices exist for every order divisible by $4$ is a famous open problem.

Exercise 6.3.64.challenge Let $𝑛$ be odd, let $𝜔$ be as in Section 6.3.4, and let $𝑔 = \sum_{𝑗 = 0}^{𝑛 - 1} 𝜔^{𝑗^{2}}$ .

(a)Show that ${| 𝑔 |}^{2} = 𝑛$ .
(b)Compute ${| 𝑔 |}^{2}$ for $𝑛 = 4$ and for $𝑛 = 6$ (with the same definition of $𝑔$ ), and explain where the proof of (a) used that $𝑛$ is odd.

Solution.

Uses. Lemma 6.3.39 (Sums of roots of unity)

Hint 1. Write

{| 𝑔 |}^{2} =

𝑔 𝑔 =

\sum_{𝑗} \sum_{𝑘} 𝜔^{𝑗^{2} - 𝑘^{2}}

. The exponent

𝑗^{2} - 𝑘^{2}

suggests substituting

𝑗 = 𝑘 + 𝑑

Hint 2. Since

𝜔^{𝑛} = 1

𝜔^{𝑗^{2}}

depends only on

𝑗

modulo

𝑛

, so for fixed

𝑘

you may let

𝑑

run over

0, \dots, 𝑛 - 1

with

𝑗 \equiv 𝑘 + 𝑑

. Then

𝑗^{2} - 𝑘^{2} \equiv 𝑑^{2} + 2 𝑑 𝑘

Hint 3. The sum over

𝑘

𝜔^{2 𝑑 𝑘}

is given by Lemma 6.3.39. For which

𝑑

is it nonzero when

𝑛

is odd?

Sketch.

{| 𝑔 |}^{2} =

\sum_{𝑘} \sum_{𝑑} 𝜔^{{(𝑘 + 𝑑)}^{2} - 𝑘^{2}} =

\sum_{𝑑} 𝜔^{𝑑^{2}} \sum_{𝑘} 𝜔^{2 𝑑 𝑘}

. The inner sum is

𝑛

𝑛 | 2 𝑑

and

0

otherwise. For odd

𝑛

𝑛 | 2 𝑑

only for

𝑑 = 0

, so

{| 𝑔 |}^{2} = 𝑛

. For

𝑛 = 4

the values

𝑑 = 0, 2

contribute, giving

8

; for

𝑛 = 6

𝑑 = 0, 3

contribute

6 (1 + 𝜔^{9}) = 0

(a) Since $𝜔^{𝑛} = 1$ , $𝜔^{𝑚}$ depends only on $𝑚$ modulo $𝑛$ ; as ${(𝑗 + 𝑛)}^{2} =$ $𝑗^{2} +$ $𝑛 (2 𝑗 + 𝑛)$ , the term $𝜔^{𝑗^{2}}$ depends only on $𝑗$ modulo $𝑛$ . Since $𝜔^{𝑘^{2}} = 𝜔^{- 𝑘^{2}}$ ,

{| 𝑔 |}^{2} = 𝑔 𝑔 = \sum_{𝑘 = 0}^{𝑛 - 1} \sum_{𝑗 = 0}^{𝑛 - 1} 𝜔^{𝑗^{2} - 𝑘^{2}} .

Fix $𝑘$ . As $𝑑$ runs over $0, \dots, 𝑛 - 1$ , the residue of $𝑘 + 𝑑$ modulo $𝑛$ runs over all residues once, so we may replace $𝑗$ by $𝑘 + 𝑑$ in the inner sum:

\sum_{𝑗 = 0}^{𝑛 - 1} 𝜔^{𝑗^{2} - 𝑘^{2}} = \sum_{𝑑 = 0}^{𝑛 - 1} 𝜔^{{(𝑘 + 𝑑)}^{2} - 𝑘^{2}} = \sum_{𝑑 = 0}^{𝑛 - 1} 𝜔^{𝑑^{2} + 2 𝑑 𝑘} .

Summing over $𝑘$ and exchanging the sums,

{| 𝑔 |}^{2} = \sum_{𝑑 = 0}^{𝑛 - 1} 𝜔^{𝑑^{2}} \sum_{𝑘 = 0}^{𝑛 - 1} 𝜔^{𝑘 (2 𝑑)} .

By Lemma 6.3.39 the inner sum is $𝑛$ if $𝑛 | 2 𝑑$ and $0$ otherwise. Since $𝑛$ is odd, $𝑛 | 2 𝑑$ implies $𝑛 | 𝑑$ , which for $0 \leq 𝑑 \leq 𝑛 - 1$ means $𝑑 = 0$ . So ${| 𝑔 |}^{2} = 𝜔^{0} \cdot 𝑛 = 𝑛$ .

(b) The computation up to the last step did not use that $𝑛$ is odd, so in general ${| 𝑔 |}^{2} = 𝑛 \sum 𝜔^{𝑑^{2}}$ over the $𝑑 \in {0, \dots, 𝑛 - 1}$ with $𝑛 | 2 𝑑$ . For $𝑛 = 4$ (where $𝜔 = 𝑖$ ) these are $𝑑 = 0, 2$ , and ${| 𝑔 |}^{2} = 4 (1 + 𝑖^{4}) = 8$ ; directly, $𝑔 =$ $1 +$ $𝑖 +$ $𝑖^{4} +$ $𝑖^{9} =$ $2 +$ $2 𝑖$ . For $𝑛 = 6$ they are $𝑑 = 0, 3$ , and ${| 𝑔 |}^{2} =$ $6 (1 + 𝜔^{9}) =$ $6 (1 + 𝜔^{3}) =$ $0$ , since $𝜔^{3} = - 1$ for $𝑛 = 6$ . The oddness of $𝑛$ was used only to conclude that $𝑛 | 2 𝑑$ forces $𝑑 = 0$ .

More practice

The practice bank has 39 exercises on this section’s topics.