16.1 Norms

Chapter 11 measured vectors, and measured them in exactly one way: $\left\| \mathbf{v} \right\| = \sqrt{\langle \mathbf{v}, \mathbf{v} \rangle}$ . Every length in Chapters 11 to 13 came out of that formula. This section keeps the measuring and throws the inner product away. The reason is not economy. The quantities this part of the book owes — how fast a sequence of matrices settles down, how far a solution moves when the data moves — are often measured most naturally by a size that no inner product produces, and the arguments that use them turn out to need only three properties of a length.

The field here is $\mathbb{R}$ or $\mathbb{C}$ , as it is throughout the chapter. A length is a real number, and the scaling rule below multiplies it by $\lvert c \rvert$ ; so the scalars must carry an absolute value, and these are the only fields in this book that do.

16.1.1. What measurement actually needs

Look back at how $\left\| \cdot \right\|$ was used after Chapter 11 defined it. Cauchy–Schwarz needed the inner product. So did Pythagoras, orthogonality and the adjoint. But a long list of arguments did not: that a convergent sequence is bounded, that $\left\| \mathbf{A}\mathbf{x} \right\|$ is small when $\mathbf{x}$ is small, that a limit of unit vectors is a unit vector, that $\left\| \mathbf{u} - \mathbf{w} \right\| \le \left\| \mathbf{u} - \mathbf{v} \right\| + \left\| \mathbf{v} - \mathbf{w} \right\|$ . Every one of those used only that $\left\| \mathbf{v} \right\|$ vanishes just for $\mathbf{v} = \mathbf{0}$ , that $\left\| c\mathbf{v} \right\| = \lvert c \rvert\left\| \mathbf{v} \right\|$ , and the triangle inequality of Corollary 11.1.6. Three properties, used over and over. Following the book’s habit, we give the three of them a name and see what else satisfies them.

A norm is a length: zero only at the zero vector, scaling with the scalar, and never rewarding a detour.

Definition 16.1.1 (Norm)

Let $F$ be $\mathbb{R}$ or $\mathbb{C}$ and let $V$ be a vector space over $F$ . A norm on $V$ is a function $\left\| \cdot \right\| \colon V \to \mathbb{R}$ such that for all $\mathbf{u}, \mathbf{v} \in V$ and all $c \in F$ :

(N1) $\left\| \mathbf{v} \right\| \ge 0$ , and $\left\| \mathbf{v} \right\| = 0$ only for $\mathbf{v} = \mathbf{0}$ (positive definiteness);
(N2) $\left\| c\mathbf{v} \right\| = \lvert c \rvert\,\left\| \mathbf{v} \right\|$ (absolute homogeneity);
(N3) $\left\| \mathbf{u} + \mathbf{v} \right\| \le \left\| \mathbf{u} \right\| + \left\| \mathbf{v} \right\|$ (the triangle inequality).

A vector space carrying a norm is a normed space. A vector with $\left\| \mathbf{v} \right\| = 1$ is a unit vector, and replacing a non-zero $\mathbf{v}$ by $\mathbf{v}/\left\| \mathbf{v} \right\|$ is normalizing it.

In words, clause by clause. (N1) says the output is a genuine non-negative size, and that only the zero vector has size zero; the word only is the whole content, since the reverse implication is free (take $c = 0$ in (N2) to get $\left\| \mathbf{0} \right\| = 0\cdot\left\| \mathbf{0} \right\| = 0$ ). (N2) says that stretching a vector by $c$ stretches its length by $\lvert c \rvert$ — the absolute value of $c$ , so that $\left\| -\mathbf{v} \right\| = \left\| \mathbf{v} \right\|$ and, over $\mathbb{C}$ , $\left\| i\mathbf{v} \right\| = \left\| \mathbf{v} \right\|$ . (N3) says that going from $\mathbf{0}$ to $\mathbf{u} + \mathbf{v}$ directly is at most as long as going by way of $\mathbf{u}$ . Note what the definition does not mention: no second vector is paired with the first, no angle appears, and there is no inner product anywhere.

Two remarks on the shape of the definition. First, the codomain is $\mathbb{R}$ even when $F = \mathbb{C}$ : a length is never complex. Second, the three clauses are not independent of the arithmetic of $\mathbb{R}$ — (N3) is an inequality, and inequalities are why the field had to be restricted.

Example (The

1

2

- and

\infty

-norms on

F^n

)

For $\mathbf{x} = (x_1, \dots, x_n) \in F^n$ put $\begin{aligned} \left\| \mathbf{x} \right\|_1 &= \lvert x_1\rvert + \dots + \lvert x_n\rvert , \\ \left\| \mathbf{x} \right\|_2 &= \bigl(\lvert x_1\rvert^2 + \dots + \lvert x_n\rvert^2\bigr)^{1/2} , \\ \left\| \mathbf{x} \right\|_\infty &= \max\{\lvert x_1\rvert, \dots, \lvert x_n\rvert\} . \end{aligned}$ Check each of them against Definition 16.1.1.

Solution. (N1) holds for all three: each is a sum, a square root of a sum, or a maximum of the non-negative numbers $\lvert x_i\rvert$ , so each is $\ge 0$ ; and each vanishes only when every $\lvert x_i \rvert = 0$ , that is, only for $\mathbf{x} = \mathbf{0}$ . (N2) holds because $\lvert cx_i\rvert = \lvert c\rvert\lvert x_i\rvert$ for every $i$ , and the common factor $\lvert c \rvert$ comes out of a sum, out of a square root of a sum of squares, and out of a maximum of non-negative numbers alike.

For (N3), the $1$ -norm inherits it one coordinate at a time: $\lvert x_i + y_i\rvert \le \lvert x_i\rvert + \lvert y_i\rvert$ for each $i$ by the triangle inequality for the modulus (Theorem 0.6.4, which covers $F = \mathbb{R}$ as well), and summing over $i$ gives $\left\| \mathbf{x} + \mathbf{y} \right\|_1 \le \left\| \mathbf{x} \right\|_1 + \left\| \mathbf{y} \right\|_1$ . The $\infty$ -norm inherits it too, but from one coordinate rather than all: for each $i$ , $\lvert x_i + y_i\rvert \le \lvert x_i\rvert + \lvert y_i\rvert \le \left\| \mathbf{x} \right\|_\infty + \left\| \mathbf{y} \right\|_\infty ,$ and a bound valid for every $i$ bounds the maximum. The $2$ -norm is the norm induced by the standard inner product on $F^n$ (Definition 11.1.3), so its triangle inequality is Corollary 11.1.6 and needs no fresh argument.

So one space carries at least three different norms. For $\mathbf{x} = (3, -4, 12) \in \mathbb{R}^3$ they give $\left\| \mathbf{x} \right\|_1 = 19$ , $\left\| \mathbf{x} \right\|_2 = 13$ and $\left\| \mathbf{x} \right\|_\infty = 12$ — three honest answers to “how big is $\mathbf{x}$ ”, and no reason yet to prefer one.

Remark. There is a $p$ -norm $\left\| \mathbf{x} \right\|_p = \bigl(\sum_i\lvert x_i\rvert^{p}\bigr)^{1/p}$ for every real $p \ge 1$ , and $\left\| \mathbf{x} \right\|_\infty$ is its limit as $p \to \infty$ . Its triangle inequality is Minkowski’s inequality, which Chapter 18 proves from Hölder’s inequality (and which is the first place real powers $t^{p}$ and the logarithm are set up properly). This chapter uses only $p = 1, 2, \infty$ , and each of those was verified above from scratch.

