# Is the operator norm always attained on a $\{0,1\}$-vector?

Given an operator $f\colon R^m\to R^n$, can one always find a non-zero vector $x\in \{ 0,1 \}^m$ such that $\|f(x)\|/\|x\|\ge0.01\|f\|$? (Here I denote by $\|\cdot\|$ both the Euclidean norms in $R^m$ and $R^n$ and the induced operator norm.) The answer may well be negative -- any examples?

In case the answer to the question above is no'' (or unknown), would it help to assume that the matrix of $f$ with respect to the standard orthonormal bases of $R^m$ and $R^n$ has all its elements equal to $0$ or $1$?

As I see it, this is basically a question in the geometry of numbers, and I would expect the answer should be known.

-

The answer is no. First, to understand the question, WLOG $f$ is symmetric and positive definite; a general $f$ has a polar decomposition $f = os$ and the orthogonal factor $o$ has no effect on any of the norms in question. Then, WLOG $f$ is a rank 1 projection. The second and subsequent eigenvalues of $f$ do not increase $||f||$, but they could increase $||f(x)||$ for some specific $x$. So in summary, we can assume that $f = vv^T$ for some vector $v$. The question is whether $v$ must always make a small angle with some binary vector.

Let $$v = (1,\frac{1}{\sqrt{2}},\frac{1}{\sqrt{3}},\ldots,\frac{1}{\sqrt{m}}).$$ If $w$ is a binary vector of weight $k$, then $|v \cdot w|$ is maximized when the non-zero entries of $w$ are at the beginning. However, $$||w|| = \sqrt{k} \qquad ||v|| = \Theta(\sqrt{\log m}) \qquad |v \cdot w| = O(\sqrt{k}).$$ This means that the angle between $w$ and $v$ is large, and therefore $||f(w)|| = ||v (v \cdot w)||$ is small compared to $||f||\;||w|| = ||v||^2 ||w||$.

The same proof works if $\{0,1\}$ is replaced by $\{-1,0,1\}$, or indeed by any finite subset of $\mathbb{R}$. On the other hand, there is a variation of the question with a positive answer.

Similar to Pietro Majer's remark, you can interpret the question as a comparison between two norms on $\mathbb{R}^m$. One is the $\ell^2$ norm, and the other is the norm whose unit ball is a polytope whose vertices are at the points in $S = \{0,1\}^m$ and its negative. By the theory of spherical packings on a sphere, for any $c < 1$, there exists a set $S$ of exponential size in $m$ such that the two norms are equal up to a factor of $c$. This is then a positive answer for that sample set of vector, even for constants close to 1. But such a set (coming from the centers of a sphere covering of the sphere) has to be fairly complicated, and I don't know if there are explicit asymptotic examples.

-
Nice answer! Is it true that your vector $v$ is an example of what is sometimes called a `badly approximable vector'? –  Robby McKilliam Oct 10 '10 at 10:03
Of course it is badly approximable in context, but Google tells me that the standard context is something else. The term usually refers to a number or vector that is badly approximable by rational numbers or vectors, in the sense that the common denominator of a good rational approximation is as large as possible. This is vaguely similar, but not really the same. –  Greg Kuperberg Oct 10 '10 at 10:12
@Greg : just a trivial remark : it seems that you exchanged "large angle" ($\cos$ near 0) and "small angle" ($|\cos|\geq c>0$) in your answer (equivalently, said "angle", thinking "absolute cosine of angle"). –  BS. Oct 12 '10 at 9:55
@BS Yeah, you're right. I think that I fixed it now. –  Greg Kuperberg Oct 12 '10 at 12:05
Great, this answers my first question - as suspected, the answer is negative. How about the second question? What if we assume that the operator under consideration has a zero-one matrix (in a pair of orthonormal bases)? –  Seva Oct 13 '10 at 21:28

Of course no. Remember that the operator norm of $A$ wrto the Eucliedan norms is the attained at an eigenvector of $S:=A^TA.$ Try a suitable simple binary $2\times 2$ matrix and compare the values of $\|Ax\|$ on the eigenvectors of $S$ and in the three nonzero binary vectors $(01), (10), (11).$

However, if instead you take in the domain $\mathbb{R}^n$ either the $l^1$ norm $\|\cdot \|_1$ or the $l^\infty$ norm $\|\cdot\|_\infty$ then, whatever norm you have in the target space $\mathbb{R}^m$, the operator norm of $A$ is attained in an extremal point of the unit ball of the domain, which is in both cases a binary vector.

-
Yes, I agree. However, I wonder if putting constraints upon $m$ or $n$ could help. The original questions asks for a constant of $0.01$. There's no way this can be absolute, but how does the best constant vary with $n$ and $m$? –  Matthew Daws Oct 10 '10 at 8:54
I may have gaven the title of my question an overly simplified form. In fact, I want the norm of $f$ to be attained on a binary vector up to a constant factor (written as $0.01$ in the body of my question). Thus, no one single particular example would resolve the question! –  Seva Oct 10 '10 at 9:18
As to the best constant -- seems I can get a very good one; namely, something like $1/\sqrt{\log s}$, with $s=\min\{m,n\}$. My question is whether this can be improved to a "constant constant"! –  Seva Oct 10 '10 at 9:46
yea, the title was somehow misleading. No matter, you then got a very clear and thorough answer by Greg Kuperberg. –  Pietro Majer Oct 10 '10 at 18:20