Small solutions of linear diophantine equations
type: Item
instance of: scholarly article
title: Small solutions of linear diophantine equations
zbMATH Open document ID: 0591.10010
DOI: 10.1016/0012-365X(86)90138-X
published in: Discrete Mathematics
publication date: 1986-01-01T00:00:00Z
review text: Given a system of linear diophantine equations and let (*) \(Ax=B\) be its matrix form, where \(A=(a_{ij})\) is a \(m\times n\), \(x=(x_ k)\) and \(B=(a_{k,n+1})\) are \(m\times 1\) matrices. Further, given integers \(1\leq j_ 1<...<j_ m\leq n+1\), let \(d_{j_ 1,...,j_ m}=\det (a_{i,j_ r}),\) \(1\leq i,r\leq m\), \(X=\sup \{| d_{j_ 1,...,j_ m}|:\quad j_ s\leq n\},\) \(Y=\sup \{| d_{j_ 1,...,j_ m}| \}.\) It is proved, that if the rows of A are linearly independent and (*) has a nonzero non-negative integral solution, then there exist a nonzero integral solution \(x=(x_ i)\) of (*) and integers \(1\leq j_ 1<...<j_ m\leq n\) such that \(d_{j_ 1,...,j_ m}\neq 0\), \(0\leq x_ p\leq X\) for \(p\not\in \{j_ 1,...,j_ m\}\) and \(0\leq x_ p\leq (n-m)X+Y\) otherwise. The paper also gives other estimates of small solutions to a system of linear equations.
Mathematics Subject Classification ID: 11D04
zbMATH DE Number: 3948369
zbMATH Keywords: system of linear diophantine equations
zbMATH Keywords: estimates of small solutions
author: Itshak Borosh
author: Mary E. Flahive
author: Bruce Treybig
reviewed by: Guram Gogishvili
MaRDI profile type: Publication
cites work: Q4050665
cites work: A Sharp Bound for Positive Solutions of Homogeneous Linear Diophantine Equations
cites work: Bounds on Positive Integral Solutions of Linear Diophantine Equations
cites work: Bounds on Positive Integral Solutions of Linear Diophantine Equations II
cites work: Q3241280
cites work: Q4198056
cites work: A Bound on Solutions of Linear Integer Equalities and Inequalities
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Q3050157
cites work: Q4113925
cites work: Bounds in Piecewise Linear Topology
Recommended article: Small solutions of quadratic Diophantine equations
Recommended article: Small Solutions of Quadratic Diophantine Equations
Recommended article: Q4731258
Recommended article: Small solutions of diagonal congruences
Recommended article: Small prime solutions to diagonal Diophantine equations
Recommended article: Small Solutions to Inhomogeneous Linear Equations Over Number Fields
Recommended article: Small solutions to systems of linear congruences over number fields
Recommended article: Small solutions to linear congruences and Hecke equidistribution
Recommended article: Linear Equations with Small Prime and Almost Prime Solutions
Recommended article: Small solutions of congruences
description: scientific article; zbMATH DE number 3948369