most recent 30 from http://mathoverflow.net 2013-05-20T03:30:31Z http://mathoverflow.net/feeds/question/44167 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/44167/is-the-norm-of-a-0-1-matrix-almost-attained-on-a-0-1-vector Seva 2010-10-29T19:11:44Z 2011-04-29T18:08:53Z

<p>I'd like to state explicitly a problem which was somehow hidden in <a href="http://mathoverflow.net/questions/41660/is-the-operator-norm-always-attained-on-a-0-1-vector" rel="nofollow">my three-week-old post</a>:</p> <blockquote> <p>Does there exist an absolute constant $c>0$ with the property that for any matrix <code>$M\in{\mathcal M}_{m\times n}(\{0,1\})$</code> (zero-one matrices with $m$ rows and $n$ columns), there is a non-zero vector <code>$x\in\{0,1\}^n$</code> such that $\|Mx\|/\|x\|\ge c\|M\|$?</p> </blockquote> <p>(Here $\|\cdot\|$ denotes both the Euclidean norms in ${\mathbb R}^m$ and ${\mathbb R}^n$ and the induced operator norm.)</p> <hr> <p>I can prove the conclusion with $c\sim 1/\sqrt{\log n}$ even in the case $M\in{\mathcal M}_{m\times n}({\mathbb R})$, and <a href="http://mathoverflow.net/questions/41660/is-the-operator-norm-always-attained-on-a-0-1-vector/41669#41669" rel="nofollow">an example</a> due to Greg Kuperberg shows that this is, essentially, best possible. The question is, can one make an improvement under the assumption that all elements of $M$ are restricted to the values $0$ and $1$?</p>

http://mathoverflow.net/questions/44167/is-the-norm-of-a-0-1-matrix-almost-attained-on-a-0-1-vector/63417#63417 Seva 2011-04-29T14:19:20Z 2011-04-29T18:08:53Z

<p>As I have figured out recently, the answer is <strong>no</strong>. The full proof is somewhat technical and I cannot supply full details within the framework of an MO post, but here is the idea behind the construction.</p> <p>Start with a symmetric matrix <code>$A\in{\mathcal M}_{n\times n}(\{0,1\})$</code> such that the Perron-Frobenius eigenvalue of $A$ is much larger than the absolute value of any other eigenvalue, and the corresponding eigenvector is "reasonably simple". Now take a high tensor power of $A$. We get a symmetric zero-one matrix $M$ which inherits the spectral gap of the original matrix $A$, and hence the norm $\|Mx\|$ is controlled by the projection of $x$ onto the Perron-Frobenius eigenvector, say $v$, of $M$. Being a tensor power of the Perron-Frobenius eigenvector of the original matrix $A$, the vector $v$ can be analyzed, and with some effort can be shown to be "oblique" in the sense that it is "not aligned" with any zero-one vector. Hence, if $x$ is a zero-one vector, then the projection of $x$ onto $v$, and therefore the norm $\|Mx\|$, are small.</p> <p>A precise result I was able to prove along these lines is as follows: there exist matrices <code>$M\in{\mathcal M}_{n\times n}(\{0,1\})$</code> of arbitrarily large order $n$ such that for any non-zero vector <code>$x\in\{0,1\}^n$</code>, we have <code>$$ \|Mx\| \ll \left( \frac{\log\log n}{\log n} \right)^{1/8} \|M\|\|x\|. $$</code></p>