# Norms over some subspaces

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.

-
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

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

-
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