18.4 Gauges, Support Functions and Dual Norms

Chapter 16 §01 observed that the closed unit ball of every norm is convex and symmetric, and left the converse alone: does every convex, symmetric set arise as the unit ball of some norm? This section answers yes, by reading a norm off a convex set from the inside, the gauge. It then reads a function off a convex set from the outside, the support function, which turns §03’s description of a closed convex set by half-spaces into a formula. Applied to a unit ball, the support function is the dual norm, the measurement Chapter 16 never gave to a linear functional, and the last part of the section proves that taking the dual twice returns the norm we started with.

Throughout, the field is $\mathbb{R}$ , and we work in $\mathbb{R}^n$ , $n \ge 1$ , with the dot product $\langle \mathbf{x}, \mathbf{y} \rangle = \mathbf{x}^{\top}\mathbf{y}$ and its norm $\left\| \cdot \right\|_2$ . So everything proved in §03 is available, with $V = \mathbb{R}^n$ . A symbol $\left\| \cdot \right\|$ without a subscript is an arbitrary norm on $\mathbb{R}^n$ in the sense of Definition 16.1.1, and $B$ is its closed unit ball (Definition 16.1.2). Interior points are meant in the sense of Definition 18.3.2, which does not depend on the norm. For a set $K$ and a real $t$ , we write $tK = \{t\mathbf{x} : \mathbf{x} \in K\}$ .

18.4.1. Gauges

Every norm can be read off its unit ball. By (N2), for $t > 0$ we have $\left\| \mathbf{x} \right\| \le t$ exactly when $\left\| \mathbf{x}/t \right\| \le 1$ , that is, when $\mathbf{x} \in tB$ . Hence $\left\| \mathbf{x} \right\| = \inf\{t > 0 : \mathbf{x} \in tB\} ,$ the inflation factor by which $B$ has to be blown up before it reaches $\mathbf{x}$ . The right-hand side makes sense for sets that are not unit balls, and this is the formula to study.

The gauge of a convex set measures a vector by how far the set must be inflated to reach it.

Definition 18.4.1 (Gauge)

Let $K \subseteq \mathbb{R}^n$ be convex, with $\mathbf{0}$ an interior point of $K$ . The gauge (or Minkowski functional) of $K$ is the function $p_K \colon \mathbb{R}^n \to \mathbb{R}$ given by $p_K(\mathbf{x}) = \inf\{t > 0 : \mathbf{x} \in tK\} .$

The infimum exists. Choose $r > 0$ with every $\mathbf{y}$ satisfying $\left\| \mathbf{y} \right\|_2 < r$ in $K$ . If $t > \left\| \mathbf{x} \right\|_2/r$ , then $\left\| \mathbf{x}/t \right\|_2 < r$ , so $\mathbf{x}/t \in K$ and $\mathbf{x} \in tK$ . So the set of admissible $t$ is non-empty, and it is bounded below by $0$ ; by the completeness of $\mathbb{R}$ , fact (A1) of Chapter 16’s introduction, it has a greatest lower bound, and $0 \le p_K(\mathbf{x}) \le \left\| \mathbf{x} \right\|_2/r \qquad \text{for every } \mathbf{x} \in \mathbb{R}^n .$ The interior point is what makes $p_K$ finite. For the segment $[-\mathbf{e}_1, \mathbf{e}_1] \subseteq \mathbb{R}^2$ , which has no interior points, the vector $\mathbf{e}_2$ lies in no multiple $tK$ , and the formula would give the infimum of the empty set.

Proposition 18.4.1 (Properties of the Gauge)

Let $K \subseteq \mathbb{R}^n$ be convex with $\mathbf{0}$ an interior point, and let $\mathbf{x} \in \mathbb{R}^n$ .

(a) $\mathbf{x} \in tK$ for every $t > p_K(\mathbf{x})$ .
(b) $p_K$ is sublinear (Definition 18.3.3).
(c) $\{\mathbf{x} : p_K(\mathbf{x}) < 1\} \subseteq K \subseteq \{\mathbf{x} : p_K(\mathbf{x}) \le 1\}$ .
(d) If $K$ is closed, then $K = \{\mathbf{x} : p_K(\mathbf{x}) \le 1\}$ .

Idea. Everything comes from one observation, (a): since $\mathbf{0} \in K$ and $K$ is convex, shrinking a point of $K$ towards $\mathbf{0}$ keeps it in $K$ , so the admissible $t$ form a whole half-line. Subadditivity is then convexity applied to $\mathbf{x}/s$ and $\mathbf{y}/t$ with weights proportional to $s$ and $t$ .

Proof.

(a) Let $t > p_K(\mathbf{x})$ . By the definition of an infimum there is $s$ with $p_K(\mathbf{x}) \le s < t$ and $\mathbf{x} \in sK$ , so $\mathbf{x}/s \in K$ . Since $\mathbf{0} \in K$ and $K$ is convex, $\frac{\mathbf{x}}{t} = \frac{s}{t}\cdot\frac{\mathbf{x}}{s} + \Bigl(1 - \frac{s}{t}\Bigr)\mathbf{0} \in K ,$ that is, $\mathbf{x} \in tK$ .
(b) Let $\lambda > 0$ . Since $\lambda\mathbf{x} \in tK$ exactly when $\mathbf{x} \in (t/\lambda)K$ , the admissible $t$ for $\lambda\mathbf{x}$ are $\lambda$ times those for $\mathbf{x}$ , and $p_K(\lambda\mathbf{x}) = \lambda p_K(\mathbf{x})$ . For $\lambda = 0$ , $\mathbf{0} \in tK$ for every $t > 0$ , so $p_K(\mathbf{0}) = 0$ . For subadditivity, let $\varepsilon > 0$ , $s = p_K(\mathbf{x}) + \varepsilon$ and $t = p_K(\mathbf{y}) + \varepsilon$ . By (a), $\mathbf{x}/s$ and $\mathbf{y}/t$ lie in $K$ , so by convexity $\frac{\mathbf{x} + \mathbf{y}}{s + t} = \frac{s}{s + t}\cdot\frac{\mathbf{x}}{s} + \frac{t}{s + t}\cdot\frac{\mathbf{y}}{t} \in K .$ Hence $p_K(\mathbf{x} + \mathbf{y}) \le s + t = p_K(\mathbf{x}) + p_K(\mathbf{y}) + 2\varepsilon$ , for every $\varepsilon > 0$ , and so $p_K(\mathbf{x} + \mathbf{y}) \le p_K(\mathbf{x}) + p_K(\mathbf{y})$ .
(c) If $p_K(\mathbf{x}) < 1$ , then $\mathbf{x} \in 1\cdot K$ by (a). If $\mathbf{x} \in K$ , then $t = 1$ is admissible, so $p_K(\mathbf{x}) \le 1$ .
(d) Let $p_K(\mathbf{x}) \le 1$ . By (a), $\mathbf{x} \in (1 + 1/k)K$ for every $k \ge 1$ , so the points $\mathbf{x}/(1 + 1/k)$ lie in $K$ . They converge to $\mathbf{x}$ , and $K$ is closed, so $\mathbf{x} \in K$ . With (c) this gives $K = \{p_K \le 1\}$ .

The gauge of a unit ball is its norm, by the computation that opened this section. A second example: for the rectangle $K = [-2, 2] \times [-1, 1] \subseteq \mathbb{R}^2$ , a vector lies in $tK$ exactly when $\lvert x_1\rvert \le 2t$ and $\lvert x_2\rvert \le t$ , so $p_K(\mathbf{x}) = \max\bigl(\tfrac12\lvert x_1\rvert,\ \lvert x_2\rvert\bigr) ,$ a weighted $\infty$ -norm of the kind in Example (Inner products, weights, and a function space) (b). At the degenerate extreme, $K = \mathbb{R}^n$ lies in every $tK$ , and $p_K$ is identically $0$ : sublinear, but no norm.

The next theorem says exactly when a gauge is a norm. Its part (b) records the facts about unit balls that make the match perfect.

Theorem 18.4.2 (Convex Bodies and Norms)

(a) Let $K \subseteq \mathbb{R}^n$ be closed, bounded, convex and symmetric ( $-K = K$ ), with $\mathbf{0}$ an interior point. Then $p_K$ is a norm on $\mathbb{R}^n$ , and its closed unit ball is $K$ .
(b) Conversely, the closed unit ball $B$ of any norm $\left\| \cdot \right\|$ on $\mathbb{R}^n$ is closed, bounded, convex and symmetric, with $\mathbf{0}$ an interior point, and $p_B = \left\| \cdot \right\|$ .

So the norms on $\mathbb{R}^n$ correspond one to one with the sets described in (a).

Idea. Sublinearity is two thirds of a norm, and Proposition 18.4.1 already has it. The missing third is absolute homogeneity for a scalar $c < 0$ , which is what symmetry buys, and positive definiteness, which is what boundedness buys: a non-zero vector cannot fit inside every shrunken copy $tK$ of a bounded set. Closedness makes the unit ball of $p_K$ equal to $K$ rather than squeezed between the two sets of Proposition 18.4.1 (c).

Proof.

