University Mathematics — Year 2 · Bachelor Year 2

5Normed Vector Spaces

When the metric space is a vector space and the distance comes from a norm, topology and linear algebra begin to interact: linear maps are continuous exactly when they are bounded on the unit ball, finite dimension forces all norms to agree, and completeness turns absolutely convergent series into convergent ones. The finite/infinite dimension divide — crystallized in Riesz’s theorem — is the deepest lesson of the chapter.

Throughout, $E, F$ are vector spaces over $K = \R$ or $\C$ .

5.1 Norms

Definition 5.1

A norm on $E$ is a map $\norm{\,\cdot\,} \colon E \to \R_+$ with, for all $x, y \in E$ , $\lambda \in K$ :

\norm x = 0 \iff x = 0, \qquad \norm{\lambda x} = \abs\lambda\,\norm x, \qquad \norm{x + y} \leq \norm x + \norm y .

Then $d(x, y) = \norm{x - y}$ is a distance, and all of Chapter 4 applies. The reverse triangle inequality $\bigl|\norm x - \norm y\bigr| \leq \norm{x - y}$ makes the norm itself $1$ -Lipschitz; addition and scalar multiplication are continuous (estimates $\norm{(x + y) - (x' + y')} \leq \norm{x - x'} + \norm{y - y'}$ , etc.).

Example 5.2

On $K^n$ :

\norm{x}_1 = \sum_i \abs{x_i}, \qquad \norm{x}_2 = \Bigl(\sum_i \abs{x_i}^2\Bigr)^{1/2}, \qquad \norm{x}_\infty = \max_i \abs{x_i}

( $\norm\cdot_2$ is a norm by Cauchy–Schwarz, Year 1 volume). On $C(\intcc{a}{b})$ :

\norm f_\infty = \sup \abs f, \qquad \norm f_1 = \int_a^b \abs f, \qquad \norm f_2 = \Bigl(\int_a^b \abs f^2\Bigr)^{1/2},

the last two being norms thanks to strict positivity of the integral and integral Cauchy–Schwarz (Year 1 volume). On matrices: any norm on $\mathcal M_n(K) \simeq K^{n^2}$ ; the operator norms below are the structurally important ones.

Definition 5.3 (Equivalent norms)

Two norms $N_1, N_2$ on $E$ are equivalent when there are constants $c, C > 0$ with

c\,N_1 \leq N_2 \leq C\, N_1 .

Equivalent norms have the same open sets, the same convergent and Cauchy sequences, the same compact and complete subsets: the same analysis.

Example 5.4 (Non-equivalence in infinite dimension)

On $C(\intcc{0}{1})$ : $\norm f_1 \leq \norm f_\infty$ always, but no reverse bound holds: $f_n(x) = x^n$ has $\norm{f_n}_\infty = 1$ and $\norm{f_n}_1 = \frac{1}{n+1} \to 0$ . So $f_n \to 0$ for $\norm\cdot_1$ but not for $\norm\cdot_\infty$ : the two norms disagree about convergence itself.

Example 5.5 (Explicit constants in dimension $n$ )

On $K^n$ the three classical norms are equivalent with sharp constants:

\norm x_\infty \leq \norm x_2 \leq \norm x_1 \leq \sqrt n\,\norm x_2 \leq n\,\norm x_\infty ,

the middle bound $\norm x_1 \leq \sqrt n\norm x_2$ coming from Cauchy–Schwarz against the all-ones vector. Extremal vectors: $e_1$ makes the first two inequalities equalities, $(1, 1, \dots, 1)$ the last two. The dimension $n$ sits visibly in the constants — the quantitative seed of the failure in infinite dimension: as $n \to \infty$ no uniform constant survives, which is exactly what Example 5.4 exhibits on function spaces.

The unit balls of the three classical norms of ℝ2, nested as the inequalities of dictate: smaller ball, larger norm. Roundness matters: the flat sides of the diamond and the square are exactly the failures of strict convexity exploited in ’s weekend problem and in this chapter’s (question 4). — The unit balls of the three classical norms of $\R^2$ , nested as the inequalities of Example 5.5 dictate: smaller ball, larger norm. Roundness matters: the flat sides of the diamond and the square are exactly the failures of strict convexity exploited in Chapter 8’s weekend problem and in this chapter’s (question 4).

5.2 Continuous linear maps

Theorem 5.6 (Characterization)

For a linear map $u \colon E \to F$ between normed spaces, the following are equivalent:

$u$ is continuous;
$u$ is continuous at $0$ ;
$u$ is bounded on the closed unit ball: $\sup_{\norm x \leq 1} \norm{u(x)} < \infty$ ;
there is $C \geq 0$ with $\norm{u(x)} \leq C \norm x$ for all $x$ ;
$u$ is Lipschitz.

The least such $C$ is the operator norm $\vertiii{u} = \sup_{\norm x \leq 1}\norm{u(x)} = \sup_{x \neq 0} \frac{\norm{u(x)}}{\norm x}$ ; it makes the space $\mathcal{L}_c(E, F)$ of continuous linear maps a normed space, with

\vertiii{v \circ u} \leq \vertiii v\, \vertiii u .

Proof. (1 $\Rightarrow$ 2) trivial. (2 $\Rightarrow$ 3): continuity at $0$ with $\varepsilon = 1$ gives $\delta$ with $\norm x \leq \delta \Rightarrow \norm{u(x)} \leq 1$ ; homogeneity then scales any $x$ with $\norm x \leq 1$ down into that ball and back:

\norm{u(x)} = \frac1\delta\,\norm{u(\delta x)} \leq \frac1\delta ,

since $\norm{\delta x} \leq \delta$ . (3 $\Rightarrow$ 4): for $x \neq 0$ , apply the bound to $\frac{x}{\norm x}$ . (4 $\Rightarrow$ 5): $\norm{u(x) - u(y)} = \norm{u(x - y)} \leq C\norm{x - y}$ . (5 $\Rightarrow$ 1) known.

Norm axioms for $\vertiii\cdot$ : homogeneity and separation are clear ( $\vertiii u = 0$ forces $u = 0$ on the ball, hence everywhere); triangle inequality from $\norm{(u + v)(x)} \leq \norm{u(x)} + \norm{v(x)}$ . Submultiplicativity: $\norm{v(u(x))} \leq \vertiii v\,\norm{u(x)} \leq \vertiii v \vertiii u \norm x$ . ∎

Example 5.7

On $\bigl(C(\intcc{0}{1}), \norm\cdot_\infty\bigr)$ : evaluation $f \mapsto f(0)$ has operator norm $1$ ; integration $f \mapsto \int_0^1 f$ has norm $1$ ; the map $f \mapsto \int_0^1 t f(t)\dd t$ has norm $\int_0^1 t\,\dd t = \frac12$ (upper bound by the triangle inequality for integrals; attained at $f \equiv 1$ ). But differentiation, from $(C^1, \norm\cdot_\infty)$ to $(C^0, \norm\cdot_\infty)$ , is not continuous: $\norm{\sin(nx)}_\infty = 1$ while the derivative has sup norm $n$ . Linear does not imply continuous in infinite dimension.

Example 5.8 (Two norms, two verdicts on one sequence)

On $C(\intcc01)$ , let $g_n(x) = \sqrt{n}\,x^n$ . Then

\norm{g_n}_1 = \frac{\sqrt n}{n + 1} \longrightarrow 0, \qquad \norm{g_n}_2^2 = \frac{n}{2n + 1} \longrightarrow \frac12, \qquad \norm{g_n}_\infty = \sqrt n \longrightarrow \infty :

one sequence, three norms, three behaviours — convergence to zero, no convergence (norms stabilize at $\frac1{\sqrt2}$ but the pointwise limit is $0$ ), and explosion. Mass concentrating near $x = 1$ is invisible to $\norm\cdot_1$ , half-visible to $\norm\cdot_2$ , dominant for $\norm\cdot_\infty$ . In infinite dimension, “does it converge?” is not a question about a sequence: it is a question about a sequence and a norm.

Method 5.9 (Computing an operator norm)

Always in two moves. Upper bound: estimate $\norm{u(x)}$ by $C\norm x$ using triangle inequalities, Cauchy–Schwarz, or integral bounds — this proves $\vertiii u \leq C$ . Witness: exhibit either a specific $x_0 \neq 0$ with $\norm{u(x_0)} = C\norm{x_0}$ (the bound is attained), or a sequence of unit vectors $x_n$ with $\norm{u(x_n)} \to C$ (the bound is approached). Both moves are mandatory: an upper bound alone gives only $\vertiii u \leq C$ , a witness alone only $\vertiii u \geq C$ . In infinite dimension the witness may have to be a sequence — the supremum need not be attained (Exercise 5.8).

Example 5.10 (Diagonal operators see every norm alike)