Example (Inner products, weights, and a function space)

Three further families.

(a) Every inner product gives a norm. If $V$ is an inner product space, then $\left\| \mathbf{v} \right\| = \sqrt{\langle \mathbf{v}, \mathbf{v} \rangle}$ satisfies (N1) and (N2) by Theorem 11.1.2 (a), (b) and (N3) by Corollary 11.1.6. In particular the Frobenius norm $\left\| \mathbf{A} \right\|_F$ on $M_{m\times n}(F)$ and the norm $\bigl(\int_0^1\lvert f\rvert^2\bigr)^{1/2}$ on $C[0,1]$ are norms.
(b) Weighted norms. Fix real weights $w_1, \dots, w_n > 0$ and put $\left\| \mathbf{x} \right\|_{w} = \max_i w_i\lvert x_i\rvert$ . All three clauses go through exactly as for $\left\| \cdot \right\|_\infty$ , the weights riding along untouched; positivity of every $w_i$ is what (N1) needs.
(c) The sup norm. On $C[0,1]$ , the real continuous functions on $[0,1]$ , put $\left\| f \right\|_\infty = \max_{t\in[0,1]}\lvert f(t)\rvert$ .

For (c) the maximum has to exist before the formula defines anything, and that is the first place this chapter borrows: $[0,1]$ is compact and $\lvert f\rvert$ is continuous, so by the extreme value theorem, fact (A4) of the chapter introduction, the maximum is attained. Granting that, (N1) says a continuous function with $\max\lvert f\rvert = 0$ is the zero function, which is true pointwise; (N2) and (N3) follow from the corresponding facts about $\lvert\cdot\rvert$ at each point, exactly as for $\left\| \cdot \right\|_\infty$ on $F^n$ . Note that $C[0,1]$ is infinite-dimensional — it contains all the polynomials — and it is kept in view deliberately, because §02’s main theorem will fail on it.

A degenerate case is worth one line. On $V = F$ itself, $\left\| c \right\| = \lvert c\rvert$ is a norm, and (N2) forces every norm on $F$ to be $\left\| c \right\| = \lvert c\rvert\left\| 1 \right\|$ , a positive multiple of that one. On the zero space $V = \{\mathbf{0}\}$ the only function to $\mathbb{R}$ is $\left\| \mathbf{0} \right\| = 0$ , and it is a norm. Both matter: they say that the theory is not empty at the bottom, and the first of them is the model for the general statement that any two norms differ by bounded factors.

Example (Three near misses)

Change one feature of an example above and watch a single clause break.

(a) Drop the square root. On $F^n$ put $N(\mathbf{x}) = \lvert x_1\rvert^2 + \dots + \lvert x_n\rvert^2$ . Then (N1) still holds. But $N(c\mathbf{x}) = \lvert c\rvert^2 N(\mathbf{x})$ , so (N2) fails as soon as $\lvert c \rvert \ne 0, 1$ : for $\mathbf{x} = \mathbf{e}_1$ and $c = 2$ it gives $N(2\mathbf{e}_1) = 4 \ne 2 = \lvert 2\rvert N(\mathbf{e}_1)$ . The square root in $\left\| \cdot \right\|_2$ is there for exactly this reason.
(b) Forget a coordinate. On $F^2$ put $N(\mathbf{x}) = \lvert x_1\rvert$ . Then (N2) and (N3) both hold, inherited from $\lvert\cdot\rvert$ on $F$ . What fails is the word only in (N1): $N(\mathbf{e}_2) = 0$ while $\mathbf{e}_2 \ne \mathbf{0}$ . A function satisfying (N1) with “only” deleted, together with (N2) and (N3), is called a seminorm; it measures a quotient of $V$ rather than $V$ .
(c) Bend the exponent the other way. On $\mathbb{R}^2$ put $N(\mathbf{x}) = \bigl(\lvert x_1\rvert^{1/2} + \lvert x_2\rvert^{1/2}\bigr)^2$ . Then (N1) holds, and (N2) holds because $\lvert c\rvert^{1/2}$ factors out of the inner sum and is squared back to $\lvert c\rvert$ . Only (N3) fails: $N(\mathbf{e}_1) = N(\mathbf{e}_2) = 1$ but $N(\mathbf{e}_1 + \mathbf{e}_2) = (1 + 1)^2 = 4 > 2$ .

Item (c) is the one to remember, because it shows the three clauses are genuinely independent: two of them can hold exactly while the third fails, and it is the failing one that carries all the geometry.

Warning. A norm is not determined by what it does to the standard basis. Both $\left\| \cdot \right\|_1$ and $\left\| \cdot \right\|_\infty$ give every $\mathbf{e}_i$ length $1$ , and so does $\left\| \cdot \right\|_2$ , yet the three disagree everywhere else: on $\mathbf{1} = (1, \dots, 1)$ they return $n$ , $1$ and $\sqrt n$ . Knowing the lengths of a basis pins down nothing, and this is worth holding on to, because §02’s theorem is sometimes misremembered as saying that norms which agree on a basis agree everywhere. It says no such thing.

One small consequence of (N3) will be used twice below and again in §02, so it gets a name here. It is Exercise (B4: A lower bound for a difference of norms) with the inner product removed from the proof.

Lemma 16.1.1 (Reverse Triangle Inequality)

Let $\left\| \cdot \right\|$ be a norm on $V$ . Then for all $\mathbf{u}, \mathbf{v} \in V$ , $\bigl\lvert\, \left\| \mathbf{u} \right\| - \left\| \mathbf{v} \right\| \,\bigr\rvert \le \left\| \mathbf{u} - \mathbf{v} \right\| .$

Proof. By (N3) applied to $\mathbf{u} = (\mathbf{u} - \mathbf{v}) + \mathbf{v}$ , we have $\left\| \mathbf{u} \right\| \le \left\| \mathbf{u} - \mathbf{v} \right\| + \left\| \mathbf{v} \right\|$ , so $\left\| \mathbf{u} \right\| - \left\| \mathbf{v} \right\| \le \left\| \mathbf{u} - \mathbf{v} \right\|$ . Swapping the roles of $\mathbf{u}$ and $\mathbf{v}$ gives $\left\| \mathbf{v} \right\| - \left\| \mathbf{u} \right\| \le \left\| \mathbf{v} - \mathbf{u} \right\|$ , and $\left\| \mathbf{v} - \mathbf{u} \right\| = \lvert -1\rvert\left\| \mathbf{u} - \mathbf{v} \right\| = \left\| \mathbf{u} - \mathbf{v} \right\|$ by (N2). The number $\lvert\left\| \mathbf{u} \right\| - \left\| \mathbf{v} \right\|\rvert$ is one of the two quantities just bounded, so it is at most $\left\| \mathbf{u} - \mathbf{v} \right\|$ . This proves the inequality.

Read with $\mathbf{v}$ replaced by $\mathbf{v}'$ , it says that the function $\left\| \cdot \right\|$ changes by at most $\left\| \mathbf{u} - \mathbf{v} \right\|$ when its argument moves from $\mathbf{u}$ to $\mathbf{v}$ . That is a Lipschitz estimate, and it is the reason a norm is continuous with respect to itself — a fact §02 turns into the main theorem.

16.1.2. Unit balls

The quickest way to see the difference between two norms is to draw the set of vectors they call short.

Definition 16.1.2 (Closed Unit Ball)

