On the existence of solutions in systems of linear Diophantine equations (Q692309)

Let \(A\) be an \(N \times M\) matrix with entries in \(\mathbb{Z}, \mathbf{y}\in \mathbb{Z}^N\), and \(\mathbf{x}=(x_1,\ldots, x_M)^T\) be a vector of indeterminates. The paper under review concerns the existence of integer solutions to the linear system \[ A\mathbf{x}=y^T. \] The main concept used in the paper is that of \textit{tester}, that is, a linear function \(f : \mathbb{Z}^N \rightarrow R \) where \(R =\mathbb{Z}\) or \(R = \mathbb{Z}/m\mathbb{Z}\) for some \(m\in \mathbb{N}\), such that \(f(\mathbf{a})=0\) for each column \(\mathbf{a}\) of \(A\). It is obvious that if the linear system has a solution then \(f(\mathbf{y}^T)=0\); a set of testers \(\{f_1, \ldots, f_k\}\) is called \textit{complete} if conversely \(f_1(\mathbf{y}^T)=\cdots = f_k(\mathbf{y}^T)= 0\) implies that the system has a solution. The authors present in Section 5 an algorithm for finding a complete set of testers. However, this algorithm involves, among other things, solving the linear system \(A^T \mathbf{z}=\mathbf{0}\), so it is not clear whether this method is more efficient than the naive one of solving the original linear system directly.