16.2 All Norms Agree

§01 left a worry. There are many norms on $F^n$ , they give different answers, and every statement of the form “this quantity is small” now has to say small in which norm. This section removes the worry in finite dimension, in the strongest way available: any two norms on a finite-dimensional space are trapped between fixed multiples of each other, so they agree about every limit, every bounded set and every continuous function. It also says what the theorem costs — constants that grow with the dimension — and where it stops being true.

16.2.1. Trapped between multiples

Look again at Proposition 16.1.2. Its four inequalities say that on $F^n$ , $\tfrac{1}{\sqrt n}\,\left\| \mathbf{x} \right\|_1 \ \le\ \left\| \mathbf{x} \right\|_2 \ \le\ \left\| \mathbf{x} \right\|_1 ,$ so $\left\| \cdot \right\|_2$ never differs from $\left\| \cdot \right\|_1$ by a factor worse than $\sqrt n$ , in either direction. Whatever $\left\| \cdot \right\|_1$ calls small, $\left\| \cdot \right\|_2$ calls small too, at the cost of a fixed factor. That is a relation worth naming.

Two norms are equivalent when each is sandwiched between two fixed multiples of the other, so that neither can be small while the other is large.

Definition 16.2.1 (Equivalent Norms)

Let $V$ be a vector space over $F = \mathbb{R}$ or $\mathbb{C}$ , and let $\left\| \cdot \right\|_a$ and $\left\| \cdot \right\|_b$ be norms on $V$ . They are equivalent if there exist real constants $c, C > 0$ , not depending on the vector, such that $c\,\left\| \mathbf{v} \right\|_b \ \le\ \left\| \mathbf{v} \right\|_a \ \le\ C\,\left\| \mathbf{v} \right\|_b \qquad \text{for every } \mathbf{v} \in V .$

In words. The two inequalities are read separately: the right one says $\left\| \cdot \right\|_a$ is no larger than a fixed multiple of $\left\| \cdot \right\|_b$ , and the left one says it is no smaller than a fixed positive multiple. The phrase not depending on the vector is the whole content, since for each individual $\mathbf{v} \ne \mathbf{0}$ the ratio $\left\| \mathbf{v} \right\|_a/\left\| \mathbf{v} \right\|_b$ is some positive number and one could always take that number as the constant. What is being asked is that one pair of constants works for all $\mathbf{v}$ at once. Note also that the definition says nothing about the two norms being close; $c$ may be $10^{-6}$ .

Example (The three

p

-norms, with best constants)

On $F^n$ , Proposition 16.1.2 gives $\begin{aligned} \left\| \mathbf{x} \right\|_\infty &\le \left\| \mathbf{x} \right\|_2 \le \sqrt n\,\left\| \mathbf{x} \right\|_\infty ,\\ \left\| \mathbf{x} \right\|_\infty &\le \left\| \mathbf{x} \right\|_1 \le n\,\left\| \mathbf{x} \right\|_\infty ,\\ \tfrac{1}{\sqrt n}\left\| \mathbf{x} \right\|_1 &\le \left\| \mathbf{x} \right\|_2 \le \left\| \mathbf{x} \right\|_1 , \end{aligned}$ so the three are pairwise equivalent. The middle line’s upper constant comes from $\left\| \mathbf{x} \right\|_1 \le \sqrt n\left\| \mathbf{x} \right\|_2 \le \sqrt n\cdot\sqrt n\,\left\| \mathbf{x} \right\|_\infty$ . Every constant shown is attained, so none of them can be improved. On the first two lines the lower constant is attained at $\mathbf{e}_1$ and the upper one at $\mathbf{1}$ . The third line runs the other way: at $\mathbf{1}$ the lower inequality reads $\tfrac{1}{\sqrt n}\cdot n = \sqrt n \le \sqrt n$ , and at $\mathbf{e}_1$ the upper one reads $1 \le 1$ .

Before the theorem, one small fact makes the proof strategy possible: it is enough to compare every norm with a single one of our choosing.

Proposition 16.2.1 (Equivalence of Norms Is an Equivalence Relation)

On a fixed vector space $V$ over $F$ , the relation of Definition 16.2.1 is reflexive, symmetric and transitive.

Proof. Reflexive: take $c = C = 1$ . Symmetric: if $c\left\| \mathbf{v} \right\|_b \le \left\| \mathbf{v} \right\|_a \le C\left\| \mathbf{v} \right\|_b$ for all $\mathbf{v}$ , then dividing through by the positive constants gives $C^{-1}\left\| \mathbf{v} \right\|_a \le \left\| \mathbf{v} \right\|_b \le c^{-1}\left\| \mathbf{v} \right\|_a$ . Transitive: if in addition $c'\left\| \mathbf{v} \right\|_d \le \left\| \mathbf{v} \right\|_b \le C'\left\| \mathbf{v} \right\|_d$ , then multiplying the first chain’s outer inequalities by the positive constants $c$ and $C$ gives $cc'\left\| \mathbf{v} \right\|_d \le c\left\| \mathbf{v} \right\|_b \le \left\| \mathbf{v} \right\|_a \le C\left\| \mathbf{v} \right\|_b \le CC'\left\| \mathbf{v} \right\|_d ,$ and $cc', CC' > 0$ . This proves all three properties.

So to prove that any two norms on $V$ are equivalent, it suffices to prove that every norm is equivalent to one fixed reference norm. We take the reference to be the Euclidean norm of a chosen basis, because that is where compactness lives.

16.2.2. Compactness enters the book

Theorem 16.2.2 (Equivalence of Norms in Finite Dimension)