Let $\left\| \cdot \right\|$ be a norm on $V$ . Its closed unit ball is $B_{\left\| \cdot \right\|} = \{\mathbf{v} \in V : \left\| \mathbf{v} \right\| \le 1\} .$ In $F^n$ we write $B_1$ , $B_2$ and $B_\infty$ for the balls of Example (The $1$ -, $2$ - and $\infty$ -norms on $F^n$ ).

In $\mathbb{R}^2$ the three are a diamond, a disc and a square, and they are nested.

$Diagram. Labels: x_1, x_2, mathbf e_1, (1,1), B_infty , the square, B_2, the disc, B_1, the diamond, The closed unit balls of the three norms on mathbb R^2. A smaller ball\\ belongs to a larger norm: B_1 subseteq B_2 subseteq B_infty says exactly that\\ \|mathbf x\|_infty le \|mathbf x\|_2 le \|mathbf x\|_1, and all three agree at mathbf e_1$

Two features of the picture are general. Each ball is symmetric, $\mathbf{v} \in B$ if and only if $-\mathbf{v} \in B$ , which is (N2) with $c = -1$ ; and each is convex, since if $\left\| \mathbf{u} \right\|, \left\| \mathbf{v} \right\| \le 1$ and $0 \le t \le 1$ then $\left\| t\mathbf{u} + (1-t)\mathbf{v} \right\| \le t\left\| \mathbf{u} \right\| + (1-t)\left\| \mathbf{v} \right\| \le 1$ by (N3) and (N2). The diamond has corners and the square has corners; convexity is what the triangle inequality buys, and it is all it buys. The disc is rounder than the other two for a reason that is the subject of the last part of this section.

The nesting in the picture is an inequality, and it holds in every dimension, with a matching chain running the other way.

Proposition 16.1.2 (Comparing the Three Norms)

For every $\mathbf{x} \in F^n$ , $\left\| \mathbf{x} \right\|_\infty \le \left\| \mathbf{x} \right\|_2 \le \left\| \mathbf{x} \right\|_1$ and $\left\| \mathbf{x} \right\|_1 \le \sqrt n\,\left\| \mathbf{x} \right\|_2 , \qquad \left\| \mathbf{x} \right\|_2 \le \sqrt n\,\left\| \mathbf{x} \right\|_\infty .$ Each of the four inequalities is attained: the first two by $\mathbf{x} = \mathbf{e}_1$ , the last two by $\mathbf{x} = \mathbf{1}$ .

Idea. Four inequalities, two moves. The ones without a $\sqrt n$ compare a sum against its largest term, or a sum of squares against the square of a sum, and need nothing but non-negativity. The ones with a $\sqrt n$ are a trade of $n$ terms against one, and the sharp constant comes from Cauchy–Schwarz against the all-ones vector $\mathbf{1}$ — which is exactly why $\mathbf{1}$ is the vector that attains them.

Proof. Write $a_i = \lvert x_i\rvert \ge 0$ and let $a_k = \max_i a_i$ . Then $a_k^2 \le \sum_i a_i^2$ , and taking non-negative square roots gives $\left\| \mathbf{x} \right\|_\infty \le \left\| \mathbf{x} \right\|_2$ . Next, $\left\| \mathbf{x} \right\|_1^2 = \Bigl(\sum_i a_i\Bigr)^2 = \sum_i a_i^2 + \sum_{i \ne j} a_ia_j \ \ge\ \left\| \mathbf{x} \right\|_2^2 ,$ since every cross term $a_ia_j$ is $\ge 0$ ; taking square roots gives $\left\| \mathbf{x} \right\|_2 \le \left\| \mathbf{x} \right\|_1$ .

For the third inequality, apply Theorem 11.1.5 in $\mathbb{R}^n$ with the dot product to the vectors $(a_1, \dots, a_n)$ and $\mathbf{1}$ : $\left\| \mathbf{x} \right\|_1 = \sum_i a_i \cdot 1 \le \Bigl(\sum_i a_i^2\Bigr)^{1/2}\Bigl(\sum_i 1\Bigr)^{1/2} = \sqrt n\,\left\| \mathbf{x} \right\|_2 .$ For the fourth, $\sum_i a_i^2 \le n\max_i a_i^2$ , and taking square roots gives $\left\| \mathbf{x} \right\|_2 \le \sqrt n\,\left\| \mathbf{x} \right\|_\infty$ .

For the equality cases, $\mathbf{e}_1$ has $\left\| \mathbf{e}_1 \right\|_1 = \left\| \mathbf{e}_1 \right\|_2 = \left\| \mathbf{e}_1 \right\|_\infty = 1$ , and $\mathbf{1}$ has $\left\| \mathbf{1} \right\|_1 = n$ , $\left\| \mathbf{1} \right\|_2 = \sqrt n$ and $\left\| \mathbf{1} \right\|_\infty = 1$ , so $\left\| \mathbf{1} \right\|_1 = \sqrt n\,\left\| \mathbf{1} \right\|_2$ and $\left\| \mathbf{1} \right\|_2 = \sqrt n\,\left\| \mathbf{1} \right\|_\infty$ . This proves the proposition.

So the three norms never disagree by a factor worse than $\sqrt n$ , and the factor $\sqrt n$ really occurs. Hold on to both halves of that sentence: §02 proves the first half for every pair of norms, and the second half is why its constants cannot be made to forget the dimension.

Quick check. Sketch the set $\{\mathbf{x} \in \mathbb{R}^2 : \left\| \mathbf{x} \right\|_{w} \le 1\}$ for the weighted norm $\left\| \mathbf{x} \right\|_{w} = \max(\lvert x_1\rvert, 2\lvert x_2\rvert)$ of Example (Inner products, weights, and a function space) (b), and find the smallest $C$ with $\left\| \mathbf{x} \right\|_\infty \le C\left\| \mathbf{x} \right\|_{w}$ for all $\mathbf{x}$ .

Solution. The ball is the rectangle $\lvert x_1\rvert \le 1$ , $\lvert x_2\rvert \le \tfrac12$ : the square $B_\infty$ squashed vertically by a factor $2$ . Since $\lvert x_1\rvert \le \left\| \mathbf{x} \right\|_{w}$ and $\lvert x_2\rvert \le \tfrac12\left\| \mathbf{x} \right\|_{w}$ , we get $\left\| \mathbf{x} \right\|_\infty \le \left\| \mathbf{x} \right\|_{w}$ , so $C = 1$ works, and it is smallest because $\mathbf{x} = \mathbf{e}_1$ gives $\left\| \mathbf{x} \right\|_\infty = \left\| \mathbf{x} \right\|_{w} = 1$ . The other direction costs a factor: $\left\| \mathbf{x} \right\|_{w} \le 2\left\| \mathbf{x} \right\|_\infty$ , attained at $\mathbf{e}_2$ . Squashing a ball inward enlarges the norm, and the largest squash factor is the constant.

16.1.3. Which norms come from an inner product

Chapter 11 §01 closed with a promise. It observed that Theorem 11.1.2 (a), (b) and Corollary 11.1.6 make every induced norm a norm in the general sense, warned that the converse fails, and named the test: the parallelogram law $\left\| \mathbf{u} + \mathbf{v} \right\|^2 + \left\| \mathbf{u} - \mathbf{v} \right\|^2 = 2\left\| \mathbf{u} \right\|^2 + 2\left\| \mathbf{v} \right\|^2 . \tag{$\ast$}$ It then proved one direction outright — expand both sides with Theorem 11.1.2 (c) and add — and left the converse to Exercise (C1: The parallelogram law characterizes inner-product norms), which carries it out in $\mathbb{R}^2$ while granting one step, the homogeneity $\beta(\mathbf{u}, t\mathbf{v}) = t\beta(\mathbf{u}, \mathbf{v})$ for real $t$ . That exercise’s own remark says where the gap is: additivity gives homogeneity for rational $t$ by induction, and passing to real $t$ needs a limit.

