This note studies χA, a condition number used in the linear programming algorithm of Vavasis and Ye whose running time depends only on the constraint matrix A ∈ ℝm×n, and σ(A), a variant of another condition number due to Ye that also arises in complexity analyses of linear programming problems. We provide a new characterization of χA and relate χA and σ(A). Furthermore, we show that if A is a standard Gaussian matrix, then E(ln χA) = O(min{m ln n, n}). Thus, the expected running time of the Vavasis–Ye algorithm for linear programming problems is bounded by a polynomial in m and n for any right-hand side and objective coefficient vectors when A is randomly generated in this way. As a corollary of the close relation between χA and σ(A), we show that the same bound holds for E(lnσ(A)).
