4
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ What you are looking for is Siegel's lemma. $\endgroup$
    – Felipe Voloch
    Sep 29, 2010 at 15:23
  • $\begingroup$ Thanks! The bound in Siegel's lemma spelled out for the euclidean norm on the vector space and in terms of $\|A\|$ does highly depend on $n$. Is that really best possible? $\endgroup$
    – Andreas Thom
    Sep 29, 2010 at 15:51
  • $\begingroup$ Very relevant. However, perhaps the fact that we are starting from a symmetric matrix makes things easier. And that lemma seems to depend on how large the determinant might be for $BB^T$ where $B$ is something like the non-zero rows of a reduced row echelon form of $A$. $\endgroup$
    – Aaron Meyerowitz
    Sep 29, 2010 at 15:59
  • $\begingroup$ @Aaron: If $A$ is not symmetric, then $A^{\tau}A$ is clearly symmetric. The eigenvalues of $A^{\tau}A$ are the squares of the singular values of $A$. Hence, one gets a similar bound in terms of the singular values since $\ker(A) = \ker(A^{\tau}A)$. $\endgroup$
    – Andreas Thom
    Sep 29, 2010 at 16:05
  • $\begingroup$ @Velipe: The moderns proofs of Siegel's Lemma rely on the Minkowski's theorem about lattice points in symmetric convex sets, and ultimately require knowledge about the determinant of the integer lattice in the kernel of $A$. Thus, the question is whether one can reasonably bound the determinant of this lattice in terms of the operator norm of $A$. $\endgroup$
    – Andreas Thom
    Sep 29, 2010 at 16:09

1 Answer 1

Reset to default
4
$\begingroup$

I would hope someone is able to bound the length in terms of the operator norm of alone. Is that possible?

This is not possible. Consider the group ring $\mathbb ZC_k$ of the cyclic group $C_k$ of order $k$. Consider $1-t\in \mathbb ZC_k$. As an operator on $l^2C_k$ it has 1-dimensional kernel generated by $v_k:=1+t+\ldots +t^{k-1}$. Vector $v_k$ has arbitrary large length, yet the oeprator $1-t$ has a bounded norm.

If you want to get a symmetric operator use the standard trick, i.e. take $(1-t^{-1})(1-t)$ which has the same kernel and only slightly bigger norm.

I also thought about this question in relation to my recent question. I don't know what application do you have in mind, but maybe what you're looking for is a statement like this (using notation from my question): let $\mathcal M$ be a regular family of matrices recognized by an automaton $A$. Suppose there exists $M\in \mathcal M$ such that $\det M=0$. Then there exists a matrix $N\in \mathcal M$ and a vector $v\in \mathbb Z^{\dim N}$ such that $Nv=0$ and the length of $v$ can be bounded by "size of $A$".

"Size of $A$" is some function which depends only on number of letters in the alphabet of $A$ and number of states of $A$. I'm not sure yet the above statement is true but, well, I'm "convinced" it is :-).

The family of operators $1-t$ above gives rise to a regular family of matrices if we allow finite automata which work with a circular tape.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot! The applications I had in mind were completely different. $\endgroup$
    – Andreas Thom
    Sep 30, 2010 at 20:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .