3
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ Integer values = integer entries, I assume... $\endgroup$
    – Igor Rivin
    Commented Sep 13, 2016 at 21:00
  • $\begingroup$ yup, sorry, 1:1 german translation ;) $\endgroup$
    – Bipolar Minds
    Commented Sep 13, 2016 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$
    – R.P.
    Commented Sep 13, 2016 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
    Commented Sep 13, 2016 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
    Commented Sep 13, 2016 at 21:47

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This is exactly what I was looking for, thank you! $\endgroup$
    – Bipolar Minds
    Commented Sep 13, 2016 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
    Commented Sep 13, 2016 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$
    – Turbo
    Commented Mar 14, 2017 at 23:45
  • $\begingroup$ @Turbo: zeroes do not affect the gcd, since they are divisible by anything. $\endgroup$
    – Ilya Bogdanov
    Commented Mar 20, 2017 at 11:59
  • $\begingroup$ For a reference on this, see page 51 of Schrijver: Theory of linear and integer programming. $\endgroup$
    – Tim Seppelt
    Commented Jan 18 at 8:06

You must log in to answer this question.

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