\[ \newcommand{R}{\mathbb{R}} \newcommand{C}{\mathbb{C}} \newcommand{defarrow}{\quad \stackrel{\text{def}}{\Longleftrightarrow} \quad} \]

Normed spaces

Definition

A normed space is a vector space \(X\) endowed with a function \[ X \to [0,\infty), \qquad x \mapsto \| x \|, \] called the norm on \(X\), which satisfies: \[ \begin{align*} &\mathrm{(i)} \quad &\|\lambda x\| &= |\lambda|\, \|x\|, \qquad&\text{(positive homogeneity)}&\\ &\mathrm{(ii)} \qquad& \|x + y\| &\leq \|x\| + \|y\|, \qquad&\text{(triangle inequality)}&\\ &\mathrm{(iii)} \quad\; &\|x\| = 0 \quad&\text{if and only if }\quad x = 0, \qquad&\text{(positive definiteness)}&\\ \end{align*} \] for all scalars \(\lambda\) and all elements \(x, y \in X\). A vector space may allow for many different norms, but not all vector spaces are normable.¹⁾

Ex.

The vector space \(\R^n\) with the usual addition and scalar multiplication allows for several norms, for example:

\(\quad\) the Euclidean norm \[ \|(x_1,\ldots, x_n)\|_{l_2} = \big( x_1^2 + \ldots + x_n^2 \big)^{1/2} \] \(\quad\) the maximum norm \[ \|(x_1,\ldots, x_n)\|_{l_\infty} = \mathrm{max} \{ |x_1|, \ldots, |x_n| \}, \] \(\quad\) and the summation norm \[ \|(x_1,\ldots, x_n)\|_{l_1} = |x_1| + \ldots + |x_n|. \] \(\quad\) These are all special cases of the (finite-dimensional) \(l_p\)-norm \(\|(x_1,\ldots, x_n)\|_{l_p} = \big( \sum_{j = 1}^n |x_j|^p \big)^{1/p}\), \(1 \leq p \leq \infty\).

Proof (of the example)

For both \(\|\cdot\|_{l_2}\), \(\|\cdot\|_{l_\infty}\) and \(\|\cdot\|_{l_1}\), it is clear that they are non-negative functions, and that \[ \| x \| = 0 \quad\Longleftrightarrow\quad x = (x_1, \ldots, x_n) = (0,\ldots,0).\] In addition, \[ \| \lambda x \|_{l_2} = \big( (\lambda x_1)^2 + \cdots + (\lambda x_n)^2 \big)^{1/2} = |\lambda| \big( x_1^2 + \cdots + x_n^2 \big)^{1/2} = |\lambda| \|x\|_{l_2}, \] and similarly for \(\|\cdot\|_{l_\infty}\) and \(\|\cdot\|_{l_1}\).

The triangle inequality for \(\|\cdot\|_{l_\infty}\) and \(\|\cdot\|_{l_1}\) follows from that on \(\R\):

\[ \begin{align} \|x +y\|_{l_1} &= \sum_{j=1}^n |x_j + y_j| \leq \sum_{j=1}^n ( |x_j| + |y_j| ) = \sum_{j=1}^n |x_j| + \sum_{j=1}^n |y_j| = \|x\|_{l_1} + \|y\|_{l_1}, \end{align} \]

\[ \begin{align} \|x +y\|_{l_\infty} &= \mathrm{max} \{ |x_1 + y_1|, \ldots, |x_n + y_n| \}\\ &\leq \mathrm{max} \{ |x_1| + |y_1|, \ldots, |x_n| + |y_n| \}\\ &\leq \mathrm{max} \{ |x_1|, \ldots, |x_n| \} + \mathrm{max} \{ |y_1|, \ldots, |y_n| \}\\ &= \|x\|_{l_\infty} + \|y\|_{l_\infty}. \end{align} \]

The triangle inequality for \(\|\cdot\|_{l_2}\) is a consequence of the Cauchy–Schwarz inequality, which we will prove later.

Ex.

The space of real- (or complex-) valued bounded and continuous functions on an interval (open or closed), \(BC(I,\R)\), becomes a normed vector space when endowed with the supremum norm²⁾ \[\|f\|_\infty = \sup_{x \in I} |f(x)|.\] If \(I = [a,b]\) it follows from the extreme value theorem that \(BC([a,b],\R) = C([a,b],\R)\) (as sets and linear spaces) and \[ \|f\|_{\infty} = \sup_{x \in [a,b]} |f(x)| = \max_{x \in [a,b]} |f(x)|.\] If \(I = (a,b)\) is either infinite or does not contain its end points, then \(BC((a,b),\R) \subsetneq C((a,b),\R)\). An example of this strict inclusion is the function \(x \mapsto 1/x\) on (0,1). It is continuous, but \[ [x \mapsto 1/x] \not\in BC((0,1),\R),\] since \(\sup_{x \in(0,1)} |1/x| = \infty.\)

Equivalence of norms

Two norms \(\|\cdot\|_1\) and \(\|\cdot\|_2\) on a vector space \(X\) are said to be equivalent if there exists a number \(c \in \R\) such that \[ c^{-1} \|x\|_1 \leq \|x\|_2 \leq c \|x\|_1 \qquad \text{ for all } \quad x \in X. \]

Ex.

The maximum and summation norms are equivalent on \(\R^n\), since \[ \max\limits_{1 \leq j \leq n} |x_j| \leq \sum_{j=1}^n |x_j| \quad\text{ and }\quad \sum_{j=1}^n |x_j| \leq n \max\limits_{1 \leq j \leq n} |x_j|.\] Hence \[n^{-1} \|x\|_{l_\infty} \leq \|x\|_{l_1} \leq n \|x\|_{l_\infty} \qquad\text{ for }\quad x = (x_1,\ldots, x_n).\]
One can show that, on a finite-dimensional vector space, any two norms are equivalent. In particular, any norm on \(\R^n\) is equivalent to the Euclidean norm.

¹⁾

Using the axiom of choice it is possible to assign a norm to any vector space, but this norm may not correspond to any natural structure of the space. For example, there is no norm such that \(C^\infty(\R,\R)\), the set of infinitely differentiable real-valued functions on \(\R\), is complete.

²⁾

The supremum of a set \(A \subset \R\) is the smallest \(M \in \R\) such that \(a \leq M\) for all \(a \in A\). If no such finite \(M\) exists, then \(\sup(A) = \infty\). One furthermore defines \(\sup(\emptyset) = -\infty\). Thus, the supremum always exists. In a similar fashion, the infimimum of a set \(A\) is the largest lower bound on the set; it can be defined as \(\inf(A) = -\sup(-A)\), where \(-A = \{ -a \in \mathbb R \colon a \in A \}\).