title:    Condition and Complexity Measures for Infeasibility
Certificates of Systems of Linear Inequalities and Their
Sensitivity Analysis

Hugo J. Lara

hugol@delfos.ucla.edu.ve.
Decanato de Ciencias. Universidad CentroOccidental Lisandro
Alvarado (UCLA). Apdo 400. Barquisimeto, 3001, Venezuela. 
Research supported in part by CDCHT-UCLA, Venezuela. Also supported by a
research grant from NSERC and a PREA of the second author
(Levent Tuncel,        Department of Combinatorics and
Optimization, Faculty of Mathematics, University of Waterloo,
Waterloo, Ontario N2L 3G1)

abstract
In this work we introduce a new condition measure $\xi(A)$ for the
linear feasibility problem. This measure is based on the signing
structure of the subspaces generated by the matrix $A$ that
defines the problem. We  consider two other condition numbers
$\bar\chi(A)$ and $\sigma(A)$, studied by Vavasis and Ye \ref{} in
the setting of interior point algorithms in linear programming. In
\ref{tuncel} Tun\c cel studied the connection between $\bar\chi(A)$ and
$\sigma(A)$ by exploiting their signing structure, and pointed at
the existence of families of condition numbers (as
$\xi(A)$)``between'' them.  We provide a dual characterization of
$\xi(A)$ and use it to study infeasibility  detection via a
constructive proof of a Helly-type theorem, in the same way that
Ho and Tun\c cel \ref{ho-tuncel} do using $\bar\chi(A)$. We also provide
characterizations of $\bar\chi(A)$ when different norms are used.
By exploiting the signing structure and it connection with
oriented matroids,  we deal with sensitivity analysis of
$\bar\chi_1(A)$, $\sigma(A)$ and $\xi(A)$. We give  geometric and
algebraic interpretations of perturbations of the matrix $A$ that
preserve the continuity of such condition numbers. Finally,
generalizations to convex cones and relationship with Renegar's
condition measure are provided.