Here is what this section adds. The dimension $2$ in Exercise (C1: The parallelogram law characterizes inner-product norms) was never used, so the computation runs in any real space; the granted step is supplied by a limit, using the completeness of $\mathbb{R}$ ; and the complex case, which Chapter 11 did not touch at all, is built from the real one. The result is the theorem the promise described, with no hypothesis on the dimension.

Theorem 16.1.3 (The Parallelogram Law Characterizes Inner-Product Norms)

Let $F$ be $\mathbb{R}$ or $\mathbb{C}$ , let $V$ be a vector space over $F$ , and let $\left\| \cdot \right\|$ be a norm on $V$ . Then there is an inner product on $V$ with $\langle \mathbf{v}, \mathbf{v} \rangle = \left\| \mathbf{v} \right\|^2$ for every $\mathbf{v}$ if and only if $\left\| \cdot \right\|$ satisfies the parallelogram law $(\ast)$ for all $\mathbf{u}, \mathbf{v} \in V$ . When it exists, that inner product is unique.

Idea. The forward direction is Chapter 11’s computation. For the converse there is only one candidate for the inner product, because Exercise (C2: Recovering the inner product from the norm) already shows that an inner product is determined by its norm through polarization; so write down the polarization formula and check the axioms. ① Over $\mathbb{R}$ the symmetry and the additivity are the computation of Exercise (C1: The parallelogram law characterizes inner-product norms), which never mentions the dimension. ② Homogeneity comes free for rational scalars and is pushed to real scalars by a limit, which is the one analytic step. ③ Over $\mathbb{C}$ , apply ① and ② to $V$ regarded as a real space, then glue the real form $\beta$ and its twist $\beta(\mathbf{u}, i\mathbf{v})$ into a complex inner product; the single identity $\beta(i\mathbf{u}, i\mathbf{v}) = \beta(\mathbf{u}, \mathbf{v})$ does all the work.

Proof. $(\Rightarrow)$ Suppose $\langle \mathbf{v}, \mathbf{v} \rangle = \left\| \mathbf{v} \right\|^2$ for an inner product on $V$ . By Theorem 11.1.2 (c) and the same identity with $-\mathbf{v}$ in place of $\mathbf{v}$ , $\begin{aligned} \left\| \mathbf{u} + \mathbf{v} \right\|^2 &= \left\| \mathbf{u} \right\|^2 + 2\operatorname{Re}\langle \mathbf{u}, \mathbf{v} \rangle + \left\| \mathbf{v} \right\|^2 ,\\ \left\| \mathbf{u} - \mathbf{v} \right\|^2 &= \left\| \mathbf{u} \right\|^2 - 2\operatorname{Re}\langle \mathbf{u}, \mathbf{v} \rangle + \left\| \mathbf{v} \right\|^2 . \end{aligned}$ Adding them gives $(\ast)$ .

$(\Leftarrow)$ Suppose $(\ast)$ holds. Regard $V$ as a vector space over $\mathbb{R}$ , by restricting which scalars are allowed. This changes nothing about $\left\| \cdot \right\|$ : the vectors, the addition and the values of the norm are the same, and (N2) for real $c$ is a special case of (N2) for $c \in F$ . Define $\beta(\mathbf{u}, \mathbf{v}) = \tfrac14\bigl(\left\| \mathbf{u} + \mathbf{v} \right\|^2 - \left\| \mathbf{u} - \mathbf{v} \right\|^2\bigr) .$

Step 1. $\beta$ is symmetric and additive in each slot. Exercise (C1: The parallelogram law characterizes inner-product norms) runs this computation in $\mathbb{R}^2$ ; rather than transport an exercise past the hypotheses it was stated under, here it is in full, for an arbitrary $V$ .

Setting $\mathbf{v} = \mathbf{u}$ gives $\beta(\mathbf{u},\mathbf{u}) = \tfrac14\left\| 2\mathbf{u} \right\|^2 = \left\| \mathbf{u} \right\|^2$ by (N2). Swapping the arguments replaces $\left\| \mathbf{u} - \mathbf{v} \right\|$ by $\left\| \mathbf{v} - \mathbf{u} \right\|$ , equal by (N2) with $c = -1$ , so $\beta(\mathbf{u},\mathbf{v}) = \beta(\mathbf{v},\mathbf{u})$ ; and $\beta(\mathbf{u},\mathbf{0}) = 0$ .

For additivity, apply $(\ast)$ twice. To the pair $\mathbf{u} + \tfrac12(\mathbf{v} + \mathbf{w})$ , $\tfrac12(\mathbf{v} - \mathbf{w})$ , whose sum is $\mathbf{u} + \mathbf{v}$ and whose difference is $\mathbf{u} + \mathbf{w}$ : $\left\| \mathbf{u} + \mathbf{v} \right\|^2 + \left\| \mathbf{u} + \mathbf{w} \right\|^2 = 2\left\| \mathbf{u} + \tfrac12(\mathbf{v} + \mathbf{w}) \right\|^2 + 2\left\| \tfrac12(\mathbf{v} - \mathbf{w}) \right\|^2 .$ Then to the pair $\mathbf{u} - \tfrac12(\mathbf{v} + \mathbf{w})$ , $\tfrac12(\mathbf{w} - \mathbf{v})$ , whose sum is $\mathbf{u} - \mathbf{v}$ and whose difference is $\mathbf{u} - \mathbf{w}$ : $\left\| \mathbf{u} - \mathbf{v} \right\|^2 + \left\| \mathbf{u} - \mathbf{w} \right\|^2 = 2\left\| \mathbf{u} - \tfrac12(\mathbf{v} + \mathbf{w}) \right\|^2 + 2\left\| \tfrac12(\mathbf{w} - \mathbf{v}) \right\|^2 .$ Subtract the second from the first. On the left, the two differences of squares are $4\beta(\mathbf{u},\mathbf{v})$ and $4\beta(\mathbf{u},\mathbf{w})$ , by the definition of $\beta$ . On the right, the last terms cancel, since $\left\| \tfrac12(\mathbf{v}-\mathbf{w}) \right\| = \left\| \tfrac12(\mathbf{w}-\mathbf{v}) \right\|$ by (N2) with $c = -1$ , and the remaining difference of squares is $4\beta\bigl(\mathbf{u}, \tfrac12(\mathbf{v}+\mathbf{w})\bigr)$ . So $4\beta(\mathbf{u},\mathbf{v}) + 4\beta(\mathbf{u},\mathbf{w}) = 8\beta\bigl(\mathbf{u},\tfrac12(\mathbf{v}+\mathbf{w})\bigr)$ , that is, $\beta(\mathbf{u}, \mathbf{v}) + \beta(\mathbf{u}, \mathbf{w}) = 2\,\beta\bigl(\mathbf{u}, \tfrac12(\mathbf{v} + \mathbf{w})\bigr) .$ Taking $\mathbf{w} = \mathbf{0}$ and using $\beta(\mathbf{u},\mathbf{0}) = 0$ turns the right-hand side into $2\beta(\mathbf{u}, \tfrac12\mathbf{v})$ , so $\beta(\mathbf{u}, \mathbf{v}) = 2\beta(\mathbf{u}, \tfrac12\mathbf{v})$ for every $\mathbf{v}$ ; substituting that back with $\mathbf{v} + \mathbf{w}$ in place of $\mathbf{v}$ gives $\beta(\mathbf{u}, \mathbf{v}) + \beta(\mathbf{u}, \mathbf{w}) = \beta(\mathbf{u}, \mathbf{v} + \mathbf{w})$ for all $\mathbf{u}, \mathbf{v}, \mathbf{w} \in V$ . Nothing in this argument mentions a dimension. Additivity in the first slot follows from the symmetry.