Let $V$ be a vector space over $F = \mathbb{R}$ or $\mathbb{C}$ with $\dim V = n < \infty$ . Then any two norms on $V$ are equivalent. Explicitly, if $\mathcal{B} = (\mathbf{v}_1, \dots, \mathbf{v}_n)$ is a basis of $V$ , if $\left\| \cdot \right\|_2$ denotes the Euclidean norm of the coordinate vector, $\Bigl\lVert \sum_i x_i\mathbf{v}_i \Bigr\rVert_2 \mathrel{:=} \bigl(\lvert x_1\rvert^2 + \dots + \lvert x_n\rvert^2\bigr)^{1/2} ,$ and if $N$ is any norm on $V$ , then there are constants $0 < m \le M$ with $m\,\left\| \mathbf{v} \right\|_2 \ \le\ N(\mathbf{v}) \ \le\ M\,\left\| \mathbf{v} \right\|_2 \qquad \text{for every } \mathbf{v} \in V .$

Idea. The two inequalities are not symmetric, and it is worth seeing why before starting. The upper bound is cheap: write $\mathbf{v}$ in the basis, apply the triangle inequality once, and the constant $M$ is built out of the numbers $N(\mathbf{v}_i)$ . The lower bound cannot be obtained the same way; there is no inequality running from $N(\sum x_i\mathbf{v}_i)$ down to the individual coordinates, and the temptation to assume that the two norms are comparable on the basis and then “extend by linearity” is exactly the error the theorem exists to forbid — Example (Agreeing on a basis is not enough) below shows two norms agreeing on a basis and differing by a factor of $n$ elsewhere.

The route is therefore ① upper bound by the triangle inequality; ② use that upper bound to show $N$ is continuous as a function of the coordinates; ③ restrict $N$ to the Euclidean unit sphere, which is compact, so $N$ attains a minimum $m$ there; ④ the minimum is positive because $N$ vanishes only at $\mathbf{0}$ , which is not on the sphere; ⑤ scale back. Compactness is what turns the infimum over infinitely many unit vectors into a value attained at a particular unit vector, and a value attained at a vector can be tested for positivity one vector at a time.

Proof. By Proposition 16.2.1 it suffices to prove the displayed two-sided bound, since then any two norms $N_1, N_2$ are each equivalent to $\left\| \cdot \right\|_2$ and hence to each other. If $n = 0$ then $V = \{\mathbf{0}\}$ , both norms are the zero function and $m = M = 1$ works; assume $n \ge 1$ . The coordinate map $\Phi \colon F^n \to V$ , $\mathbf{x} \mapsto \sum_i x_i\mathbf{v}_i$ , is an isomorphism (Corollary 2.5.5), and by construction $\left\| \Phi(\mathbf{x}) \right\|_2 = \left\| \mathbf{x} \right\|_2$ is the Euclidean norm of Example (The $1$ -, $2$ - and $\infty$ -norms on $F^n$ ). It is enough to prove the two bounds for $\mathbf{x} \in F^n$ with $N$ replaced by $f(\mathbf{x}) \mathrel{:=} N(\Phi(\mathbf{x}))$ .

Step 1. The upper bound. Let $M = \bigl(\sum_{i=1}^{n} N(\mathbf{v}_i)^2\bigr)^{1/2}$ . For $\mathbf{x} \in F^n$ , the triangle inequality (N3) applied $n - 1$ times and then (N2) give $f(\mathbf{x}) = N\Bigl(\sum_i x_i\mathbf{v}_i\Bigr) \le \sum_i \lvert x_i\rvert\,N(\mathbf{v}_i) ,$ and Theorem 11.1.5 in $\mathbb{R}^n$ , applied to the vectors $(\lvert x_1\rvert, \dots, \lvert x_n\rvert)$ and $(N(\mathbf{v}_1), \dots, N(\mathbf{v}_n))$ , bounds the right-hand side by $M\left\| \mathbf{x} \right\|_2$ . Hence $f(\mathbf{x}) \le M\left\| \mathbf{x} \right\|_2$ for every $\mathbf{x}$ . Also $M > 0$ , since $N(\mathbf{v}_1) > 0$ by (N1) and $\mathbf{v}_1 \ne \mathbf{0}$ .

Step 2. $f$ is continuous on $F^n$ for the Euclidean norm. By Lemma 16.1.1 applied to $N$ , and then Step 1 applied to $\mathbf{x} - \mathbf{y}$ , $\lvert f(\mathbf{x}) - f(\mathbf{y})\rvert \le N\bigl(\Phi(\mathbf{x} - \mathbf{y})\bigr) \le M\,\left\| \mathbf{x} - \mathbf{y} \right\|_2 .$ So $f$ changes by at most $M$ times the distance moved: it is continuous, and the continuity was deduced from Step 1 rather than assumed.

Step 3. The minimum on the unit sphere. Let $S = \{\mathbf{x} \in F^n : \left\| \mathbf{x} \right\|_2 = 1\} ,$ which is non-empty because $n \ge 1$ (it contains $\mathbf{e}_1$ ). It is bounded, and it is closed: if $\left\| \mathbf{x}_k - \mathbf{x} \right\|_2 \to 0$ with every $\left\| \mathbf{x}_k \right\|_2 = 1$ , then Lemma 16.1.1 gives $\bigl\lvert \left\| \mathbf{x} \right\|_2 - 1\bigr\rvert \le \left\| \mathbf{x} - \mathbf{x}_k \right\|_2 \to 0$ , so $\left\| \mathbf{x} \right\|_2 = 1$ and $\mathbf{x} \in S$ . By the compactness of closed bounded sets in $F^n$ , fact (A3) of the chapter introduction, $S$ is compact; by the extreme value theorem, fact (A4), the continuous function $f$ of Step 2 attains a minimum value on $S$ . Say $m = f(\mathbf{x}_0)$ with $\mathbf{x}_0 \in S$ .

