9.5 Cauchy–Schwarz and the Triangle Inequality

Section 9.4 gave $\mathbb{R}^n$ a length and a distance and proved every basic property of the distance except one: that a detour through a third point is never shorter than the direct route. This section proves it. Everything rests on one inequality between the dot product and the lengths, the Cauchy–Schwarz inequality. The method that proves it is called normalizing: shrink or stretch both vectors to length $1$ , prove the inequality there, and scale back.

9.5.1. Two earlier proofs, and why neither transfers

The triangle inequality has been proved before in this series in two settings, for real numbers and for complex numbers. Each proof used a tool that $\mathbb{R}^n$ lacks.

In $\mathbb{R}$ . Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Section 4.1, trapped each number between $\pm$ its absolute value, $-\left| x \right| \le x \le \left| x \right|$ , and added the two traps. That is how it proved the triangle inequality for absolute values, Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.3 (c)–(e). The trap compares $x$ with the number $\left| x \right|$ . For a vector $x \in \mathbb{R}^n$ with $n \ge 2$ , “ $x \le \left\| x \right\|$ ” compares a vector with a number, and $\mathbb{R}^n$ has been given no order at all.

In $\mathbb{C} = \mathbb{R}^2$ . Section 3.3 expanded $\left| z + w \right|^2$ and met the cross term $2\operatorname{Re}(z\overline{w})$ , which it bounded by $\left| z\overline{w} \right| = \left| z \right|\left| w \right|$ (Theorem 3.3.2). By Proposition 9.4.3, $\operatorname{Re}(z\overline{w}) = \langle z, w \rangle$ and $\left| z \right| = \left\| z \right\|$ , so the key step was $\langle z, w \rangle \le \left\| z \right\| \, \left\| w \right\| ,$ proved with the multiplication of $\mathbb{C}$ : the product $z\overline{w}$ and the rule $\left| z\overline{w} \right| = \left| z \right|\left| w \right|$ . For $n \ge 3$ this book defines no such multiplication on $\mathbb{R}^n$ .

The expansion itself does survive. Section 9.4 compared lengths by comparing their squares (Example (Method: expand the square)). Expanding both squares by Eq. 9.4.1 gives $\left\| x + y \right\|^2 = \left\| x \right\|^2 + 2\langle x, y \rangle + \left\| y \right\|^2 , \qquad \bigl( \left\| x \right\| + \left\| y \right\| \bigr)^2 = \left\| x \right\|^2 + 2\left\| x \right\|\,\left\| y \right\| + \left\| y \right\|^2 .$ Everything matches except the cross terms. So the triangle inequality in $\mathbb{R}^n$ rests on one inequality, $\langle x, y \rangle \le \left\| x \right\|\,\left\| y \right\|$ , and that inequality now needs a proof that uses only the laws of the dot product.

An attempt that stalls. Work coordinatewise: $x_k y_k \le \left| x_k \right|\,\left| y_k \right|$ for each $k$ , and $\left| x_k \right| \le \left\| x \right\|$ , $\left| y_k \right| \le \left\| y \right\|$ by Proposition 9.4.7 (a). Adding the $n$ bounds gives $\langle x, y \rangle \le \sum_{k=1}^{n} \left| x_k \right|\,\left| y_k \right| \le n \, \left\| x \right\| \, \left\| y \right\| ,$ which is off by the factor $n$ . Try $x = y = (1, \dots, 1)$ : then $\langle x, y \rangle = n$ and $\left\| x \right\|\,\left\| y \right\| = n$ , so the inequality we want holds with equality, while the attempt only gives $n \le n^2$ . Each bound $\left| x_k \right| \le \left\| x \right\|$ is sharp only when all of $x$ sits in coordinate $k$ . For $x \ne 0$ and $n \ge 2$ , the $n$ bounds cannot all be sharp at once. A coordinate-by-coordinate bound loses the geometry. The proof below uses the length of a whole vector instead.

9.5.2. The Cauchy–Schwarz inequality

Start with two vectors of $\mathbb{R}^2$ , $x = (3, 4)$ and $y = (4, 3)$ . Their dot product is $\langle x, y \rangle = 12 + 12 = 24$ , and both have length $5$ , so $\left\| x \right\|\,\left\| y \right\| = 25$ . The dot product is a little smaller than the product of the lengths. Now take $y = 2x = (6, 8)$ instead. Then $\langle x, y \rangle = 18 + 32 = 50$ and $\left\| x \right\|\,\left\| y \right\| = 5 \cdot 10 = 50$ : the two are equal. The theorem says that the dot product never exceeds the product of the lengths, and that equality up to sign happens exactly for parallel vectors.

Equality can hold with either sign, and the sign tells which way $y$ points along $x$ .

Theorem 9.5.1 (Cauchy–Schwarz Inequality)

Let $n \ge 1$ and $x, y \in \mathbb{R}^n$ .

(a) $\left| \langle x, y \rangle \right| \le \left\| x \right\|\,\left\| y \right\|$ .
(b) $\left| \langle x, y \rangle \right| = \left\| x \right\|\,\left\| y \right\|$ if and only if $x$ and $y$ are parallel.
(c) $\langle x, y \rangle = \left\| x \right\|\,\left\| y \right\|$ if and only if $x = 0$ or $y = cx$ for some real $c \ge 0$ .