Step 2. $\beta(\mathbf{u}, t\mathbf{v}) = t\,\beta(\mathbf{u}, \mathbf{v})$ for every real $t$ . This is the step Exercise (C1: The parallelogram law characterizes inner-product norms) granted. First, $\beta(\mathbf{u}, -\mathbf{v}) = -\beta(\mathbf{u},\mathbf{v})$ , directly from the definition of $\beta$ , since replacing $\mathbf{v}$ by $-\mathbf{v}$ exchanges the two terms. Next, induction on $m \ge 0$ using Step 1 gives $\beta(\mathbf{u}, m\mathbf{v}) = m\beta(\mathbf{u},\mathbf{v})$ , the case $m = 0$ being $\beta(\mathbf{u},\mathbf{0}) = 0$ ; combined with the previous sentence this covers every integer $m$ . For a rational $q = m/n$ with $n \ge 1$ , $n\,\beta\bigl(\mathbf{u}, q\mathbf{v}\bigr) = \beta\bigl(\mathbf{u}, nq\mathbf{v}\bigr) = \beta(\mathbf{u}, m\mathbf{v}) = m\,\beta(\mathbf{u},\mathbf{v}),$ so $\beta(\mathbf{u}, q\mathbf{v}) = q\beta(\mathbf{u},\mathbf{v})$ .

Now fix a real $t$ and put $M = \left\| \mathbf{u} \right\| + (\lvert t\rvert + 1)\left\| \mathbf{v} \right\|$ . For any rational $q$ with $\lvert q - t\rvert \le 1$ , both $\left\| \mathbf{u} \pm t\mathbf{v} \right\|$ and $\left\| \mathbf{u} \pm q\mathbf{v} \right\|$ are at most $M$ by (N2) and (N3), while Lemma 16.1.1 and (N2) give $\bigl\lvert \left\| \mathbf{u} \pm t\mathbf{v} \right\| - \left\| \mathbf{u} \pm q\mathbf{v} \right\| \bigr\rvert \le \lvert t - q\rvert\,\left\| \mathbf{v} \right\| .$ Since $\lvert a^2 - b^2\rvert = \lvert a - b\rvert(a + b)$ for $a, b \ge 0$ , each of the two squared terms in $\beta$ moves by at most $2M\left\| \mathbf{v} \right\|\lvert t - q\rvert$ , and therefore $\bigl\lvert \beta(\mathbf{u}, t\mathbf{v}) - \beta(\mathbf{u}, q\mathbf{v}) \bigr\rvert \le M\left\| \mathbf{v} \right\|\,\lvert t - q\rvert .$ By the completeness of $\mathbb{R}$ , fact (A1) of the chapter introduction, there is a sequence of rationals $q_k \to t$ , and we may assume $\lvert q_k - t\rvert \le 1$ . Then $\begin{aligned} &\bigl\lvert \beta(\mathbf{u},t\mathbf{v}) - t\beta(\mathbf{u},\mathbf{v}) \bigr\rvert \\ &\qquad \le \bigl\lvert \beta(\mathbf{u},t\mathbf{v}) - \beta(\mathbf{u},q_k\mathbf{v}) \bigr\rvert + \lvert q_k - t\rvert\,\lvert\beta(\mathbf{u},\mathbf{v})\rvert \\ &\qquad \le \bigl(M\left\| \mathbf{v} \right\| + \lvert\beta(\mathbf{u},\mathbf{v})\rvert\bigr)\lvert q_k - t\rvert , \end{aligned}$ where the middle term used $\beta(\mathbf{u}, q_k\mathbf{v}) = q_k\beta(\mathbf{u},\mathbf{v})$ . The left-hand side does not depend on $k$ , and the right-hand side tends to $0$ , so the left-hand side is $0$ .

If $F = \mathbb{R}$ , we are done: $\beta$ is symmetric, bilinear by Steps 1 and 2, and $\beta(\mathbf{v},\mathbf{v}) = \left\| \mathbf{v} \right\|^2 > 0$ for $\mathbf{v} \ne \mathbf{0}$ by (N1), so (IP1), (IP2) and (IP3) of Definition 11.1.1 all hold and the induced norm is $\left\| \cdot \right\|$ .

Step 3. The complex case. Suppose $F = \mathbb{C}$ . Steps 1 and 2 apply to $V$ as a real space, so $\beta$ is a symmetric $\mathbb{R}$ -bilinear form with $\beta(\mathbf{v},\mathbf{v}) = \left\| \mathbf{v} \right\|^2$ . Define $\langle \mathbf{u}, \mathbf{v} \rangle = \beta(\mathbf{u}, \mathbf{v}) + i\,\beta(\mathbf{u}, i\mathbf{v}) .$ Everything follows from one identity: $\beta(i\mathbf{u}, i\mathbf{v}) = \beta(\mathbf{u},\mathbf{v})$ , which holds because $\left\| i\mathbf{u} \pm i\mathbf{v} \right\| = \left\| i(\mathbf{u} \pm \mathbf{v}) \right\| = \lvert i\rvert\left\| \mathbf{u} \pm \mathbf{v} \right\| = \left\| \mathbf{u} \pm \mathbf{v} \right\|$ by (N2). Applying it twice, $\beta(i\mathbf{u}, \mathbf{v}) = \beta(i\cdot i\mathbf{u}, i\mathbf{v}) = -\beta(\mathbf{u}, i\mathbf{v})$ .

(IP3) and the norm: $\beta(\mathbf{u}, i\mathbf{u}) = \tfrac14(\left\| \mathbf{u} + i\mathbf{u} \right\|^2 - \left\| \mathbf{u} - i\mathbf{u} \right\|^2)$ , and (N2) turns this into $\tfrac14(\lvert 1 + i\rvert^2 - \lvert 1 - i\rvert^2)\left\| \mathbf{u} \right\|^2 = 0$ . Hence $\langle \mathbf{u}, \mathbf{u} \rangle = \beta(\mathbf{u},\mathbf{u}) = \left\| \mathbf{u} \right\|^2$ , which is $> 0$ for $\mathbf{u} \ne \mathbf{0}$ , and the induced norm is $\left\| \cdot \right\|$ .

(IP1): additivity in the first slot and homogeneity for real scalars come from Steps 1 and 2 applied to both $\beta(\cdot, \mathbf{v})$ and $\beta(\cdot, i\mathbf{v})$ . For the scalar $i$ , $\begin{aligned} \langle i\mathbf{u}, \mathbf{v} \rangle &= \beta(i\mathbf{u}, \mathbf{v}) + i\,\beta(i\mathbf{u}, i\mathbf{v}) \\ &= -\beta(\mathbf{u}, i\mathbf{v}) + i\,\beta(\mathbf{u}, \mathbf{v}) = i\,\langle \mathbf{u}, \mathbf{v} \rangle . \end{aligned}$ Every complex scalar is $a + bi$ with $a, b$ real, so (IP1) follows.

