Finding a partial solution to a linear system of equations in positive integers

Direct numerical methods for linear systems and matrix inversion (65F05) Numerical mathematical programming methods (65K05) Integer programming (90C10)

Review text

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.\)

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Finding a partial solution to a linear system of equations in positive integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1105986)