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.
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_{nj+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$.

$\begingroup$ Hi! Thanks for your answer. This looks promising! $\endgroup$ – Gautam Nov 13 '19 at 21:32