Some properties of Chebyshev approximation in a subspace of Rⁿ

Let K be a subspace of Rn and let K⊥ be the orthogonal complement of K. Rockafellar has shown that certain properties of K may be characterized by considering the possible patterns of signs of the nonzero components of vectors of K and of K⊥. Such considerations are shown to lead to the standard characterization theorem for discrete linear Chebyshev approximation as well as to several results on uniqueness of solutions. A method is given for testing uniqueness of a given solution. A special case related to graph theory is discussed and combinatorial methods are given for solving and testing for uniqueness. © 1976.