(c′) $\langle x, y \rangle = -\left\| x \right\|\,\left\| y \right\|$ if and only if $x = 0$ or $y = cx$ for some real $c \le 0$ .

Try it first (ten minutes): for unit vectors $u, v$ , expand $\left\| u - v \right\|^2 \ge 0$ . What does it say about $\langle u, v \rangle$ ? What else could you expand?

We know	We want
$x, y \in \mathbb{R}^n$	$\left\| \langle x, y \rangle \right\| \le \left\\| x \right\\|\,\left\\| y \right\\|$
$x, y \ne 0$ (if one is $0$ , both sides are $0$ ); $u \mathrel{:=} x/\left\\| x \right\\|$ , $v \mathrel{:=} y/\left\\| y \right\\|$ are unit vectors	$\left\| \langle u, v \rangle \right\| \le 1$ , because both sides of the old goal are $\left\\| x \right\\|\,\left\\| y \right\\|$ times those of the new one
$\left\\| u - v \right\\|^2 = 2 - 2\langle u, v \rangle \ge 0$	$-1 \le \langle u, v \rangle \le 1$ ; the upper half is done
$\left\\| u + v \right\\|^2 = 2 + 2\langle u, v \rangle \ge 0$	the lower half is done: the gap closes

The passage to unit vectors is allowed because the statement is homogeneous: replacing $x$ by $ax$ with $a > 0$ multiplies both sides by $a$ , and likewise for $y$ . For the equality cases, ask when $\left\| u - v \right\|^2$ or $\left\| u + v \right\|^2$ is $0$ .

Before reading on: where is $x \ne 0$ used, and why are both expansions needed?

Proof. Let $x, y \in \mathbb{R}^n$ .

(a) If $x = 0$ or $y = 0$ , then $\langle x, y \rangle = 0$ , because a dot product with the zero vector is $0$ . Also $\left\| x \right\|\,\left\| y \right\| = 0$ , since $\left\| 0 \right\| = 0$ . So (a) reads $0 \le 0$ .

Let $x \ne 0$ and $y \ne 0$ . Then $\left\| x \right\| > 0$ and $\left\| y \right\| > 0$ , because only the zero vector has length $0$ (Proposition 9.4.1 (a)). So $u \mathrel{:=} (1/\left\| x \right\|)\,x$ and $v \mathrel{:=} (1/\left\| y \right\|)\,y$ are unit vectors, and $x = \left\| x \right\|\,u$ , $y = \left\| y \right\|\,v$ . Pulling the two scalars out of the dot product gives

\langle x, y \rangle = \left\| x \right\|\,\left\| y \right\| \, \langle u, v \rangle .

(9.5.1)

Expanding by Eq. 9.4.1, with $\left\| u \right\|^2 = \left\| v \right\|^2 = 1$ , $\begin{aligned} 0 &\le \left\| u - v \right\|^2 = \left\| u \right\|^2 - 2\langle u, v \rangle + \left\| v \right\|^2 = 2 - 2\langle u, v \rangle , \\ 0 &\le \left\| u + v \right\|^2 = 2 + 2\langle u, v \rangle . \end{aligned}$ Add $2\langle u, v \rangle$ to the first line and $-2$ to the second, and multiply both by $\tfrac12 > 0$ . This gives $-1 \le \langle u, v \rangle \le 1$ , that is, $\left| \langle u, v \rangle \right| \le 1$ . Now multiply by $\left\| x \right\|\,\left\| y \right\| > 0$ . By Eq. 9.5.1 and the rule $\left| ab \right| = \left| a \right|\,\left| b \right|$ , $\left| \langle x, y \rangle \right| = \left\| x \right\|\,\left\| y \right\|\,\left| \langle u, v \rangle \right| \le \left\| x \right\|\,\left\| y \right\| .$

(c) $(\Leftarrow)$ If $x = 0$ , both sides are $0$ . If $y = cx$ with $c \ge 0$ , then $\langle x, y \rangle = c\langle x, x \rangle = c\left\| x \right\|^2$ . Also $\left\| x \right\|\,\left\| cx \right\| = \left| c \right|\,\left\| x \right\|^2 = c\left\| x \right\|^2$ , because $c \ge 0$ .

$(\Rightarrow)$ If $x = 0$ we are done, and if $y = 0$ , then $y = 0x$ with $c = 0$ . Otherwise $x, y \ne 0$ . With $u, v$ as in (a), Eq. 9.5.1 gives $\left\| x \right\|\,\left\| y \right\|\,\langle u, v \rangle = \left\| x \right\|\,\left\| y \right\|$ . Cancelling the non-zero factor $\left\| x \right\|\,\left\| y \right\|$ gives $\langle u, v \rangle = 1$ . Then $\left\| u - v \right\|^2 = 2 - 2 = 0$ , so $\left\| u - v \right\| = 0$ , and $u = v$ because only the zero vector has length $0$ . Hence $y = \left\| y \right\|\,u = c x$ with $c \mathrel{:=} \left\| y \right\|/\left\| x \right\| > 0$ .

