Nonnegative generalized inverses and least elements of polyhedral sets (Q2431159)

A square real matrix \(A\) is called monotone if \(Ax \geq 0\) implies \(x \geq 0.\) Here \(x=(x_i)\geq 0\) denotes the fact that \(x_i\geq 0\) for all \(i\). \textit{L. Collatz} [Arch. Math. 3, 366--376 (1952; Zbl 0048.09802)] has shown that a matrix is monotone if and only if it is invertible and the inverse is (entrywise) nonnegative. The notion of monotonicity has been generalized in several directions. An extension for characterizing nonnegativity of generalized inverses (without use of the term) was first accomplished by \textit{O. L. Mangasarian} [SIAM Rev. 10, 439--441 (1968; Zbl 0179.05102)]. \textit{A. Berman} and \textit{R. J. Plemmons} made extensive contributions to nonnegative generalized inverses by proposing various notions of monotonicity [Linear Algebra Appl. 13, 115--123 (1976; Zbl 0341.15013)]. Nonnegative inverses arise naturally when one examines the relationship between linear complementarity problems that could be solved by a single linear program and least elements of certain polyhedral sets. In this connection, there is a result of \textit{R. W. Cottle} and \textit{A. F. Veinott jun.} [Math. Program. 3, 238--249 (1972; Zbl 0245.90015)] which establishes a connection between least elements of polyhedral sets and the existence of left-inverses of a matrix that defines the polyhedral set. The results of the paper under review have been primarily motivated by the results of Cottle and Veinott. The first result of the authors characterizes the existence of least elements in terms of some of the most important generalized inverses. The result for the Moore-Penrose inverse is as follows: Let \(A \in \mathbb{R}^{m \times n}\) and \(b \in \mathbb{R}^m\) be given. \(R(A)\) and \(N(A)\) stand for the range space and the null space of \(A\), respectively. For a subspace \(M\) of \(\mathbb{R}^k\), \(P_M\) denotes the orthogonal projection of \(\mathbb{R}^k\) onto \(M\). Finally, for a subset \(X\) of \(\mathbb{R}^n\) we say that \(x^*\) is the least element of \(X\) if \(x^* \leq x\) for all \(x \in X\), where the ordering is the usual ordering of \(\mathbb{R}^n\). Set \(X_b=\{x \in \mathbb{R}^{n}:Ax+y\geq b, P_{N(A)}x=0,~P_{R(A)}y=0\), for some \(y\in \mathbb{R}^m\}.\) Then, a vector \(x^{*}\) is the least element of \(X_{b}\) if and only if \(x^{*}=A^{\dag}b\in X_{b}\) with \(A^{\dag}\geq 0\). Here \(A^{\dagger}\) denotes the Moore-Penrose inverse of \(A\). Recall that \(A^{\dagger}\) is the unique solution \(X \in \mathbb{R}^{n \times m}\) which satisfies the equations \(AXA=A;~XAX=X;~ (AX)^*=AX;~(XA)^*=XA\). In the rest of the paper, among other results, the authors present sufficient conditions in terms of least elements under which a dual linear programming problem has an explicit optimal solution. A certain converse is proved. The last three theorems reinforce the relationship between least elements and nonnegative generalized inverses. A sample result is presented. Recall that a vector \(x \in X_b\) is said to be determined by a submatrix \(B\) of \(A\) if \(Bx=b_{B}\), where \(b_{B}\) is the restriction of the vector \(b\) to those rows, corresponding to the rows of \(B\). Let \(B\) be a submatrix of \(A\) satisfying \(R(A)=R(B)\) and \(N(A)=N(B)\). Suppose that \(B^{\dag}\geq 0\) and \(x^{*}\in X_{b}\) be determined by \(B\). Then \(x^{*}\) is the least element of \(X_{b}\).