MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 10 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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