next up previous contents
Next: Smith decomposition Up: Other tools Previous: Other tools   Contents

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.

\begin{displaymath}
A*x + b = 0
\end{displaymath}

$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

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

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.


next up previous contents
Next: Smith decomposition Up: Other tools Previous: Other tools   Contents
Sorin Olaru 2002-04-24