0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ The rank nullity is true over the rationals, so take a nonzero solution, multiply it now by a common multiple of the solution's entries' denominators, and... $\endgroup$ – DonAntonio Nov 7 '18 at 17:38
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.