How to show that the unit ball of the dual norm is also polytope?

Question

Assuming a unit ball for the p-norm that is a convex polytope. How can one show that the unit ball of the dual's norm is a convex polytope?

Answer 1

Imagine the polytope $P$ (for example a cube or hexaedron..), I guess it needs to be symmetric to the origo $0$ of the vector space ($x\in P\Rightarrow -x\in P$). $P$ is going to be the unit ball for the norm to be defined.

For each vector $v\ne 0$ (imagined as a directed segment from $0$), define $||v||_P=1$ iff $v$ is on the boundary of $P$, and in general $||v||_P:=\lambda$ for that unique $\lambda>0$ which satisfies $\frac1\lambda v$ is on the boundary of $P$.

Try to find out the unit balls of the standard norms on $\Bbb R^2$: $$||(a,b)||_\max:=\max(|a|,|b|)\quad ||(a,b)||_1:=|a|+|b|\quad ||(a,b)||_2:=\sqrt{a^2+b^2}$$

---

In a general normed space, the triangle inequality (together with the scalar multiplication) yields for $u,v$ vectors in the unit ball ($||u||,\, ||v||\le 1$) and $\lambda\in [0,1]$: $$||\lambda u+(1-\lambda)v|| \le \lambda||u||+(1-\lambda)||v||\le \lambda+1-\lambda=1$$ That is, the unit ball is always convex, in particular in the dual space.

It also follows that if a polytope $P$ is not convex, then the above construction of $||\_||_P$ will not satisfy the triangle ineuqality (hence, will be not a norm).

---

The dual space of $\Bbb R^n$ is also $n$ dimensional, hence isomorphic to $\Bbb R^n$, normally it is handled with column vectors in the original space and row vectors in the dual space, since for each linear $f:\Bbb R^n\to \Bbb R$, as any linear transformation, $f$ can be identified by its matrix, which is now the row vector $$u:=\pmatrix{f\pmatrix{1\\0\\ 0 \\ \vdots}, & f\pmatrix{0\\1\\ 0 \\ \vdots}, &\dots}$$ You should check, using linearity, that for each (column) vector $v\in \Bbb R^n$, we have $$f(v)=u\cdot v$$ where $\cdot $ is the matrix product, which is basically the original scalar product of $u$ and $v$ vectors. Now, the dual norm of $||\_||_P$: $$||f|| =\sup_{||v||_P\le 1}|f(v)|= \sup_{v\in P}|u\cdot v|$$ Now if $P$ is a polytope, i.e. is an intersection of halfspaces $H_1,..,H_k$: $P=H_1\cap H_2\cap\dots H_k$, then this reduces to a $\max$ on the finitely many faces of $P$.

Try to illustrate the case with finding the dual norm of the above $||\_||_1$ on $\Bbb R^2$.