THE GEOMETRY OF BASIC, APPROXIMATE, AND MINIMUM-NORM SOLUTIONS OF LINEAR-EQUATIONS

The basic solutions of the linear equations Ax = b are the solutions o f subsystems corresponding to maximal nonsingular submatrices of A. Th e convex hull of the basic solutions is denoted by C = C(A, b). Given 1 less than or equal to p less than or equal to infinity, the l(p)-app roximate solutions of Ax = b, denoted x({p}), are minimizers of parall el to Ax - b parallel to(p). Given M is an element of D-m, the set of positive diagonal m x m matrices, the solutions of min(x) parallel to M(Ax - b)parallel to(p) are called scaled l(p)-approximate solutions. For 1 less than or equal to p(1), p(2) less than or equal to infinity, the minimum-l(p2)-norm l(p1)-approximate solutions are denoted x({p2} )({p1}). Main results: (1) If A is an element of R(m)(mxn), then C con tains all [some] minimum l(p)-norm solutions, for 1 less than or equal to p < infinity [p = infinity]. (2) For general A and any 1 less than or equal to p(1), p(2) < infinity the set C contains all x({p2})({p1} ). (3) The set of scaled l(p)-approximate solutions, with M ranging ov er D-m, is the same for all 1 < p < infinity. (4) The set of scaled le ast-squares solutions has the same closure as the set of solutions of min(x) f(\Ax - b\). where f:R(+)(m) --> R ranges over all strictly iso tone functions.