Dual norm in R^n

By | October 20, 2017

Using the separating hyperplane theorem, we prove the dual norm of the dual norm is the original norm.

1. Extension Theorem

Let \Norm{\cdot} be a norm on \mathbb{R}^{n}. The dual norm of a norm \Norm{\cdot} is defined by

    \[ \Norm y_{*}=\max\left\{ x^{T}y:x\in\mathbb{R}^{n},\Norm x\le1\right\} . \]

For any x\in\mathbb{R}^{n}, we show

    \[ \Norm x=\max\left\{ x^{T}y:y\in\mathbb{R}^{n},\Norm y_{*}\le1\right\} . \]

By definition, we have

    \[ x^{T}y\le\Norm x\Norm y_{*}. \]

So

    \[ \max\left\{ x^{T}y:y\in\mathbb{R}^{n},\Norm y_{*}\le1\right\} \le\Norm x. \]

It remains to prove the reverse inequality. We will show that there exists y\in\mathbb{R}^{n} such that \Norm y_{*}=1 and

(1)   \begin{equation*} x^{T}y=\Norm x. \end{equation*}

Theorem 1. Let A be a subspace of \mathbb{R}^{n} and let f:A\rightarrow\mathbb{R} be a linear functional on A satisfying

    \[ \left|f\left(x\right)\right|\le\Norm x\quad\text{for all }x\in A. \]

Then there exists a\in\mathbb{R}^{n} satisfying

    \[ f\left(x\right)=a^{T}x\quad\text{for all }x\in A \]

and

    \[ \left|a^{T}x\right|\le\Norm x\quad\text{for all }x\in\mathbb{R}^{n}. \]

One can prove this theorem directly. See [1] or [3].However, we prove this theorem using the following lemma:

Lemma 1. Let A be an affine set in \mathbb{R}^{n} and let C be a non-empty convex subset of \mathbb{R}^{n}, not intersecting A. Then there exists a hyperplane H in \mathbb{R}^{n} containing A and not intersecting C.

Proof. By the separating hyperplane theorem, there exist a\in\mathbb{R}^{n}\setminus\left\{ 0\right\} and b\in\mathbb{R} such that

    \[ a^{T}y\ge b\quad\text{for all }x\in A\quad\text{and}\quad a^{T}x\le b\quad\text{for all }x\in C. \]

Define

    \[ H=\left\{ z\in\mathbb{R}^{n}:a^{T}z=b\right\} . \]

Then it is a hyperplane in \mathbb{R}^{n}. There are two cases to consider. First, suppose A\cap H\neq\varnothing. Then there exists x_{0}\in\mathbb{R}^{n} with a^{T}x_{0}=b. Then for x\in A, note that 2x_{0}-x\in A since A is an affine set. So

    \begin{align*} a^{T}\left(2x_{0}-x\right) & \ge b. \end{align*}

On the other hand,

    \[ a^{T}\left(2x_{0}-x\right)=2b-a^{T}x\le b. \]

Thus,

    \[ a^{T}\left(2x_{0}-x\right)=b. \]

This implies

    \[ a^{T}x=b, \]

which proves A\subset H.

Suppose A\cap H=\varnothing. After a translation, we may assume A has 0 so that A is a subspace of \mathbb{R}^{n}. Then b<0 since A\cap H=\varnothing. Note that a^{T}x=0 for all x\in A. If it were not, then there exists x_{0}\in A satisfying a^{T}x_{0}\neq0. If a^{T}x_{0}<0, then for t>0, a^{T}\left(tx_{0}\right)<0. Letting t\rightarrow\infty, then there exists t_{0} with a^{T}\left(tx_{0}\right)<b, which contradicts a^{T}x\ge b. Similarly, a^{T}x_{0}>0 leads a contradiction. Hence a^{T}x=0 for all x\in A.

Note b<0. So a^{T}x<0 for all x\in C and a^{T}x=0 for all x\in A. This shows that \left\{ x\in\mathbb{R}^{n}:a^{T}x=0\right\} is a hyperplane in \mathbb{R}^{n} containing A and not intersecting C.

Thus, both cases gives a desired result. This completes the proof.


Using this lemma, we are ready to prove the theorem.

Proof of Theorem 1 Define

    \[ H=\left\{ x\in A:f\left(x\right)=1\right\} . \]

Then H is convex, affine subspace of \mathbb{R}^{n}. Consider

    \[ C=\left\{ x\in\mathbb{R}^{n}:\Norm x\le1\right\} . \]

Then it is also convex. Then H is a hyperplane containing A. Note that H\cap C=\varnothing since

    \[ \left|f\left(x\right)\right|\le\Norm x\quad\text{for all }x\in A. \]

