Two consequences of Minkowski's 2n theorem

Xueqing Tang, Adi Ben-Israel

Research output: Contribution to journalArticlepeer-review

Abstract

Consider the inequalities (a) |Ax| ≤ b, A ∈ ℝr x nr, r < n, b positive vector (here |y| denotes the vector of absolute values of components of the vector y) and (b) xT Ax ≤ α, A positive semi-definite ∈ ℝnxnr,r < n, α. > 0. Both inequalities are guaranteed a nonzero integer solution x for every positive right-hand side (b, α respectively). Such solutions will generally have a nonzero orthogonal projection XN(A) on the null space of A. We prove that a nonzero integer solution x exists with ∥ XN(A) ∥ bounded, for (a): ∥XN(A)∥ ≤ √n-r (vol A/b1 ⋯ br) 1/(n-r), for (b): ∥XN(A)∥ ≤ (2n √ vol A/αr/2 Kn) 1/(n-r), where vol A = √ Σ det2 AIJ summing over all r x r submatrices AIJ, and Kn is the volume of the Euclidean unit ball in ℝn.

Original languageEnglish (US)
Pages (from-to)279-282
Number of pages4
JournalDiscrete Mathematics
Volume169
Issue number1-3
DOIs
StatePublished - May 15 1997

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Convex sets
  • Determinants
  • Geometry of numbers
  • Lattice points
  • Singular values

Fingerprint

Dive into the research topics of 'Two consequences of Minkowski's 2n theorem'. Together they form a unique fingerprint.

Cite this