(a) By Proposition 18.4.1 (b), $p_K$ is sublinear, which gives (N3) and (N2) for $c \ge 0$ . For $c < 0$ , symmetry gives $\mathbf{x} \in tK$ if and only if $-\mathbf{x} \in t(-K) = tK$ , so $p_K(-\mathbf{x}) = p_K(\mathbf{x})$ and $p_K(c\mathbf{x}) = \lvert c\rvert p_K(-\mathbf{x}) = \lvert c\rvert p_K(\mathbf{x})$ . For (N1), $p_K \ge 0$ by definition. Let $R$ be such that $\left\| \mathbf{y} \right\|_2 \le R$ for all $\mathbf{y} \in K$ . If $p_K(\mathbf{x}) = 0$ , then $\mathbf{x} \in tK$ for every $t > 0$ by Proposition 18.4.1 (a), so $\left\| \mathbf{x} \right\|_2 \le tR$ for every $t > 0$ , and $\mathbf{x} = \mathbf{0}$ . So $p_K$ is a norm, and its closed unit ball $\{p_K \le 1\}$ is $K$ by Proposition 18.4.1 (d).
(b) Chapter 16 §01 showed, right after Definition 16.1.2, that $B$ is convex and symmetric. By Theorem 16.2.2 there are constants $0 < m \le M$ with $m\left\| \mathbf{x} \right\|_2 \le \left\| \mathbf{x} \right\| \le M\left\| \mathbf{x} \right\|_2$ . If $\left\| \mathbf{x} \right\| \le 1$ , then $\left\| \mathbf{x} \right\|_2 \le 1/m$ , so $B$ is bounded. If $\left\| \mathbf{x} \right\|_2 < 1/M$ , then $\left\| \mathbf{x} \right\| < 1$ , so $\mathbf{0}$ is an interior point. If $\mathbf{x}_k \in B$ and $\mathbf{x}_k \to \mathbf{x}$ , then $\lvert\left\| \mathbf{x}_k \right\| - \left\| \mathbf{x} \right\|\rvert \le \left\| \mathbf{x}_k - \mathbf{x} \right\| \le M\left\| \mathbf{x}_k - \mathbf{x} \right\|_2 \to 0$ by Lemma 16.1.1, and $\left\| \mathbf{x} \right\| \le 1$ because a non-strict inequality survives the limit; so $B$ is closed. Finally, $\mathbf{x} \in tB$ exactly when $t \ge \left\| \mathbf{x} \right\|$ , for $t > 0$ , so $p_B(\mathbf{x}) = \left\| \mathbf{x} \right\|$ (for $\mathbf{x} = \mathbf{0}$ , the infimum of all $t > 0$ is $0$ ). This proves the theorem.

This is the converse of Chapter 16’s “every unit ball is convex”. There, a norm produced a convex symmetric set, the ball of Definition 16.1.2, and convexity was what the triangle inequality bought. Here a convex symmetric set produces a norm, and the triangle inequality is what convexity buys: the subadditivity step in Proposition 18.4.1 (b) is the convexity of $K$ , used once. Norms and closed bounded symmetric convex sets with $\mathbf{0}$ inside are the same objects seen two ways, one analytic, one geometric.

Each hypothesis in (a) carries one clause of Definition 16.1.1, and dropping one breaks exactly that clause.

Drop symmetry. The triangle $T = \{\mathbf{x} : x_1 \ge -1,\ x_2 \ge -1,\ x_1 + x_2 \le 1\}$ , with vertices $(-1,-1)$ , $(2,-1)$ , $(-1,2)$ , is closed, bounded and convex, and contains the disc of radius $\tfrac12$ about $\mathbf{0}$ . A vector lies in $tT$ exactly when $-x_1 \le t$ , $-x_2 \le t$ and $x_1 + x_2 \le t$ , so $p_T(\mathbf{x}) = \max\bigl(-x_1,\ -x_2,\ x_1 + x_2\bigr) ,$ which is never negative, since the three numbers add up to $0$ . This is sublinear and satisfies (N1), but $p_T\bigl((1,1)\bigr) = 2$ while $p_T\bigl((-1,-1)\bigr) = 1$ , so (N2) fails at $c = -1$ .
Drop boundedness. The strip $S = \{\mathbf{x} \in \mathbb{R}^2 : \lvert x_2\rvert \le 1\}$ is closed, convex and symmetric, and $p_S(\mathbf{x}) = \lvert x_2\rvert$ . Now (N2) and (N3) hold but (N1) fails: $p_S(\mathbf{e}_1) = 0$ . This is the seminorm of Example (Three near misses) (b).

Quick check. Let $K$ be the open unit disc $\{\mathbf{x} \in \mathbb{R}^2 : \left\| \mathbf{x} \right\|_2 < 1\}$ , which is bounded, symmetric and convex (if $\left\| \mathbf{x} \right\|_2, \left\| \mathbf{y} \right\|_2 < 1$ and $0 \le t \le 1$ , then $\left\| (1 - t)\mathbf{x} + t\mathbf{y} \right\|_2 \le (1 - t)\left\| \mathbf{x} \right\|_2 + t\left\| \mathbf{y} \right\|_2 < 1$ ) but not closed. What is $p_K$ , and what is its closed unit ball?

Solution. For $t > 0$ , $\mathbf{x} \in tK$ exactly when $\left\| \mathbf{x} \right\|_2 < t$ , so the admissible $t$ form the interval $(\left\| \mathbf{x} \right\|_2, \infty)$ and $p_K(\mathbf{x}) = \left\| \mathbf{x} \right\|_2$ . So $p_K$ is a norm after all, but its closed unit ball is the closed disc, not $K$ . Closedness is used only for the last claim of Theorem 18.4.2 (a), through Proposition 18.4.1 (d).

18.4.2. Support functions

§03 described a closed convex set from the outside: by Corollary 18.3.3 it is the intersection of the closed half-spaces containing it. For a fixed normal vector $\mathbf{y}$ , the half-spaces $\{\mathbf{x} : \langle \mathbf{x}, \mathbf{y} \rangle \le c\}$ containing $K$ are those with $c \ge \langle \mathbf{x}, \mathbf{y} \rangle$ for every $\mathbf{x} \in K$ , and the tightest of them has $c = \sup_{\mathbf{x} \in K}\langle \mathbf{x}, \mathbf{y} \rangle$ . That number, as a function of the direction $\mathbf{y}$ , deserves a name.

The support function of a set records, for each direction, how far the set reaches in that direction.

Definition 18.4.2 (Support Function)

Let $K \subseteq \mathbb{R}^n$ be non-empty. The support function of $K$ is $h_K(\mathbf{y}) = \sup_{\mathbf{x} \in K}\langle \mathbf{x}, \mathbf{y} \rangle , \qquad \mathbf{y} \in \mathbb{R}^n ,$ with the value $+\infty$ when the numbers $\langle \mathbf{x}, \mathbf{y} \rangle$ , $\mathbf{x} \in K$ , are unbounded above.

When the numbers are bounded above, the supremum exists by (A1). If $K$ is bounded, say $\left\| \mathbf{x} \right\|_2 \le R$ on $K$ , then $\langle \mathbf{x}, \mathbf{y} \rangle \le R\left\| \mathbf{y} \right\|_2$ by Theorem 11.1.5, so $h_K$ is real-valued. If $K$ is compact, the supremum is a maximum by the extreme value theorem, fact (A4) of Chapter 16’s introduction, since $\mathbf{x} \mapsto \langle \mathbf{x}, \mathbf{y} \rangle$ is continuous: $\lvert\langle \mathbf{x}, \mathbf{y} \rangle - \langle \mathbf{x}', \mathbf{y} \rangle\rvert \le \left\| \mathbf{x} - \mathbf{x}' \right\|_2\left\| \mathbf{y} \right\|_2$ . For a unit vector $\mathbf{y}$ , the hyperplane $\{\langle \cdot, \mathbf{y} \rangle = h_K(\mathbf{y})\}$ is the one with normal $\mathbf{y}$ that touches $K$ from outside, and $h_K(\mathbf{y})$ is its signed distance from $\mathbf{0}$ .

Some examples, each computed from the definition.

A point. $h_{\{\mathbf{x}_0\}}(\mathbf{y}) = \langle \mathbf{x}_0, \mathbf{y} \rangle$ , a linear function.
The Euclidean ball. $h_{B_2}(\mathbf{y}) = \left\| \mathbf{y} \right\|_2$ : at most that by Theorem 11.1.5, and attained at $\mathbf{x} = \mathbf{y}/\left\| \mathbf{y} \right\|_2$ when $\mathbf{y} \ne \mathbf{0}$ .
The standard simplex $\operatorname{conv}\{\mathbf{e}_1, \dots, \mathbf{e}_n\}$ . By Theorem 18.1.3 its points are $\sum_i t_i\mathbf{e}_i$ with $t_i \ge 0$ and $\sum_i t_i = 1$ , and $\sum_i t_iy_i \le \max_i y_i$ , with equality at a vertex $\mathbf{e}_k$ where $y_k$ is largest. So $h(\mathbf{y}) = \max_i y_i$ .
A segment. $h_{[-\mathbf{e}_1, \mathbf{e}_1]}(\mathbf{y}) = \lvert y_1\rvert$ in $\mathbb{R}^2$ .
An unbounded set. For the half-line $\{t\mathbf{e}_1 : t \ge 0\}$ , $h(\mathbf{y}) = 0$ if $y_1 \le 0$ and $h(\mathbf{y}) = +\infty$ if $y_1 > 0$ .

Proposition 18.4.3 (Properties of the Support Function)

Let $K, L \subseteq \mathbb{R}^n$ be non-empty and bounded.

