## Abstract

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 A^{T}y = 0, b^{T}y + 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 = A^{T}w, for some w < 0. Moreover, there exists a feasible x = A^{T}w satisfying AA^{T}w = b + δw^{-1}, where δ is a positive scalar and w^{-1} = (1/w_{1}, ..., 1/w_{n})^{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 language | English (US) |
---|---|

Pages (from-to) | 795-798 |

Number of pages | 4 |

Journal | Linear Algebra and Its Applications |

Volume | 416 |

Issue number | 2-3 |

DOIs | |

State | Published - Jul 15 2006 |

## All Science Journal Classification (ASJC) codes

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

## Keywords

- Linear programming
- Matrix scaling