MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

Let $C$ be the set of all vectors of dimension $n$ such that each of its entries are one of $-1$, $0$ and $1$ and also that the every $v \in C$ has at least $\frac{n}{100}$ $1$'s and at least $\frac{n}{100}$ $-1$'s. For a matrix $A$ (its dimensions are $\Lambda n \times n$ for some sufficiently large constant $\Lambda$), define $||A||_{C,\infty}$ to be

$||A||_{C,\infty} = min _{x \in C} \ \ \ ||A x|| _{\infty}$

Is it possible to construct an $A$ such that all its entries come from the interval $[-1,1]$ and $||A||_{C,\infty} = n^{1/2 + \epsilon}$ for some $\epsilon>0$. Constructing the matrix $A$ randomly by choosing each of its entries to be independent and uniformly random elements in $[-1,1]$ gets $||A|| _{C,\infty} =n^{1/2}$. The construction does not need to be explicit.

share|cite|improve this question
I removed the inappropriate "r-matrix" tag, which refers to something in quantum groups. Please retag! – Scott Morrison Dec 12 '10 at 15:06
@Scott: retagged as [matrices] for now. Better tag suggestions are welcome. I am guessing the OP typed "matrix" into the tag field and so [matrices] didn't come up as an option. – Willie Wong Dec 12 '10 at 15:13
up vote 4 down vote accepted

The answer is negative. You can achieve at most $O(\sqrt{n\log n})$.

Since more than half of the $\pm 1$ vectors are in $C$,

$$\|A\|_{C,\infty} \leq 2 Aver(\|Av\|_\infty),$$

where the Average is taken over all $\pm 1$ vectors.

To give an upper bound on $Aver(\|Av\|_\infty)$, note that each of the coordinates of $Av$ has distribution whose tail is subgaussian with parameter $\sqrt n$. By that I mean $Prob(|\sum_ja_{ij}v_j|>C\sqrt n t)\le e^{-t^2}$, for some absolute constant $C$.

It follows that the expectation of the maximum of $\Lambda n$ such variables is at most $O(\sqrt{n\log n})$. (Note that independence of these variables is not needed).

share|cite|improve this answer
I tried to fix the LaTeX, but I am baffled by why the displayed line isn't rendering correctly on my end. Maybe someone can edit my edit. – Todd Trimble Dec 12 '10 at 14:04
@Todd: fixed. The underscores are being interpreted as emphasis marks. I just quoted the display line in backticks. – Willie Wong Dec 12 '10 at 15:11
Well, I dont see why $||A|| _{C,\infty} \leq\frac{1}{2} Aver(||Av|| _{\infty})$. Though that is fine because $C$ contains $1 -2^{-n/100}$ of all the $\pm 1$ vectors. As the max norm can be $n$, we get that $||A|| _{C,\infty} \leq Aver(||Av|| _{\infty}) + n 2^{-n/100}$ which still gives the same result. – Anindya De Dec 12 '10 at 20:05
Right, the $\frac12$ should have been 2. I'll correct it now. – Gideon Schechtman Dec 12 '10 at 21:15

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.