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


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\|. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.