Hence by Lemma 1, there exists a hyperplane H_{1} containing H and H_{1}\cap C=\varnothing. So there exist a\in\mathbb{R}^{n}\setminus\left\{ 0\right\} and b\in\mathbb{R} such that

    \[ H_{1}=\left\{ x\in\mathbb{R}^{n}:a^{T}x=b\right\} \]

with a^{T}x\le b for all x\in C. Since H_{1}\cap C=\varnothing, 0\notin H_{1}. So b\neq0. Hence we may assume

    \[ H_{1}=\left\{ x\in\mathbb{R}^{n}:a^{T}x=1\right\} . \]

Then a^{T}x\le1 for all x\in C.

Note that if H=\varnothing, then f\left(x_{0}\right)\neq1 for all x_{0}\in A. Since f is linear, f is the zero map. So there is nothing to prove. So we assume H\neq\varnothing. Then there exists x_{0}\in A with f\left(x_{0}\right)=1.

For nonzero vector x\in\mathbb{R}^{n}, \pm\frac{x}{\Norm x}\in C. So

    \[ a^{T}\left(\pm\frac{x}{\Norm x}\right)\le1 \]

and this shows

    \[ \left|a^{T}x\right|\le\Norm x\quad\text{for all }x\in\mathbb{R}^{n}. \]

If x\in A with f\left(x\right)\neq0, then

    \[ a^{T}\left(\frac{x}{f\left(x\right)}\right)=1 \]

and so

    \[ f\left(x\right)=a^{T}x. \]

If f\left(x\right)=0 for some x\in A, then

    \[ f\left(x+x_{0}\right)=1 \]

and so

    \[ a^{T}\left(x+x_{0}\right)=1. \]

Since x_{0}\in A, a^{T}x=0. So

    \[ f(x) =a^T x\quad \text{for all } x\in A \]

and

    \[ |a^T x|\leq \Norm{x} \quad \text{for all } x \in \mathbb{R}^n. \]

This completes the proof of theorem.


2. Proof of the duality

Now we are ready to prove the claim (1). If x=0, there is nothing to prove. If x\neq0, consider A=\mathbb{R}x. Define f:A\rightarrow\mathbb{R} by

(2)   \begin{equation*} f\left(tx\right)=t\Norm x^{2}. \end{equation*}

Clearly it is linear, f\left(x\right)=\Norm x^{2} and

    \begin{align*} \Norm f & =\max_{\Norm z\le1}\left|f\left(z\right)\right|\\ & =\max_{\Norm{tx}\le1}\left|t\Norm x^{2}\right|=\Norm x. \end{align*}

Also,

    \[ \left|f\left(z\right)\right|\le\Norm f\Norm z \]

for all z\in A. Hence by Theorem 1, there exists a\in\mathbb{R}^{n}\setminus\left\{ 0\right\} with

    \[ f\left(z\right)=a^{T}z\quad\text{for all }z\in A \]

with

    \[ \left|a^{T}z\right|\le\Norm f\Norm z\quad\text{for all }z\in\mathbb{R}^{n}. \]

Since

    \[ \Norm f=\max_{z\in A,\Norm z\le1}\left|a^{T}z\right|\le\max_{z\in A,\Norm z\le1}\left|a^{T}z\right|\le\Norm f, \]

we conclude that

    \[ \max_{z\in A,\Norm z\le1}\left|a^{T}z\right|=\Norm f=\Norm x \]

From (2), if we take \tilde{a}=\frac{a}{\Norm x}, then \Norm{\tilde{a}}_{*}=1 and \tilde{a}^{T}x=\Norm x, which proves the claim.

Therefore,

    \[ \Norm x=\max\left\{ x^{T}y:\Norm y_{*}=1\right\} . \]

3. Some remarks

The motivation of the proof is the philosophy that the Hahn-Banach theorem and the separating hyperplane theorem are closely related. We can prove the separating hyperplane theorem using an extension of Theorem 1. One may ask whether the converse is true. In fact, both statements are equivalent.

The proof of Theorem 1 using Lemma 1 is given in [2]. We modify the lemma and theorem and their proof so that it is suitable to our setting.

References

  1. H. Brezis, Functional Analysis, Sobolev Spaces and Partial Differential Equations, Springer, 2011.
  2. H. H. Schaefer and M. P. Wolff, Topological vector spaces, Springer, 1966.
  3. E. Stein and R. Sharkarchi, Functional Analysis: Introduction to Further Topics in Analysis, Princeton University Press, 2011.

Leave a Reply

Your email address will not be published. Required fields are marked *