(a) $h_K$ is sublinear.
(b) If $K \subseteq L$ , then $h_K \le h_L$ .
(c) $h_{\operatorname{conv} K} = h_K$ .

Idea. A supremum of linear functions of $\mathbf{y}$ inherits whatever inequalities each of them satisfies, which gives (a) and (b). For (c), a linear function takes on a convex combination a weighted average of its values, and an average never exceeds the largest value.

Proof.

(a) For $\mathbf{x} \in K$ , $\langle \mathbf{x}, \mathbf{y} + \mathbf{z} \rangle = \langle \mathbf{x}, \mathbf{y} \rangle + \langle \mathbf{x}, \mathbf{z} \rangle \le h_K(\mathbf{y}) + h_K(\mathbf{z})$ , and taking the supremum over $\mathbf{x}$ gives $h_K(\mathbf{y} + \mathbf{z}) \le h_K(\mathbf{y}) + h_K(\mathbf{z})$ . For $t > 0$ , $\langle \mathbf{x}, t\mathbf{y} \rangle = t\langle \mathbf{x}, \mathbf{y} \rangle$ , and a positive factor comes out of a supremum; for $t = 0$ both sides are $0$ , as $K \ne \emptyset$ .
(b) A supremum over a larger set is at least as large.
(c) Since $K \subseteq \operatorname{conv} K$ , (b) gives $h_K \le h_{\operatorname{conv} K}$ , once we know $\operatorname{conv} K$ is bounded: it lies in the ball $\{\left\| \mathbf{x} \right\|_2 \le R\}$ , which is convex and contains $K$ (Definition 18.1.4). Conversely, by Theorem 18.1.3 a point of $\operatorname{conv} K$ is $\mathbf{x} = \sum_i t_i\mathbf{x}_i$ with $\mathbf{x}_i \in K$ , $t_i \ge 0$ , $\sum_i t_i = 1$ , and then $\langle \mathbf{x}, \mathbf{y} \rangle = \sum_i t_i\langle \mathbf{x}_i, \mathbf{y} \rangle \le \sum_i t_i\,h_K(\mathbf{y}) = h_K(\mathbf{y}) .$ So $h_{\operatorname{conv} K} \le h_K$ .

Warning. A support function cannot see gaps. The two-point set $\{\mathbf{e}_1, -\mathbf{e}_1\}$ and the segment $[-\mathbf{e}_1, \mathbf{e}_1]$ in $\mathbb{R}^2$ have the same support function $\lvert y_1\rvert$ , by Proposition 18.4.3 (c). So $h_K$ does not determine $K$ in general; it determines only the convex hull, and the next theorem shows that among closed convex sets it determines the set.

Here is the promised formula. It is Corollary 18.3.3 with the family of half-spaces indexed by their normals.

Theorem 18.4.4 (The Support Function Determines a Closed Convex Set)

Let $K, L \subseteq \mathbb{R}^n$ be non-empty, closed and convex. Then

(a) $K = \{\mathbf{x} \in \mathbb{R}^n : \langle \mathbf{x}, \mathbf{y} \rangle \le h_K(\mathbf{y}) \text{ for every } \mathbf{y} \in \mathbb{R}^n\}$ ;
(b) $K \subseteq L$ if and only if $h_K(\mathbf{y}) \le h_L(\mathbf{y})$ for every $\mathbf{y}$ ; in particular $K = L$ if and only if $h_K = h_L$ .

Here $h_K$ and $h_L$ may take the value $+\infty$ , with $a \le +\infty$ for every $a$ .

Idea. Part (a) is Corollary 18.3.3, with the half-space for the normal $\mathbf{y}$ chosen as tight as possible, at level $h_K(\mathbf{y})$ . Part (b) then compares the two families of half-spaces normal by normal.

Proof.

(a) Every $\mathbf{x} \in K$ satisfies $\langle \mathbf{x}, \mathbf{y} \rangle \le h_K(\mathbf{y})$ by definition. Conversely let $\mathbf{x} \notin K$ . By Theorem 18.3.2 there is $\mathbf{a} \ne \mathbf{0}$ with $\langle \mathbf{a}, \mathbf{z} \rangle \le \langle \mathbf{a}, \mathbf{x} \rangle - \left\| \mathbf{a} \right\|_2^2$ for all $\mathbf{z} \in K$ . Hence $h_K(\mathbf{a}) \le \langle \mathbf{a}, \mathbf{x} \rangle - \left\| \mathbf{a} \right\|_2^2 < \langle \mathbf{x}, \mathbf{a} \rangle$ , and $\mathbf{x}$ violates the condition at $\mathbf{y} = \mathbf{a}$ .
(b) If $K \subseteq L$ , then $h_K \le h_L$ because a supremum over a larger set is at least as large. Conversely, suppose $h_K \le h_L$ and let $\mathbf{x} \in K$ . For every $\mathbf{y}$ , $\langle \mathbf{x}, \mathbf{y} \rangle \le h_K(\mathbf{y}) \le h_L(\mathbf{y})$ , so $\mathbf{x} \in L$ by (a) applied to $L$ . The last statement follows by applying this in both directions.

18.4.3. Polar sets

The condition $h_K(\mathbf{y}) \le 1$ cuts out a set of directions, and that set turns out to be a mirror image of $K$ .

Definition 18.4.3 (Polar Set)

The polar of a set $K \subseteq \mathbb{R}^n$ is $K^{\circ} = \{\mathbf{y} \in \mathbb{R}^n : \langle \mathbf{x}, \mathbf{y} \rangle \le 1 \text{ for every } \mathbf{x} \in K\} .$

For non-empty $K$ , $K^{\circ} = \{\mathbf{y} : h_K(\mathbf{y}) \le 1\}$ . The polar is always closed, convex and contains $\mathbf{0}$ , being an intersection of closed half-spaces $\{\mathbf{y} : \langle \mathbf{x}, \mathbf{y} \rangle \le 1\}$ , one for each $\mathbf{x} \in K$ . Two examples:

$(B_2)^{\circ} = B_2$ , because $h_{B_2}(\mathbf{y}) = \left\| \mathbf{y} \right\|_2$ .
For the single point $K = \{\mathbf{e}_1\}$ in $\mathbb{R}^2$ , $K^{\circ} = \{\mathbf{y} : y_1 \le 1\}$ , a half-plane. Its polar consists of the $\mathbf{x}$ with $x_1y_1 + x_2y_2 \le 1$ whenever $y_1 \le 1$ . Letting $y_2$ run over $\mathbb{R}$ forces $x_2 = 0$ , letting $y_1 \to -\infty$ forces $x_1 \ge 0$ , and $y_1 = 1$ forces $x_1 \le 1$ . So $K^{\circ\circ}$ is the segment $[\mathbf{0}, \mathbf{e}_1]$ , which is not $K$ .

The second example shows what the theorem must assume.

Theorem 18.4.5 (Bipolar Theorem)

Let $K \subseteq \mathbb{R}^n$ be closed and convex with $\mathbf{0} \in K$ . Then $K^{\circ\circ} = K$ .

Idea. One inclusion is the definition read twice. For the other, cut a point $\mathbf{x} \notin K$ off with Theorem 18.3.2, and rescale the normal so that $K$ lies in $\{\langle \cdot, \mathbf{b} \rangle \le 1\}$ while $\mathbf{x}$ does not. That rescaled normal lies in $K^{\circ}$ and witnesses $\mathbf{x} \notin K^{\circ\circ}$ ; the rescaling needs $\mathbf{0} \in K$ .

Proof. $(\supseteq)$ Let $\mathbf{x} \in K$ . For every $\mathbf{y} \in K^{\circ}$ , $\langle \mathbf{x}, \mathbf{y} \rangle \le 1$ by the definition of $K^{\circ}$ . Hence $\mathbf{x} \in K^{\circ\circ}$ .

$(\subseteq)$ Let $\mathbf{x} \notin K$ . By Theorem 18.3.2 there is $\mathbf{a} \ne \mathbf{0}$ with $\langle \mathbf{a}, \mathbf{z} \rangle \le \langle \mathbf{a}, \mathbf{x} \rangle - \left\| \mathbf{a} \right\|_2^2$ for all $\mathbf{z} \in K$ . Put $s = \sup_{\mathbf{z} \in K}\langle \mathbf{a}, \mathbf{z} \rangle$ , which exists by (A1); since $\mathbf{0} \in K$ , $s \ge 0$ , and $s < \langle \mathbf{a}, \mathbf{x} \rangle$ . If $s > 0$ , let $\mathbf{b} = \mathbf{a}/s$ . Then $\langle \mathbf{z}, \mathbf{b} \rangle \le 1$ for all $\mathbf{z} \in K$ , so $\mathbf{b} \in K^{\circ}$ , while $\langle \mathbf{x}, \mathbf{b} \rangle > 1$ . If $s = 0$ , then $\langle \mathbf{a}, \mathbf{x} \rangle > 0$ ; let $\mathbf{b} = 2\mathbf{a}/\langle \mathbf{a}, \mathbf{x} \rangle$ . Then $\langle \mathbf{z}, \mathbf{b} \rangle \le 0 \le 1$ on $K$ , so $\mathbf{b} \in K^{\circ}$ , while $\langle \mathbf{x}, \mathbf{b} \rangle = 2 > 1$ . In both cases $\mathbf{x} \notin K^{\circ\circ}$ .

The hypothesis $\mathbf{0} \in K$ was used to make $s \ge 0$ , so that dividing by $s$ keeps the direction of the inequality; the counterexample $\{\mathbf{e}_1\}$ above is exactly a closed convex set without it.

