10
$\begingroup$

Given a positive semidefinite matrix $P$, if we scale down its entries individually, will its operator norm always decrease? Put it another way:

Suppose $P\in M_n(\mathbb R)$ is positive semidefinite and $B\in M_n(\mathbb R)$ is a $[0,1]$-matrix, i.e. $B$ has all entries between $0$ and $1$ (note: $B$ is not necessarily symmetric). Let $\|\cdot\|_2$ denotes the operator norm (i.e. the largest singular value). Is it always true that $$\|P\|_2\ge\|P\circ B\|_2?\tag{$\ast$}$$

Background. I ran into this inequality in another question. Having done a numerical experiment, I believed the inequality is true, but I hadn't been able to prove it. If $(\ast)$ turns out to be true, we immediately obtain the analogous inequality $\rho(P)\ge\rho(P\circ B)$ for the spectral radii because $\rho(P)=\|P\|_2\ge\|P\circ B\|_2\ge\rho(P\circ B)$.

Remarks. There is much research on inequalities about spectral radii or operator norms of Hadamard products. Often, either all multiplicands in each product are semidefinite or all of them are nonnegative. Inequalities like those two here, which involve mixtures of semidefinite matrices with nonnegative matrices, are rarely seen.

I have tested the inequality for $n=2,3,4,5$ with 100,000 random examples for each $n$. No counterexamples were found. The semidefiniteness condition is essential. If it is removed, counterexamples with symmetric $P$s can be easily obtained. The inequality is known to be true if $P$ is also entrywise nonnegative. So, if you want to carry out a numerical experiment to verify $(\ast)$, make sure that the $P$s you generate have both positive and negative entries.

One difficulty I met in constructing a proof is that I couldn't make use of the submultiplicativity of the operator norm. Note that tie occurs if $B$ is the all-one matrix, which has spectral norm $n\,(>1)$. If you somehow manage to extract a factor like $\|B\|_2$ from $\|P\circ B\|_2$, that factor may be too large. For a similar reason, the triangle inequality also looks useless.

$\endgroup$
  • $\begingroup$ I take it that here $\circ$ means Hadamard (entrywise) product, right? $\endgroup$ – Nick Alger Jul 5 '16 at 2:19
  • $\begingroup$ @NickAlger Yes, precisely. $\endgroup$ – user1551 Jul 5 '16 at 2:26
  • $\begingroup$ There is some theory for the sensitivity of singular values with respect to changes in the entries of a matrix. One approach might be to consider a parameterized path $M$ between the matrices in the inequality, $M(s) = sP + (1-s)(P \circ B)$, and show that at each point on the path the derivative of the singular values is positive. $\endgroup$ – Nick Alger Jul 5 '16 at 2:39
  • $\begingroup$ Here's a paper about singular value sensitivity, maybe it can be of use, particularly equation (3) in section 4: users.math.msu.edu/users/markiwen/Teaching/MTH995/Papers/… $\endgroup$ – Nick Alger Jul 5 '16 at 3:36
  • $\begingroup$ @user1551: You're obviously correct. I had the inequality going the wrong way in my head. I have deleted my comment as a result. $\endgroup$ – J. Loreaux Jul 5 '16 at 16:53
9
$\begingroup$

It is not always true.

The following matrix is positive semidefinite with norm $3$: $$ P := \left(\begin{array}{ccc} 2 & 1 & 1\\ 1 & 2 & -1\\ 1 & -1 & 2\\ \end{array}\right) $$ Use $B$ to poke out the $-1$'s and you get $$ P \circ B = \left(\begin{array}{ccc} 2 & 1 & 1\\ 1 & 2 & 0\\ 1 & 0 & 2\\ \end{array}\right), $$ which is positive semidefinite with norm $2 + \sqrt{2} > 3$.

$\endgroup$
  • $\begingroup$ Congrats and +1. This is a great counterexample! $\endgroup$ – user1551 Jul 5 '16 at 4:20
  • 5
    $\begingroup$ This is a good lesson to learn. In my numerical experiment, the entries of $B$s were random floating-point numbers. Actually I was careful enough to re-do the original experiment with many more (a million) samples, but no counterexamples were found. The idea to generate random samples on the boundary (i.e. to use random $\{0,1\}$ matrices rather than random $[0,1]$-matrices) just didn't occur to me. Once I changed the code to sample integer $B$, counterexamples easily popped up. $\endgroup$ – user1551 Jul 5 '16 at 4:30
3
$\begingroup$

I think this is true. Here's an attempt that looks potentially fruitful:

Use the property given here. That is, note that $$ \DeclareMathOperator{\tr}{tr} \| P \circ B\| = \sup_{\|x\| = \|y\| = 1} x^*(P \circ B)y = \sup_{\|x\| = \|y\| = 1} \tr (D_x P D_y B^T) = \\ \sup_{\|x\| = \|y\| = 1} \langle D_x P D_y,B \rangle \leq \sup_{\|x\| = \|y\| = 1} \left(\sum_{i,j}|(D_x P D_y)_{ij}|\right)\max_{i,j}|B_{ij}| $$ here, $\langle \cdot , \cdot \rangle$ is an entry-wise dot-product, and $D_x = \operatorname{diag}(x_1,\dots,x_n)$. From here, maybe you can use the fact that $P$ can be written as a convex combination of PSD rank $1$ matrices. Perhaps it's useful to note that $D_x vv^T D_y = (x \circ v) (y \circ v)^T$.

$\endgroup$
  • 1
    $\begingroup$ Thanks and +1 for the characterisation $\|P\circ B\|=\sup_{\|x\|=\|y\|=1}\operatorname{tr}(D_xAD_yB^T)$ (I desperately wanted a characterisation of this kind, but it just didn't pop up in my mind), but as it currently stands, the later part of your approprach won't work: when $B$ is the all-one matrix, the RHS of your inequality will overshoot, as it becomes the norm of the entrywise absolute value of $P$, which can be strictly greater than $\|P\|$ when $n\ge3$. $\endgroup$ – user1551 Jul 5 '16 at 2:24
  • $\begingroup$ Sorry, my $P$ became an $A$. Glad you think the characterization is useful. And interesting observation of why my approach fails; I wouldn't have put together that it's the norm of $|P|$. I was hoping some kind of Hölder's would work here, but it seems that neither the entry-wise nor the Schatten (singular value) versions work. $\endgroup$ – Omnomnomnom Jul 5 '16 at 2:40
  • $\begingroup$ If there is no Hölder's inequality or version thereof that does the job, my next guess would be to try moving the $D_x$ and $D_y$ across the inner product, try the case where $B$ is rank $1$, or try calculus... somehow. That's all I have time for now, but hopefully that helps if you're out of ideas. $\endgroup$ – Omnomnomnom Jul 5 '16 at 2:48
  • 1
    $\begingroup$ @user1551 just occurred to me: if $|P|$ (entrywise absolute value) has a greater norm than $P$, then we have a counterexample with $B_{ij} = \operatorname{sign}(P_{ij})$ $\endgroup$ – Omnomnomnom Jul 5 '16 at 18:46
  • $\begingroup$ The sign matrix may have negative entries. So it may not be qualified as a counterexample. But your argument does succinctly point out why the complex version of the statement (or the real version with a $[−1,1]$ matrix $B$) is false. $\endgroup$ – user1551 Jul 5 '16 at 19:39

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.