Proving that the dual of the $\mathcal{l}_p$ norm is the $\mathcal{l}_q$ norm. Let $\| \cdot \|$ be a norm on $\mathbb{R}^n$. The associated dual norm, denoted $\| \cdot \|_*$ is defined
as $\| z \|_* = \sup\{ z^{t} x : \| x \| < 1 \}$. 
Does someone know how to prove that the dual norm of the $\mathcal l_{p}$ norm is the $\mathcal l_{q}$ norm? I read about norms and it was stated without proof in a book.
 A: Edit: I have edited my answer to conform more to the notation of the paper you linked.
Firstly, suppose $||\cdot||$ is a norm on $\mathbb{R}^n$, and the dual norm $||\cdot||_*$ is defined as
$$
||z||_* := \sup \{ z^{\top} x : x \in \mathbb{R}^n, ||x|| \leq 1\}
$$
for all $z \in \mathbb{R}^n$.
Note that the quantity $z^{\top} x = z\cdot x = \sum_{i=1}^n z_ix_i$ is just the dot product of $z$ and $x$ if thought of both as row vectors.
The paper you linked only mentions the case $1<p,q<\infty$, so we will work in that framework and not worry about the extremal cases. Fix $p,q \in (1,\infty)$ Holder conjugates (i.e. $\frac1p + \frac1q = 1$).
Furthermore, fix $z=(z_1,\ldots,z_n) \in \mathbb{R}^n$. We will show that
$$
\sup \left\{ \sum_{i=1}^n z_ix_i : x=(x_1,\ldots,x_n) \in \mathbb{R}^n, ||x||_q \leq 1\right\} = ||z||_p.
$$
We may assume without loss of generality that $z \neq 0$, otherwise both norms are trivially zero.
Let $x=(x_1,\ldots,x_n) \in \mathbb{R}^n$ with $||x||_q \leq 1$ be given.
We have by Holder's inequality that 
$$
\sum_{i=1}^n z_ix_i  \leq \sum_{i=1}^n |z_ix_i|=  ||zx||_1 \leq ||z||_p ||x||_q \leq ||z||_p
$$
Hence the supremum in question is at most $||z||_p$.
In order to show that the supremum is exactly $||z||_p$, it suffices to find a single $y \in \mathbb{R}^n$ with $||y||_q \leq 1$ such that $\sum_{i=1}^n z_iy_i = ||z||_p$.
Let $x := \mathrm{sign}(z) |z|^{p-1}$, i.e. $x_i := \mathrm{sign}(z_i)|z_i|^{p-1}$ for all $i=1,\ldots,n$.
We calculate
$$
\sum_{i=1}^n z_i x_i = \sum_{i=1}^n z_i  \mathrm{sign}(z_i)|z_i|^{p-1} =
\sum_{i=1}^n |z_i|^p =  ||z||_p^p
$$
where here we used the fact that $z_i \mathrm{sign}(z_i) = |z_i|$.
Furthermore, we calculate
$$
||x||_q^q = \sum_{i=1}^n |x_i|^q = \sum_{i=1}^n |\mathrm{sign}(z_i)|z_i|^{p-1}|^q 
= \sum_{i=1}^n |z_i|^{q(p-1)}= \sum_{i=1}^n |z_i|^p =||z||_p^p
$$
where here we used the fact that since $\frac1p + \frac1q = 1$ we have $q(p-1) = p$.
Now choose $y := \frac{x}{||x||_q}$ (this is where we used the fact that $z \neq 0$, so that $||x||_q > 0$). By construction we have $||y||_q = 1$, and 
$$
\sum_{i=1}^n z_i y_i = \sum_{i=1}^n z_i  \frac{x_i}{||x||_q} = \frac{1}{||x||_q}\sum_{i=1}^n z_i x_i
$$
and using the fact that $||x||_q = (||x||_q^q)^{1/q} = (||z||_p^p)^{1/q} = ||z||_p^{p/q}$ and that $\sum_{i=1}^n z_ix_i = ||z||_p^p$ we have that
$$
 \frac{1}{||x||_q}\sum_{i=1}^n z_i x_i = \frac{1}{ ||z||_p^{p/q}}||z||_p^p = ||z||_p^{p-p/q} = ||z||_p
$$
where here we used the fact that $\frac1p + \frac1q = 1$ implies $p-p/q = p(1-1/q) = p(1/p) = 1$.
Thus we have found $y \in \mathbb{R}^n$ with $||y||_q \leq 1$ such that $\sum_{i=1}^n z_i y_i = ||z||_p$ as desired, completing the proof.