Step 4. The minimum is positive. Since $\mathbf{x}_0 \in S$ we have $\left\| \mathbf{x}_0 \right\|_2 = 1 \ne 0$ , so $\mathbf{x}_0 \ne \mathbf{0}$ and hence $\Phi(\mathbf{x}_0) \ne \mathbf{0}$ , $\Phi$ being injective. By (N1) for $N$ , $m = N(\Phi(\mathbf{x}_0)) > 0$ . This is the step that needs a minimum rather than an infimum: an infimum of positive numbers can be $0$ , while a minimum is the value at an actual vector, and there (N1) can be applied.

Step 5. Scaling back. Let $\mathbf{x} \ne \mathbf{0}$ . Then $\mathbf{x}/\left\| \mathbf{x} \right\|_2 \in S$ , so $f(\mathbf{x}/\left\| \mathbf{x} \right\|_2) \ge m$ , and (N2) for $N$ gives $f(\mathbf{x}) \ge m\left\| \mathbf{x} \right\|_2$ . For $\mathbf{x} = \mathbf{0}$ both sides are $0$ . Combining with Step 1, $m\,\left\| \mathbf{x} \right\|_2 \ \le\ f(\mathbf{x}) \ \le\ M\,\left\| \mathbf{x} \right\|_2 \qquad (\mathbf{x} \in F^n),$ and transporting along $\Phi$ gives the statement for $V$ . Since $m \le f(\mathbf{x}_0) \le M\left\| \mathbf{x}_0 \right\|_2 = M$ , the constants satisfy $0 < m \le M$ . This proves the theorem.

The proof used the finite dimension twice, and it is worth saying where: once in Step 1, where the triangle inequality was applied finitely many times to a finite basis expansion, and once in Step 3, where $F^n$ is the space in which closed bounded sets are compact. Remove either and the argument collapses, as the last part of this section shows.

Example (Agreeing on a basis is not enough)

On $F^n$ , the norms $\left\| \cdot \right\|_1$ and $\left\| \cdot \right\|_\infty$ both give every standard basis vector the value $1$ . Yet $\left\| \mathbf{1} \right\|_1 = n$ and $\left\| \mathbf{1} \right\|_\infty = 1$ . So the data “ $N_1(\mathbf{v}_i) = N_2(\mathbf{v}_i)$ for every basis vector” implies no inequality between $N_1$ and $N_2$ beyond what Theorem 16.2.2 gives for any pair at all.

Quick check. In Step 1 the constant was $M = \bigl(\sum_i N(\mathbf{v}_i)^2\bigr)^{1/2}$ . Where would the proof break if we tried the symmetric guess $m = \min_i N(\mathbf{v}_i)$ for the lower bound?

Solution. It breaks immediately, and Example (Agreeing on a basis is not enough) is the witness. Take $V = F^2$ with the basis $(\mathbf{e}_1, \mathbf{e}_2)$ , $N = \left\| \cdot \right\|_\infty$ and $\left\| \cdot \right\|_2$ the Euclidean norm. Then $\min_i N(\mathbf{e}_i) = 1$ , and the guessed inequality $\left\| \mathbf{x} \right\|_\infty \ge \left\| \mathbf{x} \right\|_2$ fails at $\mathbf{x} = \mathbf{1}$ , where the two sides are $1$ and $\sqrt 2$ . The reason is that the triangle inequality only ever bounds $N(\sum x_i\mathbf{v}_i)$ from above; there is no lower bound in the axioms, because a sum of long vectors can be short. Getting a lower bound needs a genuinely different mechanism, and compactness is that mechanism.

16.2.3. What the theorem buys

The point of the theorem is that whole sentences may now drop the words “in which norm”.

Corollary 16.2.3 (Convergence and Boundedness Do Not Depend on the Norm)

Let $V$ be finite-dimensional over $\mathbb{R}$ or $\mathbb{C}$ , let $\left\| \cdot \right\|_a$ and $\left\| \cdot \right\|_b$ be norms on $V$ , and let $(\mathbf{u}_k)$ be a sequence in $V$ with $\mathbf{u} \in V$ . Then:

(a) $\left\| \mathbf{u}_k - \mathbf{u} \right\|_a \to 0$ if and only if $\left\| \mathbf{u}_k - \mathbf{u} \right\|_b \to 0$ ;
(b) $(\mathbf{u}_k)$ is bounded for $\left\| \cdot \right\|_a$ if and only if it is bounded for $\left\| \cdot \right\|_b$ ;
(c) $(\mathbf{u}_k)$ is Cauchy for $\left\| \cdot \right\|_a$ if and only if it is Cauchy for $\left\| \cdot \right\|_b$ .

Proof. By Theorem 16.2.2 there are $c, C > 0$ with $c\left\| \mathbf{v} \right\|_b \le \left\| \mathbf{v} \right\|_a \le C\left\| \mathbf{v} \right\|_b$ for every $\mathbf{v} \in V$ . For (a), apply this to $\mathbf{v} = \mathbf{u}_k - \mathbf{u}$ : if $\left\| \mathbf{u}_k - \mathbf{u} \right\|_b \to 0$ then $0 \le \left\| \mathbf{u}_k - \mathbf{u} \right\|_a \le C\left\| \mathbf{u}_k - \mathbf{u} \right\|_b \to 0$ , and conversely $\left\| \mathbf{u}_k - \mathbf{u} \right\|_b \le c^{-1}\left\| \mathbf{u}_k - \mathbf{u} \right\|_a \to 0$ . For (b), a bound $\left\| \mathbf{u}_k \right\|_b \le K$ for all $k$ gives $\left\| \mathbf{u}_k \right\|_a \le CK$ , and conversely with $c^{-1}$ . For (c), apply the same two estimates to $\mathbf{v} = \mathbf{u}_k - \mathbf{u}_l$ . This proves all three.

Now the connection this chapter was built for. Chapter 10 §10 defined convergence of matrices entrywise (Definition 10.10.1) and said, in its opening paragraph, that no notion of the size of a matrix was used and that Chapter 16 would supply one. Here is the reconciliation.