(b) Since $\left\| x \right\|\,\left\| y \right\| \ge 0$ , the definition of the absolute value gives $\left| \langle x, y \rangle \right| = \left\| x \right\|\,\left\| y \right\|$ if and only if $\langle x, y \rangle = \pm\left\| x \right\|\,\left\| y \right\|$ . By (c) and (c′) this holds if and only if $x = 0$ or $y = cx$ for some real $c$ . That is exactly the statement that $x$ and $y$ are parallel. Indeed, $0$ is parallel to every vector, and for $x \ne 0$ , $y$ is parallel to $x$ if and only if $y = cx$ for some $c$ . Section 9.2 noted this right after defining parallel vectors (Definition 9.2.3). This proves the theorem.

Uses: Proposition 9.3.1 (a), (b), (e) (symmetry, scalars, zero vector); Proposition 9.4.1 (a)–(c) (length zero, scaling, squares); Definition 9.4.2; Proposition 9.2.1 (e), (f), (i) (scalar rules, signs); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (b), (c), (e) (adding, multiplying, squares); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.3 (b), (d) (products, two-sided bounds); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Definition 4.1.1.

Quick check. For $x = (1, 2, 2)$ and $y = (2, 0, 1)$ , compute both sides of (a). Is the inequality strict, and does (b) predict the answer?

Solution. $\langle x, y \rangle = 2 + 0 + 2 = 4$ , $\left\| x \right\| = 3$ and $\left\| y \right\| = \sqrt 5$ . Since $4^2 = 16 < 45 = (3\sqrt5)^2$ and both numbers are non-negative, $4 < 3\sqrt5$ : strict. Yes: $y = cx$ would need $c = 2$ from the first coordinate and $c = 0$ from the second. And $x = cy$ is impossible since $y_2 = 0 \ne 2 = x_2$ . So $x$ , $y$ are not parallel and (b) forbids equality.

Squaring (a) gives the form used for sums of real numbers. For example, with $(1, 2, 3)$ and $(4, 5, 6)$ the sum of products is $4 + 10 + 18 = 32$ , and the sums of squares are $14$ and $77$ . The squared form reads $32^2 = 1024 \le 14 \cdot 77 = 1078$ .

Corollary 9.5.2 (Cauchy–Schwarz Inequality for Sums)

Let $n \ge 1$ and $x_1, \dots, x_n, y_1, \dots, y_n \in \mathbb{R}$ . Then $\Bigl( \sum_{k=1}^{n} x_k y_k \Bigr)^2 \le \Bigl( \sum_{k=1}^{n} x_k^2 \Bigr) \Bigl( \sum_{k=1}^{n} y_k^2 \Bigr) ,$ with equality if and only if $(x_1, \dots, x_n)$ and $(y_1, \dots, y_n)$ are parallel vectors of $\mathbb{R}^n$ .

Proof. Let $x \mathrel{:=} (x_1, \dots, x_n)$ and $y \mathrel{:=} (y_1, \dots, y_n)$ . The three sums are $\langle x, y \rangle$ , $\left\| x \right\|^2$ and $\left\| y \right\|^2$ . By Theorem 9.5.1 (a), $0 \le \left| \langle x, y \rangle \right| \le \left\| x \right\|\,\left\| y \right\|$ . Squaring keeps an inequality between non-negative numbers, so $\left| \langle x, y \rangle \right|^2 \le \left\| x \right\|^2 \left\| y \right\|^2$ . And $\left| \langle x, y \rangle \right|^2 = \langle x, y \rangle^2$ . Two non-negative reals with equal squares are equal (comparing squares, Section 9.4). So equality holds exactly when $\left| \langle x, y \rangle \right| = \left\| x \right\|\,\left\| y \right\|$ , that is, by Theorem 9.5.1 (b), when $x$ and $y$ are parallel.

Uses: Definition 9.3.1; Proposition 9.4.1 (c) (length squared); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.2 (d) (multiplying inequalities); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.3 (b) ( $\left| t \right|^2 = t^2$ ).

In the example above the inequality is strict, because the two triples are not parallel. Exercise C2 below proves it a second way, from Lagrange’s identity. For $n = 2$ that identity reads $(ac + bd)^2 + (ad - bc)^2 = (a^2 + b^2)(c^2 + d^2)$ . Chapter 3 mentioned this case as a second route in the solution of its chapter check, Exercise C1 of Section 3.3 (Exercise (C1: Exit check: the triangle inequality)).

9.5.3. The method: normalize

The proof of Theorem 9.5.1 did its work for unit vectors and then scaled back. This way of proving is called normalizing.

Example (Method: normalize)

How it goes. Suppose a statement about $x$ and $y$ is homogeneous: replacing $x$ by $ax$ with $a > 0$ multiplies both sides by the same positive factor, and likewise for $y$ . Then:

Settle $x = 0$ and $y = 0$ separately.
For $x, y \ne 0$ , put $u \mathrel{:=} x/\left\| x \right\|$ and $v \mathrel{:=} y/\left\| y \right\|$ , and prove the statement for the unit vectors $u$ , $v$ .
Scale back, multiplying by the positive factor.

When to use it. Inequalities between $\langle x, y \rangle$ and products of lengths; statements about directions rather than sizes.

Example (Two uses of Cauchy–Schwarz)

