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.

  • $\begingroup$ 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$. $\endgroup$ – Nathaniel Johnston Aug 23 '17 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$.

  • $\begingroup$ 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$. $\endgroup$ – Nik Weaver Aug 24 '17 at 16:03
  • $\begingroup$ @NikWeaver: Yes, that's what I meant, I didn't say it very clearly: if we restore $k$, then $c=1/(2k)$ works. $\endgroup$ – Christian Remling Aug 24 '17 at 16:18
  • $\begingroup$ *rescaling (auto correct) $\endgroup$ – Nik Weaver Aug 24 '17 at 18:24
  • $\begingroup$ Okay. Also, don't we actually have $\|A - B\|_1 \leq 1$? Since both are positive. $\endgroup$ – Nik Weaver Aug 24 '17 at 19:39
  • $\begingroup$ @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. $\endgroup$ – Christian Remling Aug 24 '17 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.