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?

$\endgroup$
8
  • 2
    $\begingroup$ What you are looking for is Siegel's lemma. $\endgroup$ Sep 29 '10 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$ Sep 29 '10 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$ Sep 29 '10 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$ Sep 29 '10 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$ Sep 29 '10 at 16:09
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.

$\endgroup$
1
  • $\begingroup$ Thanks a lot! The applications I had in mind were completely different. $\endgroup$ Sep 30 '10 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.