A class of ABS algorithms for Diophantine linear systems

Systems of integer linear (Diophantine) equations arise from various applic ations. In this paper we present an approach, based upon the ABS methods, t o solve a general system of linear Diophantine equations. This approach det ermines if the system has a solution, generalizing the classical fundamenta l theorem of the single linear Diophantine equation. If so, a solution is f ound along with an integer Abaffian (rank deficient) matrix such that the i nteger combinations of its rows span the integer null space of the cofficie nt matrix, implying that every integer solution is obtained by the sum of a single solution and an integer combination of the rows of the Abaffian. We show by a counterexample that, in general, it is not true that any set of linearly independent rows of the Abaffian forms an integer basis for the nu ll space, contrary to a statement by Egervary. Finally we show how to compu te the Hermite normal form for an integer matrix in the ABS framework.