Corollary 16.2.4 (Entrywise Convergence Is Convergence in Every Norm)

Let $\mathbf{M}_1, \mathbf{M}_2, \dots$ and $\mathbf{M}$ lie in $M_{p\times q}(\mathbb{C})$ , and let $\left\| \cdot \right\|$ be any norm on $M_{p\times q}(\mathbb{C})$ . Then $\mathbf{M}_k \to \mathbf{M}$ entrywise in the sense of Definition 10.10.1 if and only if $\left\| \mathbf{M}_k - \mathbf{M} \right\| \to 0$ . Likewise $(\mathbf{M}_k)$ is bounded in the sense of Definition 10.10.1 if and only if $\bigl(\left\| \mathbf{M}_k \right\|\bigr)$ is a bounded sequence of real numbers.

Idea. Entrywise convergence is convergence in one particular norm, the entrywise maximum. Theorem 16.2.2 says every other norm is trapped between two multiples of it, and a quantity squeezed between two multiples of something tending to $0$ tends to $0$ as well. Both directions are that one sentence.

Proof. The space $M_{p\times q}(\mathbb{C})$ is a complex vector space of dimension $pq$ , and $N_\infty(\mathbf{M}) = \max_{r,s}\lvert m_{rs}\rvert$ is a norm on it: it is the $\infty$ -norm of Example (The $1$ -, $2$ - and $\infty$ -norms on $F^n$ ) read on the list of entries, through the coordinate isomorphism of Corollary 2.5.5 that sends a matrix to its $pq$ entries. By Definition 10.10.1 (a), $\mathbf{M}_k \to \mathbf{M}$ entrywise means $(\mathbf{M}_k)_{rs} \to \mathbf{M}_{rs}$ for each of the finitely many positions $(r,s)$ , and since a maximum of finitely many non-negative sequences tends to $0$ exactly when each of them does, this says precisely $N_\infty(\mathbf{M}_k - \mathbf{M}) \to 0$ . By Theorem 16.2.2 the norms $N_\infty$ and $\left\| \cdot \right\|$ are equivalent, so Corollary 16.2.3 (a) converts this into $\left\| \mathbf{M}_k - \mathbf{M} \right\| \to 0$ . The statement about boundedness is Definition 10.10.1 (b) together with Corollary 16.2.3 (b), read the same way.

Example (Watching one sequence converge)

In $M_2(\mathbb{R})$ let $\mathbf{M}_k = \begin{pmatrix} \tfrac1k & 2 \\[2pt] 0 & 1 - \tfrac1k \end{pmatrix} , \qquad k \ge 1 .$ Entry by entry, $\tfrac1k \to 0$ , $2 \to 2$ , $0 \to 0$ and $1 - \tfrac1k \to 1$ , so $\mathbf{M}_k \to \mathbf{M} = \begin{psmallmatrix} 0 & 2 \\ 0 & 1\end{psmallmatrix}$ in the sense of Definition 10.10.1. The corollary says this is convergence in every norm, and here one can see it directly: $\mathbf{M}_k - \mathbf{M} = \operatorname{diag}(\tfrac1k, -\tfrac1k)$ , so $\left\| \mathbf{M}_k - \mathbf{M} \right\|_F = \sqrt{\tfrac{1}{k^2} + \tfrac{1}{k^2}} = \frac{\sqrt2}{k} \longrightarrow 0 ,$ and $\left\| \mathbf{M}_k - \mathbf{M} \right\|_\infty$ , the largest absolute row sum, is $\tfrac1k$ . Different norms, different constants, the same verdict — which is the content of the corollary.

So Chapter 10 §10 lost nothing by working entrywise. Its Theorem 10.10.2, Theorem 10.10.3, Theorem 10.10.4 and Theorem 10.10.6 are statements about the convergence of matrices, and every norm this chapter introduces — the Frobenius norm, the operator norms of §03, anything at all — measures the same thing. What the norms add is not a new notion of limit but a rate: a single number $\left\| \mathbf{A}^{k} \right\|$ that can be bounded, compared and summed, where an entrywise statement gives $pq$ separate sequences and no way to combine them.

One more corollary, which §03 will use to know that the operator norm exists at all.

Corollary 16.2.5 (Closed and Bounded Is Compact, in Every Norm)

Let $V$ be finite-dimensional over $\mathbb{R}$ or $\mathbb{C}$ . Call a subset $K \subseteq V$ bounded for a norm if $K \subseteq \{\mathbf{v} : \left\| \mathbf{v} \right\| \le R\}$ for some real $R$ , and closed for that norm if whenever $\left\| \mathbf{u}_k - \mathbf{u} \right\| \to 0$ with every $\mathbf{u}_k \in K$ , also $\mathbf{u} \in K$ . Then a subset that is closed and bounded for one norm is closed and bounded for every norm, and is compact: every sequence in it has a subsequence converging to a point of it. In particular, when $V \ne \{\mathbf{0}\}$ , the unit sphere $\{\mathbf{v} : \left\| \mathbf{v} \right\| = 1\}$ of any norm is non-empty and compact, and a continuous real-valued function on it attains a maximum and a minimum.

Idea. Both words in “closed and bounded” are defined by a norm, so the first thing to check is that changing the norm changes neither. That is Theorem 16.2.2 again. Once the words are norm-free, the statement is Theorem 16.2.2’s own compactness step read in a coordinate-free way: carry $K$ to $F^n$ by coordinates, apply (A3), and carry the limit back.

Proof. Fix a basis and transport everything to $F^n$ by the coordinate isomorphism (Corollary 2.5.5), as in the proof of Theorem 16.2.2. Let $\left\| \cdot \right\|_a$ and $\left\| \cdot \right\|_b$ be norms, with $c\left\| \cdot \right\|_b \le \left\| \cdot \right\|_a \le C\left\| \cdot \right\|_b$ from Theorem 16.2.2. A set bounded for one is bounded for the other by the same two estimates as in Corollary 16.2.3 (b). A set closed for one is closed for the other, because by Corollary 16.2.3 (a) the two norms have the same convergent sequences with the same limits, and the notion of closed defined in the statement asks exactly that limits of convergent sequences stay in the set.

