Is the norm of a $0-1$ matrix (almost) attained on a $0-1$ vector?

Question

I'd like to state explicitly a problem which was somehow hidden in my three-week-old post:

Does there exist an absolute constant $c>0$ with the property that for any matrix $M\in{\mathcal M}_{m\times n}(\{0,1\})$ (zero-one matrices with $m$ rows and $n$ columns), there is a non-zero vector $x\in\{0,1\}^n$ such that $\|Mx\|/\|x\|\ge c\|M\|$?

(Here $\|\cdot\|$ denotes both the Euclidean norms in ${\mathbb R}^m$ and ${\mathbb R}^n$ and the induced operator norm.)

---

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 an example 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$?

Answer 1

As I have figured out recently, the answer is no. 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.

Start with a symmetric matrix $A\in{\mathcal M}_{n\times n}(\{0,1\})$ 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.

A precise result I was able to prove along these lines is as follows: there exist matrices $M\in{\mathcal M}_{n\times n}(\{0,1\})$ of arbitrarily large order $n$ such that for any non-zero vector $x\in\{0,1\}^n$, we have $$ \|Mx\| \ll \left( \frac{\log\log n}{\log n} \right)^{1/8} \|M\|\|x\|. $$