# On Nonnegative Moore-Penrose Inverses of Perturbed Matrices

Authors: Shani Jose; K. C. Sivakumar
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Nonnegativity of the Moore-Penrose inverse of a perturbation of the formA−XGYT is considered when A†≥0. Using a generalized version of the Sherman-Morrison-Woodbury formula, conditions for (A−XGYT)† to be nonnegative are derived. Applications of the results are presented briefly. Iterative versions of the results are also studied.


---

## Body

## 1. Introduction

We consider the problem of characterizing nonnegativity of the Moore-Penrose inverse for matrix perturbations of the typeA-XGYT, when the Moore-Penrose inverse of A is nonnegative. Here, we say that a matrix B=(bij) is nonnegative and denote it by B≥0 if bij≥0, ∀i,j. This problem was motivated by the results in [1], where the authors consider an M-matrix A and find sufficient conditions for the perturbed matrix (A-XYT) to be an M-matrix. Let us recall that a matrix B=(bij) is said to Z-matrix if bij≤0 for all i, j, i≠j. An M-matrix is a nonsingular Z-matrix with nonnegative inverse. The authors in [1] use the well-known Sherman-Morrison-Woodbury (SMW) formula as one of the important tools to prove their main result. The SMW formula gives an expression for the inverse of (A-XYT) in terms of the inverse of A, when it exists. When A is nonsingular, A-XYT is nonsingular if and only I-YTA-1X is nonsingular. In that case,
(1)(A-XYT)-1=A-1-A-1X(I-YTA-1X)-1YTA-1.The main objective of the present work is to study certain structured perturbationsA-XYT of matrices A such that the Moore-Penrose inverse of the perturbation is nonnegative whenever the Moore-Penrose inverse of A is nonnegative. Clearly, this class of matrices includes the class of matrices that have nonnegative inverses, especially M-matrices. In our approach, extensions of SMW formula for singular matrices play a crucial role. Let us mention that this problem has been studied in the literature. (See, for instance [2] for matrices and [3] for operators over Hilbert spaces). We refer the reader to the references in the latter for other recent extensions.In this paper, first we present alternative proofs of generalizations of the SMW formula for the cases of the Moore-Penrose inverse (Theorem5) and the group inverse (Theorem 6) in Section 3. In Section 4, we characterize the nonnegativity of (A-XGYT)†. This is done in Theorem 9 and is one of the main results of the present work. As a consequence, we present a result for M-matrices which seems new. We present a couple of applications of the main result in Theorems 13 and 15. In the concluding section, we study iterative versions of the results of the second section. We prove two characterizations for (A-XYT)† to be nonnegative in Theorems 18 and 21.Before concluding this introductory section, let us give a motivation for the work that we have undertaken here. It is a well-documented fact thatM-matrices arise quite often in solving sparse systems of linear equations. An extensive theory of M-matrices has been developed relative to their role in numerical analysis involving the notion of splitting in iterative methods and discretization of differential equations, in the mathematical modeling of an economy, optimization, and Markov chains [4, 5]. Specifically, the inspiration for the present study comes from the work of [1], where the authors consider a system of linear inequalities arising out of a problem in third generation wireless communication systems. The matrix defining the inequalities there is an M-matrix. In the likelihood that the matrix of this problem is singular (due to truncation or round-off errors), the earlier method becomes inapplicable. Our endeavour is to extend the applicability of these results to more general matrices, for instance, matrices with nonnegative Moore-Penrose inverses. Finally, as mentioned earlier, since matrices with nonnegative generalized inverses include in particular M-matrices, it is apparent that our results are expected to enlarge the applicability of the methods presently available for M-matrices, even in a very general framework, including the specific problem mentioned above.


## 2. Preliminaries

