Finding a partial solution to a linear system of equations in positive integers (Q1105986): Difference between revisions

An algorithm is given to determine the set of positive integer solutions of the system \(AX=b\) where \(A\in M_{m,n}({\mathbb{Z}})\) and \(b\in {\mathbb{Z}}^ n\). Denoting \(X_{| B}\in N^ B\) as \(X_ i=(X_{| B})_ i\) for every \(i\in B\subset \{1,...,n)\) and \(x\in N^ n\); \(S=\{X\in N^ n| AX=b\},\quad \sup p A=\{1\leq i\leq n;\quad \exists X\in N^ n,\quad X_ i>0;\quad AX=0\};\quad B=\{1\leq i\leq n;\quad i\not\in \sup p A\},\) two-problems are solved: (A) ``compute B and \(u\in Q^ m\) such that \(A^ tu\geq 0\) and \((A^ tu)_ i>0\) iff \(i\not\in \sup p A''\). (B) ``If \(B=\emptyset\), is \(S=\emptyset ?\) Else for \(y\in R'\) determine \(X\in N^ n\) such that \(X_{| B}=Y\) and \(AX=b''\) where \(R=S_{| B}=\{X_ B,\quad X\in S\}\) and R' is the set of \(X\in N^ B\) satisfying \(u^ tAX=u^ tb.\)