Positive semidefinite operators and norm polytopes | Population Algorithms by Petar Maymounkov

Positive semidefinite operators and norm polytopes - 5

I’ve been obsessing over the following conjecture. And to be honest I haven’t been able to find any counterexamples, nor make any significant progress towards proving it. So, here goes:

If $A,B$ are positive semidefinite and $A\preccurlyeq B$ , then $\|A\|_{1\rightarrow 1} \le \|B\|_{1\rightarrow 1}$ .

In fact, it seems that if this is true for the $\|\cdot\|_{1\rightarrow 1}$ -norm, it probably is true for all norms of the form $\|\cdot\|_{p\rightarrow p}$ . Any ideas or references would be greatly appreciated.

5 Comments ↓

#alex at 11:47 pm on April 18th, 2008

I’m not familiar with this notation: what does the 1->1 norm mean?

#petar at 6:55 am on April 19th, 2008

Hi Alex. (And thanks for your continued interest!) For a (linear) transformation $A$ the operator norm is defined as $\|A\|_{p\rightarrow q}=\sup_{x\neq 0} \|Ax\|_q/\|x\|_p$ . You can check, for example, that $\|A\|_{1\rightarrow 1}=\max_i \|A_i\|_1$ , where $A_i$ is the i-th column of $A$ .

#alex at 7:07 pm on April 19th, 2008

I like puzzles about math :)

To get a counterexample, I think one can take any positive symmetric matrix with unequal column sums, with large enough diagonal to make it positive definite. I’m too lazy to cook up a nice example of this form, so here is a “proof by matlab”:

If A = [2 1; 1 3] (in matlab notation) then matlab gives that the eigenvalues of A are, to two digits, 1.38 and 3.62. This means that if B = 3.7*[1 0;0 1], then B-A is PSD and $\|A\|_{1\rightarrow 1}=4$ and $\|B\|_{1\rightarrow 1}=3.7$ .

#petar at 7:20 pm on April 19th, 2008

Great. Thanks. I will think about your counterexample, when I am not out the door (like now). One last thing I want to check is whether $\|A\|\le\gamma\|B\|$ for some universal $\gamma=O(1)$ . I’ll post whatever comes out of this. If you play with examples geometrically, there is definitely some rigidity (at least in 2-dimensions) to how much you can violate this inequality.

#alex at 9:08 pm on April 19th, 2008

I don’t think its true. The following counterexample is probably too complicated, but – I read this paper a while ago, and the counterexample is a simple consequence of the main theorem.

Suppose we generate a random matrix as follows. Each upper triangular entry is +1 or -1 with equal probability. We want the matrix to be symmetric, so that we set the lower triangular elements equal to the upper triangular ones. The diagonal is composed of zeros. Lets call R the matrix generated this way.

Then, the Furedi/Komlos paper I linked to will imply that with high probability, all eigenvalues lie in $(-c n^{1/2}, +cn^{1/2})$ for some constant c. Define $A = cn^{1/2} I+R$ , and $B=2c n^{1/2} I$ .