For $D = \operatorname{diag}(d_1, \dots, d_n)$ on $K^n$ with any of the norms $\norm\cdot_1, \norm\cdot_2, \norm\cdot_\infty$ : from $\abs{d_ix_i} \leq \bigl(\max_j\abs{d_j}\bigr)\abs{x_i}$ coordinatewise, $\norm{Dx} \leq \max_j\abs{d_j}\,\norm x$ ; and $x = e_{j_0}$ (a maximizing index) attains it. So $\vertiii D = \max_j\abs{d_j}$ in all three cases: for diagonal maps, all reasonable norms tell the same story, the largest stretch factor. Everything difficult about operator norms is about non-diagonal behaviour — which is why the adapted norms of this chapter’s weekend problem (question 22) work by forcing a matrix to become diagonal first.

Example 5.11 (Column sums: the $1$ -norm twin of Exercise 5.4)

On $(\R^n, \norm\cdot_1)$ , the operator norm of a matrix $A$ is the largest absolute column sum. Run the method: for $\norm x_1 \leq 1$ ,

\norm{Ax}_1 = \sum_i\Bigl|\sum_j a_{ij}x_j\Bigr| \leq \sum_j \abs{x_j}\sum_i\abs{a_{ij}} \leq \Bigl(\max_j\sum_i\abs{a_{ij}}\Bigr)\norm x_1 ,

and the bound is attained at $x = e_{j_0}$ for a maximizing column $j_0$ — the tidiest witness imaginable. So for $A = \left(\begin{smallmatrix}1 & -2\\ 3 & 1\end{smallmatrix}\right)$ : $\vertiii A_1 = \max(1 + 3,\ 2 + 1) = 4$ , while $\vertiii A_\infty = 4$ too (rows) — a coincidence here, not a law: transpose the matrix entries asymmetrically and the two norms part company. Rows for $\norm\cdot_\infty$ , columns for $\norm\cdot_1$ : the mnemonic is that each norm’s unit vectors (sign patterns, resp. basis vectors) pick out the matching sums.

Proposition 5.12 (Bilinear maps)

A bilinear map $b \colon E \times F \to G$ is continuous iff $\norm{b(x,y)} \leq C\norm x\,\norm y$ for some $C$ ; then it is Lipschitz on bounded sets. (Same proof pattern; the product $(u, v) \mapsto v \circ u$ and matrix multiplication are the key examples.)

Proof. If the bound holds:

b(x,y) - b(x_0,y_0) = b(x - x_0,\, y) + b(x_0,\, y - y_0),

so $\norm{b(x,y) - b(x_0,y_0)} \leq C\norm{x - x_0}\norm y + C\norm{x_0}\norm{y - y_0}$ : continuity at $(x_0, y_0)$ , and a Lipschitz bound where $\norm x, \norm y \leq R$ . Conversely, continuity at $(0,0)$ gives $\delta$ with $\norm{b(x,y)} \leq 1$ on $\norm x, \norm y \leq \delta$ ; scale both variables. ∎

5.3 Finite dimension

Theorem 5.13 (Equivalence of norms in finite dimension)

On a finite-dimensional space, all norms are equivalent. Consequently, in finite dimension: convergence, openness, compactness, completeness are norm-independent notions; compact $=$ closed and bounded; the space is complete; and every linear (or multilinear) map from a finite-dimensional space is continuous.

Proof. Fix a basis and identify $E \simeq K^n$ ; it suffices to compare any norm $N$ with $\norm\cdot_\infty$ .

One direction is algebra: $N(x) = N(\sum x_i e_i) \leq \sum \abs{x_i} N(e_i) \leq C \norm x_\infty$ with $C = \sum N(e_i)$ . This also shows $N$ is continuous on $(K^n, \norm\cdot_\infty)$ (it is $C$ -Lipschitz: $\abs{N(x) - N(y)} \leq N(x - y)$ ).

The other is topology: the unit sphere $S = \{x : \norm{x}_\infty = 1\}$ is closed and bounded in $(K^n, \norm\cdot_\infty)$ , hence compact (Theorem 4.16 (2), valid for $\C^n \simeq \R^{2n}$ ). The continuous function $N$ attains its minimum $c$ on $S$ ; $c > 0$ since $N$ vanishes only at $0 \notin S$ . Homogeneity spreads the bound: $N(x) \geq c \norm{x}_\infty$ for all $x$ .

Consequences: all statements reduce to $(K^n, \norm\cdot_\infty)$ , where they are known (Theorem 4.9, Theorem 4.16); a linear $u$ from finite-dimensional $E$ satisfies $\norm{u(x)} \leq \sum\abs{x_i} \norm{u(e_i)} \leq C'\norm{x}_\infty$ : bound (4) of Theorem 5.6. ∎

Corollary 5.14

A finite-dimensional subspace of any normed space is closed.

Proof. It is complete for the induced norm (Theorem 5.13), and complete subsets are closed (Definition 4.7). ∎

Example 5.15 (A best approximation computed by symmetry)

In $\bigl(C(\intcc{-1}{1}), \norm\cdot_\infty\bigr)$ , how far is $f(x) = \abs x$ from the (closed, two-dimensional) subspace of affine functions $a + bx$ ? By symmetry, replacing $a + bx$ by $a - bx$ leaves $\norm{f - (a \pm bx)}_\infty$ unchanged, and the midpoint $a$ does at least as well (triangle inequality on the average): it suffices to consider constants. For a constant $a$ :

\norm{\abs x - a}_\infty = \max\,(1 - a,\ a) \geq \frac12 ,

minimized at $a = \frac12$ : the distance is $\frac12$ , attained by the constant $\frac12$ . Note the error curve $\abs x - \frac12$ : it reaches $\pm\frac12$ alternately at $x = -1, 0, 1$ — three extrema of alternating sign for a best approximation from a two-parameter family. That equioscillation pattern is no accident; it is the signature of optimality that this chapter’s weekend problem turns into Chebyshev’s theorem.

Example 5.16 (Closed versus dense subspaces)

In $E = \bigl(C(\intcc{0}{1}), \norm\cdot_\infty\bigr)$ : each $\R_n[X]$ (polynomials of degree $\leq n$ , restricted to $\intcc01$ ) is a finite-dimensional, hence closed, subspace — a uniform limit of polynomials of degree $\leq n$ is one. But the union $\R[X]$ of all of them is dense in $E$ (the Weierstrass approximation theorem, proved in Chapter 10), and dense proper subspaces are as non-closed as can be. The moral: closedness of subspaces is a finite-dimensional privilege; stacking closed floors can build a dense skyscraper.

Theorem 5.17 (Riesz)

The closed unit ball of a normed space $E$ is compact if and only if $\dim E < \infty$ .

Proof. Finite dimension: closed and bounded suffices (Theorem 5.13).

Conversely, suppose $\dim E = \infty$ . Riesz’s lemma: for every proper closed subspace $F \subsetneq E$ and $\varepsilon \in \intoo{0}{1}$ , there is a unit vector $x$ with $d(x, F) \geq 1 - \varepsilon$ . Proof: pick $y \notin F$ , let $\delta = d(y, F) > 0$ ( $F$ closed), choose $f \in F$ with $\norm{y - f} \leq \frac{\delta}{1 - \varepsilon}$ , and set $x = \frac{y - f}{\norm{y - f}}$ : for any $g \in F$ ,

\norm{x - g} = \frac{\norm{y - (f + \norm{y-f}\,g)}}{\norm{y - f}} \geq \frac{\delta}{\norm{y-f}} \geq 1 - \varepsilon ,

the numerator being a distance from $y$ to a point of $F$ .

Now build unit vectors $x_1, x_2, \dots$ inductively: $F_k = \operatorname{Vect}(x_1, \dots, x_k)$ is finite-dimensional, hence closed (Corollary 5.14) and proper; Riesz’s lemma with $\varepsilon = \frac12$ provides a unit $x_{k+1}$ with $d(x_{k+1}, F_k) \geq \frac12$ . The sequence satisfies $\norm{x_p - x_q} \geq \frac12$ for $p \neq q$ : no convergent subsequence — the unit ball is not compact. ∎

Example 5.18 (Riesz as a dimension detector)

Is $C(\intcc01)$ finite-dimensional? Riesz answers without exhibiting any explicit infinite free family: the sequence $f_n(x) = x^n$ lies in the closed unit ball and satisfies, for $m > n$ , $\norm{f_n - f_m}_\infty \geq f_n(x_0) - f_m(x_0) > 0$ at suitable points — quantified cleanly in this chapter’s weekend problem (question 16), where a subsequence stays at mutual distance $\geq \frac14$ . No convergent subsequence, so the ball is not compact, so $\dim C(\intcc01) = \infty$ by Theorem 5.17. Compactness of the unit ball is a perfect dichotomy: it holds in finite dimension, fails in infinite dimension, with no middle ground — geometry alone reads off the dimension type.

