# Minimizing the Schatten 1-norm over symmetric matrices.

Let $X$ be an $n \times n$ Hermitian matrix, it follows that we can write $X=A+iB$ where $A$ is symmetric and $B$ is skew-symmetric. Let $S$ be the set of $n \times n$ symmetric matrices and define the Schatten $1$-norm (also known as trace norm) as $\lVert M \rVert_1=\sum_j \sigma_j(M)$, where $\sigma_j(M)$ are the singular values of $M$. To measure how close $X$ is to the subspace of symmetric the matrices, we can define the distance measure $$D(X) = \min_{Y\in S} \lVert X-Y \rVert_1 .$$ Expanding $X$ into symmetric and skew-symmetric parts, we get that $$D(X)= \min_{Y\in S} \lVert (A-Y)+iB \rVert_1$$ From this it seems intuitively that the minimum occurs when $Y=A$, in which case $D(X)=\lVert B\rVert_1$ is simply the $1$-norm of the imaginary part of $X$. How would one show that this quantity is minimized for $A=Y$?

• I think my answer covers you either way, but are we minimising over positive semi-definite matrices or (real?) symmetric matrices? The question, as stated, is a little confusing on this point. I encourage you to make the question clearer for future reference, even if you are satisfied with the answer. :-) – Josse van Dobben de Bruyn Oct 5 '17 at 2:46
• @JossevanDobbendeBruyn Thanks, as your proof holds over all symmetric matrices I will update the question to be more general. – gene Oct 5 '17 at 2:48