18.4.4. Dual norms

Chapter 16 measured vectors (Definition 16.1.1) and matrices (Definition 16.3.2). A third kind of object sits between them and was never measured: a linear functional on $\mathbb{R}^n$ , which by Theorem 5.1.1 is $\mathbf{x} \mapsto \mathbf{y}^{\top}\mathbf{x} = \langle \mathbf{x}, \mathbf{y} \rangle$ for exactly one $\mathbf{y}$ . How big is it?

When $\mathbf{x}$ is measured by $\left\| \cdot \right\|_2$ , Theorem 11.1.5 answers: $\lvert\langle \mathbf{x}, \mathbf{y} \rangle\rvert \le \left\| \mathbf{x} \right\|_2\left\| \mathbf{y} \right\|_2$ , and the constant $\left\| \mathbf{y} \right\|_2$ is the best possible. When $\mathbf{x}$ is measured by another norm, the question is the same — what is the smallest $c$ with $\lvert\langle \mathbf{x}, \mathbf{y} \rangle\rvert \le c\left\| \mathbf{x} \right\|$ for every $\mathbf{x}$ ? — and the answer is the largest value of $\langle \mathbf{x}, \mathbf{y} \rangle$ over the unit ball. That is the support function of $B$ , and it is also the operator norm of the $1 \times n$ matrix $\mathbf{y}^{\top}$ . An expression that turns up three ways deserves a name.

The dual norm of $\mathbf{y}$ is the most that the functional $\langle \cdot, \mathbf{y} \rangle$ can extract from a vector of norm at most one.

Definition 18.4.4 (Dual Norm)

Let $\left\| \cdot \right\|$ be a norm on $\mathbb{R}^n$ , with closed unit ball $B$ . The dual norm of $\left\| \cdot \right\|$ is the function $\left\| \cdot \right\|_{*} \colon \mathbb{R}^n \to \mathbb{R}$ given by $\left\| \mathbf{y} \right\|_{*} = \max\{\langle \mathbf{x}, \mathbf{y} \rangle : \mathbf{x} \in \mathbb{R}^n,\ \left\| \mathbf{x} \right\| \le 1\} = h_B(\mathbf{y}) .$

The maximum exists. By Theorem 18.4.2 (b), $B$ is non-empty, closed and bounded, hence compact by Corollary 16.2.5, which rests on fact (A3) of Chapter 16’s introduction; and $\mathbf{x} \mapsto \langle \mathbf{x}, \mathbf{y} \rangle$ is continuous, so by the extreme value theorem, fact (A4), it attains its maximum on $B$ .

In words: fix $\mathbf{y}$ , let $\mathbf{x}$ range over the vectors that the given norm calls short, and record the largest value of $\langle \mathbf{x}, \mathbf{y} \rangle$ . The inner product is part of the definition, and so is the norm; changing either changes $\left\| \cdot \right\|_{*}$ . No absolute value is needed in the maximum: $B$ is symmetric, so replacing $\mathbf{x}$ by $-\mathbf{x}$ shows that the largest value of $\langle \mathbf{x}, \mathbf{y} \rangle$ on $B$ is also the largest value of $\lvert\langle \mathbf{x}, \mathbf{y} \rangle\rvert$ .

Proposition 18.4.6 (Properties of the Dual Norm)

Let $\left\| \cdot \right\|$ be a norm on $\mathbb{R}^n$ , with closed unit ball $B$ .

(a) $\left\| \cdot \right\|_{*}$ is a norm on $\mathbb{R}^n$ .
(b) $\lvert\langle \mathbf{x}, \mathbf{y} \rangle\rvert \le \left\| \mathbf{x} \right\|\,\left\| \mathbf{y} \right\|_{*}$ for all $\mathbf{x}, \mathbf{y}$ , and $\left\| \mathbf{y} \right\|_{*}$ is the smallest constant $c$ with $\lvert\langle \mathbf{x}, \mathbf{y} \rangle\rvert \le c\left\| \mathbf{x} \right\|$ for every $\mathbf{x}$ .
(c) $\left\| \mathbf{y} \right\|_{*}$ is the operator norm (Definition 16.3.2) of the $1 \times n$ matrix $\mathbf{y}^{\top}$ , with $\left\| \cdot \right\|$ on $\mathbb{R}^n$ and $\lvert\cdot\rvert$ on $\mathbb{R}$ .
(d) The closed unit ball of $\left\| \cdot \right\|_{*}$ is the polar $B^{\circ}$ .

Idea. Each norm axiom for $\left\| \cdot \right\|_{*}$ is checked one $\mathbf{x} \in B$ at a time and then survives the maximum; (N1) needs a good test vector, $\mathbf{y}$ itself rescaled into $B$ . For (b), rescale any $\mathbf{x} \ne \mathbf{0}$ into $B$ . Parts (c) and (d) only compare definitions.

Proof.

(a) (N1): $\mathbf{x} = \mathbf{0} \in B$ gives $\left\| \mathbf{y} \right\|_{*} \ge 0$ . If $\mathbf{y} \ne \mathbf{0}$ , then $\mathbf{x} = \mathbf{y}/\left\| \mathbf{y} \right\| \in B$ gives $\left\| \mathbf{y} \right\|_{*} \ge \left\| \mathbf{y} \right\|_2^2/\left\| \mathbf{y} \right\| > 0$ . (N2): for $c \ge 0$ , $\max_B\langle \mathbf{x}, c\mathbf{y} \rangle = c\max_B\langle \mathbf{x}, \mathbf{y} \rangle$ ; for $c < 0$ , $\langle \mathbf{x}, c\mathbf{y} \rangle = \lvert c\rvert\langle -\mathbf{x}, \mathbf{y} \rangle$ , and $-\mathbf{x}$ runs over $B$ as $\mathbf{x}$ does, by (N2) for $\left\| \cdot \right\|$ . (N3): for $\mathbf{x} \in B$ , $\langle \mathbf{x}, \mathbf{y} + \mathbf{z} \rangle = \langle \mathbf{x}, \mathbf{y} \rangle + \langle \mathbf{x}, \mathbf{z} \rangle \le \left\| \mathbf{y} \right\|_{*} + \left\| \mathbf{z} \right\|_{*}$ ; take the maximum over $\mathbf{x}$ .
(b) For $\mathbf{x} = \mathbf{0}$ there is nothing to prove. For $\mathbf{x} \ne \mathbf{0}$ , $\mathbf{x}/\left\| \mathbf{x} \right\| \in B$ , so $\pm\langle \mathbf{x}, \mathbf{y} \rangle/\left\| \mathbf{x} \right\| = \langle \pm\mathbf{x}/\left\| \mathbf{x} \right\|, \mathbf{y} \rangle \le \left\| \mathbf{y} \right\|_{*}$ , using that $B$ is symmetric. If $c$ is any constant with $\lvert\langle \mathbf{x}, \mathbf{y} \rangle\rvert \le c\left\| \mathbf{x} \right\|$ for all $\mathbf{x}$ , then $\langle \mathbf{x}, \mathbf{y} \rangle \le c$ on $B$ , so $\left\| \mathbf{y} \right\|_{*} \le c$ .
(c) By Definition 16.3.2 and the equivalent descriptions that follow it in Chapter 16 §03, the operator norm of $\mathbf{y}^{\top}$ is $\max\{\lvert\mathbf{y}^{\top}\mathbf{x}\rvert : \left\| \mathbf{x} \right\| \le 1\}$ , which is $\left\| \mathbf{y} \right\|_{*}$ by the remark after Definition 18.4.4.
(d) $\left\| \mathbf{y} \right\|_{*} \le 1$ exactly when $\langle \mathbf{x}, \mathbf{y} \rangle \le 1$ for every $\mathbf{x} \in B$ , which is the definition of $\mathbf{y} \in B^{\circ}$ (Definition 18.4.3).

Part (b) is Cauchy–Schwarz for an arbitrary norm, with the price that the two factors are measured differently. Now the three norms of Chapter 16.

Proposition 18.4.7 (Duals of the 1-, 2- and Infinity-Norms)

On $\mathbb{R}^n$ with the dot product,

(a) the dual of $\left\| \cdot \right\|_1$ is $\left\| \cdot \right\|_\infty$ ;
(b) the dual of $\left\| \cdot \right\|_\infty$ is $\left\| \cdot \right\|_1$ ;
(c) the dual of $\left\| \cdot \right\|_2$ is $\left\| \cdot \right\|_2$ .

Idea. Each part is an upper bound and a witness, the same pattern as Theorem 16.3.3. For the $1$ -norm, all of the budget $\left\| \mathbf{x} \right\|_1 \le 1$ goes on the coordinate where $\lvert y_k\rvert$ is largest. For the $\infty$ -norm, every coordinate can be spent at once, each with the sign of $y_i$ , so nothing cancels. For the $2$ -norm, the witness is $\mathbf{y}$ itself, rescaled.

Proof.

