Show that the dual norm of the spectral norm is the nuclear norm Could someone help me understand why the dual norm of the spectral norm is the nuclear norm?
We can focus on the real field. Given a matrix $X \in \mathbb{R}^{m \times n},$  then the spectral norm is defined by
$$\left \| X\right\| = \max\limits_{i \in \{1, \dots, \min\{m,n\}\} }\sigma_i (X)$$
whereas the nuclear norm is defined by
$$\left \| X \right \|_* = \sum\limits_{i=1}^ {\min\{m,n\}} \sigma_i (X)$$
Can someone show me the reasoning process? Thank you in advance.
 A: I proved it here in a question about whether or not the nuclear norm is convex. I will reproduce the result here. If the mods see fit to close the question as a duplicate that's fine, but they may not since the question itself is different.
Recall that for any norm, the definition of the dual norm
$\|\cdot\|_*$ is
$$\|A\|_* = \sup_{\|Q\|\leq 1} \langle Q, A \rangle.$$
For the nuclear norm, 
$$\|Q\| \triangleq \sigma_1(Q), \quad \|A\|_* \triangleq \sum_i \sigma_i(A).$$
Therefore we seek to prove that
$$\sup_{\sigma_1(Q)\leq 1} \langle Q, A \rangle = 
\sup_{\sigma_1(Q)\leq 1} \mathop{\textrm{Tr}}(Q^HA) = \sum_i \sigma_i(A).$$
We will first prove that $\sup_{\sigma_1(Q)\leq 1} \langle Q, A \rangle \geq \sum_i\sigma_i(A).$ Let $A=U\Sigma V^H=\sum_i \sigma_i u_i v_i^H$ be the singular value decomposition of $A$, and define $\bar{Q}=UV^H=UIV^H$. $\bar{Q}$ is unitary, so all of its singular values are 1, hence $\sigma_1(\bar{Q})=1$. And
$$\langle \bar{Q}, A \rangle = \langle UV^H, U\Sigma V^H \rangle = \mathop{\textrm{Tr}}(VU^HU\Sigma V^H)
= \mathop{\textrm{Tr}}(V^HVU^HU\Sigma) = \mathop{\textrm{Tr}}(\Sigma) = \sum_i \sigma_i.$$
(Note our use of the identity $\mathop{\textrm{Tr}}(ABC)=\mathop{\textrm{Tr}}(CAB)$; this is always true when both multiplications are well-posed.) Since the supremum cannot be smaller than this single instance, we have
$$\sup_{\sigma_1(Q)\leq 1} \langle Q, A \rangle \geq \langle\bar{Q}, A \rangle = \sum_i \sigma_i(A).$$
Now let's prove the other direction:
$$\sup_{\sigma_1(Q)\leq 1} \langle Q, A \rangle =
\sup_{\sigma_1(Q)\leq 1} \mathop{\textrm{Tr}}(Q^HU\Sigma V^H) =
\sup_{\sigma_1(Q)\leq 1} \mathop{\textrm{Tr}}(V^HQ^HU\Sigma) =
\sup_{\sigma_1(Q)\leq 1} \langle UQV^H, \Sigma \rangle =
\sup_{\sigma_1(Q)\leq 1} \sum_{i=1}^n \sigma_i (UQV^H)_{ii} =
\sup_{\sigma_1(Q)\leq 1} \sum_{i=1}^n \sigma_i u_i Q v_i^H \leq
\sup_{\sigma_1(Q)\leq 1} \sum_{i=1}^n \sigma_i \sigma_1(Q) =
\sum_{i=1}^n \sigma_i.
$$
The inequality comes from the fact that $\|u_i\|=\|v_i\|=1$, and
$$u_i^H Q v_i \leq \sup_{\|u\|_2=\|v\|_2=1} u^HQv = \sigma_1(Q).$$
Therefore,
$$\sup_{\sigma_1{Q}\leq 1} \langle Q, A \rangle \leq \sum_i \sigma_i(A).$$
We have proven both the $\leq$ and $\geq$ cases, so equality is confirmed.
