8
votes
1answer
610 views

Projecting the unit cube onto a (very special) subspace

Let $n>1$ be an integer, and $a>1$ a real number. Consider the subspace $L<R^{2^n}$ generated by the $n$ possible tensor products of the $n-1$ copies of the vector $(1,a)$ and one copy of ...
2
votes
2answers
549 views

Projecting the unit cube onto a subspace [closed]

I have some (rather exotic) subspace $L<R^n$, and I want to show that every non-zero vector in $\{0,1\}^n$ has a relatively small projection onto $L$. What general results and tools can be helpful? ...
4
votes
0answers
312 views

An operator-norm version of Siegel's Lemma

Is there a kind of Siegel's Lemma saying that if $M$ is a ``small-height'' integer matrix, then there is a "small-height" vector $x$ with $\|Mx\|=\|M\|\|x\|$? (Here $\|Mx\|$ and $\|x\|$ denote the ...
17
votes
1answer
530 views

Is the norm of a $0-1$ matrix (almost) attained on a $0-1$ vector?

I'd like to state explicitly a problem which was somehow hidden in my three-week-old post: Does there exist an absolute constant $c>0$ with the property that for any matrix $M\in{\mathcal ...
6
votes
2answers
667 views

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