On the existence of solutions in systems of linear Diophantine equations
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.
- Methods of solution and criteria of consistency of systems of linear Diophantine equations over the set of natural numbers
- scientific article; zbMATH DE number 800104
- Showing the non-existence of solutions in systems of linear Diophantine equations
- Algorithms for solving systems of linear Diophantine equations in integer domains
- scientific article; zbMATH DE number 4101294
- A fast method for finding the basis of non-negative solutions to a linear diophantine equation
- Algorithms for the Solution of Systems of Linear Diophantine Equations
- An algorithm to generate the basis of solutions to homogeneous linear Diophantine equations
- An efficient incremental algorithm for solving systems of linear diophantine equations
- Bounds on Positive Integral Solutions of Linear Diophantine Equations
- Efficient solution of linear diophantine equations
- scientific article; zbMATH DE number 1253960 (Why is no real title available?)
- scientific article; zbMATH DE number 1254241 (Why is no real title available?)
- scientific article; zbMATH DE number 1254302 (Why is no real title available?)
- scientific article; zbMATH DE number 1090094 (Why is no real title available?)
- New methods for proving the impossibility to solve problems through reduction of problem spaces
- On Systems of Linear Diophantine Equations
- Showing the non-existence of solutions in systems of linear Diophantine equations
- On lengths of non-unique factorizations and systems of linear diophantine inequalities
- Showing the non-existence of solutions in systems of linear Diophantine equations
- scientific article; zbMATH DE number 800104 (Why is no real title available?)
- scientific article; zbMATH DE number 7510495 (Why is no real title available?)
This page was built for publication: On the existence of solutions in systems of linear Diophantine equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692309)
