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

The problem of testing the feasibility of a system of linear inequalitiies \(Ax<b\) is considered. According to Gordan's theorem \(Ax<b\) is feasible if and only if the homogeneous problem \(A^Ty=0\), \(b^Ty+s=0\), \((0,0)\neq(y,s)\geq(0,0)\), is infeasible. The authors prove a more stronger result: if \(Ax<b\) is feasible, then there is a feasible point satisfying \(x=A^Tw\), for some \(w<0\). The existence of \(w\) and its computation are based on Chvátal's procedure for solving linear programming as homogeneous problems, as well as on results on diagonal matrix scaling of positive semidefinite matrices.