Take the 2-minute tour ×

Consider two square matrices $A, B \in \mathbb{R}^{n \times n}$ and let $\| \cdot\|_1$ and $\|\cdot\|$ be, respectively, the trace norm (the sum of singular values) and the usual operator norm (the maximum of singular values).

Is there a known bound for the following quantity? $$ \sup\{\alpha > 0: \; \alpha \, \text{tr}(A^TB) \le \| A+B\|_1, \, \forall B \; \text{s.t.} \;\|B\| \le 1\} $$

share|improve this question
Cross-posted on MSE. –  1015 Jul 7 '13 at 20:29
Maybe I'm missing something. If $A = 0$, then $\alpha$ becomes unbounded....? –  Suvrit Jul 9 '13 at 17:42
@suvrit: the MSE version is already edited. It is annoying with all these cross-posts... –  András Bátkai Jul 9 '13 at 18:57
@András: ah, ok. You are right, too much cross-posting! –  Suvrit Jul 9 '13 at 22:08

1 Answer 1

up vote 4 down vote accepted

Since I cant comment, I will leave this thought here. Since $||\cdot||_1$ and $||\cdot||$ (as you defined them) are dual norms, it must be that tr$((A+B)^TX)\leq||A+B||_1$ for any $X$ such that $||X||\leq 1$. Therefore, tr$(A^TB)\leq ||A+B||_1 - ||B||^2<||A+B||_1$ (since tr$(B^TB)\geq||B||^2$).

(edit: fixed typo and replaced $||B||$ with $||B||^2$ in the final step)

share|improve this answer
It is rather $\|B\|^2=\|B^TB\|=\rho(B^TB)\leq \mbox{tr}(B^TB)$. And since $\|B\|\leq 1$... But you still have $\|A+B\|_1-\mbox{tr}(B^TB)\leq \|A+B\|_1$, though. –  1015 Jul 7 '13 at 20:46
@julien. You're right. I fixed the typo. Thanks! –  Skoro Jul 7 '13 at 21:03
@Skoro, thanks. Your argument shows that the supremum is at least one. But can it be bigger? For example, are there matrices $A\neq 0$ for which that supremum is at least, say 3? I am interested in bounds relating that quantity to the spectrum of $A$. –  passerby51 Jul 8 '13 at 18:53
Interesting. It looks like one can get an upper bound on $\alpha$ by substituting $B = A/||A||$. This results in the following bound: $\alpha \leq \frac{||A||_1(||A||+1)}{tr(A^TA)} = \frac{(\sum \sigma_i)(\max \sigma_i+1)}{\sum \sigma_i^2}$. maybe this could be controlled using the condition number of $A$. –  Skoro Jul 8 '13 at 21:07

Your Answer