(a) Show that $(a + b + c)^2 \le 3(a^2 + b^2 + c^2)$ for all real $a, b, c$ , with equality if and only if $a = b = c$ .
(b) Find the largest value of $2x_1 + 3x_2 - x_3$ over all unit vectors $x \in \mathbb{R}^3$ , and every unit vector where it is attained.

Solution.

(a) Apply Corollary 9.5.2 to $(a, b, c)$ and $w \mathrel{:=} (1, 1, 1)$ . The left side is $(a + b + c)^2$ and the right side is $(a^2 + b^2 + c^2) \cdot 3$ . Equality holds if and only if $(a, b, c)$ is parallel to $w$ . Since $w \ne 0$ , this means $(a, b, c) = tw$ for some $t$ , that is, $a = b = c$ .
(b) Let $p \mathrel{:=} (2, 3, -1)$ , so the expression is $\langle p, x \rangle$ and $\left\| p \right\| = \sqrt{14}$ . The statement $\langle p, x \rangle \le \sqrt{14}\,\left\| x \right\|$ is homogeneous in $x$ . So by normalizing it is enough to look at unit $x$ , which is what the question does. For unit $x$ , using $t \le \left| t \right|$ and then Theorem 9.5.1 (a), $\langle p, x \rangle \le \left| \langle p, x \rangle \right| \le \left\| p \right\|\,\left\| x \right\| = \sqrt{14} .$ The value $\sqrt{14}$ is attained at $x_0 \mathrel{:=} p/\sqrt{14}$ , a unit vector, since $\langle p, x_0 \rangle = 14/\sqrt{14} = \sqrt{14}$ (because $\sqrt{14} \cdot \sqrt{14} = 14$ ). Conversely, suppose $\langle p, x \rangle = \sqrt{14} = \left\| p \right\|\,\left\| x \right\|$ . Since $p \ne 0$ , Theorem 9.5.1 (c), with $p$ in the first place, gives $x = cp$ with $c \ge 0$ . Then $1 = \left\| x \right\| = c\sqrt{14}$ , so $c = 1/\sqrt{14}$ and $x = x_0$ . The largest value is $\sqrt{14}$ , attained only at $(2, 3, -1)/\sqrt{14}$ . For $x = 0$ both sides of $\langle p, x \rangle \le \sqrt{14}\,\left\| x \right\|$ are $0$ . Scaling back the other $x$ , $2x_1 + 3x_2 - x_3 \le \sqrt{14}\,\left\| x \right\|$ for every $x \in \mathbb{R}^3$ .

Uses: Definition 9.2.3 and the remark after it (parallel to $w \ne 0$ ); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.3 (c) ( $t \le \left| t \right|$ ).

9.5.4. The triangle inequality

Theorem 9.5.3 (Triangle Inequality for Vectors)

Let $x, y, z \in \mathbb{R}^n$ .

(a) $\left\| x + y \right\| \le \left\| x \right\| + \left\| y \right\|$ , with equality if and only if $x = 0$ or $y = cx$ for some real $c \ge 0$ .
(b) $\bigl| \left\| x \right\| - \left\| y \right\| \bigr| \le \left\| x - y \right\|$ .
(c) $d(x, z) \le d(x, y) + d(y, z)$ .

Idea. As in Example (Method: expand the square): compare squares, expand, and bound the cross term $2\langle x, y \rangle$ by $2\left\| x \right\|\,\left\| y \right\|$ , now with Cauchy–Schwarz. Parts (b) and (c) are (a) applied to well-chosen vectors.

Before reading on: which equality case of Theorem 9.5.1 does the equality case of (a) use, and why not (b)?

Proof.

(a) Expand the square, then use $\langle x, y \rangle \le \left| \langle x, y \rangle \right|$ and Theorem 9.5.1 (a), adding the inequalities: $\begin{aligned} \left\| x + y \right\|^2 &= \left\| x \right\|^2 + 2\langle x, y \rangle + \left\| y \right\|^2 \\ &\le \left\| x \right\|^2 + 2\left| \langle x, y \rangle \right| + \left\| y \right\|^2 \\ &\le \left\| x \right\|^2 + 2\left\| x \right\|\,\left\| y \right\| + \left\| y \right\|^2 = \bigl( \left\| x \right\| + \left\| y \right\| \bigr)^2 . \end{aligned}$ Both $\left\| x + y \right\|$ and $\left\| x \right\| + \left\| y \right\|$ are non-negative, so comparing squares (Section 9.4) gives $\left\| x + y \right\| \le \left\| x \right\| + \left\| y \right\|$ . For the same reason the two lengths are equal if and only if their squares are. Comparing the first and last expressions of the display, this means $2\langle x, y \rangle = 2\left\| x \right\|\,\left\| y \right\|$ . By Theorem 9.5.1 (c), this holds if and only if $x = 0$ or $y = cx$ with $c \ge 0$ .
(b) The argument is the one Section 3.3 used for complex numbers (Corollary 3.3.3 (a)), with $\left\| \cdot \right\|$ in place of $\left| \cdot \right|$ . Apply (a) to $x = (x - y) + y$ . This gives $\left\| x \right\| - \left\| y \right\| \le \left\| x - y \right\|$ . Exchanging $x$ and $y$ gives $\left\| y \right\| - \left\| x \right\| \le \left\| y - x \right\|$ . Also $\left\| y - x \right\| = \left\| x - y \right\|$ , since $y - x = (-1)(x - y)$ . The two bounds together say $-\left\| x - y \right\| \le \left\| x \right\| - \left\| y \right\| \le \left\| x - y \right\|$ , which is (b).
(c) By Proposition 9.2.1, $x - z = (x - y) + (y - z)$ . So by (a) and the definition of distance, $d(x, z) = \left\| (x - y) + (y - z) \right\| \le \left\| x - y \right\| + \left\| y - z \right\| = d(x, y) + d(y, z) .$ This proves the theorem.

