Skip to main content
1 of 2
Seva
  • 23k
  • 2
  • 59
  • 141

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 Euclidean norms, and $\|M\|$ is the operator norm, induced by the Euclidean norm.) I am particularly interested in the case where the elements of $M$ are restricted to the values $0$ and $1$; what can be said in this situation about the vectors $x$ with $\|Mx\|=\|M\|\|x\|$ (or with the weaker property that, say, $\|Mx\|\ge 0.1\|M\|\|x\|$)? Can one guarantee that some of these vectors have, in some reasonable sense, a low height?

Seva
  • 23k
  • 2
  • 59
  • 141