# Inequality between nuclear norm and operator norm for positive definite matrices

I will use $\|\|_*$ to denote the nuclear norm (sum of singular values) and $\|\|_2$ to denote the operator norm / matrix 2-norm (largest singular value).

Consider two positive definite $n \times n$ matrices $A$ and $B$ such that $\text{trace}(A)=\text{trace}(B)\equiv k$. I am interested in finding the largest constant $c \geq 0$ such that the following inequality holds:

$$\|\sqrt{B}^{-1} A \sqrt{B}^{-1}\|_2 \geq c \|A - B\|_*.$$

Unable to obtain a proof, I have done some numerical investigation and I have noticed that it's easy to get violations of the inequality if the trace of the matrices $k$ is chosen to be much larger than $n$ (with fixed $c$). However, as the trace decreases, so do the violations, and for smaller values of $k$ I was not able to find numerical counterexamples unless the value of $c$ gets very large.

I am curious about whether, given $n$ and $k$, there is a value of $c$ such that the inequality always holds. Or perhaps whether the inequality always holds for some $n$-dependent $c$ when one simply sets $k=1$.

I would appreciate any thoughts and ideas.

• Do you have any partial results so far? I can show that you can choose $c = 1/(2k\sqrt{n})$, but this is surely not the largest possible $c$. Aug 23, 2017 at 22:24

There is essentially no $n$ dependence here. It suffices to consider the case $k=1$ (by rescaling), and then $c=1/2$ works for all $n$. This follows because $$\|B^{-1/2}AB^{-1/2} \| \ge 1 ,\quad\quad\quad\quad (1)$$ and clearly $\|A-B\|_1\le 2$. (So there is no interaction between the terms, the inequality just says that $\min (LHS)\ge\max (RHS)$.)
To prove (1), let's write $\lambda_j$ and $\mu_j$ for the eigenvalues of $A$ and $B$, respectively, arranged in increasing order. By our assumptions, $0<\lambda_j,\mu_j\le 1$.
I'll compute the norm of $M=B^{-1/2}AB^{-1/2}$ by maximizing the quadratic form. I start out by testing $M$ on $B^{1/2}v_n$, where $Av_n=\lambda_n v_n$; it follows that $\|M\|\ge \lambda_n/\mu_n$. Next, I test $M$ on the space spanned by $B^{1/2}v_j$, $j=n-1,n$. Since this space is two-dimensional, its intersection with the orthogonal complement of $w_n$, $Bw_n=\mu_n w_n$, is still at least one-dimensional, so we now see that also $\|M\|\ge \lambda_{n-1}/\mu_{n-1}$. We can continue in this style, and we in fact have that $\|M\|\ge \lambda_j/\mu_j$ for all $j$. Since $\sum\mu_j=1$ and $\sum (\lambda_j/\mu_j)\mu_j=1$ also, there is a $j$ with $\lambda_j/\mu_j\ge 1$. This gives (1), and it's also clear that (1) is optimal, since we can take $A=B$.
• You sure about revealing to get rid of $k$? If you multiply $A$ and $B$ by $k$ the left side of the desired inequality doesn't change but the right side is multiplied by $k$. Aug 24, 2017 at 16:03
• @NikWeaver: Yes, that's what I meant, I didn't say it very clearly: if we restore $k$, then $c=1/(2k)$ works. Aug 24, 2017 at 16:18
• Okay. Also, don't we actually have $\|A - B\|_1 \leq 1$? Since both are positive. Aug 24, 2017 at 19:39
• @NikWeaver: I don't think that follows, for example $A=\begin{pmatrix} 1 & 0 \\ 0 & 0\end{pmatrix}$, $B=\begin{pmatrix} 0 & 0\\ 0 & 1\end{pmatrix}$, and $\|A-B\|_1=2$ ($A,B$ are not invertible here, but of course I can take matrices close to those). What is true is that those $A,B$ that make the LHS small (close to $1$, that is), will probably give a bound on $\|A-B\|_1$ somewhat better than $2$, so $c=1/2$ is unlikely to be best possible. But my interpretation of the OP was that we want to know how $c$ varies with $n$, and the answer to that is: not very much. Aug 24, 2017 at 21:40