Letℝ, ℝn, and ℝm×n denote the set of all real numbers, the n-dimensional real Euclidean space, and the set of all m×n matrices over ℝ. For A∈ℝm×n, let R(A), N(A), R(A)⊥, and AT denote the range space, the null space, the orthogonal complement of the range space, and the transpose of the matrix A, respectively. For x=(x1,x2,…,xn)T∈ℝn, we say that x is nonnegative, that is, x≥0 if and only if xi≥0 for all i=1,2,…,n. As mentioned earlier, for a matrix B we use B≥0 to denote that all the entries of B are nonnegative. Also, we write A≤B if B-A≥0.Letρ(A) denote the spectral radius of the matrix A. If ρ(A)<1 for A∈ℝn×n, then I-A is invertible. The next result gives a necessary and sufficient condition for the nonnegativity of (I-A)-1. This will be one of the results that will be used in proving the first main result.Lemma 1 (see [5, Lemma 2.1, Chapter 6]).
LetA∈ℝn×n be nonnegative. Then, ρ(A)<1 if and only if (I-A)-1 exists and
(2)(I-A)-1=∑k=0∞‍Ak≥0.More generally, matrices having nonnegative inverses are characterized using a property called monotonicity. The notion of monotonicity was introduced by Collatz [6]. A real n×n matrix A is called monotone if Ax≥0⇒x≥0. It was proved by Collatz [6] that A is monotone if and only if A-1 exists and A-1≥0.One of the frequently used tools in studying monotone matrices is the notion of a regular splitting. We only refer the reader to the book [5] for more details on the relationship between these concepts.The notion of monotonicity has been extended in a variety of ways to singular matrices using generalized inverses. First, let us briefly review the notion of two important generalized inverses.ForA∈ℝm×n, the Moore-Penrose inverse is the unique Z∈ℝn×m satisfying the Penrose equations: AZA=A, ZAZ=Z, (AZ)T=AZ, and (ZA)T=ZA. The unique Moore-Penrose inverse of A is denoted by A†, and it coincides with A-1 when A is invertible.The following theorem by Desoer and Whalen, which is used in the sequel, gives an equivalent definition for the Moore-Penrose inverse. Let us mention that this result was proved for operators between Hilbert spaces.Theorem 2 (see [7]).
LetA∈ℝm×n. Then A†∈ℝn×m is the unique matrix X∈ℝn×m satisfying  (i)
ZAx=x, ∀x∈R(AT),(ii)
Zy=0, ∀y∈N(AT).Now, forA∈ℝn×n, any Z∈ℝn×n satisfying the equations AZA=A,  ZAZ=Z, and AZ=ZA is called the group inverse of A. The group inverse does not exist for every matrix. But whenever it exists, it is unique. A necessary and sufficient condition for the existence of the group inverse of A is that the index of A is 1, where the index of a matrix is the smallest positive integer k such that rank(Ak+1)=rank(Ak).Some of the well-known properties of the Moore-Penrose inverse and the group inverse are given as follows:R(AT)=R(A†), N(AT)=N(A†), A†A=PR(AT), and AA†=PR(A). In particular, x∈R(AT) if and only if x=A†Ax. Also, R(A)=R(A#), N(A)=N(A#), and A#A=AA#=PR(A),N(A). Here, for complementary subspaces L and M of ℝk, PL,M denotes the projection of ℝk onto L along M. PL denotes PL,M if M=L⊥. For details, we refer the reader to the book [8].In matrix analysis, a decomposition (splitting) of a matrix is considered in order to study the convergence of iterative schemes that are used in the solution of linear systems of algebraic equations. As mentioned earlier, regular splittings are useful in characterizing matrices with nonnegative inverses, whereas, proper splittings are used for studying singular systems of linear equations. Let us next recall this notion. For a matrixA∈ℝm×n, a decomposition A=U-V is called a proper splitting [9] if R(A)=R(U) and N(A)=N(U). It is rather well-known that a proper splitting exists for every matrix and that it can be obtained using a full-rank factorization of the matrix. For details, we refer to [10]. Certain properties of a proper splitting are collected in the next result.Theorem 3 (see [9, Theorem 1]).
LetA=U-V be a proper splitting of A∈ℝm×n. Then, (a)
A=U(I-U†V),(b)
I-U†V is nonsingular and,(c)
A†=(I-U†V)-1U†.The following result by Berman and Plemmons [9] gives a characterization for A† to be nonnegative when A has a proper splitting. This result will be used in proving our first main result.Theorem 4 (see [9, Corollary 4]).
LetA=U-V be a proper splitting of A∈ℝm×n, where U†≥0 and U†V≥0. Then A†≥0 if and only if ρ(U†V)<1.


## 3. Extensions of the SMW Formula for Generalized Inverses

The primary objects of consideration in this paper are generalized inverses of perturbations of certain types of a matrixA. Naturally, extensions of the SMW formula for generalized inverses are relevant in the proofs. In what follows, we present two generalizations of the SMW formula for matrices. We would like to emphasize that our proofs also carry over to infinite dimensional spaces (the proof of the first result is verbatim and the proof of the second result with slight modifications applicable to range spaces instead of ranks of the operators concerned). However, we are confining our attention to the case of matrices. Let us also add that these results have been proved in [3] for operators over infinite dimensional spaces. We have chosen to include these results here as our proofs are different from the ones in [3] and that our intention is to provide a self-contained treatment.Theorem 5 (see [3, Theorem 2.1]).
LetA∈ℝm×n, X∈ℝm×k, and Y∈ℝn×k be such that
(3)R(X)⊆R(A),R(Y)⊆R(AT).
Let G∈ℝk×k, and Ω=A-XGYT. If
(4)R(XT)⊆R((G†-YTA†X)T),R(YT)⊆R(G†-YTA†X),R(XT)⊆R(G),R(YT)⊆R(GT)
then
(5)Ω†=A†+A†X(G†-YTA†X)†YTA†.Proof.
SetZ=A†+A†XH†YTA†, where H=G†-YTA†X. From the conditions (3) and (4), it follows that AA†X=X, A†AY=Y, H†HXT=XT, HH†YT=YT, GG†XT=XT, and G†GYT=YT.
Now,(6)A†XH†YT-A†XH†YTA†XGYT=A†XH†(G†GYT-YTA†XGYT)=A†XH†HGYT=A†XGYT.
Thus, ZΩ=A†A. Since R(ΩT)⊆R(AT), it follows that ZΩ(x)=x, ∀x∈R(ΩT).
Lety∈N(ΩT). Then, ATy-YGTXTy=0 so that XTA†T(AT-YGTXT)y=0. Substituting XT=GG†XT and simplifying it, we get HTGTXTy=0. Also, ATy=YGTXTy=YHH†GTXTy=0 and so A†y=0. Thus, Zy=0 for y∈N(ΩT). Hence, by Theorem 2, Z=Ω†.The result for the group inverse follows.Theorem 6.
LetA∈ℝn×n be such that A# exists. Let X, Y∈ℝn×k and G be nonsingular. Assume that R(X)⊆R(A), R(Y)⊆R(AT) and G-1-YTA#X is nonsingular. Suppose that rank(A-XGYT)=rank(A). Then, (A-XGYT)# exists and the following formula holds:
(7)(A-XGYT)#=A#+A#X(G-1-YTA#X)-1YTA#.
Conversely, if (A-XGYT)# exists, then the formula above holds, and we have rank(A-XGYT)=rank(A).Proof.
SinceA# exists, R(A) and N(A) are complementary subspaces of ℝn×n.
Suppose thatrank(A-XGYT)=rank(A). As R(X)⊆R(A), it follows that R(A-XGYT)⊆R(A). Thus R(A-XGYT)=R(A). By the rank-nullity theorem, the nullity of both A-XGYT and A are the same. Again, since R(Y)⊆R(AT), it follows that N(A-XGYT)=N(A). Thus, R(A-XGYT) and N(A-XGYT) are complementary subspaces. This guarantees the existence of the group inverse of A-XGYT.
Conversely, suppose that(A-XGYT)# exists. It can be verified by direct computation that Z=A#+A#X(G-1-YTA#X)-1YTA# is the group inverse of A-XGYT. Also, we have (A-XGYT)(A-XGYT)#=AA#, so that R(A-XGYT)=R(A), and hence the rank(A-XGYT)=rank(A).We conclude this section with a fairly old result [2] as a consequence of Theorem 5.Theorem 7 (see [2, Theorem 15]).
LetA∈ℝm×n of rankr, X∈ℝm×r and  Y∈ℝn×r. Let G be an r×r nonsingular matrix. Assume that R(X)⊆R(A),  R(Y)⊆R(AT), and G-1-YTA†X is nonsingular. Let Ω=A-XGYT. Then
(8)(A-XGYT)†=A†+A†X(G-1-YTA†X)-1YTA†.


## 4. Nonnegativity of(A-XGYT)†

In this section, we consider perturbations of the formA-XGYT and derive characterizations for (A-XGYT)† to be nonnegative when A†≥0,  X≥0,  Y≥0 and G≥0. In order to motivate the first main result of this paper, let us recall the following well known characterization of M-matrices [5].Theorem 8.
LetA be a Z-matrix with the representation A=sI-B, where B≥0 and s≥0. Then the following statements are equivalent:(a)
A-1 exists and A-1≥0.(b)
There existsx>0 such that Ax>0.(c)
ρ(B)<s.Let us prove the first result of this article. This extends Theorem8 to singular matrices. We will be interested in extensions of conditions (a) and (c) only.Theorem 9.
LetA=U-V be a proper splitting of A∈ℝm×n with U†≥0, U†V≥0 and ρ(U†V)<1. Let G∈ℝk×k be nonsingular and nonnegative, X∈ℝm×k, and Y∈ℝn×k be nonnegative such that R(X)⊆R(A), R(Y)⊆R(AT) and G-1-YTA†X is nonsingular. Let Ω=A-XGYT. Then, the following are equivalent(a)
Ω†≥0.(b)
(G-1-YTA†X)-1≥0.(c)
ρ(U†W)<1 where W=V+XGYT.Proof.
First, we observe that sinceR(X)⊆R(A), R(Y)⊆R(AT), and G-1-YTA†X is nonsingular, by Theorem 7, we have
(9)Ω†=A†+A†X(G-1-YTA†X)-1YTA†.
We thus have ΩΩ†=AA† and Ω†Ω=A†A. Therefore,
(10)R(Ω)=R(A),N(Ω)=N(A).
Note that the first statement also implies that A†≥0, by Theorem 4.
(
a
)
⇒
(
b
): By taking E=A and F=XGYT, we get Ω=E-F as a proper splitting for Ω such that E†=A†≥0 and E†F=A†XGYT≥0 (since XGYT≥0). Since Ω†≥0, by Theorem 4, we have ρ(A†XGYT)=ρ(E†F)<1. This implies that ρ(YTA†XG)<1. We also have YTA†XG≥0. Thus, by Lemma 1, (I-YTA†XG)-1 exists and is nonnegative. But, we have I-YTA†XG=(G-1-YTA†X)G. Now, 0≤(I-YTA†XG)-1=G-1(G-1-YTA†X)-1. This implies that (G-1-YTA†X)-1≥0 since G≥0. This proves (b).
(
b
)
⇒
(
c
): We have U-W=U-V-XGYT=A-XYT=Ω. Also R(Ω)=R(A)=R(U) and N(Ω)=N(A)=N(U). So, Ω=U-W is a proper splitting. Also U†≥0 and U†W=U†(V+XGYT)≥U†V≥0. Since (G-1-YTA†X)-1≥0, it follows from (9) that Ω†≥0. (c) now follows from Theorem 4.
(
c
)
⇒
(
a
): Since A=U-V, we have Ω=U-V-XGYT=U-W. Also we have U†≥0, U†V≥0. Thus, U†W≥0, since XGYT≥0. Now, by Theorem 4, we are done if the splitting Ω=U-W is a proper splitting. Since A=U-V is a proper splitting, we have R(U)=R(A) and N(U)=N(A). Now, from the conditions in (10), we get that R(U)=R(Ω) and N(U)=N(Ω). Hence Ω=U-W is a proper splitting, and this completes the proof.The following result is a special case of Theorem9.Theorem 10.
LetA=U-V be a proper splitting of A∈ℝm×n with U†≥0,  U†V≥0 and ρ(U†V)<1. Let X∈ℝm×k and Y∈ℝn×k be nonnegative such that R(X)⊆R(A), R(Y)⊆R(AT), and I-YTA†X is nonsingular. Let Ω=A-XYT. Then the following are equivalent: (a)
Ω†≥0.(b)
(I-YTA†X)-1≥0.(c)
ρ(U†W)<1, where W=V+XYT.The following consequence of Theorem10 appears to be new. This gives two characterizations for a perturbed M-matrix to be an M-matrix.Corollary 11.
LetA=sI-B where, B≥0 and ρ(B)<s (i.e., A is an M-matrix). Let X∈ℝm×k and Y∈ℝn×k be nonnegative such that I-YTA†X is nonsingular. Let Ω=A-XYT. Then the following are equivalent: (a)
Ω-1≥0.(b)
(I-YTA†X)-1≥0.(c)
ρ(B(I+XYT))<s.Proof.
From the proof of Theorem10, since A is nonsingular, it follows that ΩΩ†=I and Ω†Ω=I. This shows that Ω is invertible. The rest of the proof is omitted, as it is an easy consequence of the previous result.In the rest of this section, we discuss two applications of Theorem10. First, we characterize the least element in a polyhedral set defined by a perturbed matrix. Next, we consider the following Suppose that the “endpoints” of an interval matrix satisfy a certain positivity property. Then all matrices of a particular subset of the interval also satisfy that positivity condition. The problem now is if that we are given a specific structured perturbation of these endpoints, what conditions guarantee that the positivity property for the corresponding subset remains valid.The first result is motivated by Theorem12 below. Let us recall that with respect to the usual order, an element x*∈𝒳⊆ℝn is called a least element of 𝒳 if it satisfies x*≤x for all x∈𝒳. Note that a nonempty set may not have the least element, and if it exists, then it is unique. In this connection, the following result is known.Theorem 12 (see [11, Theorem 3.2]).
ForA∈ℝm×n and b∈ℝm, let
(11)𝒳b={x∈ℝn:Ax+y≥b,PN(A)x=0,PR(A)y=0,forsomey∈ℝm}.
Then, a vector x* is the least element of 𝒳b if and only if x*=A†b∈𝒳b with A†≥0.Now, we obtain the nonnegative least element of a polyhedral set defined by a perturbed matrix. This is an immediate application of Theorem10.Theorem 13.
LetA∈ℝm×n be such that A†≥0. Let X∈ℝm×k, and let Y∈ℝn×k be nonnegative, such that R(X)⊆R(A), R(Y)⊆R(AT), and I-YTA†X is nonsingular. Suppose that (I-YTA†X)-1≥0. For b∈ℝm, b≥0, let
(12)𝒮b={x∈ℝn:Ωx+y≥b,PN(Ω)x=0,PR(Ω)y=0,forsomey∈ℝm},
where Ω=A-XYT. Then, x*=(A-XYT)†b is the least element of 𝒮b.Proof.
From the assumptions, using Theorem10, it follows that Ω†≥0. The conclusion now follows from Theorem 12.To state and prove the result for interval matrices, let us first recall the notion of interval matrices. ForA, B∈ℝm×n, an interval (matrix) J=[A,B] is defined as J=[A,B]={C:A≤C≤B}. The interval J=[A,B] is said to be range-kernel regular if R(A)=R(B) and N(A)=N(B). The following result [12] provides necessary and sufficient conditions for C†≥0 for C∈K, where K={C∈J:R(C)=R(A)=R(B),N(C)=N(A)=N(B)}.Theorem 14.
LetJ=[A,B] be range-kernel regular. Then, the following are equivalent: (a)
C†≥0 whenever C∈K,(b)
A†≥0 and B†≥0.
In such a case, we haveC†=∑j=0∞‍(B†(B-C))jB†.Now, we present a result for the perturbation.Theorem 15.
LetJ=[A,B] be range-kernel regular with A†≥0 and B†≥0. Let X1, X2, Y1, and Y2 be nonnegative matrices such that R(X1)⊆R(A), R(Y1)⊆R(AT), R(X2)⊆R(B), and R(Y2)⊆R(BT). Suppose that I-Y1TA†X1 and I-Y2TA†X2 are nonsingular with nonnegative inverses. Suppose further that X2Y2T≤X1Y1T. Let J~=[E,F], where E=A-X1Y1T and F=B-X2Y2T. Finally, let K~={Z∈J~:R(Z)=R(E)=R(F)andN(Z)=N(E)=N(F)}. Then, (a)
E†≥0 and F†≥0.(b)
Z†≥0 whenever Z∈K~.
In that case,Z†=∑j=0∞‍(B†B-F†Z)jF†.Proof.
It follows from Theorem7 that
(13)E†=A†+A†X1(I-Y1TA†X1)-1Y1TA†,F†=B†+B†X2(I-Y2TB†X2)-1Y2TB†.
Also, we have EE†=AA†, E†E=A†A, F†F=B†B, and FF†=BB†. Hence, R(E)=R(A), N(E)=N(A), R(F)=R(B), and N(F)=N(B). This implies that the interval J~ is range-kernel regular. Now, since E and F satisfy the conditions of Theorem 10, we have E†≥0 and F†≥0 proving (a). Hence, by Theorem 14, Z†≥0 whenever Z∈K~. Again, by Theorem 14, we have Z†=∑j=0∞‍(F†(F-Z))jF†=∑j=0∞‍(B†B-F†Z)jF†.


## 5. Iterations That Preserve Nonnegativity of the Moore-Penrose Inverse

In this section, we present results that typically provide conditions for iteratively defined matrices to have nonnegative Moore-Penrose inverses given that the matrices that we start with have this property. We start with the following result about the rank-one perturbation case, which is a direct consequence of Theorem10.Theorem 16.
LetA∈ℝn×n be such that A†≥0. Let x∈ℝm and y∈ℝn be nonnegative vectors such that x∈R(A), y∈R(AT), and 1-yTA†x≠0. Then (A-xyT)†≥0 if and only if yTA†x<1.Example 17.
Let us considerA=(1/3)(1-11-14-11-11). It can be verified that A can be written in the form A=(I2e1T)(I2+e1e1T)-1C-1(I2+e1e1T)-1(I2e1) where e1=(1,0)T and C is the 2×2 circulant matrix generated by the row (1,1/2). We have A†=(1/2)(212121212)≥0. Also, the decomposition A=U-V, where U=(1/3)(1-12-14-21-12), and V=(1/3)(00102-1001) is a proper splitting of A with U†≥0,  U†V≥0, and ρ(U†V)<1.
Letx=y=(1/3,1/6,1/3)T. Then, x and let y are nonnegative, x∈R(A) and y∈R(AT). We have 1-yTA†x=5/12>0 and ρ(U†W)<1 for W=V+xyT. Also, it can be seen that (A-xyT)†=(1/20)(472847283228472847)≥0. This illustrates Theorem 10.Letx1,x2,…,xk∈ℝm and y1,y2,…,yk∈ℝn be nonnegative. Denote Xi=(x1,x2,…,xi) and Yi=(y1,y2,…,yi) for i=1,2,…,k. Then A-XkYkT=A-∑i=1k‍xiyiT. The following theorem is obtained by a recurring application of the rank-one result of Theorem 16.Theorem 18.
LetA∈ℝm×n and let Xi,Yi be as above. Further, suppose that xi∈R(A-Xi-1Yi-1T), yi∈R(A-Xi-1Yi-1T)T and 1-yiT(A-Xi-1Yi-1T)†xi be nonzero. Let (A-Xi-1Yi-1T)†≥0, for all i=1,2,…,k. Then (A-XkYkT)†≥0 if and only if yiT(A-Xi-1Yi-1T)†xi<1, where A-X0Y0T is taken as A.Proof.
SetBi=A-XiYiT for i=0,1,…,k, where B0 is identified as A. The conditions in the theorem can be written as:
(14)xi∈R(Bi-1),yi∈R(Bi-1T),1-yiTBi-1†xi≠0,∀i=1,2…,k.
Also, we have Bi†≥0, for all i=0,1,…,k-1.
Now, assume thatBk†≥0. Then by Theorem 16 and the conditions in (14) for i=k, we have ykBk-1†xk<1. Also since by assumption Bi†≥0 for all i=0,1…,k-1, we have yiTBi-1†xi<1 for all i=1,2…,k.
The converse part can be proved iteratively. Then conditiony1TB0†x1<1 and the conditions in (14) for i=1 imply that B1†≥0. Repeating the argument for i=2 to k proves the result.The following result is an extension of Lemma 2.3 in [1], which is in turn obtained as a corollary. This corollary will be used in proving another characterization for (A-XkYkT)†≥0.Theorem 19.
LetA∈ℝn×n, b,c∈ℝn be such that -b≥0, -c≥0 and α(∈ℝ)>0. Further, suppose that b∈R(A) and c∈R(AT). Let A^=(AbcTα)∈ℝ(n+1)×(n+1). Then, A^†≥0 if and only if A†≥0 and cTA†b<α.Proof.
Let us first observe thatAA†b=b and cTA†A=cT. Set
(15)X=(A†+A†bcTA†α-cTA†b-A†bα-cTA†b-cTA†α-cTA†b1α-cTA†b).
It then follows that A^X=(AA†00T1) and XA^=(A†A00T1). Using these two equations, it can easily be shown that X=A^†.
Suppose thatA†≥0 and β=α-cTA†b>0. Then, A^†≥0. Conversely suppose that A^†≥0. Then, we must have β>0. Let {e1,e2,…,en+1} denote the standard basis of ℝn+1. Then, for i=1,2,…,n, we have 0≤A^†(ei)=(A†ei+(A†bcTA†ei/β), -(cTA†ei/β))T. Since c≤0, it follows that A†ei≥0 for i=1,2,…,n. Thus, A†≥0.Corollary 20 (see [1, Lemma  2.3]).
LetA∈ℝn×n be nonsingular. Let b,c∈ℝn be such that -b≥0, -c≥0 and α(∈ℝ)>0. Let A^=(AbcTα). Then, A^-1∈ℝ(n+1)×(n+1) is nonsingular with A^-1≥0 if and only if A-1≥0 and cTA-1b<α.Now, we obtain another necessary and sufficient condition for(A-XkYkT)† to be nonnegative.Theorem 21.
LetA∈ℝm×n be such that A†≥0. Let xi,yi be nonnegative vectors in ℝn and ℝm respectively, for every i=1,…,k, such that
(16)xi∈R(A-Xi-1Yi-1T),yi∈R(A-Xi-1Yi-1T)T,
where Xi=(x1,…,xi), Yi=(y1,…,yi) and A-X0Y0T is taken as A. If Hi=Ii-YiTA†Xi is nonsingular and 1-yiTA†xi is positive for all i=1,2,…,k, then (A-XkYkT)†≥0 if and only if
(17)yiTA†xi<1-yiTA†Xi-1Hi-1-1Yi-1TA†xi,∀i=1,…,k.Proof.
The range conditions in (16) imply that R(Xk)⊆R(A) and R(Yk)⊆R(AT). Also, from the assumptions, it follows that Hk is nonsingular. By Theorem 10, (A-XkYkT)†≥0 if and only if Hk-1≥0. Now,
(18)Hk=(Hk-1-Yk-1TA†xk-ykTA†Xk-11-ykTA†xk).
Since 1-ykTA†xk>0, using Corollary 20, it follows that Hk-1≥0 if and only if ykTA†Xk-1Hk-1-1Yk-1TA†xk<1-ykTA†xk and Hk-1-1≥0.
Now, applying the above argument to the matrixHk-1, we have that Hk-1-1≥0 holds if and only if Hk-2-1≥0 holds and yk-1TA†Xk-2(Ik-2-Yk-2TA†Xk-2)-1Yk-2TA†xk-1<1-yk-1TA†xk-1. Continuing the above argument, we get, (A-XkykT)†≥0 if and only if yiTA†Xi-1Hi-1-1Yi-1TA†xi<1-yiTA†xi, ∀i=1,…,k. This is condition (17).We conclude the paper by considering an extension of Example17.Example 22.
For a fixedn, let C be the circulant matrix generated by the row vector (1,(1/2),(1/3),…(1/(n-1))). Consider
(19)A=(Ie1T)(I+e1e1T)-1C-1(I+e1e1T)-1(Ie1),
where I is the identity matrix of order n-1,  e1 is (n-1)×1 vector with 1 as the first entry and 0 elsewhere. Then, A∈ℝn×n. A† is the n×n nonnegative Toeplitz matrix
(20)A†=(11n-11n-2…1211211n-1…1312⋮⋮⋮⋮⋮⋮1n-11n-21n-3…11n-111n-11n-2…121).
Letxi be the first row of Bi-1† written as a column vector multiplied by 1/ni and let yi be the first column of Bi-1† multiplied by 1/ni, where Bi=A-XiYiT, with B0 being identified with A, i=0,2,…,k. We then have xi≥0, yi≥0, x1∈R(A) and y1∈R(AT). Now, if Bi-1†≥0 for each iteration, then the vectors xi and yi will be nonnegative. Hence, it is enough to check that 1-yiTBi-1†xi>0 in order to get Bi†≥0. Experimentally, it has been observed that for n>3, the condition 1-yiTBi-1†xi>0 holds true for any iteration. However, for n=3, it is observed that B1†≥0,  B2†≥0,  1-y1TA†x1>0, and 1-y2†B1†x2>0. But, 1-y3TB2†x3<0, and in that case, we observe that B3† is not nonnegative.



---

*Source: 680975-2013-05-20.xml*