For compactness, let $K \subseteq F^n$ be closed and bounded for some norm; by the previous paragraph it is closed and bounded for $\left\| \cdot \right\|_2$ . By the compactness of closed bounded sets in $F^n$ , fact (A3) of the chapter introduction, every sequence in $K$ has a subsequence converging in $\left\| \cdot \right\|_2$ to a point of $K$ , and by Corollary 16.2.3 (a) that subsequence converges in every norm to the same point. The unit sphere of a norm $N$ is bounded, and it is closed because $\lvert N(\mathbf{v}) - N(\mathbf{u}_k)\rvert \le N(\mathbf{v} - \mathbf{u}_k)$ by Lemma 16.1.1, so a limit of vectors with $N = 1$ has $N = 1$ ; it is non-empty when $V \ne \{\mathbf{0}\}$ , since $N(\mathbf{v})^{-1}\mathbf{v}$ lies on it for any $\mathbf{v} \ne \mathbf{0}$ . The last sentence is then the extreme value theorem, fact (A4), applied to that non-empty compact set. This proves the corollary.

16.2.4. Two warnings, and where the theorem stops

The theorem is not permission to forget which norm is in use. Here is the first reason.

Warning. The constants depend on the dimension, and grow. Example (The three $p$ -norms, with best constants) gives $\left\| \mathbf{x} \right\|_1 \le n\left\| \mathbf{x} \right\|_\infty$ on $F^n$ , and Exercise (C1: Sharpness of the comparison constants) shows the constant $\sqrt n$ in $\left\| \mathbf{x} \right\|_1 \le \sqrt n\left\| \mathbf{x} \right\|_2$ is attained, hence best possible. So a statement such as “the error is at most $10^{-6}$ in the $\infty$ -norm” translates into the $1$ -norm as “at most $n \cdot 10^{-6}$ ”, which is a different statement when $n$ is a million. Theorem 16.2.2 says the two norms cannot disagree about whether something tends to zero; it says nothing about how fast, and every quantitative estimate in the rest of this chapter names its norm for that reason.

The second reason is that the theorem is false without the finite dimension, and not by a narrow margin.

Example (Two inequivalent norms on a space of polynomials)

Let $V = \mathbb{R}[x]$ , the real polynomials — equivalently, the sequences of real coefficients with only finitely many non-zero terms. For $p = a_0 + a_1x + \dots + a_dx^d$ put $\left\| p \right\|_1 = \lvert a_0\rvert + \dots + \lvert a_d\rvert , \qquad \left\| p \right\|_\infty = \max_i \lvert a_i\rvert .$ Both are norms, by the same coordinatewise checks as in Example (The $1$ -, $2$ - and $\infty$ -norms on $F^n$ ); the only difference is that the number of coordinates is unbounded. One inequality survives: $\left\| p \right\|_\infty \le \left\| p \right\|_1$ always. The other fails completely. Put $p_k = 1 + x + x^2 + \dots + x^{k-1} .$ Then $\left\| p_k \right\|_1 = k$ while $\left\| p_k \right\|_\infty = 1$ , so a constant $C$ with $\left\| p \right\|_1 \le C\left\| p \right\|_\infty$ for all $p$ would have to satisfy $C \ge k$ for every $k$ . No such $C$ exists, and the two norms are not equivalent.

Look at what the sequence $\bigl(\tfrac1k p_k\bigr)$ does: it tends to $0$ in $\left\| \cdot \right\|_\infty$ , since $\left\| \tfrac1k p_k \right\|_\infty = 1/k$ , while $\left\| \tfrac1k p_k \right\|_1 = 1$ for every $k$ . So the two norms disagree about which sequences converge — not about the rate, about the fact. Everything in Corollary 16.2.3 and Corollary 16.2.5 fails here at once, and it fails because Step 3 of the proof of Theorem 16.2.2 has nothing to stand on. The general reason is recorded, and not proved, in the warning below.

Warning. Infinite dimension is outside the scope of this book. The closed unit ball of a normed space is compact only when the space is finite-dimensional. That is a genuine theorem, due to Riesz, and it is recorded here, not proved: it lies outside the four imported facts of the chapter introduction, this book never uses it as a step in an argument, and it is stated only so that Example (Two inequivalent norms on a space of polynomials) is not mistaken for an accident of a badly chosen pair. Every result of this chapter carries the hypothesis $\dim V < \infty$ , and on $C[0,1]$ or $\mathbb{R}[x]$ none of them is available. The study of norms on infinite-dimensional spaces is functional analysis, and there the choice of norm is the main content rather than an irrelevance.

Quick check. On $C[0,1]$ , compare the sup norm $\left\| f \right\|_\infty$ of Example (Inner products, weights, and a function space) (c) with $\left\| f \right\|_1 = \int_0^1\lvert f\rvert$ , which is a norm because a continuous $f \ge 0$ with $\int_0^1 f = 0$ is the zero function — the one fact from analysis that Chapter 11 §01 recorded when it put an inner product on $C[0,1]$ , quoted again here. Which of the two inequalities of Definition 16.2.1 holds, and which fails?