Edit: It seems that I let myself get carried away by specifics, and as a consequence completely missed the bigger picture. My old answer is kept at the bottom for historical purposes. Let it be a reminder to all — including myself — that accepted answers on this site can occasionally be clumsy, needlessly complicated, or potentially even incorrect (though the latter doesn't seem to apply here).

$${}$$

## New answer — much shorter and more general:

We present the result in a much more general setting (which is probably closer to your intuition).

Definition. Let $X$ be a complex vector space. A complex conjugation is a conjugate-linear map $f : X \to X$ which is equal to its own inverse, in other words:

• For all $x,y\in X$ and $\lambda,\mu \in \mathbb{C}$ we have $f(\lambda x + \mu y) = \overline\lambda f(x) + \overline \mu f(y)$;
• For all $x\in X$ we have $f(f(x)) = x$.

Instead of $f$ we usually write $\bar{\ }\, : X \to X$. The conjugate of an element $x\in X$ is written $\overline x$. We say that $x$ is real if $\overline x = x$ holds. Every $x\in X$ can be uniquely expressed as $x = a + ib$ with $a$ and $b$ real. These $a$ and $b$ are given by $a = \text{Re}(x) := \tfrac{1}{2}(x + \overline x)$ and $b = \text{Im}(x) := \tfrac{1}{2i}(x - \overline x)$. The set of real elements of $X$ forms an $\mathbb{R}$-subspace (but not a $\mathbb{C}$-subspace!), which we denote by $\text{Re}(X)$.

If $(X,\lVert\:\cdot\:\rVert)$ is a normed space, then a complex conjugation $\bar{\ }\, : X \to X$ defines an isometry (of the underlying metric space) if and only if $\lVert \overline x\rVert = \lVert x\rVert$ holds for all $x\in X$.

Proposition. Let $(X,\lVert\:\cdot\:\rVert)$ be a complex normed space and let $\bar{\ }\, : X \to X$ be an isometric complex conjugation. Then for any $x\in X$ and $y\in\text{Re}(X)$ we have $$\lVert x - y\rVert \: \geq \: \lVert x - \text{Re}(x)\rVert.$$

Proof. Write $x = a + ib$ with $a,b\in\text{Re}(X)$, given explicitly by $a := \text{Re}(x)$ and $b := \text{Im}(x)$. The result follows from a simple application of the triangle inequality: Indeed, we have \begin{align} \hspace{-35mm}2\lVert x - \text{Re}(x)\rVert \: = \: \lVert 2ib\rVert \: &= \: \lVert (a + ib) - y \: + \: y - (a - ib)\rVert\\[1ex] &\leq \: \lVert (a + ib) - y \rVert + \lVert y - (a - ib)\rVert\\[1ex] &= \: \lVert (a + ib) - y\rVert + \lVert (a - ib) - y\rVert\\[1ex] &= \: \lVert (a + ib) - y\rVert + \big\lVert \, \overline{(a + ib) - y} \, \big\rVert\tag*{(since $a,b,y\in\text{Re}(X)$)}\\[1ex] &= \: 2\lVert (a + ib) - y\rVert\tag*{(since $\bar{\ }\,$ is isometric)}\\[1ex] &= \: 2\lVert x - y\rVert.\tag*{$\blacksquare$} \end{align}

Now all that remains is to show that the entry-wise complex conjugation $\bar{\ }\, : M_n(\mathbb{C}) \to M_n(\mathbb{C})$ preserves the trace norm. This is not so hard to do. For arbitrary matrices $A,B \in M_n(\mathbb{C})$ we have $\overline{AB} = \overline A \, \overline B$ and $\overline{A}^* = \overline{A^*}$, hence $$\overline{A}^*\,\overline A \: = \: \overline{A^*A}.$$ Now it is easy to see that $\overline{|A|}$ is a positive semidefinite square root of $\overline{A^*A}$, so it follows that $\overline{|A|} = |\,\overline A\,|$ holds. Finally, we find $$\lVert \overline A\rVert_1 \: = \: \text{tr}\big(\big|\,\overline A\,\big|\big) \: = \: \text{tr}\left(\overline{|A|}\right) \: = \: \overline{\text{tr}(|A|)} \: = \: \overline{\lVert A\rVert_1} \: = \: \lVert A\rVert_1.$$

$${}$$

In summary: the entire result follows essentially from one application of the triangle inequality.

$${}$$

## Old answer — needlessly complicated:

Your intuition is correct, but it's not particularly easy to prove this. We will need quite a few facts about the trace norm. Let $\mathbb{C}^{n\times n}$ denote the algebra of $n\times n$ complex matrices, and let $\lVert \:\cdot\: \rVert_\infty : \mathbb{C}^{n\times n} \to \mathbb{R}_{\geq 0}$ denote the operator norm (also know as the Schatten $\infty$-norm).

Proposition 1 ("non-commutative Hölder inequality", case $p = 1$ and $q = \infty$). For any $X,Y\in \mathbb{C}^{n\times n}$ we have $\lVert XY\rVert_1 \leq \lVert X\rVert_1\cdot \lVert Y\rVert_\infty$.

Proof. See your favourite textbook on Schatten norms. (The only references I can produce at this time are books in functional analysis and operator theory, which are likely to be inappropriate due to being way too advanced.)

Proposition 2. For any $X\in \mathbb{C}^{n\times n}$ we have $|\text{tr}(X)| \leq \lVert X\rVert_1$.

Proof. Use this question and the triangle inequality.

Proposition 3. For any $X\in \mathbb{C}^{n\times n}$ there exists a unitary $U\in \mathbb{C}^{n\times n}$ such that $|X| = UX$.

Proof. This is (equivalent to) the polar decomposition.

Corollary 4. For any $X\in \mathbb{C}^{n\times n}$ we have $$\lVert X\rVert_1 = \max_{\substack{Y \in \mathbb{C}^{n\times n}\\\lVert Y \rVert_\infty \leq 1}} |\text{tr}(XY)|.$$ Furthermore, there exists some $U\in \mathbb{C}^{n\times n}$ with $\lVert U\rVert_\infty = 1$ such that $\lVert X\rVert_1 = \text{tr}(XU)$ holds (note the omission of the absolute value).

Proof. By propositions 1 & 2, any $Y\in \mathbb{C}^{n\times n}$ with $\lVert Y\rVert_\infty \leq 1$ satisfies $$|\text{tr}(XY)| \leq \lVert XY\rVert_1 \leq \lVert X\rVert_1\cdot \lVert Y\rVert_\infty \leq \lVert X\rVert_1.$$ By proposition 3, there is some unitary $U\in \mathbb{C}^{n\times n}$ such that $|X| = UX$ holds. Note that we have $\lVert U \rVert_\infty = 1$ since $U$ is unitary. Now we have $\lVert X\rVert_1 = \text{tr}(|X|) = \text{tr}(UX) = \text{tr}(XU)$.

Now that we have all the ingredients, let's get on with the exercise at hand. Recall that we have $X = A + iB$ with $A$ real symmetric and $B$ real skew-symmetric, and we want to find a real symmetric matrix $Y$ minimising the distance $\lVert X - Y\rVert_1$.

Assume without loss of generality that $A = 0$ holds, so that we have $X = iB$. We prove that the minimum occurs at $Y = 0$. Choose some $U \in \mathbb{C}^{n\times n}$ satisfying $\lVert U\rVert_\infty \leq 1$ as well as $\lVert X\rVert_1 = \text{tr}(XU)$. Now we have $$\text{tr}(XU) = \text{tr}\big((XU)^T\big) = \text{tr}\big(U^TX^T\big) = -\text{tr}\big(U^TX\big) = -\text{tr}\big(XU^T\big),$$ so we may assume without loss of generality that $U$ is skew-symmetric (replace $U$ by $\tfrac{1}{2}(U - U^T)$, if neccesary, then the properties $\lVert U\rVert_\infty \leq 1$ and $\lVert X\rVert_1 = \text{tr}(XU)$ still hold).

Now let $Y$ be an arbitrary real symmetric matrix, then we have $$\text{tr}(YU) = \text{tr}\big((YU)^T\big) = \text{tr}\big(U^TY^T\big) = \text{tr}\big(U^TY\big) = -\text{tr}(UY) = -\text{tr}(YU),$$ hence $\text{tr}(YU) = 0$. As a result, by corollary 4 we have $$\lVert X - Y\rVert_1 \geq \big|\text{tr}\big((X - Y)U\big)\big| = |\text{tr}(XU) - \text{tr}(YU)| = \big|\lVert X\rVert_1 - 0\big| = \lVert X\rVert_1,$$ which proves the result.

Closing remarks:

1. It might be true that we can always choose a skew-symmetric unitary $U$ in the polar decomposition of a skew-symmetric self-adjoint matrix; I'm not entirely sure about that. In any case, proving that seemed like a hassle, so I decided on the above workaround.
2. Note that we didn't really use that $Y$ was real, only that it was symmetric. As such, it seems that the result extends to the minimisation problem over all complex symmetric matrices. (Come to think of it, we didn't really use that $B$ was real either...)
3. The minimum is not always unique. If $n$ is even, then the spectrum of $X$ is of the form $\{-\lambda_1,\lambda_1,-\lambda_2,\lambda_2,\ldots\}$ with $0 \leq \lambda_1 \leq \lambda_2 \leq \cdots$. If we have $\mu\in\mathbb{R}$ and $0 < |\mu| \leq \lambda_1$, then $Y = \mu I$ is also at minimal distance. After all, half of the eigenvalues are moved closer to zero and half are moved away from zero, so the sum of their absolute values remains the same.
4. The same result holds if we replace the trace norm by the Hilbert–Schmidt norm $\lVert \:\cdot\: \rVert_2$ (also known as the Schatten 2-norm), and the proof is much easier in this case. I'll leave this as an exercise. ;-)
• Incredible answer, I was starting to think my bounty would expire! – Alex Oct 5 '17 at 2:45
• @Alex Haha, thanks, I was also starting to think that. ;-) It was a tough nut to crack. That's the problem with finite-dimensional linear algebra over $\mathbb{R}$ or $\mathbb{C}$: there are too many things to try because we know so much about it! :P – Josse van Dobben de Bruyn Oct 5 '17 at 2:51
• @Alex ouch, it turns out that my original answer was really clumsy and needlessly complicated. I preserved it for historical reference, but I also edited my answer to give a much simpler (and more intuitive) proof. :-) – Josse van Dobben de Bruyn Jan 26 '18 at 18:12