A class of ABS algorithms for Diophantine linear systems |
| |
Authors: | Hamid Esmaeili Nezam Mahdavi-Amiri Emilio Spedicato |
| |
Institution: | (1) Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran, IR;(2) Department of Mathematics, Statistics and Computer Science, University of Bergamo, 24129 Bergamo, Italy, IT |
| |
Abstract: | Summary. Systems of integer linear (Diophantine) equations arise from various applications. In this paper we present an approach,
based upon the ABS methods, to solve a general system of linear Diophantine equations. This approach determines if the system
has a solution, generalizing the classical fundamental theorem of the single linear Diophantine equation. If so, a solution
is found along with an integer Abaffian (rank deficient) matrix such that the integer combinations of its rows span the integer
null space of the cofficient 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 null space, contrary to a statement by Egervary.
Finally we show how to compute the Hermite normal form for an integer matrix in the ABS framework.
Received July 9, 1999 / Revised version received May 8, 2000 / Published online May 4, 2001 |
| |
Keywords: | Mathematics Subject Classification (1991): 65F30 |
本文献已被 SpringerLink 等数据库收录! |
|