(IP2): using $\beta(\mathbf{v}, i\mathbf{u}) = \beta(i\mathbf{v}, i\cdot i\mathbf{u}) = -\beta(\mathbf{u}, i\mathbf{v})$ and the symmetry of $\beta$ , $\langle \mathbf{v}, \mathbf{u} \rangle = \beta(\mathbf{u},\mathbf{v}) - i\,\beta(\mathbf{u}, i\mathbf{v}) = \overline{\langle \mathbf{u}, \mathbf{v} \rangle} .$

So $\langle \cdot, \cdot \rangle$ is an inner product inducing $\left\| \cdot \right\|$ .

Uniqueness. Suppose $\langle \cdot, \cdot \rangle'$ is any inner product on $V$ with $\langle \mathbf{v}, \mathbf{v} \rangle' = \left\| \mathbf{v} \right\|^2$ for every $\mathbf{v}$ . The two displays of the $(\Rightarrow)$ direction apply to it verbatim, and subtracting them instead of adding them gives $\left\| \mathbf{u} + \mathbf{v} \right\|^2 - \left\| \mathbf{u} - \mathbf{v} \right\|^2 = 4\operatorname{Re}\langle \mathbf{u}, \mathbf{v} \rangle' ,$ that is, $\operatorname{Re}\langle \mathbf{u}, \mathbf{v} \rangle' = \beta(\mathbf{u},\mathbf{v})$ : the real part of $\langle \cdot, \cdot \rangle'$ is forced to be the $\beta$ built above. Over $\mathbb{R}$ an inner product is real-valued, so $\langle \mathbf{u}, \mathbf{v} \rangle' = \beta(\mathbf{u},\mathbf{v})$ and there is nothing left to choose. Over $\mathbb{C}$ , apply the same identity to the pair $\mathbf{u}, i\mathbf{v}$ . By (IP1) and (IP2) together the form is conjugate-linear in its second slot, so $\langle \mathbf{u}, i\mathbf{v} \rangle' = \overline{i}\,\langle \mathbf{u}, \mathbf{v} \rangle' = -i\,\langle \mathbf{u}, \mathbf{v} \rangle'$ , whose real part is $\operatorname{Im}\langle \mathbf{u}, \mathbf{v} \rangle'$ . Hence $\operatorname{Im}\langle \mathbf{u}, \mathbf{v} \rangle' = \beta(\mathbf{u}, i\mathbf{v})$ , and the two parts together give $\langle \mathbf{u}, \mathbf{v} \rangle' = \beta(\mathbf{u},\mathbf{v}) + i\,\beta(\mathbf{u}, i\mathbf{v})$ , which is exactly the inner product constructed above. So it is the only one. (Exercise (C2: Recovering the inner product from the norm) set this computation as an exercise in Chapter 11; it is carried out here because the theorem rests on it.)

This proves the theorem.

The theorem says that the parallelogram law is not one property of induced norms among many — it is the whole difference. A norm either obeys it, and then it is secretly an inner product with an inner product’s entire apparatus of angles, orthogonality and adjoints; or it violates it once, and then no inner product will ever produce it.

Warning. Neither $\left\| \cdot \right\|_1$ nor $\left\| \cdot \right\|_\infty$ comes from an inner product. Test $(\ast)$ on $\mathbf{u} = \mathbf{e}_1$ and $\mathbf{v} = \mathbf{e}_2$ in $F^2$ . Both $\mathbf{u} + \mathbf{v} = (1,1)$ and $\mathbf{u} - \mathbf{v} = (1,-1)$ have $\left\| \cdot \right\|_1 = 2$ , so the left side of $(\ast)$ is $4 + 4 = 8$ , while the right side is $2 + 2 = 4$ . For $\left\| \cdot \right\|_\infty$ both have norm $1$ , so the left side is $2$ and the right side is again $4$ . One failing pair is enough, and there is no repair: by Theorem 16.1.3 no inner product whatsoever induces these norms, in any dimension $\ge 2$ . The same two vectors $f(t) = t$ and $g(t) = 1 - t$ in $C[0,1]$ refute it for the sup norm, since $\left\| f \right\|_\infty = \left\| g \right\|_\infty = \left\| f+g \right\|_\infty = \left\| f-g \right\|_\infty = 1$ .

Quick check. The function $N(\mathbf{x}) = \bigl(x_1^2 + 4x_2^2\bigr)^{1/2}$ is a norm on $\mathbb{R}^2$ , and it is lopsided: $N(\mathbf{e}_1) = 1$ while $N(\mathbf{e}_2) = 2$ . Does it come from an inner product?

Solution. Yes. It is the norm induced by $\langle \mathbf{x}, \mathbf{y} \rangle = x_1y_1 + 4x_2y_2$ , which satisfies (IP1) and (IP2) by inspection and (IP3) because $x_1^2 + 4x_2^2 > 0$ for $\mathbf{x} \ne \mathbf{0}$ . One may also check $(\ast)$ directly: both sides expand to $2x_1^2 + 8x_2^2 + 2y_1^2 + 8y_2^2$ . The lesson is that a norm can be visibly lopsided — its unit ball here is an ellipse, not a circle — and still be an inner-product norm. What matters is not roundness but the parallelogram law.

So the norms of this book split in two. On one side sit $\left\| \cdot \right\|_2$ , the Frobenius norm and every weighted Euclidean norm, where Chapters 11 to 13 apply in full. On the other sit $\left\| \cdot \right\|_1$ , $\left\| \cdot \right\|_\infty$ and the sup norm, where there is no orthogonality and no adjoint, and the only tools are the three axioms. The next section shows that for questions about convergence the split does not matter at all.

16.1.4. Exercises

A. Check your understanding

Exercise (A1)

(a) State the three clauses of Definition 16.1.1, and say which one fails for $N(\mathbf{x}) = \lvert x_1\rvert$ on $F^2$ .
(b) Deduce $\left\| \mathbf{0} \right\| = 0$ from (N2) alone, and explain why (N1) is therefore stated with the word only.
(c) True or false: a function satisfying (N1) and (N3) but not (N2) cannot exist. Justify your answer.
(d) Name the test that decides whether a norm is induced by an inner product, and state what Exercise (C1: The parallelogram law characterizes inner-product norms) had already established before this section.
(e) Order $\left\| \mathbf{x} \right\|_1$ , $\left\| \mathbf{x} \right\|_2$ , $\left\| \mathbf{x} \right\|_\infty$ for a general $\mathbf{x} \in F^n$ , and give a vector for which all three are equal.

Solution.