Uses: Eq. 9.4.1; Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.3 (c), (d) ( $t \le \left| t \right|$ , two-sided bounds); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (b) (adding inequalities); Proposition 9.4.1 (b) with $c = -1$ ; Definition 9.4.3.

For $n = 2$ , (a) is the triangle inequality of Section 3.3 (Theorem 3.3.2), now proved by a route with no complex multiplication. The translation between the two is Proposition 9.4.3 (c). Chapter 3 found its equality case in a different form: $z\overline{w}$ is a non-negative real (Exercise (B1: The equality case)). Section 9.6 returns to the comparison in a review exercise.

Solution. $\langle x, y \rangle = -2 \cdot 14 = -28$ and $\left\| x \right\|\,\left\| y \right\| = \sqrt{14} \cdot 2\sqrt{14} = 28$ : yes, as (b) of Theorem 9.5.1 predicts for parallel vectors. But $x + y = -x$ , so $\left\| x + y \right\| = \sqrt{14}$ , while $\left\| x \right\| + \left\| y \right\| = 3\sqrt{14}$ : no, since $y = cx$ with $c = -2 < 0$ .

9.5.5. Sums of many vectors

Adding one vector at a time extends (a) to any finite number of terms. For instance, in $\mathbb{R}^3$ , $e_1 + e_2 + e_3 = (1, 1, 1)$ has length $\sqrt 3$ , while the three lengths add up to $3$ , and $\sqrt 3 \le 3$ because $3 \le 9$ .

Corollary 9.5.4 (Triangle Inequality for Finite Sums)

For every $m \in \mathbb{N}$ and all $v_1, \dots, v_m \in \mathbb{R}^n$ , $\Bigl\| \sum_{j=1}^{m} v_j \Bigr\| \le \sum_{j=1}^{m} \left\| v_j \right\| .$

Proof. We use induction on $m \ge 0$ . The sums are defined by recursion, as in Lemma 9.2.2. For $m = 0$ both sides are $0$ . Suppose the inequality holds for $m$ . Split off the last term by the recursion, apply Theorem 9.5.3 (a), and then add $\left\| v_{m+1} \right\|$ to both sides of the inequality for $m$ : $\Bigl\| \sum_{j=1}^{m+1} v_j \Bigr\| \le \Bigl\| \sum_{j=1}^{m} v_j \Bigr\| + \left\| v_{m+1} \right\| \le \sum_{j=1}^{m+1} \left\| v_j \right\| .$

Uses: Sets and Functions, Theorem 3.2.1; Proposition 9.4.1 (a) ( $\left\| 0 \right\| = 0$ ); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (b) (adding inequalities).

Length and the sum of the absolute values of the coordinates are comparable, with constants $1$ and $\sqrt n$ . For $x = (3, 4)$ , the length is $5$ and the sum is $7$ . Indeed $5 \le 7$ , and $7 \le \sqrt 2 \cdot 5$ because $49 \le 50$ .

Corollary 9.5.5 (Length against the Sum of the Coordinates)

For every $x \in \mathbb{R}^n$ , $\left\| x \right\| \le \sum_{k=1}^{n} \left| x_k \right| \le \sqrt{n}\,\left\| x \right\| .$

Proof. By Proposition 9.2.3, $x = \sum_k x_k e_k$ . So Corollary 9.5.4 gives $\left\| x \right\| \le \sum_k \left\| x_k e_k \right\| = \sum_k \left| x_k \right|$ , since $\left\| x_k e_k \right\| = \left| x_k \right|$ . For the second inequality let $a \mathrel{:=} (\left| x_1 \right|, \dots, \left| x_n \right|)$ and $w \mathrel{:=} (1, \dots, 1)$ . Then $\langle a, w \rangle = \sum_k \left| x_k \right|$ and $\left\| w \right\| = \sqrt n$ . Also $\left\| a \right\| = \left\| x \right\|$ : both are non-negative with the same square $\sum_k x_k^2$ , and a non-negative square root is unique (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 6.1.4). Using $t \le \left| t \right|$ and then Theorem 9.5.1 (a), $\sum_k \left| x_k \right| \le \left| \langle a, w \rangle \right| \le \left\| a \right\|\,\left\| w \right\| = \sqrt n \, \left\| x \right\| .$

Uses: Proposition 9.4.1 (b), (e) ( $\left\| x_k e_k \right\| = \left| x_k \right|$ ); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.3 (b), (c) ( $\left| t \right|^2 = t^2$ , $t \le \left| t \right|$ ).