(a) For $\left\| \mathbf{x} \right\|_1 \le 1$ , $\langle \mathbf{x}, \mathbf{y} \rangle \le \sum_i\lvert x_i\rvert\lvert y_i\rvert \le \left\| \mathbf{y} \right\|_\infty\sum_i\lvert x_i\rvert \le \left\| \mathbf{y} \right\|_\infty$ . Choose $k$ with $\lvert y_k\rvert = \left\| \mathbf{y} \right\|_\infty$ , and let $\mathbf{x} = \pm\mathbf{e}_k$ with the sign of $y_k$ (either sign if $y_k = 0$ ). Then $\left\| \mathbf{x} \right\|_1 = 1$ and $\langle \mathbf{x}, \mathbf{y} \rangle = \lvert y_k\rvert = \left\| \mathbf{y} \right\|_\infty$ .
(b) For $\left\| \mathbf{x} \right\|_\infty \le 1$ , $\langle \mathbf{x}, \mathbf{y} \rangle \le \sum_i\lvert x_i\rvert\lvert y_i\rvert \le \sum_i\lvert y_i\rvert = \left\| \mathbf{y} \right\|_1$ . Let $x_i = 1$ if $y_i \ge 0$ and $x_i = -1$ if $y_i < 0$ . Then $\left\| \mathbf{x} \right\|_\infty = 1$ and $\langle \mathbf{x}, \mathbf{y} \rangle = \sum_i\lvert y_i\rvert = \left\| \mathbf{y} \right\|_1$ .
(c) For $\left\| \mathbf{x} \right\|_2 \le 1$ , $\langle \mathbf{x}, \mathbf{y} \rangle \le \left\| \mathbf{x} \right\|_2\left\| \mathbf{y} \right\|_2 \le \left\| \mathbf{y} \right\|_2$ by Theorem 11.1.5. For $\mathbf{y} \ne \mathbf{0}$ , $\mathbf{x} = \mathbf{y}/\left\| \mathbf{y} \right\|_2$ gives equality; for $\mathbf{y} = \mathbf{0}$ both sides are $0$ .

So the $1$ - and $\infty$ -norms are each other’s duals, and the Euclidean norm is its own. In the language of polars, (a) and (b) say $(B_1)^{\circ} = B_\infty$ and $(B_\infty)^{\circ} = B_1$ : the diamond and the square of Chapter 16’s picture are polar to each other, and the disc is polar to itself. Part (b) of Proposition 18.4.6 now reads $\lvert\langle \mathbf{x}, \mathbf{y} \rangle\rvert \le \left\| \mathbf{x} \right\|_1\left\| \mathbf{y} \right\|_\infty$ , the simplest of a family of inequalities. The general member pairs $\left\| \cdot \right\|_p$ with $\left\| \cdot \right\|_q$ , $\tfrac1p + \tfrac1q = 1$ ; it is Hölder’s inequality, and §11 of this chapter proves it and deduces that the dual of $\left\| \cdot \right\|_p$ is $\left\| \cdot \right\|_q$ for every $1 < p < \infty$ . The degenerate case $n = 1$ is worth one line: every norm on $\mathbb{R}$ is $\left\| x \right\| = a\lvert x\rvert$ with $a > 0$ , its ball is $[-1/a, 1/a]$ , and $\left\| y \right\|_{*} = \lvert y\rvert/a$ .

A non-example by minimal change. Keep the formula $\max_K\langle \mathbf{x}, \mathbf{y} \rangle$ , and replace the symmetric ball by the triangle $K = \operatorname{conv}\{(-1,-1), (2,-1), (-1,2)\}$ , which is compact and convex and has $\mathbf{0}$ inside. By Proposition 18.4.3 (c), $h_K(\mathbf{y})$ is the largest of $-y_1 - y_2$ , $2y_1 - y_2$ and $-y_1 + 2y_2$ . It is sublinear by Proposition 18.4.3 (a), and positive at every $\mathbf{y} \ne \mathbf{0}$ , since the three numbers add up to $0$ and are not all zero. But $h_K(\mathbf{e}_1) = 2$ and $h_K(-\mathbf{e}_1) = 1$ , so (N2) fails at $c = -1$ . Symmetry of the ball is exactly what makes a dual norm a norm.

Why this definition, and not another? The measurement of a functional must be compatible with the measurement of its inputs, in the sense that $\lvert\langle \mathbf{x}, \mathbf{y} \rangle\rvert \le c\left\| \mathbf{x} \right\|$ for every $\mathbf{x}$ , and Proposition 18.4.6 (b) says that $\left\| \mathbf{y} \right\|_{*}$ is the smallest compatible $c$ . Any larger choice would be a bound, not a measurement. Abstractly, the dual norm lives on the dual space: for $\varphi \in (\mathbb{R}^n)^{*}$ one would put $\left\| \varphi \right\| = \max_{\left\| \mathbf{x} \right\| \le 1}\varphi(\mathbf{x})$ , and the dot product is used only to name $\varphi$ by a vector, through Theorem 5.1.1. That is why a different inner product on $\mathbb{R}^n$ gives a different formula for “the same” dual norm. The name is standard: the dual space carries the dual norm.

Warning. A larger norm has a smaller dual. If $\left\| \mathbf{x} \right\|_a \le \left\| \mathbf{x} \right\|_b$ for all $\mathbf{x}$ , then the ball of $\left\| \cdot \right\|_b$ lies inside the ball of $\left\| \cdot \right\|_a$ , and a maximum over a smaller set is smaller: $\left\| \mathbf{y} \right\|_{b*} \le \left\| \mathbf{y} \right\|_{a*}$ . For instance $N(\mathbf{x}) = 2\left\| \mathbf{x} \right\|_2$ has ball of radius $\tfrac12$ and dual $N_{*}(\mathbf{y}) = \tfrac12\left\| \mathbf{y} \right\|_2$ , not $2\left\| \mathbf{y} \right\|_2$ . Scaling a norm up scales its dual down.

Chapter 16 measured vectors and matrices but never a linear functional; Definition 18.4.4 fills that gap, and Proposition 18.4.6 (c) shows it is exactly an operator norm of Chapter 16, the one for $1 \times n$ matrices. The one question it leaves open is whether the construction loses information.

18.4.5. The dual of the dual

Apply the construction twice. Since $\left\| \cdot \right\|_{*}$ is a norm, it has a dual $\left\| \cdot \right\|_{**}$ , and the natural guess is that we are back where we started. For the three norms of Proposition 18.4.7 this is visible: $1 \to \infty \to 1$ and $2 \to 2 \to 2$ . In general it is a theorem, and its proof is a supporting hyperplane.

Theorem 18.4.8 (The Dual of the Dual Norm)

For every norm $\left\| \cdot \right\|$ on $\mathbb{R}^n$ , $\left\| \cdot \right\|_{**} = \left\| \cdot \right\|$ .

Idea. One inequality is Cauchy–Schwarz for dual norms. For the other, take $\mathbf{x}$ on the unit sphere of $\left\| \cdot \right\|$ . It is on the edge of the ball $B$ , so §03 provides a supporting hyperplane of $B$ at $\mathbf{x}$ . Its normal $\mathbf{a}$ is a direction in which $B$ reaches no further than $\mathbf{x}$ does, so the maximum defining $\left\| \mathbf{a} \right\|_{*}$ is attained at $\mathbf{x}$ ; rescaling $\mathbf{a}$ produces a functional of dual norm $1$ that takes the value $1$ at $\mathbf{x}$ .

Proof. Let $\mathbf{x} \in \mathbb{R}^n$ . For every $\mathbf{y}$ with $\left\| \mathbf{y} \right\|_{*} \le 1$ , Proposition 18.4.6 (b) gives $\langle \mathbf{x}, \mathbf{y} \rangle \le \left\| \mathbf{x} \right\|\left\| \mathbf{y} \right\|_{*} \le \left\| \mathbf{x} \right\|$ . By Definition 18.4.4 applied to $\left\| \cdot \right\|_{*}$ , whose unit ball is $\{\mathbf{y} : \left\| \mathbf{y} \right\|_{*} \le 1\}$ , this says $\left\| \mathbf{x} \right\|_{**} \le \left\| \mathbf{x} \right\|$ .

For the reverse inequality, both sides vanish at $\mathbf{x} = \mathbf{0}$ , and both are absolutely homogeneous, so it suffices to take $\left\| \mathbf{x} \right\| = 1$ . Then $\mathbf{x} \in B$ , but $\mathbf{x}$ is not an interior point of $B$ : the vectors $(1 + 1/k)\mathbf{x}$ have norm $1 + 1/k > 1$ and $\left\| (1 + 1/k)\mathbf{x} - \mathbf{x} \right\|_2 = \left\| \mathbf{x} \right\|_2/k \to 0$ . By Theorem 18.3.6, applied to the convex set $B$ and the point $\mathbf{x}$ , there is $\mathbf{a} \ne \mathbf{0}$ with $\langle \mathbf{z}, \mathbf{a} \rangle \le \langle \mathbf{x}, \mathbf{a} \rangle$ for every $\mathbf{z} \in B$ . Since $\mathbf{x} \in B$ , the maximum in Definition 18.4.4 is attained at $\mathbf{x}$ : $\left\| \mathbf{a} \right\|_{*} = \max_{\mathbf{z} \in B}\langle \mathbf{z}, \mathbf{a} \rangle = \langle \mathbf{x}, \mathbf{a} \rangle .$ By Proposition 18.4.6 (a), $\left\| \mathbf{a} \right\|_{*} > 0$ . Let $\mathbf{y} = \mathbf{a}/\left\| \mathbf{a} \right\|_{*}$ . Then $\left\| \mathbf{y} \right\|_{*} = 1$ and $\langle \mathbf{x}, \mathbf{y} \rangle = 1$ . Hence $\left\| \mathbf{x} \right\|_{**} \ge 1 = \left\| \mathbf{x} \right\|$ . This proves the theorem.

