Minimal trace norm on the set of matrices with fixed diagonal entries

Question

What is the minimal nuclear norm (sum of singular values) on all $n \times n$ matrices $A$ whose diagonal is fixed, i.e., $diag(A) = v$? Is it true that the diagonal matrix is a minimizer?

Answer 1

The nuclear norm is dual to the spectral norm $\| \cdot\|_2$: $$ \|A\|_* = \max_{\|X\|_2 \le 1} \langle A, X \rangle $$ Then since $\|\operatorname{diag}(\operatorname{sign}(v))\|_2 \le 1$, any matrix $A$ which satisfies $\operatorname{diag}(A)=v$ must have:

$$ \|A\|_*\ge \langle A, \operatorname{diag}(\operatorname{sign}(v)) \rangle = \langle v, \operatorname{sign}(v) \rangle=\|v\|_1 $$ In particular, $\|\operatorname{diag}(v)\|_* = \|v\|_1$, so the diagonal matrix is a minimizer.