For $n = 2$ the first inequality is the last one of Lemma 3.3.1. Both are sharp: $x = e_1$ gives equality on the left, and $x = (1, \dots, 1)$ on the right.

9.5.6. Exercises

A. Check your understanding

Exercise (A1)

These questions are about the proof of Theorem 9.5.1.

(a) Where is $x \ne 0$ used?
(b) Which expansion gives which half of $-1 \le \langle u, v \rangle \le 1$ ?
(c) Run the proof on $x = (3, 4)$ , $y = (4, 3)$ : compute $u$ , $v$ , $\langle u, v \rangle$ and $\left\| u - v \right\|^2$ .
(d) In the scratch work, what goes wrong with the expansion of $\left\| u - v \right\|^2$ if $u$ is not a unit vector?
(e) Give the idea of the proof in two sentences.

Solution.

(a) To form $u = x/\left\| x \right\|$ , which needs $\left\| x \right\| \ne 0$ , that is, $x \ne 0$ (Proposition 9.4.1 (a)). The zero case is settled separately.
(b) $\left\| u - v \right\|^2 = 2 - 2\langle u, v \rangle \ge 0$ gives $\langle u, v \rangle \le 1$ ; $\left\| u + v \right\|^2 = 2 + 2\langle u, v \rangle \ge 0$ gives $\langle u, v \rangle \ge -1$ .
(c) $\left\| x \right\| = \left\| y \right\| = 5$ , $u = (\tfrac35, \tfrac45)$ , $v = (\tfrac45, \tfrac35)$ , $\langle u, v \rangle = \tfrac{24}{25}$ , and $\left\| u - v \right\|^2 = \tfrac1{25} + \tfrac1{25} = \tfrac{2}{25} = 2 - \tfrac{48}{25}$ . Scaling back, $\langle x, y \rangle = 25 \cdot \tfrac{24}{25} = 24 \le 25$ .
(d) The expansion becomes $\left\| u - v \right\|^2 = \left\| u \right\|^2 - 2\langle u, v \rangle + \left\| v \right\|^2$ , not $2 - 2\langle u, v \rangle$ . It only gives $\langle u, v \rangle \le \tfrac12(\left\| u \right\|^2 + \left\| v \right\|^2)$ , which exceeds $\left\| u \right\|\,\left\| v \right\|$ unless $\left\| u \right\| = \left\| v \right\|$ , since $\tfrac12(a^2 + b^2) - ab = \tfrac12(a - b)^2 > 0$ for real $a \ne b$ .
(e) The inequality is homogeneous, so after disposing of zero vectors it is enough to prove $\left| \langle u, v \rangle \right| \le 1$ for unit vectors. That follows from $\left\| u \mp v \right\|^2 = 2 \mp 2\langle u, v \rangle \ge 0$ .

B. Practice

Exercise (B1: Proof ordering)

The eight lines below are shuffled. Six of them, in a suitable order, prove Theorem 9.5.3 (b) from (a); the other two belong in no proof. Write an admissible order without rereading the proof above, and say why each of the two other lines fails.

(i) So $\left\| x \right\| - \left\| y \right\| \le \left\| x - y \right\|$ .
(ii) $\left\| -y \right\| = -\left\| y \right\|$ .
(iii) So $-\left\| x - y \right\| \le \left\| x \right\| - \left\| y \right\| \le \left\| x - y \right\|$ , and Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.3 (d) gives $\bigl| \left\| x \right\| - \left\| y \right\| \bigr| \le \left\| x - y \right\|$ .
(iv) $x = (x - y) + y$ .
(v) $\left\| y - x \right\| = \left\| x - y \right\|$ , by Proposition 9.4.1 (b) with $c = -1$ .
(vi) The same with $x$ and $y$ exchanged: $\left\| y \right\| - \left\| x \right\| \le \left\| y - x \right\|$ .
(vii) $\left\| x - y \right\| \le \left\| x \right\| - \left\| y \right\|$ , by (a) applied to $x$ and $-y$ .
(viii) So $\left\| x \right\| \le \left\| x - y \right\| + \left\| y \right\|$ , by (a).

Solution. An admissible order is (iv), (viii), (i), (vi), (v), (iii). Line (iv) must precede (viii), and (viii) must precede (i). Line (i) must precede (vi), which repeats (iv), (viii), (i) with the letters exchanged. Line (v) may stand anywhere before (iii). Line (iii) comes last, since it uses (i), (vi) and (v).

Exercise (B2)

Solution. The method is to expand the square (Example (Method: expand the square)). Both lengths are non-negative, so they are equal if and only if their squares are (comparing squares, Section 9.4). Subtracting the two expansions gives $\left\| x + y \right\|^2 - \left\| x - y \right\|^2 = 4\langle x, y \rangle$ , which is Proposition 9.4.6 (a) multiplied by $4$ . This is $0$ if and only if $\langle x, y \rangle = 0$ . Indeed, if $4\langle x, y \rangle = 0$ , then $4 = 0$ or $\langle x, y \rangle = 0$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Lemma 4.1.1 (d)), and $4 \ne 0$ since $4 > 0$ in the ordered field $\mathbb{R}$ . By the definition of orthogonal vectors, $\langle x, y \rangle = 0$ holds if and only if $x \perp y$ .