Alternatively, the vector $\mathbf{y}$ can be obtained from Hahn–Banach. Corollary 18.3.9, applied to $U = \operatorname{span}(\mathbf{x})$ and $f(t\mathbf{x}) = t\left\| \mathbf{x} \right\|$ , gives a functional $F$ with $F(\mathbf{x}) = \left\| \mathbf{x} \right\|$ and $\lvert F\rvert \le \left\| \cdot \right\|$ ; writing $F = \langle \cdot, \mathbf{y} \rangle$ by Theorem 5.1.1, the second property says $\left\| \mathbf{y} \right\|_{*} \le 1$ by Proposition 18.4.6 (b), so $\left\| \mathbf{x} \right\|_{**} \ge \langle \mathbf{x}, \mathbf{y} \rangle = \left\| \mathbf{x} \right\|$ . So the analytic and the geometric forms of §03 each prove the theorem, which is one more sign that they are the same fact.

Read with the definition of $\left\| \cdot \right\|_{**}$ unwound, the theorem is a formula for the original norm.

Corollary 18.4.9 (A Norm Is a Maximum of Linear Functions)

For every norm $\left\| \cdot \right\|$ on $\mathbb{R}^n$ and every $\mathbf{x} \in \mathbb{R}^n$ , $\left\| \mathbf{x} \right\| = \max\{\langle \mathbf{x}, \mathbf{y} \rangle : \left\| \mathbf{y} \right\|_{*} \le 1\} ,$ and when $\mathbf{x} \ne \mathbf{0}$ the maximum is attained at some $\mathbf{y}$ with $\left\| \mathbf{y} \right\|_{*} = 1$ .

Proof. The right-hand side is $\left\| \mathbf{x} \right\|_{**}$ by Definition 18.4.4 applied to $\left\| \cdot \right\|_{*}$ , and it equals $\left\| \mathbf{x} \right\|$ by Theorem 18.4.8. For $\mathbf{x} \ne \mathbf{0}$ , the proof of Theorem 18.4.8, applied to $\mathbf{x}/\left\| \mathbf{x} \right\|$ , produced $\mathbf{y}$ with $\left\| \mathbf{y} \right\|_{*} = 1$ and $\langle \mathbf{x}/\left\| \mathbf{x} \right\|, \mathbf{y} \rangle = 1$ , so $\langle \mathbf{x}, \mathbf{y} \rangle = \left\| \mathbf{x} \right\|$ .

So every norm is the support function of the unit ball of its dual, $\left\| \cdot \right\| = h_{\{\mathbf{y} : \left\| \mathbf{y} \right\|_{*} \le 1\}}$ : a maximum of the linear functions $\mathbf{x} \mapsto \langle \mathbf{x}, \mathbf{y} \rangle$ , one for each $\mathbf{y}$ in a compact set. §10 of this chapter shows that a pointwise maximum of linear functions is always convex, and norms (their convexity was already the triangle inequality) are among its first examples.

Quick check. For $\mathbf{x} = (3, -4)$ , find a $\mathbf{y}$ with $\left\| \mathbf{y} \right\|_\infty = 1$ and $\langle \mathbf{x}, \mathbf{y} \rangle = \left\| \mathbf{x} \right\|_1$ , and a $\mathbf{y}$ with $\left\| \mathbf{y} \right\|_1 = 1$ and $\langle \mathbf{x}, \mathbf{y} \rangle = \left\| \mathbf{x} \right\|_\infty$ .

Solution. The dual of $\left\| \cdot \right\|_1$ is $\left\| \cdot \right\|_\infty$ (Proposition 18.4.7 (a)), so the first $\mathbf{y}$ is a sign vector: $\mathbf{y} = (1, -1)$ gives $3 + 4 = 7 = \left\| \mathbf{x} \right\|_1$ . The dual of $\left\| \cdot \right\|_\infty$ is $\left\| \cdot \right\|_1$ , so the second $\mathbf{y}$ puts all its weight on the largest coordinate: $\mathbf{y} = (0, -1)$ gives $4 = \left\| \mathbf{x} \right\|_\infty$ . Each is the witness from the proof of Proposition 18.4.7, with the roles of $\mathbf{x}$ and $\mathbf{y}$ exchanged.

18.4.6. Operator norms as maxima of bilinear values

The corollary also rewrites Chapter 16’s operator norm. Fix a norm $\left\| \cdot \right\|_\alpha$ on $\mathbb{R}^n$ and a norm $\left\| \cdot \right\|_\beta$ on $\mathbb{R}^m$ , and write $\left\| \mathbf{A} \right\|_{\alpha\to\beta}$ for the operator norm of $\mathbf{A} \in M_{m\times n}(\mathbb{R})$ that they induce (Definition 16.3.2). By the equivalent descriptions after that definition, $\left\| \mathbf{A} \right\|_{\alpha\to\beta} = \max\{\left\| \mathbf{A}\mathbf{x} \right\|_\beta : \left\| \mathbf{x} \right\|_\alpha \le 1\}$ .

Proposition 18.4.10 (Operator Norms through Dual Norms)

Let $\mathbf{A} \in M_{m \times n}(\mathbb{R})$ , and let $\left\| \cdot \right\|_\alpha$ , $\left\| \cdot \right\|_\beta$ be norms on $\mathbb{R}^n$ and $\mathbb{R}^m$ , with duals $\left\| \cdot \right\|_{\alpha*}$ and $\left\| \cdot \right\|_{\beta*}$ . Then

(a) $\left\| \mathbf{A} \right\|_{\alpha\to\beta} = \max\{\mathbf{y}^{\top}\mathbf{A}\mathbf{x} : \left\| \mathbf{x} \right\|_\alpha \le 1,\ \left\| \mathbf{y} \right\|_{\beta*} \le 1\}$ ;
(b) $\left\| \mathbf{A}^{\top} \right\|_{\beta*\to\alpha*} = \left\| \mathbf{A} \right\|_{\alpha\to\beta}$ .

Idea. Write the outer norm $\left\| \mathbf{A}\mathbf{x} \right\|_\beta$ as a maximum over its dual ball by Corollary 18.4.9, and the operator norm becomes one maximum over pairs $(\mathbf{x}, \mathbf{y})$ . Since $\mathbf{y}^{\top}\mathbf{A}\mathbf{x} = \mathbf{x}^{\top}\mathbf{A}^{\top}\mathbf{y}$ , the same double maximum, taken with $\mathbf{x}$ innermost, is the operator norm of $\mathbf{A}^{\top}$ , which gives (b).

Proof.

(a) For $\left\| \mathbf{x} \right\|_\alpha \le 1$ , Corollary 18.4.9 in $\mathbb{R}^m$ gives $\left\| \mathbf{A}\mathbf{x} \right\|_\beta = \max\{\mathbf{y}^{\top}\mathbf{A}\mathbf{x} : \left\| \mathbf{y} \right\|_{\beta*} \le 1\}$ . So every value $\mathbf{y}^{\top}\mathbf{A}\mathbf{x}$ in the set is at most $\left\| \mathbf{A}\mathbf{x} \right\|_\beta \le \left\| \mathbf{A} \right\|_{\alpha\to\beta}$ . Conversely, choose $\mathbf{x}_0$ with $\left\| \mathbf{x}_0 \right\|_\alpha \le 1$ and $\left\| \mathbf{A}\mathbf{x}_0 \right\|_\beta = \left\| \mathbf{A} \right\|_{\alpha\to\beta}$ , which exists by Lemma 16.3.1, and then $\mathbf{y}_0$ attaining the maximum for $\left\| \mathbf{A}\mathbf{x}_0 \right\|_\beta$ . The value $\mathbf{y}_0^{\top}\mathbf{A}\mathbf{x}_0$ equals $\left\| \mathbf{A} \right\|_{\alpha\to\beta}$ , so the maximum exists and has this value.
(b) By the equivalent descriptions after Definition 16.3.2, and then Definition 18.4.4 for $\left\| \cdot \right\|_{\alpha*}$ , $\left\| \mathbf{A}^{\top} \right\|_{\beta*\to\alpha*} = \max_{\left\| \mathbf{y} \right\|_{\beta*} \le 1}\left\| \mathbf{A}^{\top}\mathbf{y} \right\|_{\alpha*} = \max_{\left\| \mathbf{y} \right\|_{\beta*} \le 1}\ \max_{\left\| \mathbf{x} \right\|_\alpha \le 1}\langle \mathbf{x}, \mathbf{A}^{\top}\mathbf{y} \rangle .$ Since $\langle \mathbf{x}, \mathbf{A}^{\top}\mathbf{y} \rangle = \mathbf{x}^{\top}\mathbf{A}^{\top}\mathbf{y} = \mathbf{y}^{\top}\mathbf{A}\mathbf{x}$ , this is the maximum in (a).

