Let $Ax=B$ be a system of linear diophantine equations, where $A$ is a full rank $n \times 2n$-matrix with integer entries. In the case $n=1$ we have solutions parameterized by $\mathbb{Z}$ iff $gcd(a_{11},a_{12})$ divides $b_{11}$. Is there a similar statement for arbitrary $n$ of the form "We get solutions paramterized by $\mathbb{Z}^n$ iff condition on $B$"

EDIT: Since I know basically nothing about diophantine equations, it could be that this question is far from being research level.. if so, just tell me and I will delete it and bring it up in math SE

  • $\begingroup$ Integer values = integer entries, I assume... $\endgroup$ – Igor Rivin Sep 13 '16 at 21:00
  • $\begingroup$ yup, sorry, 1:1 german translation ;) $\endgroup$ – Bipolar Minds Sep 13 '16 at 21:02
  • 1
    $\begingroup$ The answer you're looking for is probably the one given by Noam Elkies in this thread: mathoverflow.net/questions/208147/… $\endgroup$ – RP_ Sep 13 '16 at 21:03
  • $\begingroup$ hm, I was hoping for something more concrete, like a general condition on B in terms of gcd's of the entries of $A$.. but I think you're right, thx $\endgroup$ – Bipolar Minds Sep 13 '16 at 21:12
  • $\begingroup$ @BipolarMinds if you wish to reply to a comment and have that person be notified that there is some kind of response, you need to start with an at sign @ and then, at least, the first three letters of that username. Usually, if you type that much, it will allow you to click on a complete version of that username, which is what i did here... $\endgroup$ – Will Jagy Sep 13 '16 at 21:47

Surely, the Smith normal form does it all. But if you need a more concrete condition, here is one.

Let $X$ be the set of all $n\times n$ minors of $A$, and let $Y$ be the set of all $n\times n$ minors of $(A\,| B)$. Then the equivalent condition is that $\gcd(X)=\gcd(Y)$. Indeed, this condition is equivalent if the system is in the Smith form, and moreover it is preserved by $SL(n,\mathbb Z)$-transforms.

| cite | improve this answer | |
  • $\begingroup$ This is exactly what I was looking for, thank you! $\endgroup$ – Bipolar Minds Sep 13 '16 at 21:53
  • $\begingroup$ as a neat aside: If (as in my case) $A$ is the concatenation of two upper triangular matrices, then $|X|=C_n$ is the $n$th Catalan number $\endgroup$ – Bipolar Minds Sep 13 '16 at 22:28
  • $\begingroup$ @ilyabogbanov if $0\in X$ and $0\in Y$ then does $gcd(X)=gcd(Y)$ hold and what if $0\in X$ and $0\notin Y$ and $gcd(X\backslash\{0\})=gcd(Y)$ holds? $\endgroup$ – T.... Mar 14 '17 at 23:45
  • $\begingroup$ @Turbo: zeroes do not affect the gcd, since they are divisible by anything. $\endgroup$ – Ilya Bogdanov Mar 20 '17 at 11:59

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.