Linear Diophantine equations

Linear Diophantine equations are linear equations in which only integer solutions are allowed.

Consider a system of $m$ equations in $n$ variables for which we look for integral solutions.

$$A*x + b = 0$$

$A$ is a $m \times n$ matrix and $b$ is a vector of order $m$.

In the homogeneous space, the equation is $Mx=0$ where

$$M = \left[ \begin{array}{cc} A & b\\ 0 & 1 \end{array} \right]$$

To solve such a sytems, first the rows of $M$ are rearranged in such a way that the first $rank$ rows of $A$ are the ones which contribute to the rank. This is done with:

static void RearrangeMatforSolveDio (Matrix *M)

: rearrange the matrix in order to solve a diofantine equation.

Then the function SolveDiophantine for solving the equation can be used. If a solution exists, the procedure returns $rank$, otherwise it returns $-1$.

int SolveDiophantine (Matrix *M, Matrix **U, Vector **X)

: solve Diophantine Equations

Generally this functions is used in connection with operations on lattices because a lattice can be seen as a solution of a Diophantine equation.