With $\alpha = \beta = \infty$ , part (b) and Proposition 18.4.7 say $\left\| \mathbf{A}^{\top} \right\|_1 = \left\| \mathbf{A} \right\|_\infty$ : the largest column sum of $\mathbf{A}^{\top}$ is the largest row sum of $\mathbf{A}$ , which is also what Theorem 16.3.3 gives directly. With $\alpha = \beta = 2$ it says $\left\| \mathbf{A}^{\top} \right\|_2 = \left\| \mathbf{A} \right\|_2$ , that is, $\sigma_1(\mathbf{A}^{\top}) = \sigma_1(\mathbf{A})$ . For the matrix $\mathbf{A} = \begin{psmallmatrix} 3 & 0 \\ 4 & 5\end{psmallmatrix}$ of Example (One matrix, four numbers), $\left\| \mathbf{A} \right\|_1 = 7$ and $\left\| \mathbf{A} \right\|_\infty = 9$ . Its transpose $\begin{psmallmatrix} 3 & 4 \\ 0 & 5\end{psmallmatrix}$ has column sums $3$ and $9$ and row sums $7$ and $5$ , so $\left\| \mathbf{A}^{\top} \right\|_1 = 9 = \left\| \mathbf{A} \right\|_\infty$ and $\left\| \mathbf{A}^{\top} \right\|_\infty = 7 = \left\| \mathbf{A} \right\|_1$ , as (b) predicts.

18.4.7. Exercises

A. Check your understanding

Exercise (A1)

(a) Define the gauge $p_K$ , the support function $h_K$ and the dual norm $\left\| \cdot \right\|_{*}$ , stating what each needs of the set or norm involved.
(b) Determine whether the following statement is correct, and justify your answer: the support function of every non-empty bounded subset of $\mathbb{R}^2$ is a norm.
(c) What is the dual of $\left\| \cdot \right\|_\infty$ on $\mathbb{R}^n$ ? What is the dual of that?
(d) Which result of §03 does the proof of Theorem 18.4.8 use, and at which point?
(e) Determine whether the following statement is correct, and justify your answer: $K^{\circ\circ} = K$ for every non-empty closed convex $K \subseteq \mathbb{R}^n$ .

Solution.

(a) For $K$ convex with $\mathbf{0}$ an interior point, $p_K(\mathbf{x}) = \inf\{t > 0 : \mathbf{x} \in tK\}$ (Definition 18.4.1). For $K$ non-empty, $h_K(\mathbf{y}) = \sup_{\mathbf{x} \in K}\langle \mathbf{x}, \mathbf{y} \rangle$ , possibly $+\infty$ (Definition 18.4.2). For a norm $\left\| \cdot \right\|$ with ball $B$ , $\left\| \mathbf{y} \right\|_{*} = \max_{\mathbf{x} \in B}\langle \mathbf{x}, \mathbf{y} \rangle = h_B(\mathbf{y})$ (Definition 18.4.4).
(b) Incorrect. For $K = \{\mathbf{0}\}$ , $h_K = 0$ , which violates (N1). For the segment $[-\mathbf{e}_1, \mathbf{e}_1]$ , $h_K(\mathbf{y}) = \lvert y_1\rvert$ vanishes at $\mathbf{e}_2$ . Support functions are sublinear (Proposition 18.4.3 (a)) but need not be norms.
(c) $\left\| \cdot \right\|_1$ , by Proposition 18.4.7 (b); and the dual of $\left\| \cdot \right\|_1$ is $\left\| \cdot \right\|_\infty$ again, by (a) of the same proposition, as Theorem 18.4.8 requires.
(d) Theorem 18.3.6, applied to the unit ball $B$ at a point $\mathbf{x}$ with $\left\| \mathbf{x} \right\| = 1$ , to produce a normal $\mathbf{a}$ at which the maximum defining $\left\| \mathbf{a} \right\|_{*}$ is attained at $\mathbf{x}$ .
(e) Incorrect. For $K = \{\mathbf{e}_1\}$ in $\mathbb{R}^2$ , $K^{\circ\circ}$ is the segment $[\mathbf{0}, \mathbf{e}_1]$ . Theorem 18.4.5 needs $\mathbf{0} \in K$ .

B. Practice

Exercise (B1: A weighted norm and its dual)

On $\mathbb{R}^2$ let $N(\mathbf{x}) = \max\bigl(\lvert x_1\rvert, 2\lvert x_2\rvert\bigr)$ .

(a) Prove that $N_{*}(\mathbf{y}) = \lvert y_1\rvert + \tfrac12\lvert y_2\rvert$ .
(b) Verify Theorem 18.4.8 for $N$ by computing $N_{**}$ directly.

Solution.

(a) The ball of $N$ is the rectangle $\lvert x_1\rvert \le 1$ , $\lvert x_2\rvert \le \tfrac12$ . On it, $\langle \mathbf{x}, \mathbf{y} \rangle \le \lvert x_1\rvert\lvert y_1\rvert + \lvert x_2\rvert\lvert y_2\rvert \le \lvert y_1\rvert + \tfrac12\lvert y_2\rvert$ . The point $\mathbf{x} = (s_1, \tfrac12 s_2)$ , where $s_i = 1$ if $y_i \ge 0$ and $s_i = -1$ otherwise, lies in the ball and gives equality. So $N_{*}(\mathbf{y}) = \lvert y_1\rvert + \tfrac12\lvert y_2\rvert$ .
(b) The ball of $N_{*}$ is $\{\lvert y_1\rvert + \tfrac12\lvert y_2\rvert \le 1\}$ . On it, $\langle \mathbf{x}, \mathbf{y} \rangle \le \lvert x_1\rvert\lvert y_1\rvert + 2\lvert x_2\rvert\cdot\tfrac12\lvert y_2\rvert \le N(\mathbf{x})\bigl(\lvert y_1\rvert + \tfrac12\lvert y_2\rvert\bigr) \le N(\mathbf{x}) .$ If $N(\mathbf{x}) = \lvert x_1\rvert$ , the point $\mathbf{y} = \pm\mathbf{e}_1$ (sign of $x_1$ ) lies in the ball and gives $\langle \mathbf{x}, \mathbf{y} \rangle = \lvert x_1\rvert$ . If $N(\mathbf{x}) = 2\lvert x_2\rvert$ , the point $\mathbf{y} = \pm2\mathbf{e}_2$ (sign of $x_2$ ) lies in the ball, since $\tfrac12\cdot 2 = 1$ , and gives $\langle \mathbf{x}, \mathbf{y} \rangle = 2\lvert x_2\rvert$ . So $N_{**} = N$ .

Exercise (B2: A hexagonal norm)

Let $K = \{\mathbf{x} \in \mathbb{R}^2 : \lvert x_1\rvert \le 1,\ \lvert x_2\rvert \le 1,\ \lvert x_1 - x_2\rvert \le 1\}$ .

(a) Check that $K$ satisfies the hypotheses of Theorem 18.4.2 (a).
(b) Show that $p_K(\mathbf{x}) = \max\bigl(\lvert x_1\rvert, \lvert x_2\rvert, \lvert x_1 - x_2\rvert\bigr)$ , and compute $p_K\bigl((2, -1)\bigr)$ .
(c) Determine whether $p_K$ is induced by an inner product. Justify your answer.

Solution.

(a) $K$ is the intersection of six closed half-planes, such as $\{x_1 \le 1\}$ and $\{x_1 - x_2 \ge -1\}$ , each closed and convex (§03, before Definition 18.3.1); so $K$ is closed and convex. It is bounded, since $\left\| \mathbf{x} \right\|_2 \le \sqrt2$ when $\lvert x_1\rvert, \lvert x_2\rvert \le 1$ . It is symmetric, since each condition is unchanged by $\mathbf{x} \mapsto -\mathbf{x}$ . And if $\left\| \mathbf{x} \right\|_2 < \tfrac12$ , then $\lvert x_1\rvert, \lvert x_2\rvert < \tfrac12$ and $\lvert x_1 - x_2\rvert < 1$ , so $\mathbf{x} \in K$ and $\mathbf{0}$ is an interior point.
(b) For $t > 0$ , $\mathbf{x} \in tK$ exactly when $\mathbf{x}/t \in K$ , that is, when $\lvert x_1\rvert \le t$ , $\lvert x_2\rvert \le t$ and $\lvert x_1 - x_2\rvert \le t$ . The infimum of such $t$ is $M = \max(\lvert x_1\rvert, \lvert x_2\rvert, \lvert x_1 - x_2\rvert)$ when $\mathbf{x} \ne \mathbf{0}$ , and $0 = M$ when $\mathbf{x} = \mathbf{0}$ . So $p_K\bigl((2,-1)\bigr) = \max(2, 1, 3) = 3$ .
(c) No. With $\mathbf{u} = \mathbf{e}_1$ and $\mathbf{v} = \mathbf{e}_2$ , $p_K(\mathbf{u} + \mathbf{v}) = \max(1, 1, 0) = 1$ and $p_K(\mathbf{u} - \mathbf{v}) = \max(1, 1, 2) = 2$ , so the left side of the parallelogram law is $1 + 4 = 5$ , while the right side is $2\cdot 1 + 2\cdot 1 = 4$ . By Theorem 16.1.3, no inner product induces $p_K$ .

Exercise (B3: The polar of a triangle)

Let $K = \operatorname{conv}\{(-1,-1), (2,-1), (-1,2)\} \subseteq \mathbb{R}^2$ .

(a) Compute $h_K(\mathbf{e}_1)$ , $h_K(-\mathbf{e}_1)$ and $h_K\bigl((1,1)\bigr)$ .
(b) Describe $K^{\circ}$ by three linear inequalities.
(c) Show that $(-1, 0)$ , $(0, -1)$ and $(1, 1)$ lie in $K^{\circ}$ , and that $(1, 0)$ does not.

Solution.

