A procedure of Chvátal for testing feasibility in linear programming and matrix scaling

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


The problems of testing the feasibility of a system of linear inequalities, or strict inequalities, are well-known to be the most fundamental problems in the theory and practice of linear programming. From Gordan's Theorem it follows that Ax < b is feasible if and only if the homogeneous problem ATy = 0, bTy + s = 0, (0, 0) ≠ (y, s) {greater than or slanted equal to} (0, 0), is infeasible. We prove a stronger result: if Ax < b is feasible, then there is a feasible point satisfying x = ATw, for some w < 0. Moreover, there exists a feasible x = ATw satisfying AATw = b + δw-1, where δ is a positive scalar and w-1 = (1/w1, ..., 1/wn)T. The existence of w and its computation is motivated by a procedure suggested by Chvátal for solving linear programming as homogeneous problems, as well as results on diagonal matrix scaling of positive semidefinite matrices. Not only these reveal the significance of the homogeneous problem, but also practical and theoretical relevance of Khachiyan and Kalantari's diagonal matrix scaling algorithm, in computing an interior point of a linear system of inequalities, or in solving linear programming itself, over the reals or the rationals.

Original languageEnglish (US)
Pages (from-to)795-798
Number of pages4
JournalLinear Algebra and Its Applications
Issue number2-3
StatePublished - Jul 15 2006

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


  • Linear programming
  • Matrix scaling


Dive into the research topics of 'A procedure of Chvátal for testing feasibility in linear programming and matrix scaling'. Together they form a unique fingerprint.

Cite this