A class of ABS algorithms for Diophantine linear systems (Q5958923)

An approach is proposed, based on Abaffy-Broyden-Spedicato methods (ABS), for solving the linear Diophantine vector equation \(Ax=b\), where \(A\in\mathbb{Z}^{m\times n}(m\leq n)\), \(b\in\mathbb{Z}^m\), \(x\in\mathbb{Z}^n\) is the solution and \(\mathbb{Z}\) is the set of integers. The approach constructively determines whether the equation has a solution. A counterexample for a previous hypothesis of \textit{E. Egerváry} [Publ. Math. Debrecen 4, 481-483 (1955-1956; Zbl 0074.27301); Z. Angew. Math. Phys. 11, 376-386 (1960; Zbl 0102.11401)] concerning such equations is given. Finally an application to the determination of the Hermite normal form of an integer matrix is presented.