(a) By Proposition 18.4.3 (c), $h_K(\mathbf{y})$ is the largest of $\langle \mathbf{v}, \mathbf{y} \rangle$ over the three vertices $\mathbf{v}$ , that is, of $-y_1 - y_2$ , $2y_1 - y_2$ , $-y_1 + 2y_2$ . So $h_K(\mathbf{e}_1) = \max(-1, 2, -1) = 2$ , $h_K(-\mathbf{e}_1) = \max(1, -2, 1) = 1$ , and $h_K\bigl((1,1)\bigr) = \max(-2, 1, 1) = 1$ .
(b) $\mathbf{y} \in K^{\circ}$ exactly when $h_K(\mathbf{y}) \le 1$ , that is, $-y_1 - y_2 \le 1, \qquad 2y_1 - y_2 \le 1, \qquad -y_1 + 2y_2 \le 1 .$
(c) At $(-1, 0)$ the three left sides are $1, -2, 1$ ; at $(0, -1)$ they are $1, 1, -2$ ; at $(1, 1)$ they are $-2, 1, 1$ . All are $\le 1$ . At $(1, 0)$ the second is $2 > 1$ , so $(1, 0) \notin K^{\circ}$ , in agreement with $h_K(\mathbf{e}_1) = 2$ .

C. Going deeper

Exercise (C1: The norm from 1 to infinity)

Let $\mathbf{A} \in M_{m \times n}(\mathbb{R})$ , and let $\left\| \mathbf{A} \right\|_{1\to\infty}$ be the operator norm with $\left\| \cdot \right\|_1$ on $\mathbb{R}^n$ and $\left\| \cdot \right\|_\infty$ on $\mathbb{R}^m$ .

(a) Using Proposition 18.4.10 (a), prove that $\left\| \mathbf{A} \right\|_{1\to\infty} = \max_{i,j}\lvert a_{ij}\rvert$ .
(b) Deduce from Proposition 18.4.10 (b) that the operator norm of $\mathbf{A}^{\top}$ with $\left\| \cdot \right\|_1$ on $\mathbb{R}^m$ and $\left\| \cdot \right\|_\infty$ on $\mathbb{R}^n$ is the same number.
(c) Explain why this does not contradict the warning of Chapter 16 §03 that the entrywise maximum is not a matrix norm.

Solution.

(a) By Proposition 18.4.7 (b), the dual of $\left\| \cdot \right\|_\infty$ is $\left\| \cdot \right\|_1$ , so Proposition 18.4.10 (a) gives $\left\| \mathbf{A} \right\|_{1\to\infty} = \max\{\mathbf{y}^{\top}\mathbf{A}\mathbf{x} : \left\| \mathbf{x} \right\|_1 \le 1,\ \left\| \mathbf{y} \right\|_1 \le 1\}$ . Write $M = \max_{i,j}\lvert a_{ij}\rvert$ . For such $\mathbf{x}, \mathbf{y}$ , $\mathbf{y}^{\top}\mathbf{A}\mathbf{x} = \sum_{i,j}y_ia_{ij}x_j \le M\sum_i\lvert y_i\rvert\sum_j\lvert x_j\rvert \le M .$ If $\lvert a_{kl}\rvert = M$ , then $\mathbf{x} = \mathbf{e}_l$ and $\mathbf{y} = \pm\mathbf{e}_k$ , with the sign of $a_{kl}$ , give $\mathbf{y}^{\top}\mathbf{A}\mathbf{x} = M$ . So $\left\| \mathbf{A} \right\|_{1\to\infty} = M$ .
(b) By Proposition 18.4.10 (b) with $\alpha = 1$ and $\beta = \infty$ , $\left\| \mathbf{A}^{\top} \right\|_{\beta*\to\alpha*} = \left\| \mathbf{A}^{\top} \right\|_{1\to\infty}$ equals $\left\| \mathbf{A} \right\|_{1\to\infty}$ , using $\beta* = 1$ and $\alpha* = \infty$ from Proposition 18.4.7. This is consistent with (a), since $\mathbf{A}$ and $\mathbf{A}^{\top}$ have the same entries.
(c) $\left\| \cdot \right\|_{1\to\infty}$ uses different norms on the source and the target, so the product $\mathbf{A}\mathbf{B}$ of two square matrices is measured by a norm that does not compose: submultiplicativity in Theorem 16.3.2 (d) needs the target norm of $\mathbf{B}$ to be the source norm of $\mathbf{A}$ . With one norm on $M_n(\mathbb{R})$ the entrywise maximum is not submultiplicative (Example (The entrywise maximum is not submultiplicative)), and nothing here says otherwise.

Exercise (C2: Equivalence constants dualize)

Let $N_1, N_2$ be norms on $\mathbb{R}^n$ and $0 < m \le M$ constants with $mN_1(\mathbf{x}) \le N_2(\mathbf{x}) \le MN_1(\mathbf{x})$ for every $\mathbf{x}$ .

(a) Prove that $\tfrac1M N_{1*}(\mathbf{y}) \le N_{2*}(\mathbf{y}) \le \tfrac1m N_{1*}(\mathbf{y})$ for every $\mathbf{y}$ .
(b) Apply (a) to $\left\| \mathbf{x} \right\|_2 \le \left\| \mathbf{x} \right\|_1 \le \sqrt n\,\left\| \mathbf{x} \right\|_2$ from Proposition 16.1.2, and compare the result with that proposition.

Solution.

(a) If $N_2(\mathbf{x}) \le 1$ , then $N_1(\mathbf{x}) \le 1/m$ , so $\mathbf{x} = \tfrac1m\mathbf{x}'$ with $N_1(\mathbf{x}') \le 1$ , and $\langle \mathbf{x}, \mathbf{y} \rangle = \tfrac1m\langle \mathbf{x}', \mathbf{y} \rangle \le \tfrac1m N_{1*}(\mathbf{y})$ . Taking the maximum over the ball of $N_2$ gives $N_{2*}(\mathbf{y}) \le \tfrac1m N_{1*}(\mathbf{y})$ . If $N_1(\mathbf{x}) \le 1$ , then $N_2(\mathbf{x}) \le M$ , and Proposition 18.4.6 (b) gives $\langle \mathbf{x}, \mathbf{y} \rangle \le N_2(\mathbf{x})N_{2*}(\mathbf{y}) \le MN_{2*}(\mathbf{y})$ ; so $N_{1*}(\mathbf{y}) \le MN_{2*}(\mathbf{y})$ .
(b) Take $N_1 = \left\| \cdot \right\|_2$ , $N_2 = \left\| \cdot \right\|_1$ , $m = 1$ , $M = \sqrt n$ . The duals are $\left\| \cdot \right\|_2$ and $\left\| \cdot \right\|_\infty$ (Proposition 18.4.7), so (a) gives $\tfrac{1}{\sqrt n}\left\| \mathbf{y} \right\|_2 \le \left\| \mathbf{y} \right\|_\infty \le \left\| \mathbf{y} \right\|_2$ . These are exactly the other two inequalities $\left\| \mathbf{y} \right\|_\infty \le \left\| \mathbf{y} \right\|_2 \le \sqrt n\,\left\| \mathbf{y} \right\|_\infty$ of Proposition 16.1.2: that proposition is closed under duality, with the constants carried over unchanged.

Exercise (C3: The gauge is the support function of the polar)

Let $K \subseteq \mathbb{R}^n$ be closed and convex, with $\mathbf{0}$ an interior point.

(a) Prove that $p_K(\mathbf{x}) = h_{K^{\circ}}(\mathbf{x})$ for every $\mathbf{x}$ . Hint: for $t > 0$ , rewrite “ $\mathbf{x} \in tK$ ” using Theorem 18.4.5.
(b) Deduce Theorem 18.4.8 again from (a), Theorem 18.4.2 (b) and Proposition 18.4.6 (d).

Solution.

(a) The polar $K^{\circ}$ contains $\mathbf{0}$ , so $h_{K^{\circ}}(\mathbf{x}) \ge \langle \mathbf{x}, \mathbf{0} \rangle = 0$ . Let $t > 0$ . By Theorem 18.4.5, $K = K^{\circ\circ}$ , so $\mathbf{x} \in tK \iff \mathbf{x}/t \in K^{\circ\circ} \iff \langle \mathbf{x}, \mathbf{y} \rangle \le t \text{ for every } \mathbf{y} \in K^{\circ} \iff h_{K^{\circ}}(\mathbf{x}) \le t .$ So the admissible $t$ in Definition 18.4.1 are the $t > 0$ with $t \ge h_{K^{\circ}}(\mathbf{x})$ , and their infimum is $h_{K^{\circ}}(\mathbf{x})$ (if $h_{K^{\circ}}(\mathbf{x}) = 0$ , the admissible $t$ are all $t > 0$ , with infimum $0$ ). In particular $h_{K^{\circ}}(\mathbf{x})$ is finite.
(b) Let $B$ be the ball of $\left\| \cdot \right\|$ . By Theorem 18.4.2 (b), $B$ is closed and convex with $\mathbf{0}$ interior, and $\left\| \cdot \right\| = p_B$ . By (a), $p_B = h_{B^{\circ}}$ , and $B^{\circ}$ is the ball of $\left\| \cdot \right\|_{*}$ by Proposition 18.4.6 (d). So $\left\| \mathbf{x} \right\| = \max\{\langle \mathbf{x}, \mathbf{y} \rangle : \left\| \mathbf{y} \right\|_{*} \le 1\} = \left\| \mathbf{x} \right\|_{**}$ , the maximum existing by Definition 18.4.4 applied to $\left\| \cdot \right\|_{*}$ .