(a) (N1) positive definiteness, (N2) absolute homogeneity, (N3) the triangle inequality (Definition 16.1.1). For $N(\mathbf{x}) = \lvert x_1\rvert$ only (N1) fails, and only its “only” half: $N(\mathbf{e}_2) = 0$ with $\mathbf{e}_2 \ne \mathbf{0}$ (Example (Three near misses) (b)).
(b) Take $c = 0$ and any $\mathbf{v}$ : (N2) gives $\left\| \mathbf{0} \right\| = \left\| 0\mathbf{v} \right\| = \lvert 0\rvert\left\| \mathbf{v} \right\| = 0$ . So “ $\mathbf{v} = \mathbf{0} \Rightarrow \left\| \mathbf{v} \right\| = 0$ ” is automatic, and the only content left in (N1) is the converse, which is why it is the clause that is stated.
(c) False. Take $N(\mathbf{x}) = \min(\left\| \mathbf{x} \right\|_2, 1)$ on $\mathbb{R}^2$ . It is $\ge 0$ and vanishes only at $\mathbf{0}$ , so (N1) holds. For (N3), note first that $\min(a + b, 1) \le \min(a,1) + \min(b,1)$ for all $a, b \ge 0$ : if either $a \ge 1$ or $b \ge 1$ the right side is at least $1$ , which bounds the left side; and otherwise the right side is $a + b$ , which is at least $\min(a+b, 1)$ . Applying this to $a = \left\| \mathbf{u} \right\|_2$ , $b = \left\| \mathbf{v} \right\|_2$ and using that $s \mapsto \min(s,1)$ is increasing gives (N3). But $N(2\mathbf{e}_1) = 1 \ne 2 = 2N(\mathbf{e}_1)$ , so (N2) fails.
(d) The parallelogram law $(\ast)$ : a norm is induced by an inner product exactly when $\left\| \mathbf{u}+\mathbf{v} \right\|^2 + \left\| \mathbf{u}-\mathbf{v} \right\|^2 = 2\left\| \mathbf{u} \right\|^2 + 2\left\| \mathbf{v} \right\|^2$ always (Theorem 16.1.3). Before this section, Exercise (C1: The parallelogram law characterizes inner-product norms) had proved the converse direction on $\mathbb{R}^2$ , and only modulo the granted homogeneity $\beta(\mathbf{u},t\mathbf{v}) = t\beta(\mathbf{u},\mathbf{v})$ for real $t$ ; the general dimension, the real homogeneity step and the complex case are what Theorem 16.1.3 adds.
(e) $\left\| \mathbf{x} \right\|_\infty \le \left\| \mathbf{x} \right\|_2 \le \left\| \mathbf{x} \right\|_1$ (Proposition 16.1.2). All three agree at $\mathbf{x} = \mathbf{e}_1$ , and more generally at any $\mathbf{x}$ with at most one non-zero coordinate.

B. Practice

Exercise (B1: Three measurements)

For $\mathbf{x} = (1, -1, 2, -2) \in \mathbb{R}^4$ , compute $\left\| \mathbf{x} \right\|_1$ , $\left\| \mathbf{x} \right\|_2$ and $\left\| \mathbf{x} \right\|_\infty$ , and verify all four inequalities of Proposition 16.1.2. Which of them is closest to being an equality?

Solution. $\left\| \mathbf{x} \right\|_1 = 1 + 1 + 2 + 2 = 6$ ; $\left\| \mathbf{x} \right\|_2 = (1 + 1 + 4 + 4)^{1/2} = \sqrt{10}$ ; $\left\| \mathbf{x} \right\|_\infty = 2$ . Here $n = 4$ , so $\sqrt n = 2$ . The four inequalities read $2 \le \sqrt{10} \le 6, \qquad 6 \le 2\sqrt{10}, \qquad \sqrt{10} \le 4 ,$ and $\sqrt{10} \approx 3.162$ , so all four hold. The tightest is $\left\| \mathbf{x} \right\|_1 \le \sqrt n\left\| \mathbf{x} \right\|_2$ , that is $6 \le 6.32$ ; this is as expected, since equality there needs all coordinates of equal modulus, and $\mathbf{x}$ has only two distinct moduli.

Exercise (B2: Determine which are norms)

Determine which of the following define norms on $\mathbb{R}^2$ . For those that do, verify all three clauses of Definition 16.1.1; for those that do not, name the exact clause that fails and give a witness. Justify your answer.

(a) $N(\mathbf{x}) = \lvert x_1\rvert + 2\lvert x_2\rvert$ .
(b) $N(\mathbf{x}) = \lvert x_1 - x_2\rvert$ .
(c) $N(\mathbf{x}) = \max\bigl(\lvert x_1\rvert, \lvert x_2\rvert\bigr) - \tfrac14\min\bigl(\lvert x_1\rvert, \lvert x_2\rvert\bigr)$ .
(d) $N(\mathbf{x}) = \lvert x_1\rvert + \lvert x_2\rvert - \tfrac12\min\bigl(\lvert x_1\rvert, \lvert x_2\rvert\bigr)$ .

Solution.

(a) A norm. It is the weighted norm of Example (Inner products, weights, and a function space) (b) in its $1$ -norm form: (N1) because both terms are $\ge 0$ and both vanish only for $\mathbf{x} = \mathbf{0}$ ; (N2) because $\lvert cx_i\rvert = \lvert c\rvert\lvert x_i\rvert$ ; (N3) coordinatewise, exactly as for $\left\| \cdot \right\|_1$ .
(b) Not a norm. (N2) and (N3) hold, inherited from $\lvert\cdot\rvert$ on $\mathbb{R}$ . (N1) fails: $N\bigl((1,1)\bigr) = 0$ with $(1,1) \ne \mathbf{0}$ .
(c) Not a norm. (N1) holds, since $N(\mathbf{x}) \ge \tfrac34\max(\lvert x_1\rvert, \lvert x_2\rvert)$ , which is $> 0$ for $\mathbf{x} \ne \mathbf{0}$ ; and (N2) holds because $\max$ and $\min$ of the scaled moduli both pick up the factor $\lvert c\rvert$ . (N3) fails: with $\mathbf{u} = (1,1)$ and $\mathbf{v} = (1,-1)$ we get $N(\mathbf{u}) = N(\mathbf{v}) = 1 - \tfrac14 = \tfrac34$ , while $\mathbf{u} + \mathbf{v} = (2,0)$ has $N(\mathbf{u} + \mathbf{v}) = 2 - 0 = 2 > \tfrac32$ . Subtracting from the largest coordinate is exactly what a cancellation in the sum can punish.
(d) A norm, despite the minus sign. Since $\lvert x_1\rvert + \lvert x_2\rvert = \max + \min$ , the formula is $N(\mathbf{x}) = \max + \tfrac12\min$ , which is $N(\mathbf{x}) = \tfrac12\left\| \mathbf{x} \right\|_1 + \tfrac12\left\| \mathbf{x} \right\|_\infty .$ A sum of two norms, each scaled by a positive number, is a norm: (N1), (N2) and (N3) are each inherited term by term, and (N1) needs only one of the two summands to detect $\mathbf{x} \ne \mathbf{0}$ . Compare (c): there the subtracted term was large enough to break (N3), here it is not, and the way to tell is to rewrite the formula rather than to guess.

Exercise (B3: Which of these come from an inner product?)

For each norm, determine whether it is induced by an inner product. Justify your answer, using Theorem 16.1.3 in each case.

(a) $\left\| \mathbf{x} \right\| = \bigl(x_1^2 + x_1x_2 + x_2^2\bigr)^{1/2}$ on $\mathbb{R}^2$ .
(b) $\left\| \mathbf{A} \right\|_F$ on $M_2(\mathbb{R})$ .
(c) $N(\mathbf{A}) = \max_{i,j}\lvert a_{ij}\rvert$ on $M_2(\mathbb{R})$ .

Solution.