Uses: Proposition 9.4.6 (a); Definition 9.3.2.

Exercise (B3: Prove or disprove)

For each statement about all $x, y \in \mathbb{R}^n$ (or all unit vectors $u, v$ ), prove it or give a counterexample.

(a) $\langle x, y \rangle \le \tfrac12 \bigl( \left\| x \right\|^2 + \left\| y \right\|^2 \bigr)$ .
(b) $\left\| x + y \right\| \ge \left\| x \right\|$ .
(c) Unit vectors $u, v$ with $\langle u, v \rangle = 1$ are equal.
(d) Equality $\left| \langle x, y \rangle \right| = \left\| x \right\|\,\left\| y \right\|$ holds only when $x = y$ .
(e) $\langle x, y \rangle \le \tfrac12 \left\| x \right\|\,\left\| y \right\|$ .

Solution.

(a) True. $0 \le \left\| x - y \right\|^2 = \left\| x \right\|^2 - 2\langle x, y \rangle + \left\| y \right\|^2$ ; add $2\langle x, y \rangle$ and halve.
(b) False. For $x = e_1$ , $y = -e_1$ : $\left\| x + y \right\| = 0 < 1 = \left\| x \right\|$ .
(c) True. $\left\| u - v \right\|^2 = 2 - 2 \cdot 1 = 0$ , so $u - v = 0$ by Proposition 9.4.1 (a).
(d) False. For $x = e_1$ , $y = 2e_1$ : $\left| \langle x, y \rangle \right| = 2 = 1 \cdot 2$ , and $x \ne y$ .
(e) False. For $x = y = e_1$ it reads $1 \le \tfrac12$ . The statement is homogeneous, so normalizing is legitimate here: it reduces the claim to “ $\langle u, v \rangle \le \tfrac12$ for unit $u, v$ ”, which fails at $u = v$ .

Exercise (B4)

(a) Prove that $\bigl( \sum_{k=1}^{n} x_k \bigr)^2 \le n \sum_{k=1}^{n} x_k^2$ for real $x_1, \dots, x_n$ , with equality if and only if all $x_k$ are equal.
(b) Find the smallest value of $\left\| x \right\|^2$ over all $x \in \mathbb{R}^3$ with $x_1 + 2x_2 + 2x_3 = 9$ , and every $x$ where it is attained.

Solution.

(a) Apply Corollary 9.5.2 to $x$ and $w \mathrel{:=} (1, \dots, 1)$ , with $\sum_k 1^2 = n$ . Equality holds if and only if $x$ is parallel to $w \ne 0$ , that is, $x = tw$ for some $t$ : all $x_k$ are equal.
(b) Let $p \mathrel{:=} (1, 2, 2)$ , so $\left\| p \right\| = 3$ and the condition is $\langle p, x \rangle = 9$ . By Theorem 9.5.1 (a), $9 = \langle p, x \rangle \le \left| \langle p, x \rangle \right| \le \left\| p \right\|\,\left\| x \right\| = 3\left\| x \right\|$ . So $\left\| x \right\| \ge 3$ , and squaring gives $\left\| x \right\|^2 \ge 9$ . If $\left\| x \right\|^2 = 9$ , then $\left\| x \right\| = 3$ and $\langle p, x \rangle = 9 = \left\| p \right\|\,\left\| x \right\|$ . Since $p \ne 0$ , Theorem 9.5.1 (c) gives $x = cp$ with $c \ge 0$ , and the condition gives $9c = 9$ , so $x = (1, 2, 2)$ . This point satisfies the condition, $1 + 4 + 4 = 9$ , and $\left\| (1, 2, 2) \right\|^2 = 9$ . The smallest value is $9$ , attained only at $(1, 2, 2)$ .

Uses: Definition 9.2.3 and the remark after it (parallel to $w \ne 0$ ); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.3 (c) ( $t \le \left| t \right|$ ); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.2 (d) (squaring keeps $\le$ ).

C. Going deeper

Exercise (C1: Chapter check: Cauchy–Schwarz)

Use only the definitions of the dot product and the length and the results of Sections 9.2–9.4. Prove that for all $x, y \in \mathbb{R}^n$ : (a) $\left| \langle x, y \rangle \right| \le \left\| x \right\|\,\left\| y \right\|$ ; (b) equality holds if and only if $x$ and $y$ are parallel.

Solution (Hint 1). Dispose of the zero cases, then scale both vectors to length $1$ .

Solution (Hint 2). For unit $u, v$ , expand $\left\| u - v \right\|^2$ and $\left\| u + v \right\|^2$ .

Solution.

