2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I removed the inappropriate "r-matrix" tag, which refers to something in quantum groups. Please retag! $\endgroup$ Dec 12, 2010 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$ Dec 12, 2010 at 15:13

1 Answer 1

4
$\begingroup$

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

$\endgroup$
2
  • $\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, 2010 at 20:05
  • $\begingroup$ Right, the $\frac12$ should have been 2. I'll correct it now. $\endgroup$ Dec 12, 2010 at 21:15

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.