We show the equivalence among the following three condition measures of a full column rank matrix $A$: the chi measure, the signed Hoffman constant, and the signed distance to ill-posedness. The latter two measures are constructed via suitable collections of matrices obtained by flipping the signs of some rows of $A$. Our results provide a procedure to estimate $\chi(A)$ thereby opening an avenue to identify classes of linear programs solvable in polynomial time in the real model of computation.
Citation
Technical Report, Carnegie Mellon University, May 2019.