Minimize matrix norm over the unitary matrices

Question

Suppose $C_1$ and $C_2$ are some fixed $n \times n$ matrices. Define the norm $\| M \| = \sum_{i = 1}^n \max_j |M_{ij}|$. What is $\min_U \|C_1 U C_2 \|$? Here $U$ ranges over the $n \times n$ unitary matrices. I would also be interested to know what is the minimizer when the norm is one of the "standard" norms, such as the Frobenius norm or the nuclear norm.

Answer 1

I can provide the answer in the case when the norm is the Frobenius norm $\|\cdot\|_{\text{F}}$. In this case, $$\|C_1UC_2\|_{\text{F}} = \sqrt{\mathrm{tr}\big((C_1UC_2)(C_1UC_2)^*\big)} = \sqrt{\mathrm{tr}(UC_2C_2^*U^*C_1^*C_1)}.$$ It is a standard result of matrix theory that minimizing this quantity over unitary matrices $U$ gives $$\mathrm{min}_U\|C_1UC_2\|_{\text{F}} = \sqrt{\sum_{j=1}^n\lambda_j\mu_{n-j+1}},$$ where $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$ are the eigenvalues of $C_1^*C_1$ and $\mu_1 \geq \mu_2 \geq \cdots \geq \mu_n$ are the eigenvalues of $C_2C_2^*$ (this follows immediately from Problem III.6.14 in Bhatia's Matrix Analysis book, for example). Furthermore, a unitary $U$ that achieves this minimum is one that makes $UC_2C_2^*U^*$ diagonal in the same basis as $C_1^*C_1$.