5.4 Banach spaces

Definition 5.19

A Banach space is a complete normed space. Examples: every finite-dimensional normed space (Theorem 5.13); $\bigl(C(\intcc{a}{b}), \norm\cdot_\infty\bigr)$ (Theorem 4.9); $\mathcal{L}_c(E, F)$ for $F$ Banach (same proof pattern as for continuous functions). Non-example: $\bigl(C(\intcc{0}{1}), \norm\cdot_1\bigr)$ (Exercise 5.7).

Example 5.20 (The operator norm of integration)

On $\bigl(C(\intcc01), \norm\cdot_\infty\bigr)$ , let $T(f)(x) = \int_0^x f(t)\,\dd t$ (an endomorphism: $T(f)$ is continuous). Run Method 5.9. Upper bound:

\abs{T(f)(x)} \leq \int_0^x\abs f \leq x\,\norm f_\infty \leq \norm f_\infty ,

so $\vertiii T \leq 1$ . Witness: $f \equiv 1$ gives $T(f)(x) = x$ and $\norm{T(f)}_\infty = 1 = \norm f_\infty$ : attained, $\vertiii T = 1$ . But note $\vertiii{T^2} = \frac12 \neq \vertiii T^2$ : indeed $T^2(f)(x) = \int_0^x(x - t)f(t)\dd t$ has $\abs{T^2(f)(x)} \leq \frac{x^2}2\norm f_\infty$ , attained again at $f \equiv 1$ ; and generally $\vertiii{T^n} = \frac1{n!}$ — the submultiplicative bound $\vertiii T^n = 1$ is off by a factorial. This is exactly the phenomenon the iterate trick of Chapter 4’s weekend problem converts into global solvability of linear differential equations.

Theorem 5.21 (Absolute convergence in Banach spaces)

In a Banach space, if $\sum \norm{u_n} < \infty$ then $\sum u_n$ converges, and $\norm{\sum u_n} \leq \sum\norm{u_n}$ . (The full theory of series in normed spaces is Chapter 7.)

Proof. Partial sums $S_N$ : for $q > p$ , $\norm{S_q - S_p} \leq \sum_{n=p+1}^{q}\norm{u_n}$ , which tends to $0$ (Cauchy criterion for the real series of norms): $(S_N)$ is Cauchy, hence convergent. The inequality passes to the limit from the finite triangle inequality. ∎

Example 5.22 (Matrix exponential, first contact)

The matrix exponential: $\mathcal{M}_n(K)$ with any submultiplicative norm ( $\vertiii{AB} \leq \vertiii A \vertiii B$ ) is Banach (finite dimension). Then, for every $A$ ,

\eu^A = \sum_{k=0}^{\infty} \frac{A^k}{k!}

converges absolutely ( $\vertiii{A^k/k!} \leq \vertiii A^k /k!$ , summable): well defined. Chapter 16 exploits it systematically.

Example 5.23 (A Neumann series that terminates)

For $A = \left(\begin{smallmatrix}0 & \frac12\\ 0 & 0\end{smallmatrix}\right)$ : $\vertiii A < 1$ in any operator norm built on Example 5.2’s norms, and $A^2 = 0$ , so the geometric series collapses:

(I - A)^{-1} = \sum_{k \geq 0} A^k = I + A = \begin{pmatrix}1 & \tfrac12\\ 0 & 1\end{pmatrix},

verified by $(I - A)(I + A) = I - A^2 = I$ . Nilpotency truncates the series exactly as it truncated the exponential in Chapter 3; and the example calibrates expectations: the Neumann inverse is an infinite series in general, a polynomial precisely when the perturbation is nilpotent, and the error after $N$ terms is always bounded by the geometric tail $\vertiii A^{N+1}/(1 - \vertiii A)$ .

Example 5.24 (The exponential of a rotation generator)

Take $A = \left(\begin{smallmatrix}0 & -\theta\\ \theta & 0\end{smallmatrix}\right)$ . Then $A^2 = -\theta^2 I$ , so the powers cycle with period four, and the series splits into even and odd parts:

\eu^{A} = \sum_{k}\frac{A^k}{k!} = \Bigl(\sum_{j}\frac{(-1)^j\theta^{2j}}{(2j)!}\Bigr) I + \Bigl(\sum_{j}\frac{(-1)^j\theta^{2j+1}}{(2j+1)!}\Bigr) \frac{A}{\theta} = \begin{pmatrix} \cos\theta & -\sin\theta\\ \sin\theta & \cos\theta \end{pmatrix},

all rearrangements being licensed by absolute convergence. The exponential of an antisymmetric generator is a rotation — computed here purely from the series, three chapters before the differential equation $x' = Ax$ (Chapter 16) explains why: $\eu^{tA}$ is uniform circular motion. The closing insight: identities among matrix series are proved exactly like scalar ones, once a submultiplicative norm certifies absolute convergence.

Example 5.25 (Sup norm means uniform: the dictionary)

The statement $\norm{f_n - f}_\infty \to 0$ is uniform convergence: one number, $\sup_x\abs{f_n(x) - f(x)}$ , bounds the error at every point simultaneously. The dictionary in action on $f_n(x) = x^n$ over $\intcc{0}{1}$ : pointwise, $f_n \to 0$ on $\intco{0}{1}$ and $f_n(1) = 1$ ; in norm, $\norm{f_n - 0}_\infty = 1 \not\to 0$ , and indeed the pointwise limit is discontinuous, hence out of reach of a $\norm\cdot_\infty$ -limit in $C(\intcc01)$ (which is closed under uniform limits, Theorem 4.9). On $\intcc{0}{a}$ , $a < 1$ : $\norm{f_n}_\infty = a^n \to 0$ — uniform convergence restored by shrinking the domain. Every convergence statement of Chapter 10 is a statement about this one norm; keeping the dictionary in mind halves that chapter.

Remark 5.26 (Common pitfalls)

(i) An operator norm depends on both chosen norms: the same matrix has $\vertiii\cdot_\infty$ given by row sums (Exercise 5.4) and a different $\vertiii\cdot_1$ (column sums); quoting “the” norm of a matrix without naming the underlying norms is meaningless. (ii) $\vertiii{AB} \leq \vertiii A\,\vertiii B$ is an inequality, usually strict — powers can shrink much faster than the bound $\vertiii A^k$ suggests, which is the whole point of adapted norms (this chapter’s weekend problem, question 22). (iii) “Linear implies continuous” is a finite-dimensional privilege: differentiation on polynomials is linear and unbounded (Example 5.7). (iv) Absolute convergence of $\sum u_n$ only helps when the space is complete (Exercise 7.9 builds the counterexample). (v) In infinite dimension a supremum over the unit ball is a genuine supremum: do not assume it is attained (Exercise 5.8).

Remark 5.27 (Perspectives within this volume)

Three appointments are now fixed. With Chapter 7: in a Banach space, absolutely convergent series converge, so the geometric and exponential series of operators become everyday tools — inverting $I - A$ , defining $\eu^{A}$ (Example 7.2). With Chapter 10 and Chapter 11: convergence of function sequences and power series is convergence in $\bigl(C, \norm\cdot_\infty\bigr)$ (Example 5.25), and the radius of convergence is a statement about which geometric series dominate. With Chapter 14: the norms $\norm\cdot_2$ and $\norm\cdot_\infty$ genuinely disagree on $C(\intcc{0}{1})$ (Example 5.8), which is exactly why mean-square convergence of Fourier series and uniform convergence are two different theorems with two different prices.

Remark 5.28 (Where this chapter is used)

Operator norms and the geometric series drive the perturbation arguments of Chapter 15 (inverse function theorem) and the matrix exponential of Chapter 16; equivalence of norms silently authorizes every “choose your favourite norm” argument in Chapter 10 and beyond; and the finite/infinite divide of Riesz’s theorem — made quantitative in this chapter’s weekend problem — is the reason the Year 3 volume needs new tools (weak convergence, Arzelà–Ascoli, Hilbert space projections) where this volume could still extract convergent subsequences.

5.5 Exercises

Exercise 5.1 ★

On $\R^2$ , draw the unit balls of $\norm\cdot_1$ , $\norm\cdot_2$ , $\norm\cdot_\infty$ , and prove the inequalities $\norm x_\infty \leq \norm x_2 \leq \norm x_1 \leq 2\norm x_\infty$ with the best constants in dimension $2$ .

Solution

Solution of Exercise 5.1.

Unit balls: a diamond ( $\norm\cdot_1$ ), a disk ( $\norm\cdot_2$ ), a square ( $\norm\cdot_\infty$ ), nested in that order. Inequalities: $\norm x_\infty \leq \norm x_2$ (one square is at most the sum); $\norm x_2 \leq \norm x_1$ (squaring: $x_1^2 + x_2^2 \leq (\abs{x_1} + \abs{x_2})^2$ ); $\norm x_1 \leq 2\norm x_\infty$ (two terms, each $\leq \max$ ). Sharpness: $(1, 0)$ makes the first two equalities; $(1, 1)$ makes $\norm x_1 = 2\norm x_\infty$ and also shows $\norm x_2 = \sqrt2 \norm x_\infty$ and $\norm x_1 = \sqrt2 \norm x_2$ are the extreme ratios in the other direction.

