Solutions to homogeneous linear system of equations over the integers.

Question

Let $Ax=0$ a linear system of equations over the integers (i.e. all the entries of $A$ and $x$ are integers), where $A$ is an $m \times n $ matrix.

Do we know that if $n>m$ then there is a nonzero solution over the integers?

In linear algebra, for a homogeneous system this follows by the rank-nullity theorem. There has to be at least one linearly independent column, making the dimension of the kernel nontrivial. Is there something equivalent to this when we are no longer over a field, but instead over $Z$? Or is there perhaps some other useful fact about systems of linear equations over the integers that helps guarantee a solution to such a homogeneous system?

Answer 1

Let $B^n_s$ be the set of of points in $n$ dimensions that have integer coords $\le s$ in modulus. Then $A$ takes $B^n_s$ into $B^m_t$ with $t=|A|ns$, with $|A|$ denoting the element of $A$ with the highest magnitude. Now $B^n_s$ has $(2s+1)^n$ elements, and $B^m_t$ has $(2|A|ns+1)^m$. If I make $s$ sufficiently large, the former exceeds the latter and so (pigeon-hole principle) two points must have the same image. Their difference maps to zero, and this gives a solution to $Ax=0$. This method also gives an upper bound on the size of such a solution. Proof courtesy of Lang.

Answer 2

the usual question is this: if $A$ can be completed to a square matrix $B$ with integer entries and determinant $1,$ the rows of $A$ are a "primitively embedded lattice" and we would like an integral basis for the orthogonal lattice.

Well, find $B^{-1}$ which is also all integers. From $B B^{-1} = I,$ we see that the right hand $(n-m)$ columns of $B^{-1}$ are such a basis.

see comments at https://mathoverflow.net/questions/103152/determinant-of-integer-lattice-basis-of-l-x-1-ldots-x-n-a-1x-1-cdotsa