Nonnegative generalized inverses and least elements of polyhedral sets

DOI10.1016/J.LAA.2010.12.031MaRDI QIDQ2431159zbMATH OpenOpenAlexFDO

Authors Debasisha Mishra, K. C. Sivakumar

Publication date 11 April 2011

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2010.12.031

Drazin inverse generalized inverse group inverse least elements linear complementarity problems linear program Moore-Penrose inverse nonnegativity polyhedral sets

Mathematics Subject Classification ID

Theory of matrix inversion and generalized inverses (15A09) Positive matrices and their generalizations; cones of matrices (15B48) Linear programming (90C05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Review text

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}\).

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Nonnegative generalized inverses and least elements of polyhedral sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431159)