Exercise 5.2 ★

Is $N(f) = \abs{f(0)} + \norm{f'}_\infty$ a norm on $C^1(\intcc{0}{1})$ ? Compare it with $\norm{f}_\infty$ : one inequality holds, the other fails (exhibit).

Solution

Solution of Exercise 5.2.

Norm axioms: homogeneity and triangle inequality are inherited termwise; separation: $N(f) = 0$ forces $f' = 0$ (so $f$ constant) and $f(0) = 0$ : $f = 0$ . It is a norm.

Comparison: $\norm f_\infty \leq N(f)$ , since $\abs{f(x)} \leq \abs{f(0)} + \abs{\int_0^x f'} \leq \abs{f(0)} + \norm{f'}_\infty$ . The converse fails: take $f_n(x) = \frac1n \sin(nx)$ : then $\norm{f_n}_\infty \leq \frac1n \to 0$ while $N(f_n) = 0 + \norm{\cos(nx)}_\infty = 1$ . No constant $C$ gives $N \leq C\norm\cdot_\infty$ .

Exercise 5.3 ★

Compute the operator norm of $u(f) = \int_0^1 f(t)\,\eu^t\,\dd t$ on $\bigl(C(\intcc{0}{1}), \norm\cdot_\infty\bigr) \to \R$ , and of the shift $S(x_1, x_2, \dots, x_n) = (x_2, \dots, x_n, 0)$ on $(K^n, \norm\cdot_\infty)$ .

Solution

Solution of Exercise 5.3.

$\abs{u(f)} \leq \norm f_\infty \int_0^1 \eu^t\,\dd t = (\eu - 1)\norm f_\infty$ , with equality for $f \equiv 1$ : $\vertiii u = \eu - 1$ .

Shift: $\norm{S(x)}_\infty = \max(\abs{x_2}, \dots, \abs{x_n}) \leq \norm x_\infty$ , equality at $x = e_2$ : $\vertiii S = 1$ (for $n \geq 2$ ).

Exercise 5.4 ★★

On $(\R^n, \norm\cdot_\infty)$ , prove that the operator norm of a matrix $A$ is $\vertiii A_\infty = \max_i \sum_j \abs{a_{ij}}$ (the largest absolute row sum). Compute it for $\begin{pmatrix} 1 & -2\\ 3 & 1\end{pmatrix}$ .

Solution

Solution of Exercise 5.4.

Upper bound: for $\norm x_\infty \leq 1$ ,

\abs{(Ax)_i} = \Bigl|\sum_j a_{ij}x_j\Bigr| \leq \sum_j \abs{a_{ij}},

so $\norm{Ax}_\infty \leq \max_i \sum_j \abs{a_{ij}}$ . Attained: let $i_0$ realize the max and take $x_j = \operatorname{sign}(a_{i_0 j})$ (modulus $1$ entries): then $(Ax)_{i_0} = \sum_j \abs{a_{i_0 j}}$ . Hence the formula. For the given matrix: row sums $3$ and $4$ : $\vertiii A_\infty = 4$ .

Exercise 5.5 ★★

Prove that $GL_n(K)$ is open in $\mathcal{M}_n(K)$ and that $A \mapsto A^{-1}$ is continuous on it. Hint: for openness, if $\vertiii H < \frac{1}{\vertiii{A^{-1}}}$ then $A + H = A(I + A^{-1}H)$ with $\vertiii{A^{-1}H} < 1$ , and $I + B$ is invertible for $\vertiii B < 1$ by the geometric series (Theorem 5.21); for continuity, bound $(A+H)^{-1} - A^{-1}$ using the same series.

Solution

Solution of Exercise 5.5.

Geometric series: for $\vertiii B < 1$ , the series $\sum B^k$ converges absolutely in the Banach $\mathcal{M}_n(K)$ (Theorem 5.21, $\vertiii{B^k} \leq \vertiii B^k$ ), and

(I - B)\sum_{k=0}^{K} B^k = I - B^{K+1} \longrightarrow I :

by continuity of the product (Proposition 5.12), $(I - B)\sum_{k\geq0} B^k = I$ , so $I - B$ is invertible with inverse the sum (and $\vertiii{(I-B)^{-1}} \leq \frac{1}{1 - \vertiii B}$ ).

Openness: for $A$ invertible and $\vertiii H < \frac{1}{\vertiii{A^{-1}}}$ : $A + H = A(I + A^{-1}H)$ with $\vertiii{A^{-1}H} \leq \vertiii{A^{-1}}\vertiii H < 1$ : invertible. So a ball around $A$ stays in $GL_n$ .

Continuity of inversion: with $B = -A^{-1}H$ ,

(A + H)^{-1} - A^{-1} = \bigl((I - B)^{-1} - I\bigr)A^{-1} = \Bigl(\sum_{k \geq 1} B^k\Bigr) A^{-1},

of norm $\leq \frac{\vertiii B}{1 - \vertiii B}\vertiii{A^{-1}} \to 0$ as $H \to 0$ .

Exercise 5.6 ★★

Let $\varphi$ be a linear form on a normed space $E$ . Prove that $\varphi$ is continuous if and only if $\ker\varphi$ is closed. (If $\ker\varphi$ is closed and $\varphi \neq 0$ , pick $a$ with $\varphi(a) = 1$ and $r > 0$ with $B(a, r) \cap \ker\varphi = \emptyset$ ; deduce $\abs{\varphi(h)} \leq \frac{1}{r}\norm h$ by a scaling argument on $a - \frac{h}{\varphi(h)}$ .)

Solution

Solution of Exercise 5.6.

Continuous $\Rightarrow$ closed kernel: preimage of the closed $\{0\}$ (Theorem 4.6).

Conversely, suppose $\ker\varphi$ closed and $\varphi \neq 0$ . Pick $a$ with $\varphi(a) = 1$ ; since $a \notin \ker\varphi$ and the kernel is closed, some ball $B(a, r)$ misses it. Now let $h \in E$ with $\varphi(h) \neq 0$ : the vector $a - \frac{h}{\varphi(h)}$ lies in $\ker\varphi$ , hence outside $B(a, r)$ :

\Bigl\Vert \frac{h}{\varphi(h)} \Bigr\Vert \geq r \quad\Longrightarrow\quad \abs{\varphi(h)} \leq \frac{\norm h}{r},

an inequality trivially true when $\varphi(h) = 0$ as well: bound (4) of Theorem 5.6: continuous.

Exercise 5.7 ★★

Prove that $\bigl(C(\intcc{0}{1}), \norm\cdot_1\bigr)$ is not complete: show that the functions $f_n$ , affine ramps from $0$ to $1$ over $\bigl[\frac12 - \frac1n, \frac12\bigr]$ (value $0$ before, $1$ after), form a Cauchy sequence with no continuous $\norm\cdot_1$ -limit.

Solution

Solution of Exercise 5.7.

Let $f_n$ be $0$ on $\intcc{0}{\frac12 - \frac1n}$ , affine up to value $1$ at $\frac12$ , then $1$ on $\intcc{\frac12}{1}$ . For $m \geq n$ , $f_m - f_n$ is supported on an interval of length $\frac1n$ with values in $\intcc{-1}{1}$ : $\norm{f_m - f_n}_1 \leq \frac1n$ : Cauchy.

Suppose $f_n \to f$ in $\norm\cdot_1$ with $f$ continuous. On $\intcc{0}{\frac12 - \delta}$ (fixed $\delta$ ): $\int \abs{f} = \int\abs{f - f_n} \leq \norm{f - f_n}_1 \to 0$ for $n > \frac1\delta$ , so $\int_0^{1/2 - \delta}\abs f = 0$ , and by strict positivity $f = 0$ there — for every $\delta$ : $f = 0$ on $\intoo{0}{\frac12}$ . Similarly $f = 1$ on $\intcc{\frac12}{1}$ (the $f_n$ all equal $1$ there). By continuity at $\frac12$ : $0 = 1$ , absurd. No limit exists: the space is not complete.

Exercise 5.8 ★★★

On $E = C(\intcc{0}{1})$ with $\norm\cdot_\infty$ , consider

\varphi(f) = \sum_{n \geq 1} (-1)^n\, 2^{-n} f\bigl(\tfrac1n\bigr).

Prove that $\varphi$ is a well-defined continuous linear form with $\vertiii\varphi = 1$ , but that the supremum defining $\vertiii\varphi$ is not attained on the closed unit ball. (Upper bound: triangle inequality. Norm $= 1$ : build continuous $f_K$ with $\norm{f_K}_\infty \leq 1$ and $f_K(\frac1n) = (-1)^n$ for $n \leq K$ — the points $\frac1n$ are isolated from each other. Non-attainment: equality would force $f(\frac1n) = (-1)^n$ for every $n$ , incompatible with continuity of $f$ at $0$ since $\frac1n \to 0$ .)

Solution

Solution of Exercise 5.8.

Well defined and continuous: $\abs{\varphi(f)} \leq \sum 2^{-n} \norm f_\infty = \norm f_\infty$ , so $\varphi$ is a linear form with $\vertiii\varphi \leq 1$ (the series converges absolutely for each $f$ ).

Norm $1$ : fix $K$ ; the points $1, \frac12, \dots, \frac1K$ are pairwise distinct, so there is a continuous $f_K$ , $\norm{f_K}_\infty \leq 1$ , with $f_K(\frac1n) = (-1)^n$ for $n \leq K$ (piecewise affine interpolation, constant near $0$ ). Then

\varphi(f_K) \geq \sum_{n=1}^{K} 2^{-n} - \sum_{n > K} 2^{-n} = 1 - 2^{-K+1} \xrightarrow[K \to \infty]{} 1 .

Not attained: if $\norm f_\infty \leq 1$ and $\varphi(f) = 1$ , each term must contribute its maximum: $(-1)^n f(\frac1n) = 1$ for every $n$ (otherwise the strict deficit of one term cannot be compensated, all terms being $\leq 2^{-n}$ ). So $f(\frac1n) = (-1)^n$ ; but $\frac1n \to 0$ and $f$ is continuous at $0$ , forcing the contradictory convergence of $(-1)^n$ . Hence the supremum is not a maximum — impossible in finite dimension, where the closed unit ball is compact.

Exercise 5.9 ★★★

Let $E$ be a normed space in which the closed unit ball is compact. Re-derive, without quoting Theorem 5.17, that every bounded sequence has a convergent subsequence, and prove that every linear form on $E$ is continuous if and only if $\dim E < \infty$ . (For infinite dimension, build a discontinuous form by defining it freely on a linearly independent normalized sequence and extending — admitting the existence of an algebraic complement.)

Solution

Solution of Exercise 5.9.

Bounded sequences: a bounded sequence lies in some closed ball $\overline B(0, R) = R\,\overline B(0,1)$ , compact (image of the compact unit ball under the homeomorphism $x \mapsto Rx$ ): extract there.

Linear forms: if $\dim E < \infty$ , every linear map from $E$ is continuous (Theorem 5.13). Conversely, suppose $\dim E = \infty$ (which, by Theorem 5.17, is actually excluded by the compactness hypothesis — the point of this question is the implication between the two properties in general normed spaces): choose a normalized linearly independent sequence $(e_n)$ , complete it into an algebraic basis (admitted), and define $\varphi(e_n) = n$ , $\varphi = 0$ on the other basis vectors, extended linearly. Then $\abs{\varphi(e_n)} = n$ with $\norm{e_n} = 1$ : unbounded on the unit ball, discontinuous. So “all forms continuous” forces finite dimension.

Exercise 5.10 ★★

On $C(\intcc{0}{1})$ , prove $\norm f_1 \leq \norm f_2 \leq \norm f_\infty$ (Cauchy–Schwarz for the first), and show with the family $f_n(x) = x^n$ that neither inequality can be reversed up to a constant: the three norms are pairwise non-equivalent.

Solution

Solution of Exercise 5.10.

Cauchy–Schwarz with the constant function $1$ : $\norm f_1 = \int_0^1 \abs f\cdot 1 \leq \bigl(\int_0^1 f^2\bigr)^{1/2}\bigl(\int_0^1 1\bigr)^{1/2} = \norm f_2$ . And $\norm f_2^2 = \int f^2 \leq \norm f_\infty^2$ . For $f_n(x) = x^n$ :

\norm{f_n}_1 = \frac1{n+1}, \qquad \norm{f_n}_2 = \frac1{\sqrt{2n+1}}, \qquad \norm{f_n}_\infty = 1 .

Then $\norm{f_n}_2/\norm{f_n}_1 = \frac{n+1}{\sqrt{2n+1}} \to \infty$ and $\norm{f_n}_\infty/\norm{f_n}_2 = \sqrt{2n+1} \to \infty$ : no reverse inequalities, no pair is equivalent.

Exercise 5.11 ★★

(Distance to a hyperplane) Let $\varphi$ be a nonzero continuous linear form on a normed space $E$ . Prove that

d\bigl(x, \ker\varphi\bigr) = \frac{\abs{\varphi(x)}}{\vertiii\varphi} \qquad (x \in E),

and check on Exercise 5.8 that the infimum need not be attained by any point of the hyperplane.

Solution

Solution of Exercise 5.11.

Lower bound for the distance: for $h \in \ker\varphi$ , $\abs{\varphi(x)} = \abs{\varphi(x - h)} \leq \vertiii\varphi\,\norm{x - h}$ ; take the infimum over $h$ : $d(x, \ker\varphi) \geq \abs{\varphi(x)}/\vertiii\varphi$ .

Upper bound: we may assume $\varphi(x) \neq 0$ . Given $\varepsilon > 0$ , pick a unit $u$ with $\abs{\varphi(u)} \geq \vertiii\varphi - \varepsilon > 0$ and set $h = x - \frac{\varphi(x)}{\varphi(u)}\,u$ : then $\varphi(h) = 0$ and

\norm{x - h} = \frac{\abs{\varphi(x)}}{\abs{\varphi(u)}} \leq \frac{\abs{\varphi(x)}}{\vertiii\varphi - \varepsilon}.

Let $\varepsilon \to 0$ : $d(x, \ker\varphi) \leq \abs{\varphi(x)}/\vertiii\varphi$ ; equality.

Non-attainment: take $\varphi$ from Exercise 5.8 ( $\vertiii\varphi = 1$ , not attained) and any $x$ with $\varphi(x) \neq 0$ . If some $h \in \ker\varphi$ realized $\norm{x - h} = \abs{\varphi(x)}$ , the unit vector $v = (x - h)/\norm{x - h}$ would satisfy $\abs{\varphi(v)} = \abs{\varphi(x)}/\norm{x - h} = 1 = \vertiii\varphi$ : the operator norm would be attained — contradiction.

Exercise 5.12 ★★★

On $E = \R[X]$ (all polynomials), let $N_1(P) = \sup_{\intcc{0}{1}}\abs P$ and $N_2(P) = \sup_{\intcc{0}{2}}\abs P$ . Show that $N_1 \leq N_2$ but that $N_1$ and $N_2$ are not equivalent; deduce that the identity $(E, N_2) \to (E, N_1)$ is a continuous linear bijection whose inverse is discontinuous. Show finally that $(E, N_1)$ is not complete (Taylor partial sums of $\eu^x$ ). All three phenomena are impossible in finite dimension — say why.

Solution

Solution of Exercise 5.12.

$N_1 \leq N_2$ is monotonicity of the sup in the domain, so the identity $(E, N_2) \to (E, N_1)$ is $1$ -Lipschitz. For $P_n(x) = (x/2)^n$ : $N_2(P_n) = 1$ (attained at $x = 2$ ) while $N_1(P_n) = 2^{-n}$ : a bound $N_2 \leq CN_1$ would give $1 \leq C2^{-n}$ for all $n$ : impossible. So the norms are not equivalent and the inverse identity is a discontinuous linear bijection.

Incompleteness: let $S_n = \sum_{k=0}^{n}\frac{X^k}{k!}$ . For $m > n$ , $N_1(S_m - S_n) \leq \sum_{k>n}\frac1{k!} \to 0$ : Cauchy for $N_1$ . If $S_n \to P$ in $(E, N_1)$ , then pointwise $P(x) = \lim S_n(x) = \eu^x$ on $\intcc{0}{1}$ ; but a polynomial of degree $d$ cannot equal $\eu^x$ on an interval (differentiate $d + 1$ times: the left side dies, $\eu^x$ does not). No limit in $E$ : not complete.

In finite dimension all three phenomena are impossible: all norms are equivalent, every normed space is complete, and the inverse of a linear bijection is linear from a finite-dimensional space, hence continuous (Theorem 5.13).

5.6 Problem: Best Approximation and Chebyshev’s Theorem

How well can a function be approximated by polynomials of a given degree, and which polynomial does it best? On the existence side, the answer belongs to this chapter: compactness in finite dimension makes best approximations exist. On the explicit side, one nontrivial case can be solved completely with bare hands — among all monic polynomials of degree $n$ , the one of smallest sup norm on $\intcc{-1}{1}$ is the (normalized) Chebyshev polynomial, of norm $2^{1-n}$ : Chebyshev’s extremal theorem. The problem proves both sides, then measures how badly compactness fails in infinite dimension: the unit ball of $C(\intcc{0}{1})$ contains infinite constellations of points at mutual distance $1$ .

Problem 5.1

Weekend problem — Chebyshev’s extremal theorem and the geometry of the unit ball

Norms without subscript are sup norms on the indicated segment.

Part I — Best approximation in normed spaces.

Let $F$ be a finite-dimensional subspace of a normed space $E$ and $x \in E$ . Prove that the distance $d(x, F) = \inf_{f \in F}\norm{x - f}$ is attained (reduce to a closed bounded subset of $F$ and use Theorem 5.13).
A norm is strictly convex when $\norm u = \norm v = 1$ and $u \neq v$ imply $\bigl\Vert\frac{u + v}2\bigr\Vert < 1$ . Show that $\norm\cdot_2$ on $\R^n$ is strictly convex (parallelogram identity), and that $\norm\cdot_1$ and $\norm\cdot_\infty$ are not for $n \geq 2$ .
Prove that for a strictly convex norm, the best approximation of question 1 is unique.
In $(\R^2, \norm\cdot_\infty)$ , compute all best approximations of $x = (0, 1)$ by the line $F = \operatorname{Vect}\bigl((1,0)\bigr)$ : an interval of minimizers.
In $\bigl(C(\intcc{a}{b}), \norm\cdot_\infty\bigr)$ , show that the best approximation of $f$ by constants is unique, equal to $c^* = \frac{\max f + \min f}{2}$ , with distance $\frac{\max f - \min f}{2}$ ; compute both for $f(x) = x^2$ on $\intcc{0}{1}$ .

Part II — Chebyshev polynomials.

Show there is exactly one polynomial $T_n$ with $T_n(\cos\theta) = \cos n\theta$ for all $\theta$ (recurrence $T_{n+1} = 2XT_n - T_{n-1}$ from the cosine addition formula), that $\deg T_n = n$ , and that its leading coefficient is $2^{n-1}$ for $n \geq 1$ .
Show $\abs{T_n} \leq 1$ on $\intcc{-1}{1}$ , with $T_n(\eta_k) = (-1)^k$ at the $n + 1$ points $\eta_k = \cos\frac{k\pi}{n}$ ( $k = 0, \dots, n$ ), and that the roots of $T_n$ are the $n$ points $\cos\frac{(2k-1)\pi}{2n}$ , interlacing the $\eta_k$ .
Compute $T_2, T_3, T_4$ , and verify the alternation of $T_3$ at $\eta_0, \dots, \eta_3 = 1, \frac12, -\frac12, -1$ by direct evaluation.
For $\abs x \geq 1$ , prove

$T_n(x) = \frac{\bigl(x + \sqrt{x^2 - 1}\bigr)^n + \bigl(x - \sqrt{x^2 - 1}\bigr)^n}{2},$

and deduce $T_n(x) \sim \frac12\bigl(x + \sqrt{x^2 - 1}\bigr)^n \to \infty$ geometrically for fixed $x > 1$ .
Prove the composition law $T_m \circ T_n = T_{mn}$ (check on $\intcc{-1}{1}$ and invoke the rigidity of polynomials).

Part III — Chebyshev’s extremal theorem. Write $Q_n = 2^{1-n}T_n$ (monic, by question 6).

Let $P$ be monic of degree $n \geq 1$ with $\sup_{\intcc{-1}{1}}\abs P < 2^{1-n}$ . By evaluating $D = Q_n - P$ at the points $\eta_k$ and counting sign changes, derive a contradiction. Conclude:

$\sup_{\intcc{-1}{1}}\abs P \;\geq\; 2^{1-n} \qquad\text{for every monic } P \text{ of degree } n.$
(Equality case) Suppose $\sup_{\intcc{-1}{1}}\abs P = 2^{1-n}$ with $P$ monic of degree $n$ , and let $D = Q_n - P \neq 0$ . Show $(-1)^kD(\eta_k) \geq 0$ for all $k$ ; show that each of the $n$ intervals $\intcc{\eta_{k}}{\eta_{k-1}}$ contains a zero of $D$ , and that a zero shared by two consecutive intervals is an interior point $\eta_k$ where $D' = 0$ as well. Conclude that $D$ has $n$ zeros counted with multiplicity, hence $D = 0$ : the minimizer is exactly $Q_n$ — Chebyshev’s extremal theorem.
Restate the theorem as a distance: on $\intcc{-1}{1}$ ,

$d_\infty\bigl(X^n,\ \R_{n-1}[X]\bigr) = 2^{1-n},$

with unique best approximation $X^n - Q_n$ ; and show by the affine substitution $x = \frac{1+t}2$ that on $\intcc{0}{1}$ the distance becomes $2^{1-2n}$ .
(Optimal interpolation nodes) For $n$ nodes $x_1, \dots, x_n \in \intcc{-1}{1}$ , the node polynomial $\omega(x) = \prod_i(x - x_i)$ is monic of degree $n$ . Deduce from question 12 which choice of nodes minimizes $\sup_{\intcc{-1}{1}}\abs\omega$ , the node-dependent factor of the classical interpolation error bound, and give the minimal value.
Verify the case $n = 2$ of the theorem by hand (find $\inf_c \sup_{\intcc{-1}{1}}\abs{x^2 - c}$ directly), and compute numerically the distance of question 13 on $\intcc{0}{1}$ for $n = 10$ . What does its size say about the graph of $x^{10}$ ?

Part IV — The unit ball of $C(\intcc{0}{1})$ .

Let $g_k(x) = x^{2^k}$ . Show $\norm{g_k}_\infty = 1$ and $\norm{g_k - g_j}_\infty \geq \frac14$ for $j > k$ (evaluate at the point where $x^{2^k} = \frac12$ ): an explicit bounded sequence with no convergent subsequence — the closed unit ball is not compact, by bare hands.
(Riesz’s lemma, sharpened) Let $F$ be a finite-dimensional proper subspace of a normed space $E$ . Using question 1, produce a unit vector $x$ with $d(x, F) = 1$ exactly — not just $\geq 1 - \varepsilon$ as in Theorem 5.17’s lemma.
Deduce: in every infinite-dimensional normed space there is a sequence of unit vectors with pairwise distances $\geq 1$ , and re-derive Riesz’s theorem from it.
In $C(\intcc{0}{1})$ , exhibit such a constellation explicitly: the tent functions $h_n$ supported on $\bigl[\frac1{n+1}, \frac1n\bigr]$ with peak value $1$ . Verify $\norm{h_n} = 1$ , $\norm{h_n - h_m} = 1$ for $n \neq m$ , and note that $h_n \to 0$ pointwise but not uniformly.
(Total boundedness fails) Show that the closed unit ball of $C(\intcc{0}{1})$ cannot be covered by finitely many balls of radius $\frac13$ (each such ball contains at most one $h_n$ ) — contrast with the total-boundedness step in the proof of Theorem 4.20.

Part V — Norms at work on matrices, and synthesis.

Prove that every eigenvalue $\lambda$ of $A \in \mathcal{M}_n(\C)$ satisfies $\abs\lambda \leq \vertiii A$ for every operator norm; apply Exercise 5.4 to bound the eigenvalues of $\left(\begin{smallmatrix}1 & -2\\ 3 & 1\end{smallmatrix}\right)$ and compare with their true modulus.
(Adapted norms) Let $A$ be diagonalizable, $A = P\,\mathrm{diag}(\lambda_1, \dots, \lambda_n)\,P^{-1}$ . Show $N_P(x) = \norm{P^{-1}x}_\infty$ is a norm whose operator norm satisfies $\vertiii A_{N_P} = \max_i\abs{\lambda_i}$ .
Deduce: for diagonalizable $A$ , $A^k \to 0$ if and only if all eigenvalues satisfy $\abs{\lambda_i} < 1$ — equivalence of norms makes the conclusion norm-independent. Check on $A = \frac14\left(\begin{smallmatrix}1 & 2\\ 2 & 1\end{smallmatrix}\right)$ .
(Equivalence constants blow up) On $\R_n[X]$ , compare $N_c(P) = \max_k \abs{a_k}$ (coefficients) and $\norm{P}_{\intcc{0}{1}}$ : both are norms, so they are equivalent for each fixed $n$ ; but show, using the monic minimizer of question 13 on $\intcc{0}{1}$ , that the best constant $C_n$ in $N_c \leq C_n\norm\cdot_{\intcc{0}{1}}$ satisfies $C_n \geq 2^{2n-1}$ . Conclude in one sentence why “all norms are equivalent” dies in infinite dimension.
(Synthesis) One sentence each: where compactness of finite-dimensional balls worked (questions 1, 12); what strict convexity governs; what the constellation of questions 18–19 destroys; and how question 24 quantifies the failure. Name the summit (Chebyshev’s extremal theorem) and state where best approximation finds its modern home (the projection theorem on Hilbert spaces, Year 3 volume, where completeness replaces compactness).

Solution

Solution of Problem 5.1.

1. The candidates worth considering form $K = \{f \in F : \norm{x - f} \leq \norm x\}$ : nonempty ( $0 \in K$ ), closed (preimage of a closed interval under the continuous $f \mapsto \norm{x - f}$ , intersected with the closed $F$ , Corollary 5.14), bounded ( $\norm f \leq \norm{f - x} + \norm x \leq 2\norm x$ ). In the finite-dimensional $F$ , closed and bounded means compact (Theorem 5.13); the continuous function $f \mapsto \norm{x - f}$ attains on $K$ its infimum, which equals the infimum over all of $F$ (any $f \notin K$ gives $\norm{x - f} > \norm x \geq \inf$ ).

2. Parallelogram identity in $(\R^n, \norm\cdot_2)$ : $\norm{u + v}^2 + \norm{u - v}^2 = 2\norm u^2 + 2\norm v^2$ (expand the squares of sums of coordinates). For unit $u \neq v$ :

\Bigl\Vert\frac{u+v}2\Bigr\Vert^2 = 1 - \frac{\norm{u - v}^2}{4} < 1 .

Not strictly convex: for $\norm\cdot_\infty$ , take $u = (1, 1, 0, \dots)$ , $v = (1, -1, 0, \dots)$ : unit vectors with midpoint $(1, 0, \dots)$ of norm $1$ ; for $\norm\cdot_1$ , take $u = (1, 0, \dots)$ , $v = (0, 1, 0, \dots)$ : midpoint $(\frac12, \frac12, 0, \dots)$ of norm $1$ .

3. Let $d = d(x, F)$ . If $d = 0$ : $x \in \overline F = F$ and the only minimizer is $x$ . If $d > 0$ and $f_1 \neq f_2$ both minimize: $u = \frac{x - f_1}{d}$ and $v = \frac{x - f_2}{d}$ are distinct unit vectors, so

\Bigl\Vert x - \frac{f_1 + f_2}2\Bigr\Vert = d\,\Bigl\Vert\frac{u + v}2\Bigr\Vert < d ,

with $\frac{f_1 + f_2}2 \in F$ : contradicts the definition of $d$ . Unique minimizer.

4. $\norm{(0,1) - t(1,0)}_\infty = \max(\abs t, 1) \geq 1$ , with equality iff $\abs t \leq 1$ : the minimizers form the segment $\{t(1, 0) : t \in \intcc{-1}{1}\}$ , all at distance $1$ — uniqueness fails exactly because the square ball has flat sides (question 2).

5. Let $M = \max f$ , $m = \min f$ (attained: compactness). For any constant $c$ : $\sup\abs{f - c} \geq \max(M - c,\, c - m) \geq \frac{M - m}2$ , the last inequality because the two quantities average to $\frac{M-m}2$ ; equality in both forces $M - c = c - m$ , i.e. $c = c^* = \frac{M + m}2$ . Conversely $\sup\abs{f - c^*} = \max(M - c^*, c^* - m) = \frac{M - m}2$ . Unique best constant. For $f(x) = x^2$ on $\intcc01$ : $c^* = \frac12$ , distance $\frac12$ .

6. From $\cos(n{+}1)\theta + \cos(n{-}1)\theta = 2\cos\theta\cos n\theta$ : the polynomials defined by $T_0 = 1$ , $T_1 = X$ , $T_{n+1} = 2XT_n - T_{n-1}$ satisfy $T_n(\cos\theta) = \cos n\theta$ by induction. Uniqueness: two polynomials agreeing on $\intcc{-1}{1}$ (infinitely many points) are equal. Induction again: $\deg T_n = n$ with leading coefficient $2^{n-1}$ for $n \geq 1$ ( $T_1$ : coefficient $1 = 2^0$ ; the recurrence doubles it).

7. Every $x \in \intcc{-1}{1}$ is $\cos\theta$ , and $\abs{\cos n\theta} \leq 1$ . At $\eta_k = \cos\frac{k\pi}n$ : $T_n(\eta_k) = \cos k\pi = (-1)^k$ , and $1 = \eta_0 > \eta_1 > \dots > \eta_n = -1$ . Roots: $\cos n\theta = 0$ iff $\theta = \frac{(2k-1)\pi}{2n}$ : the $n$ distinct points $\cos\frac{(2k-1)\pi}{2n}$ , and since $\frac{(k-1)\pi}n < \frac{(2k-1)\pi}{2n} < \frac{k\pi}n$ , each root lies strictly between two consecutive extrema.

8. $T_2 = 2X^2 - 1$ , $T_3 = 4X^3 - 3X$ , $T_4 = 8X^4 - 8X^2 + 1$ . For $T_3$ : $T_3(1) = 1$ , $T_3(\tfrac12) = \tfrac12 - \tfrac32 = -1$ , $T_3(-\tfrac12) = 1$ , $T_3(-1) = -1$ : perfect alternation.

9. Let $u_\pm = x \pm \sqrt{x^2 - 1}$ for $x \geq 1$ : the roots of $z^2 - 2xz + 1$ , with $u_+u_- = 1$ . The sequence $s_n = \frac{u_+^n + u_-^n}2$ satisfies $s_{n+1} = 2x\,s_n - s_{n-1}$ (Newton-type recurrence from the quadratic), $s_0 = 1$ , $s_1 = x$ : the same recurrence and initial values as $n \mapsto T_n(x)$ , so $s_n = T_n(x)$ for all $n$ . Since $0 < u_- \leq 1 \leq u_+$ with $u_+ > 1$ for $x > 1$ : $T_n(x) \geq \frac{u_+^n}2 \to \infty$ and $T_n(x) \sim \frac12\bigl(x + \sqrt{x^2-1}\bigr)^n$ . (For $x \leq -1$ use the parity $T_n(-x) = (-1)^nT_n(x)$ , clear from the recurrence.)

10. For every $\theta$ : $T_m\bigl(T_n(\cos\theta)\bigr) = T_m(\cos n\theta) = \cos mn\theta = T_{mn}(\cos\theta)$ . The polynomials $T_m \circ T_n$ and $T_{mn}$ agree on $\intcc{-1}{1}$ , hence are equal.

11. $D = Q_n - P$ has degree $\leq n - 1$ (the monic leading terms cancel). At the extrema: $(-1)^kD(\eta_k) = 2^{1-n} - (-1)^kP(\eta_k) \geq 2^{1-n} - \abs{P(\eta_k)} > 0$ by hypothesis. So $D$ takes nonzero values of alternating signs at the $n + 1$ decreasing points $\eta_0 > \dots > \eta_n$ : by the intermediate value theorem it has at least $n$ distinct roots, one in each open interval $\intoo{\eta_{k}}{\eta_{k-1}}$ . A nonzero polynomial of degree $\leq n - 1$ cannot have $n$ roots; and $D = 0$ contradicts the strict signs. Contradiction: $\sup\abs P \geq 2^{1-n}$ for every monic $P$ of degree $n$ .

12. Now $(-1)^kD(\eta_k) = 2^{1-n} - (-1)^kP(\eta_k) \geq 0$ since $\abs{P} \leq 2^{1-n}$ . On each $\intcc{\eta_k}{\eta_{k-1}}$ ( $k = 1, \dots, n$ ) the endpoint values of $D$ have opposite weak signs: the intermediate value theorem yields a zero $z_k$ in the closed interval. If the $z_k$ can be chosen pairwise distinct, $D \neq 0$ of degree $\leq n-1$ has $n$ roots: contradiction. Two consecutive intervals can only share the zero $z_k = z_{k+1} = \eta_k$ with $0 < k < n$ (interior). There, $D(\eta_k) = 0$ means $P(\eta_k) = (-1)^k2^{1-n}$ , an extremal value of $P$ on $\intcc{-1}{1}$ attained at an interior point: $P'(\eta_k) = 0$ ; and $\eta_k$ is an interior extremum of $T_n$ too: $Q_n'(\eta_k) = 0$ . Hence $D'(\eta_k) = 0$ : $\eta_k$ is a root of multiplicity $\geq 2$ , compensating the shared interval. In all cases $D$ has at least $n$ roots counted with multiplicity, degree $\leq n - 1$ , so $D = 0$ : $P = Q_n$ . Chebyshev’s extremal theorem is proved: the unique monic minimizer is $2^{1-n}T_n$ , of sup norm $2^{1-n}$ .

13. Monic polynomials of degree $n$ are exactly the $X^n - R$ with $R \in \R_{n-1}[X]$ , so

d_\infty\bigl(X^n, \R_{n-1}[X]\bigr) = \min_{P \text{ monic}}\ \sup_{\intcc{-1}{1}}\abs P = 2^{1-n},

uniquely at $R^* = X^n - Q_n$ . Substitution $x = \frac{1+t}2$ : if $P$ is monic of degree $n$ on $\intcc01$ , then $t \mapsto 2^nP\bigl(\frac{1+t}2\bigr)$ is monic on $\intcc{-1}{1}$ with sup equal to $2^n\sup_{\intcc01}\abs P$ : hence $\sup_{\intcc01}\abs P \geq 2^{-n}\cdot2^{1-n} = 2^{1-2n}$ , with equality exactly for $P^*(x) = 2^{-n}Q_n(2x - 1)$ : on $\intcc{0}{1}$ the distance is $2^{1-2n}$ .

14. $\omega$ is monic of degree $n$ , so $\sup_{\intcc{-1}{1}}\abs\omega \geq 2^{1-n}$ with equality iff $\omega = Q_n = 2^{1-n}T_n$ , i.e. iff the nodes are the $n$ roots of $T_n$ : $x_k = \cos\frac{(2k-1)\pi}{2n}$ — the Chebyshev nodes. Minimal value: $2^{1-n}$ . Equidistant nodes are strictly worse; the interpolation error factor is minimized by clustering nodes near the endpoints.

15. $n = 2$ by hand: $x^2$ ranges over $\intcc01$ , so $\sup_{\intcc{-1}{1}}\abs{x^2 - c} = \max(\abs c, \abs{1 - c}) \geq \frac12$ , minimized at $c = \frac12$ : minimal monic quadratic $x^2 - \frac12 = \frac12(2x^2 - 1) = Q_2$ , value $\frac12 = 2^{1-2}$ . For $n = 10$ on $\intcc{0}{1}$ : $2^{1-20} = 2^{-19} \approx 1.9\cdot10^{-6}$ . Some polynomial of degree $9$ stays within two millionths of $x^{10}$ on the whole of $\intcc01$ : at this scale the two graphs are indistinguishable — the flatness of $x^{10}$ near $0$ lets lower degrees do all the work.

16. $\norm{g_k}_\infty = g_k(1) = 1$ . For $j > k$ set $a = 2^k$ , $b = 2^j \geq 2a$ , and evaluate at $x_0 = 2^{-1/a}$ (so $x_0^a = \frac12$ ):

g_k(x_0) - g_j(x_0) = \frac12 - \Bigl(\frac12\Bigr)^{b/a} \geq \frac12 - \frac14 = \frac14 .

So $\norm{g_k - g_j}_\infty \geq \frac14$ for all $j \neq k$ : no subsequence is Cauchy, none converges. The closed unit ball of $\bigl(C(\intcc01), \norm\cdot_\infty\bigr)$ is not compact.

17. $F$ is closed (Corollary 5.14) and proper: pick $y \notin F$ , so $\delta = d(y, F) > 0$ . By question 1 the distance is attained at some $f^* \in F$ . Set $x = \frac{y - f^*}{\delta}$ , a unit vector ( $\norm{y - f^*} = \delta$ ). For every $g \in F$ :

\norm{x - g} = \frac{\norm{y - (f^* + \delta g)}}{\delta} \geq \frac{\delta}{\delta} = 1 ,

since $f^* + \delta g \in F$ . Hence $d(x, F) \geq 1$ ; and $d(x, F) \leq \norm{x - 0} = 1$ : exactly $1$ .

18. In an infinite-dimensional $E$ , build unit vectors inductively: $x_1$ arbitrary; given $x_1, \dots, x_k$ , the subspace $F_k = \operatorname{Vect}(x_1, \dots, x_k)$ is finite-dimensional, hence proper, and question 17 gives a unit $x_{k+1}$ with $d(x_{k+1}, F_k) = 1$ : in particular $\norm{x_{k+1} - x_i} \geq 1$ for $i \leq k$ . The sequence has pairwise distances $\geq 1$ : the unit ball contains a sequence with no convergent subsequence, hence is not compact — Riesz’s theorem, with the sharp constant $1$ .

19. Let $h_n$ be affine on each half of $\bigl[\frac1{n+1}, \frac1n\bigr]$ , from $0$ up to $1$ at the midpoint and back to $0$ , and zero elsewhere: continuous, $\norm{h_n}_\infty = 1$ . For $n \neq m$ the supports meet at most at a common endpoint, where both vanish; at the peak of $h_n$ , $h_m = 0$ : $\norm{h_n - h_m}_\infty = 1$ exactly. For fixed $x > 0$ : $h_n(x) = 0$ as soon as $\frac1n < x$ , and $h_n(0) = 0$ always: $h_n \to 0$ pointwise; but $\norm{h_n - 0}_\infty = 1$ : not uniformly. An explicit constellation at mutual distance $1$ inside the unit ball.

20. A ball of radius $\frac13$ has diameter $\leq \frac23 < 1$ , so it contains at most one of the $h_n$ (two are at distance $1$ ). Finitely many such balls contain finitely many of the infinitely many $h_n$ : they cannot cover the unit ball. Total boundedness — which compact metric spaces enjoy, by the proof of Theorem 4.20 — fails as badly as possible.

21. If $Ax = \lambda x$ with $x \neq 0$ : $\abs\lambda\,\norm x = \norm{Ax} \leq \vertiii A\,\norm x$ , so $\abs\lambda \leq \vertiii A$ . For $\left(\begin{smallmatrix}1 & -2\\ 3 & 1\end{smallmatrix}\right)$ : $\vertiii A_\infty = \max(1 + 2,\ 3 + 1) = 4$ (Exercise 5.4), so every eigenvalue has modulus $\leq 4$ ; in fact $\chi_A = X^2 - 2X + 7$ gives $\lambda = 1 \pm \iu\sqrt6$ of modulus $\sqrt7 \approx 2.65$ : the bound is valid, not sharp.

22. $N_P$ is a norm: $N_P(x) = 0$ forces $P^{-1}x = 0$ , so $x = 0$ ; homogeneity and triangle inequality are inherited from $\norm\cdot_\infty$ through the linear $P^{-1}$ . Operator norm: with $y = P^{-1}x$ and $D = \mathrm{diag}(\lambda_i)$ ,

N_P(Ax) = \norm{P^{-1}AP\,y}_\infty = \norm{Dy}_\infty,

so $\vertiii A_{N_P}$ is the $\norm\cdot_\infty$ -operator norm of $D$ , which is its largest absolute row sum (Exercise 5.4): $\max_i\abs{\lambda_i}$ .

23. If all $\abs{\lambda_i} < 1$ : $N_P(A^kx) \leq \rho^kN_P(x)$ with $\rho = \max\abs{\lambda_i} < 1$ , so $A^kx \to 0$ for every $x$ , and $A^k \to 0$ in any norm on $\mathcal{M}_n$ (all equivalent in finite dimension, Theorem 5.13; convergence of $A^ke_j$ for each $j$ is entrywise convergence). If some $\abs{\lambda} \geq 1$ with eigenvector $x$ : $\norm{A^kx} = \abs\lambda^k\norm x \not\to 0$ . For $A = \frac14\left(\begin{smallmatrix}1 & 2\\ 2 & 1\end{smallmatrix}\right)$ : eigenvalues $\frac14(1 \pm 2) = \frac34, -\frac14$ , both of modulus $< 1$ : $A^k \to 0$ .

24. Both are norms on the finite-dimensional $\R_n[X]$ , hence equivalent for each $n$ . Take the minimal monic $P^*_n$ of question 13 on $\intcc01$ : its coefficient of $X^n$ is $1$ , so $N_c(P^*_n) \geq 1$ , while $\norm{P^*_n}_{\intcc01} = 2^{1-2n}$ . Hence

C_n \geq \frac{N_c(P^*_n)}{\norm{P^*_n}_{\intcc01}} \geq 2^{2n-1} .

The equivalence constants explode with the dimension: on the union $\R[X]$ no single constant serves, which is exactly the non-equivalence seen in Exercise 5.12 — “all norms are equivalent” is a theorem about one dimension at a time, and infinite dimension is where it dies.

25. Compactness of closed bounded sets in finite dimension produced existence of best approximations (question 1) and powered the zero-counting at the $n + 1$ extremal points (questions 11–12, via attained sups). Strict convexity governs uniqueness of best approximation — round balls give one minimizer, flat-sided balls give segments of them (questions 2–4). The constellation of unit vectors at mutual distance $1$ (questions 17–19) destroys compactness of the unit ball and total boundedness with it (question 20). Question 24 quantifies the collapse: the constants relating two norms on $\R_n[X]$ grow like $4^n$ , so no uniform comparison survives the passage to $\R[X]$ . The summit is Chebyshev’s extremal theorem (questions 11–12): the unique monic minimizer $2^{1-n}T_n$ . Best approximation finds its modern home in Hilbert spaces, where the projection theorem replaces compactness by completeness plus the parallelogram identity — proved honestly in the Year 3 volume.