Solution. The inequality $\left\| f \right\|_1 \le \left\| f \right\|_\infty$ holds, since $\int_0^1\lvert f\rvert \le \int_0^1\left\| f \right\|_\infty = \left\| f \right\|_\infty$ . The other fails. Take $f_k(t) = \max(0, 1 - kt)$ for $k \ge 1$ , the spike that drops from $1$ to $0$ on $[0, 1/k]$ . Then $\left\| f_k \right\|_\infty = f_k(0) = 1$ , while $\left\| f_k \right\|_1 = \int_0^{1/k}(1 - kt)\,\mathrm{d} t = \frac{1}{2k} ,$ the area of a triangle of base $1/k$ and height $1$ , so no integration theory is needed to evaluate it. A constant $C$ with $\left\| f \right\|_\infty \le C\left\| f \right\|_1$ would need $C \ge 2k$ for every $k$ . A tall thin spike has small integral and large maximum, and in infinite dimension nothing stops it from being arbitrarily thin.

With the choice of norm made harmless in finite dimension, the next section can measure matrices without apologizing for which measurement it uses — and then, when the estimates start to matter, name the norm on purpose.

16.2.5. Exercises

A. Check your understanding

Exercise (A1)

(a) State Definition 16.2.1, and explain why the phrase “not depending on the vector” cannot be dropped.
(b) State Theorem 16.2.2, including its hypothesis on $V$ .
(c) Which two of the four imported analysis facts does the proof of Theorem 16.2.2 use, and at which step is each used?
(d) True or false: if two norms on $\mathbb{R}^n$ are equivalent, then some sequence converges in one and not the other. Justify your answer.
(e) True or false: equivalent norms give the same value to every vector. Justify your answer.

Solution.

(a) Two norms $\left\| \cdot \right\|_a, \left\| \cdot \right\|_b$ on $V$ are equivalent if there are constants $c, C > 0$ , independent of the vector, with $c\left\| \mathbf{v} \right\|_b \le \left\| \mathbf{v} \right\|_a \le C\left\| \mathbf{v} \right\|_b$ for every $\mathbf{v} \in V$ (Definition 16.2.1). Without the phrase the condition is vacuous: for each $\mathbf{v} \ne \mathbf{0}$ the number $\left\| \mathbf{v} \right\|_a/\left\| \mathbf{v} \right\|_b$ is positive and could be taken as both $c$ and $C$ at that one vector, so every pair of norms would qualify.
(b) On a finite-dimensional vector space over $\mathbb{R}$ or $\mathbb{C}$ , any two norms are equivalent (Theorem 16.2.2). Finite dimension is essential — see Example (Two inequivalent norms on a space of polynomials).
(c) Fact (A3), the compactness of closed bounded sets in $F^n$ , at Step 3, to know the Euclidean unit sphere is compact; and fact (A4), the extreme value theorem, also at Step 3, to know that the continuous function $f$ attains a minimum there rather than merely approaching an infimum.
(d) False, and this is the content of Corollary 16.2.3 (a): equivalent norms have exactly the same convergent sequences with exactly the same limits.
(e) False. $\left\| \cdot \right\|_1$ and $\left\| \cdot \right\|_\infty$ on $\mathbb{R}^2$ are equivalent by Example (The three $p$ -norms, with best constants), yet $\left\| \mathbf{1} \right\|_1 = 2 \ne 1 = \left\| \mathbf{1} \right\|_\infty$ . Equivalence constrains ratios, not values.

B. Practice

Exercise (B1: Best constants for a weighted norm)

On $\mathbb{R}^2$ let $N(\mathbf{x}) = \bigl(x_1^2 + 4x_2^2\bigr)^{1/2}$ . Find the best constants $c, C > 0$ with $c\,\left\| \mathbf{x} \right\|_\infty \le N(\mathbf{x}) \le C\,\left\| \mathbf{x} \right\|_\infty \qquad (\mathbf{x} \in \mathbb{R}^2),$ and give a vector attaining each. Hence deduce that $N$ and $\left\| \cdot \right\|_\infty$ are equivalent.

Solution. Write $a = \lvert x_1\rvert$ , $b = \lvert x_2\rvert$ and $M = \max(a,b) = \left\| \mathbf{x} \right\|_\infty$ . Then $N(\mathbf{x})^2 = a^2 + 4b^2$ .

Upper: $a^2 + 4b^2 \le M^2 + 4M^2 = 5M^2$ , so $N(\mathbf{x}) \le \sqrt5\,\left\| \mathbf{x} \right\|_\infty$ . Equality needs $a = b = M$ , and $\mathbf{x} = (1,1)$ gives $N(\mathbf{x}) = \sqrt5$ and $\left\| \mathbf{x} \right\|_\infty = 1$ . So $C = \sqrt5$ and it cannot be lowered.

Lower: if $M = a$ then $a^2 + 4b^2 \ge a^2 = M^2$ , and if $M = b$ then $a^2 + 4b^2 \ge 4b^2 \ge M^2$ . Either way $N(\mathbf{x}) \ge \left\| \mathbf{x} \right\|_\infty$ , so $c = 1$ works, and $\mathbf{x} = \mathbf{e}_1$ gives $N(\mathbf{x}) = \left\| \mathbf{x} \right\|_\infty = 1$ , so it cannot be raised.

Since $1$ and $\sqrt5$ are positive constants independent of $\mathbf{x}$ , the two norms are equivalent by Definition 16.2.1.

Exercise (B2: Reading a convergence off the entries)

In $M_2(\mathbb{R})$ let $\mathbf{M}_k = \begin{pmatrix} 1 + \frac{1}{k} & \frac{(-1)^k}{k^2} \\ \frac{1}{2^k} & 3 - \frac{5}{k} \end{pmatrix} .$ Determine $\lim_k \mathbf{M}_k$ in the sense of Definition 10.10.1, and compute $\left\| \mathbf{M}_k - \mathbf{M} \right\|_F$ explicitly. Hence confirm Corollary 16.2.4 for this sequence and the Frobenius norm.

