# Off-diagonal part of PSD matrix Eigenvalue Bound

Let $A\succeq 0$ and $M = A - \operatorname{diag}(A)$ be $M$ modified by setting the diagonal terms to zero. While $\operatorname{diag}(A)\succeq 0$, $M$ need not be positive or negative definite (consider $A$ as the all-ones matrix which has characteristic polynomial $(-1)^n\bigl(x - (n-1)\bigr)(x+1)^{n-1}$).

Can we bound $\|M\|$ in terms of $\|A\|$?

At least in the $A = \mathbf{1}\mathbf{1}^*$ example $\|M\|\leq \|A\|$ holds.

• Related question here. – cdipaolo Aug 23 '18 at 18:24

$\newcommand\diag{\operatorname{diag}}$This is true. Decompose $M = A - \diag A$ and pick $x$ of unit length so that $x^* M x = \|M\|$. Then $$\|M\| = x^* M x = x^* A x - x^* \diag(A) x \leq \|A\| - x^*\diag(A) x \leq \|A\|$$ since $\diag(A)\succeq 0$. The more specific bound $$\|M\| \leq \|A\| - \min\{a_{ii}\}$$ holds similarly.
• How do we know that $x^TAx\leq||A||$? – MrYouMath Aug 24 '18 at 18:18
• @MrYouMath This. For self-adjoint $B$, $\|B\| = \max_{\|x\|=1}x^* B x$ and $x$ here had unit length. That's also how we can come up with $x^*\operatorname{diag}(A)x \geq \min\{a_{ii}\}$. – cdipaolo Aug 24 '18 at 18:19