Generating the integer null space and conditions for determination of an integer basis using the ABS algorithms (Q699262)

The class of ABC methods [cf. \textit{J. Abaffy, C. G. Broyden} and \textit{E. Spedicato}, Numer. Math. 45, 361-376 (1984; Zbl 0535.65009)], now extensively used for solving general linear systems, is discussed and some of its properties are provided. An algorithm based on ABC methods for solving the Diophantine system of linear equations \(Ax=b\), \(x \in {\mathbb Z}^n\), where \(A \in {\mathbb Z}^{m \times n}\), \(b \in {\mathbb Z}^n\), \(m \leq n\) and \(\mathbb {Z}\) represents all integers, is given. The algorithm of direct iteration type produces an integer solution \(\overline{x}\), if it exists, and an integer matrix, named Abaffian, whose integer row combinations span the integer null space of the coefficient matrix \(A\). It is shown that, in general, one cannot expect that any full set of linearly independent rows of the Abaffian matrix form a basis for the integer null space of the coefficient matrix. Necessary and sufficient conditions on the Abaffian for the existence and the determination of an integer basis are presented.