(a) Yes. Put $\langle \mathbf{x}, \mathbf{y} \rangle = x_1y_1 + \tfrac12(x_1y_2 + x_2y_1) + x_2y_2$ . It is bilinear and symmetric by inspection, and $\langle \mathbf{x}, \mathbf{x} \rangle = x_1^2 + x_1x_2 + x_2^2 = (x_1 + \tfrac12x_2)^2 + \tfrac34x_2^2$ , which is $> 0$ unless $x_2 = 0$ and $x_1 = 0$ ; so (IP3) holds and the induced norm is the given one. (Completing the square is also how one sees that the given function is a norm at all.)
(b) Yes. The Frobenius norm is induced by the Frobenius inner product $\langle \mathbf{A}, \mathbf{B} \rangle = \operatorname{tr}(\mathbf{B}^{\top}\mathbf{A})$ (Example (Inner products, weights, and a function space) (a)), so $(\ast)$ holds by the forward direction of Theorem 16.1.3.
(c) No. Take $\mathbf{A} = \mathbf{E}_{11}$ and $\mathbf{B} = \mathbf{E}_{12}$ , the matrix units. Then $\mathbf{A} \pm \mathbf{B}$ has entries $1$ and $\pm 1$ in the first row and zeros elsewhere, so $N(\mathbf{A} + \mathbf{B}) = N(\mathbf{A} - \mathbf{B}) = 1$ and the left side of $(\ast)$ is $2$ , while the right side is $2 \cdot 1 + 2\cdot 1 = 4$ . By Theorem 16.1.3 no inner product induces $N$ .

C. Going deeper

Exercise (C1: Sharpness of the comparison constants)

(a) Prove that $\left\| \mathbf{x} \right\|_1 = \sqrt n\,\left\| \mathbf{x} \right\|_2$ holds if and only if all the numbers $\lvert x_1\rvert, \dots, \lvert x_n\rvert$ are equal. Hint: the equality case of Theorem 11.1.5.
(b) Hence deduce that no constant $C$ independent of $n$ satisfies $\left\| \mathbf{x} \right\|_1 \le C\left\| \mathbf{x} \right\|_2$ for all $n$ and all $\mathbf{x} \in \mathbb{R}^n$ .

Solution.

(a) With $\mathbf{a} = (\lvert x_1\rvert, \dots, \lvert x_n\rvert)$ , the proof of Proposition 16.1.2 reads $\left\| \mathbf{x} \right\|_1 = \langle \mathbf{a}, \mathbf{1} \rangle \le \left\| \mathbf{a} \right\|_2\left\| \mathbf{1} \right\|_2 = \sqrt n\left\| \mathbf{x} \right\|_2$ , an application of Theorem 11.1.5 to $\mathbf{a}$ and $\mathbf{1}$ . Equality in Theorem 11.1.5 holds exactly when $(\mathbf{a}, \mathbf{1})$ is dependent. Since $\mathbf{1} \ne \mathbf{0}$ , that means $\mathbf{a} = t\mathbf{1}$ for some real $t$ , which is $t \ge 0$ because the entries of $\mathbf{a}$ are; and $\mathbf{a} = t\mathbf{1}$ says precisely that all the $\lvert x_i\rvert$ are equal.
(b) By (a), $\mathbf{x} = \mathbf{1} \in \mathbb{R}^n$ gives $\left\| \mathbf{1} \right\|_1 = n$ and $\left\| \mathbf{1} \right\|_2 = \sqrt n$ , so any valid $C$ satisfies $C \ge n/\sqrt n = \sqrt n$ . As $n$ is arbitrary, no single $C$ works for all $n$ . The comparison constants between two norms are genuinely functions of the dimension.

Exercise (C2: A real norm that is not a complex norm)

Regard $\mathbb{C}$ as a one-dimensional complex vector space, and also as $\mathbb{R}^2$ by $z = a + bi \leftrightarrow (a,b)$ . Define $N(z) = 2\lvert a\rvert + \lvert b\rvert$ .

(a) Prove that $N$ is a norm on $\mathbb{R}^2$ .
(b) Prove that $N$ is not a norm on $\mathbb{C}$ as a complex vector space, and name the exact clause that fails.
(c) Prove that if $\left\| \cdot \right\|$ is any norm on a complex vector space $V$ , then it is also a norm on $V$ regarded as a real vector space. Explain why (b) does not contradict this.

Solution.

(a) It is the weighted $1$ -norm $\lvert x_1\rvert\cdot 2 + \lvert x_2\rvert \cdot 1$ of Exercise (B2: Determine which are norms) (a) with the weights swapped, so all three clauses hold as there.
(b) (N2) fails for the complex scalar $c = i$ . Indeed $N(1) = 2$ and $N(i) = 1$ , while (N2) would demand $N(i\cdot 1) = \lvert i\rvert N(1) = 2$ .
(c) Restricting the scalars from $\mathbb{C}$ to $\mathbb{R}$ leaves the vectors, the addition and the zero vector unchanged, so (N1) and (N3) are the same statements. (N2) for real $c$ is a special case of (N2) for complex $c$ , the absolute value of a real number being the same in $\mathbb{R}$ and in $\mathbb{C}$ . There is no contradiction with (b) because the implication runs one way only: (N2) over $\mathbb{C}$ is a strictly stronger demand than (N2) over $\mathbb{R}$ , the extra content being $\left\| i\mathbf{v} \right\| = \left\| \mathbf{v} \right\|$ , and $N$ fails exactly that.

Exercise (C3: The ball determines the norm)

Let $\left\| \cdot \right\|$ and $N$ be two norms on a vector space $V$ with the same closed unit ball, in the sense of Definition 16.1.2: $\{\mathbf{v} : \left\| \mathbf{v} \right\| \le 1\} = \{\mathbf{v} : N(\mathbf{v}) \le 1\} .$

(a) Prove that for every $\mathbf{v} \in V$ and every real $t > 0$ , we have $\left\| \mathbf{v} \right\| \le t$ if and only if $\mathbf{v}/t$ lies in the closed unit ball of $\left\| \cdot \right\|$ .
(b) Hence prove that $\left\| \mathbf{v} \right\| = N(\mathbf{v})$ for every $\mathbf{v} \in V$ .
(c) Give two different norms on $\mathbb{R}^2$ whose closed unit balls have the same area, and say why (b) does not apply to them.

Solution.

(a) Since $t > 0$ , (N2) gives $\left\| \mathbf{v}/t \right\| = \left\| \mathbf{v} \right\|/t$ . So $\mathbf{v}/t$ lies in the ball exactly when $\left\| \mathbf{v} \right\|/t \le 1$ , that is, exactly when $\left\| \mathbf{v} \right\| \le t$ .
(b) For $\mathbf{v} = \mathbf{0}$ both sides are $0$ by (N1). Let $\mathbf{v} \ne \mathbf{0}$ and put $t = \left\| \mathbf{v} \right\| > 0$ . By (a), $\mathbf{v}/t$ lies in the ball of $\left\| \cdot \right\|$ , hence in the ball of $N$ , hence $N(\mathbf{v}) \le t = \left\| \mathbf{v} \right\|$ by (a) applied to $N$ . Swapping the roles of $\left\| \cdot \right\|$ and $N$ gives $\left\| \mathbf{v} \right\| \le N(\mathbf{v})$ . Therefore $\left\| \mathbf{v} \right\| = N(\mathbf{v})$ .
(c) Take $\left\| \cdot \right\|_1$ , whose ball is the diamond with vertices $\pm\mathbf{e}_1$ and $\pm\mathbf{e}_2$ , of area $2$ ; and $N(\mathbf{x}) = 2\lvert x_1\rvert + \tfrac12\lvert x_2\rvert$ , whose ball is the diamond with vertices $\pm\tfrac12\mathbf{e}_1$ and $\pm2\mathbf{e}_2$ , also of area $2$ . They differ at $\mathbf{e}_1$ , where they give $1$ and $2$ . Part (b) does not apply because equal area is far weaker than equal set: the recipe in (a) reads the norm off the ball as a set of vectors, and the area of that set retains almost none of it.