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.

  • $\begingroup$ I removed the inappropriate "r-matrix" tag, which refers to something in quantum groups. Please retag! $\endgroup$ – Scott Morrison Dec 12 '10 at 15:06
  • $\begingroup$ @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. $\endgroup$ – Willie Wong Dec 12 '10 at 15:13

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).

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Todd Trimble Dec 12 '10 at 14:04
  • $\begingroup$ @Todd: fixed. The underscores are being interpreted as emphasis marks. I just quoted the display line in backticks. $\endgroup$ – Willie Wong Dec 12 '10 at 15:11
  • $\begingroup$ 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. $\endgroup$ – Anindya De Dec 12 '10 at 20:05
  • $\begingroup$ Right, the $\frac12$ should have been 2. I'll correct it now. $\endgroup$ – Gideon Schechtman Dec 12 '10 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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