Let $A$ be a non-zero symmetric $n \times n$-matrix with integer entries and suppose that $\det(A) =0$.

Question:How long is the shortest non-zero integer vector in the kernel of $A$?

Example: If $A$ has non-zero eigenvalues $\xi_1,\dots,\xi_k$ (not necessarily counting with multiplicities), then the polynomial $p(t) = (\xi_1-t) \cdots (\xi_k -t)$ has integer coefficients. Hence, $p(A) \in M_n {\mathbb Z}$ and at the same time $Ap(A)=0$. Clearly, $$p(A) = {\rm det}'(A) \cdot Q_{\ker(A)},$$ where $\det'(A) := \xi_1 \cdots \xi_k$ and $Q_{\ker(A)}$ denotes the orthogonal projection onto the kernel of $A$. Hence, we get for the operator norm $\|p(A)\| = |\det'(A)|$. Now, there exists an index $1 \leq i \leq n$, such that $v:=p(A)e_i \neq 0$ and one gets $\|v\| \leq \det'(A)$. At the same time $v$ has integer entries and lies in the kernel of $A$.

In many examples one can do much better. I would hope someone is able to bound the length in terms of the operator norm of $A$ alone. Is that possible?

The problem can also be phrased in terms of additive combinatorics. Indeed, if one identifies the image of ${\mathbb Z}^n$ under $A$ with ${\mathbb Z}^{k}$ for some $k < n$, then injectivity of $A$ on the set $X=\lbrace-m,\dots,m\rbrace ^n$ implies that $X$ can be embedded in ${\mathbb Z}^k$ preserving the addition whenever it made sense on $X$. This alone seems to require a lot of distortion, i.e. a large operator norm of $A$.

What kind of literature can be recommended?

singularvalues of $A$. Hence, one gets a similar bound in terms of the singular values since $\ker(A) = \ker(A^{\tau}A)$. – Andreas Thom Sep 29 '10 at 16:05