Solution. Each entry converges: $1 + 1/k \to 1$ , $(-1)^k/k^2 \to 0$ , $2^{-k} \to 0$ , $3 - 5/k \to 3$ . So $\mathbf{M}_k \to \mathbf{M} = \begin{pmatrix} 1 & 0 \\ 0 & 3\end{pmatrix}$ entrywise. Then $\left\| \mathbf{M}_k - \mathbf{M} \right\|_F = \Bigl(\tfrac{1}{k^2} + \tfrac{1}{k^4} + \tfrac{1}{4^k} + \tfrac{25}{k^2}\Bigr)^{1/2} ,$ which is at most $\bigl(28/k^2\bigr)^{1/2} = \sqrt{28}/k$ for $k \ge 1$ , since $1/k^4 \le 1/k^2$ and $4^{-k} \le 1/k^2$ for $k \ge 1$ . Hence $\left\| \mathbf{M}_k - \mathbf{M} \right\|_F \to 0$ , as Corollary 16.2.4 predicts. Note what the norm added: a single sequence $\sqrt{28}/k$ bounding the whole matrix, where the entrywise statement gave four unrelated sequences.

Exercise (B3: An equivalence with the constants written down)

Let $V = \mathbb{R}[x]_{\le 2}$ with basis $\mathcal{B} = (1, x, x^2)$ . For $p \in V$ let $\left\| p \right\|_{\mathcal{B}}$ be the Euclidean norm of the coefficient vector, and let $N(p) = \lvert p(0)\rvert + \lvert p(1)\rvert + \lvert p(-1)\rvert$ .

(a) Prove that $N$ is a norm on $V$ .
(b) Find an explicit $M$ with $N(p) \le M\left\| p \right\|_{\mathcal{B}}$ , following Step 1 of the proof of Theorem 16.2.2.
(c) Explain, without computing it, why a constant $m > 0$ with $N(p) \ge m\left\| p \right\|_{\mathcal{B}}$ exists.

Solution.

(a) (N2) and (N3) are inherited pointwise from $\lvert\cdot\rvert$ on $\mathbb{R}$ , exactly as for $\left\| \cdot \right\|_1$ in Example (The $1$ -, $2$ - and $\infty$ -norms on $F^n$ ). For (N1): $N(p) = 0$ forces $p(0) = p(1) = p(-1) = 0$ , so $p$ has three distinct roots while $\deg p \le 2$ , hence $p = 0$ . This is the only clause with any content, and it is where $\dim V = 3$ and the three sample points match up.
(b) Step 1 takes $M = \bigl(\sum_i N(\mathbf{v}_i)^2\bigr)^{1/2}$ over the basis. Here $N(1) = 1 + 1 + 1 = 3$ , $N(x) = 0 + 1 + 1 = 2$ and $N(x^2) = 0 + 1 + 1 = 2$ , so $M = \bigl(9 + 4 + 4\bigr)^{1/2} = \sqrt{17} .$
(c) $V$ is finite-dimensional, so Theorem 16.2.2 applies to the pair $N$ , $\left\| \cdot \right\|_{\mathcal{B}}$ and delivers both constants at once. Only the upper one is computable by hand from the basis; the lower one comes from compactness and the proof gives no formula for it.

C. Going deeper

Exercise (C1: Every linear map out of a finite-dimensional space is continuous)

Let $V$ be finite-dimensional over $F$ with norm $\left\| \cdot \right\|_V$ , let $W$ be a normed space over $F$ with norm $\left\| \cdot \right\|_W$ , and let $T \colon V \to W$ be linear. Fix a basis $\mathcal{B} = (\mathbf{v}_1, \dots, \mathbf{v}_n)$ of $V$ and write $\left\| \cdot \right\|_1$ for the $1$ -norm of the coordinate vector in the basis $\mathcal{B}$ .

(a) Prove that $\left\| T\mathbf{v} \right\|_W \le K\left\| \mathbf{v} \right\|_1$ for every $\mathbf{v} \in V$ , where $K = \max_i\left\| T\mathbf{v}_i \right\|_W$ .
(b) Hence prove that there is a constant $L$ with $\left\| T\mathbf{u} - T\mathbf{v} \right\|_W \le L\left\| \mathbf{u} - \mathbf{v} \right\|_V$ for all $\mathbf{u}, \mathbf{v} \in V$ .
(c) Explain why (b) may fail when $V$ is infinite-dimensional, using Example (Two inequivalent norms on a space of polynomials).

Solution.

(a) Write $\mathbf{v} = \sum_i x_i\mathbf{v}_i$ . By linearity of $T$ , then (N3) and (N2) in $W$ , $\left\| T\mathbf{v} \right\|_W = \Bigl\lVert \sum_i x_iT\mathbf{v}_i \Bigr\rVert_W \le \sum_i \lvert x_i\rvert\,\left\| T\mathbf{v}_i \right\|_W \le K\left\| \mathbf{v} \right\|_1 .$
(b) The function $\left\| \cdot \right\|_1$ is a norm on $V$ (it is $\left\| \cdot \right\|_1$ of Example (The $1$ -, $2$ - and $\infty$ -norms on $F^n$ ) transported by the coordinate isomorphism Corollary 2.5.5), and $V$ is finite-dimensional, so by Theorem 16.2.2 there is $C > 0$ with $\left\| \mathbf{v} \right\|_1 \le C\left\| \mathbf{v} \right\|_V$ for all $\mathbf{v}$ . Put $L = KC$ . By linearity, $T\mathbf{u} - T\mathbf{v} = T(\mathbf{u} - \mathbf{v})$ , so (a) gives $\left\| T\mathbf{u} - T\mathbf{v} \right\|_W \le K\left\| \mathbf{u} - \mathbf{v} \right\|_1 \le L\left\| \mathbf{u} - \mathbf{v} \right\|_V .$
(c) Part (a) needs a finite basis expansion, and part (b) needs Theorem 16.2.2, which is false in infinite dimension. Concretely, take $V = \mathbb{R}[x]$ with the coefficient norm $\left\| \cdot \right\|_\infty$ of Example (Two inequivalent norms on a space of polynomials), $W = \mathbb{R}$ with $\lvert\cdot\rvert$ , and the linear functional $T(p) = p(1)$ , which adds up the coefficients. With $p_k = 1 + x + \dots + x^{k-1}$ as there, the polynomials $q_k = \tfrac1k p_k$ satisfy $\left\| q_k \right\|_\infty = 1/k \to 0$ while $T(q_k) = 1$ for every $k$ . So $T$ sends a sequence tending to $0$ to a sequence that does not, and no constant $L$ can exist.

