### 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 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Algebra and Number Theory
- Numerical Analysis

### Cite this

}

*Linear Algebra and Its Applications*, vol. 416, no. 2-3, pp. 795-798. https://doi.org/10.1016/j.laa.2005.12.022

**A procedure of Chvátal for testing feasibility in linear programming and matrix scaling.** / Jin, Yi; Kalantari, Bahman.

Research output: Contribution to journal › Article

TY - JOUR

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

AU - Jin, Yi

AU - Kalantari, Bahman

PY - 2006/7/15

Y1 - 2006/7/15

N2 - 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 Ty = 0, b Ty + 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 Tw, for some w < 0. Moreover, there exists a feasible x = A Tw satisfying AA Tw = 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.

AB - 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 Ty = 0, b Ty + 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 Tw, for some w < 0. Moreover, there exists a feasible x = A Tw satisfying AA Tw = 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.

UR - http://www.scopus.com/inward/record.url?scp=33646925930&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646925930&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2005.12.022

DO - 10.1016/j.laa.2005.12.022

M3 - Article

VL - 416

SP - 795

EP - 798

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

IS - 2-3

ER -