Finding a partial solution to a linear system of equations in positive integers
type: Item
instance of: scholarly article
title: Finding a partial solution to a linear system of equations in positive integers
zbMATH Open document ID: 0649.65033
DOI: 10.1016/0898-1221(88)90172-1
author: J. L. Lambert
publication date: 1988-01-01T00:00:00Z
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.\)
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 4060642
zbMATH Keywords: partial solutions
zbMATH Keywords: linear system
zbMATH Keywords: algorithm
zbMATH Keywords: positive integer solutions
MaRDI profile type: Publication
full work available at URL: 0898-1221(88)90172-1
OpenAlex ID: W1993260645
cites work: An algorithm to generate the basis of solutions to homogeneous linear Diophantine equations
cites work: Q4723808
cites work: Q3236239
cites work: Q5558820
cites work: Q3818127
cites work: An Algorithm for the General Petri Net Reachability Problem
published in: Computers & Mathematics with Applications
description: scientific article; zbMATH DE number 4060642