×

zbMATH — the first resource for mathematics

Finding a partial solution to a linear system of equations in positive integers. (English) Zbl 0649.65033
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.\)
Reviewer: P.Stavre

MSC:
65K05 Numerical mathematical programming methods
65F05 Direct numerical methods for linear systems and matrix inversion
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Gordan, P., Ueber die auflosungen linearer gleichungen mit reelen coefficienten, Math. ann., 6, 23-28, (1873) · JFM 05.0095.01
[2] Hilbert, D., Ueber die theorie der algebraischen formen., Math. ann., 36, 473-534, (1890) · JFM 22.0133.01
[3] Dickson, L.E., Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors, Am. J. math., 35, 413-422, (1913) · JFM 44.0220.02
[4] Huet, G., An algorithm to generate the basis of solutions to homogeneous linear Diophantine equations, Infor. process. lett., 7, 144-147, (1978) · Zbl 0377.10011
[5] Lambert, J.L., Une borne pour LES génératuers des solutions entières positives d’uneéquation diophantienne linéaire, C.r. hebd. Séanc. acad. sci. Paris, 305, 39-40, (1987)
[6] Fortenbacher, A., Algebraische unifikation, ()
[7] Lambert, J.L., Le problème de l’accessibilitédans LES réseaux de Petri, ()
[8] Tucker, A.W., Dual systems of homogeneous linear relations, () · Zbl 0072.37503
[9] Nikaido, H., Convex, structures and economic theory, (1968), Academic Press New York · Zbl 0172.44502
[10] Schrijver, A., Theory of linear and integer programming, (1986), Wiley New York · Zbl 0665.90063
[11] Mayr, E., An algorithm for the general Petri net reachability problem, SIAM. J. comput., 441-460, (1984) · Zbl 0563.68057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.