Exercise (C2: No dimension-free constants)

For each $n \ge 1$ let $c_n, C_n > 0$ be the best constants with $c_n\left\| \mathbf{x} \right\|_\infty \le \left\| \mathbf{x} \right\|_1 \le C_n\left\| \mathbf{x} \right\|_\infty \qquad (\mathbf{x} \in F^n) .$

(a) Determine $c_n$ and $C_n$ , with a vector attaining each.
(b) Deduce that there is no pair of constants $c, C > 0$ working simultaneously for every $n$ .
(c) A statement about $\mathbb{R}^n$ says “the error $\mathbf{e}$ satisfies $\left\| \mathbf{e} \right\|_\infty \le 10^{-6}$ ”. What is the strongest bound on $\left\| \mathbf{e} \right\|_1$ that follows, and for which $n$ does it stop being informative if the entries of $\mathbf{e}$ are themselves of size about $10^{-6}$ ?

Solution.

(a) $c_n = 1$ and $C_n = n$ . Indeed $\left\| \mathbf{x} \right\|_\infty = \lvert x_k\rvert$ for some $k$ , and $\lvert x_k\rvert \le \sum_i\lvert x_i\rvert = \left\| \mathbf{x} \right\|_1$ , with equality at $\mathbf{x} = \mathbf{e}_1$ ; and $\left\| \mathbf{x} \right\|_1 = \sum_i\lvert x_i\rvert \le n\max_i\lvert x_i\rvert = n\left\| \mathbf{x} \right\|_\infty$ , with equality at $\mathbf{x} = \mathbf{1}$ . Both constants are therefore attained and cannot be improved.
(b) A dimension-free $C$ would need $C \ge C_n = n$ for every $n$ , which is impossible. (The constant $c = 1$ does happen to work for all $n$ ; it is the upper constant that blows up, and one blown-up constant is enough.)
(c) The strongest bound is $\left\| \mathbf{e} \right\|_1 \le n\cdot 10^{-6}$ , by (a), and it is attained when all entries have modulus $10^{-6}$ — which is exactly the situation described. So for $n = 10^{6}$ the bound reads $\left\| \mathbf{e} \right\|_1 \le 1$ , which says nothing useful about a quantity that is itself of order $1$ . The two norms agree that the error tends to $0$ as the computation improves; they disagree, by a factor of $n$ , about whether it is currently small.

Exercise (C3: A finite-dimensional subspace is closed)

Let $W$ be a normed space over $F$ with norm $\left\| \cdot \right\|$ , and let $U \subseteq W$ be a finite-dimensional subspace. Let $(\mathbf{u}_k)$ be a sequence in $U$ with $\left\| \mathbf{u}_k - \mathbf{w} \right\| \to 0$ for some $\mathbf{w} \in W$ .

(a) Prove that $(\mathbf{u}_k)$ is bounded in $U$ for the restricted norm.
(b) Using Corollary 16.2.5, produce a subsequence $(\mathbf{u}_{k_j})$ converging to some $\mathbf{u} \in U$ .
(c) Deduce that $\mathbf{w} = \mathbf{u}$ , so that $U$ contains the limit of every convergent sequence of its own elements. Hint: the triangle inequality, through $\mathbf{u}_{k_j}$ .

Solution.

(a) By Lemma 16.1.1, $\bigl\lvert\left\| \mathbf{u}_k \right\| - \left\| \mathbf{w} \right\|\bigr\rvert \le \left\| \mathbf{u}_k - \mathbf{w} \right\|$ , and the right side tends to $0$ . So there is $K$ with $\left\| \mathbf{u}_k - \mathbf{w} \right\| \le 1$ for $k \ge K$ , whence $\left\| \mathbf{u}_k \right\| \le \left\| \mathbf{w} \right\| + 1$ for those $k$ ; the finitely many earlier terms are bounded by their maximum. Hence $(\mathbf{u}_k)$ is bounded.
(b) The restriction of $\left\| \cdot \right\|$ to $U$ is a norm on $U$ , and $U$ is finite-dimensional. The set $K = \{\mathbf{u} \in U : \left\| \mathbf{u} \right\| \le R\}$ , with $R$ the bound from (a), is closed and bounded in $U$ , hence compact by Corollary 16.2.5. The sequence $(\mathbf{u}_k)$ lies in $K$ , so some subsequence $(\mathbf{u}_{k_j})$ converges to a point $\mathbf{u} \in K \subseteq U$ .
(c) For every $j$ , by (N3), $\left\| \mathbf{w} - \mathbf{u} \right\| \le \left\| \mathbf{w} - \mathbf{u}_{k_j} \right\| + \left\| \mathbf{u}_{k_j} - \mathbf{u} \right\| .$ Both terms on the right tend to $0$ as $j \to \infty$ : the first because $(\mathbf{u}_k)$ converges to $\mathbf{w}$ and a subsequence of a convergent sequence has the same limit, the second by (b). The left side does not depend on $j$ , so $\left\| \mathbf{w} - \mathbf{u} \right\| = 0$ , and (N1) gives $\mathbf{w} = \mathbf{u} \in U$ . Hence $U$ contains every such limit, which is what it means for $U$ to be closed in $W$ . Note that $W$ itself was never assumed finite-dimensional; only $U$ was, and that is exactly where Corollary 16.2.5 was applied.