# Relationship of norm and quadratic form for an ordering

Given a partial ordering of the form $(1-\epsilon) B \preceq A \preceq (1+ \epsilon) B$ (where $A \preceq B$ means that $B-A$ is positive semi definite) for symmetric psd matrices $A,B$, can I derive a bound for the operator norm of $||A-B||$ in terms of the norm of $B$? I was just using the fact that the largest eigenvalue is similar to the two norm and then I would obtain the bound $||A-B|| \leq \epsilon ||B||$. is there any stronger bound possible? Below I quickly describe how I achieve the bound. I hope this is correct: From the partial ordering we have $$B-A \preceq \epsilon\ A \leftrightarrow x^T(B-A)\ x \leq \epsilon\ x^TAx,$$ for all $x$, and this holds in particular for $x=s_{max}$ being the eigenvector corresponding to the largest eigenvalue of $\lambda_{max}(B-A)$. Hence we obtain (for orthonormal eigenvectors $s_i$, since $A,B$ symmetric) $$\lambda_{max}(B-A) \leq \epsilon\ s_{max}^T A s_{max} = \epsilon \sum_i \lambda_i(A) s_{max}^T \hat s_i \hat s_i^T s_{max} \leq \epsilon\ \lambda_{max}(A) \sum_i s_{max}^T \hat s_i \hat s_i^T s_{max} .$$ Now since $\sum_i \hat s_i s_i^T = I$, $A,B$ symmetric, and since $s_{max}^T s_{max} = 1$ we have $$\lambda_{max}(B-A) = ||B-A||_2 \leq \epsilon \lambda_{max}(A)\ \cdot 1 = \epsilon\ ||A||_2,$$ and the bound follows. Please correct me if I made a mistake there, in particular is there a way to improve this without using the assumption that the eigenvectors of $A$ form a complete basis?

• If you take $A = (1-\epsilon)I$ and $B = I$ you have $\|A-B\| = \epsilon\|B\|$, so no stronger bound is possible, although i'd like to see in details how you get the inequality. – Gribouillis Dec 16 '17 at 16:52
• Thanks, yes that makes sense. I hope my proof above is correct, but I added it to the description. Note that I deal with full rank, symmetric matrices above, since I guess otherwise this would not necessarily hold? – LeoW. Dec 17 '17 at 8:27
• However I realize that this proof does not work if the eigenvectors don't form a basis, or is there a way to still do it? – LeoW. Dec 17 '17 at 9:13
• It looks good, you are using that the spectral radius of a real symmetric matrix is equal to its norm. There is a small detail that worries me: the hypothesis $(B-A)\preceq \epsilon A$ does not imply that $B-A$ is psd, so its eigenvalue with maximum modulus could be negative, which would break the proof. Is there a solution to this issue? – Gribouillis Dec 17 '17 at 9:28
• The eigenvectors do form a basis. There is an orthogonal matrix $Q$ and an diagonal matrix $\Lambda$ such that $A = Q \Lambda Q^\top$. The columns of $Q$ are the eigenvectors. – Gribouillis Dec 17 '17 at 9:34

The hypothesis $\left(1-{\epsilon}\right) B \preceq A \preceq \left(1+{\epsilon}\right) B$ implies that

$$B-A \preceq {\epsilon} B \qquad \ \text{and} \ \qquad A-B \preceq {\epsilon} B$$

The real symmetric matrices $B-A$ and $A-B$ have opposite eigenvalues, hence one of them has its largest eigenvalue equal to its spectral radius. Suppose without loss of generality that it is $B-A$. If ${s}_{\max }$ is a normed eigenvector of $B-A$ for the eigenvalue ${\rho} \left(B-A\right)$, one has

$${\rho} \left(B-A\right) = {s}_{\max }^{\top } \left(B-A\right) {s}_{\max } \leqslant {\epsilon} {s}_{\max }^{\top } B {s}_{\max } \leqslant \left|{\epsilon}\right| \left\|B\right\| {\left\|{s}_{\max }\right\|}^{2} = \left|{\epsilon}\right| \left\|B\right\|$$

For real symmetric matrices, the spectral radius is equal to the operator norm, hence

$$\left\|B-A\right\| \leqslant \left|{\epsilon}\right| \left\|B\right\|$$

This inequality is optimal, as the example $A = \left(1-{\epsilon}\right) I$ and $B = I$ shows, for ${\epsilon} > 0$.