(a) If $x = 0$ or $y = 0$ , both sides are $0$ . Otherwise $\left\| x \right\|, \left\| y \right\| > 0$ . Let $u \mathrel{:=} x/\left\| x \right\|$ and $v \mathrel{:=} y/\left\| y \right\|$ : these are unit vectors with $\langle x, y \rangle = \left\| x \right\|\,\left\| y \right\|\,\langle u, v \rangle$ . From $0 \le \left\| u \mp v \right\|^2 = 2 \mp 2\langle u, v \rangle$ we get $-1 \le \langle u, v \rangle \le 1$ , so $\left| \langle u, v \rangle \right| \le 1$ . Multiplying by $\left\| x \right\|\,\left\| y \right\| > 0$ gives (a).
(b) If $x = 0$ or $y = 0$ , the two vectors are parallel and both sides of (a) are $0$ . Let $x, y \ne 0$ . If equality holds, then $\langle u, v \rangle = \pm 1$ , so $\left\| u \mp v \right\|^2 = 0$ . Hence $v = \pm u$ and $y = \pm(\left\| y \right\|/\left\| x \right\|)\,x$ : parallel. Conversely, if they are parallel, then $y = cx$ for some $c$ (remark after Definition 9.2.3), and $\left| \langle x, cx \rangle \right| = \left| c \right|\,\left\| x \right\|^2 = \left\| x \right\|\,\left\| cx \right\|$ .

What a complete answer needs. (10 points) - 1: settles $x = 0$ or $y = 0$ . - 2: reduces the general case to one it can bound, saying why the reduction is legitimate; for unit vectors: the statement is homogeneous and the factor $\left\| x \right\|\,\left\| y \right\|$ is positive. - 3: proves $\left| \langle u, v \rangle \right| \le 1$ for unit vectors, by any correct route. - 1: scales back to (a). - 3: proves the equality case in both directions, zero vectors included.

A proof through Lagrange’s identity (C2) scores on the same points. It gets 1 for the zero cases, which are automatic there. It gets 2 + 3 + 1 for proving the identity, reading off $\langle x, y \rangle^2 \le \left\| x \right\|^2\left\| y \right\|^2$ and taking roots. It gets 3 for “all $x_j y_k - x_k y_j = 0$ if and only if parallel”.

A proof that normalizes nothing, expanding $\left\| x - t_0 y \right\|^2 \ge 0$ with $t_0 \mathrel{:=} \langle x, y \rangle/\left\| y \right\|^2$ , also scores on the same points. It gets 1 for $y = 0$ , 2 for setting up $t_0$ using $y \ne 0$ , 3 for the inequality on squares, 1 for taking roots, and 3 for the equality case through $\left\| x - t_0 y \right\| = 0$ .

Exercise (C2: Lagrange’s identity)

Let $x, y \in \mathbb{R}^n$ . Prove that $\Bigl( \sum_{k=1}^{n} x_k^2 \Bigr) \Bigl( \sum_{k=1}^{n} y_k^2 \Bigr) - \Bigl( \sum_{k=1}^{n} x_k y_k \Bigr)^2 = \frac12 \sum_{j=1}^{n} \sum_{k=1}^{n} (x_j y_k - x_k y_j)^2 ,$ and deduce Corollary 9.5.2 with its equality case: equality holds if and only if $x_j y_k = x_k y_j$ for all $j, k$ , if and only if $x$ and $y$ are parallel.

Solution (Hint 1). Expand the square inside the double sum and use the product form of Proposition 1.1.6 three times.

Solution (Hint 2). For “parallel”: if $x = 0$ it is clear; otherwise pick $m$ with $x_m \ne 0$ and set $c \mathrel{:=} y_m / x_m$ .

Solution. Write $A \mathrel{:=} \sum_k x_k^2$ , $B \mathrel{:=} \sum_k y_k^2$ , $C \mathrel{:=} \sum_k x_k y_k$ . Expanding each term, $(x_j y_k - x_k y_j)^2 = x_j^2 y_k^2 - 2 (x_j y_j)(x_k y_k) + x_k^2 y_j^2 .$ Sum over $j$ and $k$ , splitting termwise (Lemma 1.1.3 (a), (b)). By the product form of Proposition 1.1.6, $\sum_j \sum_k x_j^2 y_k^2 = AB$ , $\sum_j \sum_k x_k^2 y_j^2 = BA$ and $\sum_j \sum_k (x_j y_j)(x_k y_k) = C^2$ . The double sum is $2AB - 2C^2$ , and halving proves the identity.

Each term $(x_j y_k - x_k y_j)^2$ is a square, so it is $\ge 0$ . So each inner sum is $\ge 0$ , and then so is the double sum (Proposition 1.1.5 (b)). Hence $C^2 \le AB$ , which is Corollary 9.5.2. Equality holds if and only if the double sum is $0$ . Apply Proposition 1.1.5 (e) to the outer sum and then to each inner sum. So equality holds if and only if every term is $0$ , that is, $x_j y_k = x_k y_j$ for all $j, k$ .

It remains to match this with “parallel”. If $y = cx$ , each $x_j y_k - x_k y_j = c(x_j x_k - x_k x_j) = 0$ ; if $x = cy$ , likewise $c(y_j y_k - y_k y_j) = 0$ . Conversely, suppose all $x_j y_k = x_k y_j$ . If $x = 0$ , $x$ is parallel to $y$ . Otherwise choose $m$ with $x_m \ne 0$ and let $c \mathrel{:=} y_m / x_m$ . For every $k$ , $x_m y_k = x_k y_m$ gives $y_k = c x_k$ , so $y = cx$ .

For $n = 2$ the terms with $j = k$ vanish and the other two are both $(x_1 y_2 - x_2 y_1)^2$ , so the identity is $AB - C^2 = (x_1 y_2 - x_2 y_1)^2$ .

Uses: Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (e) (squares are non-negative).