����������� ������ 54 (2002), 139–144

UDK 517.984.3

���������� ������ ��� research paper

DISPLACEMENT STRUCTURE OF GENERALIZED INVERSE A_{T ,S}^{(1,2)}

Mei Qin and Yimin Wei

Abstract. It is well known that matrices with a UV -displacement structure possess generalized inverse with a V U-displacement structure. Estimation for the displacement rank of A_{T,S}^{(1,2)}U − V A_{T,S}^{(1,2)} are presented, where A_{T,S}^{(1,2)} is the (1, 2)-inverse of A with prescribed range T and null space S. We extend the results due to G. Heinig and F. Hellinger, Wei and Ng, Cai and Wei for the Moore-Penorse inverse, group inverse and weighted Moore-Penrose inverse, respectively.

1. Introduction and Preliminaries

The aim of the present paper is to study the generalized inverse of a structured matrix. To begin with, we recall some facts concerning the regular inversion of structured matrices, which are motivated by [5, 6]. If the rank of a matrix’s displacement is small, fast algorithms for the matrix are available.

A matrix is called matrix with displacement structure [2, 3, 8] if and only if the rank of the matrix AU − V A or A − V AU is small compared with the order of the matrix A. The rank of AU − V A is said to be Sylvester UV -displacement rank and the rank of A − V AU is called the Stein UV -displacement rank of A, since A is the solution of a Sylvester or Stein equation, respectively.

As is well known, fast inversion algorithms for matrix A can be constructed if A is a matrix with displacement structure. We are interested in the generalized inverse with as small as possible displacement rank. We present the estimate for the rank of A_{T,S}^{(1,2)}U −V A_{T,S}^{(1,2)}, where A_{T,S}^{(1,2)} is the (1, 2)-inverse of A, in Section 2. Then we give an explicit estimate for general displacement, which is defined in the paper, Section 3. Our results cover the previous results [2, 4, 14] for the Moore-Penrose inverse, weighted Moore-Penrose, inverse and group inverse, respectively.

AMS Subject Classification: 15 A 09,65 F 20

Keywords and phrases: Displacement, (1, 2)-inverse, structured matrix.

Communicated at the 5th International Symposium on Mathematical Analysis and its Applications, Niška banja, Yugoslavia, October, 2–6, 2002.

This project is supported by National Natural Science Foundation of China under grant 19901006 and 10171021 and Doctoral Point Foundation of China.

A matrix X is said to be a (1, 2)-inverse of A if the following condition is fulfilled:

XAX = X, AXA = A.

Let A ∈ C_{r}^{m×n}, T and S are subspaces of C^{n} and C^{m}, respectively, the dimensions of T and S are r and m − r, then A has a unique (1, 2)-inverse X satisfying R(X) = T, N(X) = S if and only if R(A) ⨁ S = C^{m}, Ker(A) ⨁ T = C^{n}. We denote X by A_{T,S}^{(1,2)}.

If G ∈ C^{n×m}, and G satisfies R(G) = T, N(G) = S, then we get [9]

A_{T,S}^{(1,2)} = (GA)_{g}G = G(AG)_{g}, AA_{T,S}^{(1,2)} = AG(AG)_{g}, A_{T,S}^{(1,2)}A = (GA)_{g}GA,

where (AG)_{g} and (GA)_{g} are group inverses of AG and GA.

From Jordan canonical form theory, we get that for any complex m×n matrix A with rank(A) = r with prescribed range T and null space S, there exist nonsingular matrices R and N [13] such that

A = R^{−1} [ \begin{matrix}A_{11} & 0 \\ 0 & 0 \end{matrix} ] N, G = N^{−1} [ \begin{matrix}G_{11} & 0 \\ 0 & 0 \end{matrix} ] R  (1)

where R is an m × m nonsingular matrix and N is n × n. Note that A_{11}, G_{11} are nonsingular matrices. Now we can write A_{T,S}^{(1,2)} of A in the form [13],

A_{T,S}^{(1,2)} = N^{−1} [ \begin{matrix}A_{11}^{−1} & 0 \\ 0 & 0 \end{matrix} ] R  (2)

Let

Q = A_{T,S}^{(1,2)}A, P = I − Q, Q_{∗} = AA_{T,S}^{(1,2)}, P_{∗} = I − Q_{∗}.  (3)

Obviously, Q and P are oblique projections, where Im(A) denotes the range of A and Ker(A) is the null space of A. It is easy to check that

\begin{aligned}Im(Q) & = Im(A_{T,S}^{(1,2)}) = Ker(P) = Im(G), & Im(Q_{∗}) & = Ker(P_{∗}) = Im(A), \\ Im(P_{∗}) & = Ker(A_{T,S}^{(1,2)}) = Ker(Q_{∗}) = Ker(G), & Im(P) & = Ker(Q) = Ker(A). \end{aligned}

(4)

For recent results on the generalized inverse A_{T,S}^{(1,2)}, we refer to [10, 11, 12, 15].

2. Sylvester displacement rank

Throughout the paper, U ∈ C^{n×n} and V ∈ C^{m×m} are some fixed matrices. The operator

d(U, V) = AU − V A

is called the UV-displacement of A. To distinguish this displacement concept from the more general case in Section 3 we call it the Sylvester UV-displacement, since A is the solution of a certain Sylvester equation. We can easily find that for a nonsingular matrix A with UV-displacement structure the inverse matrix A^{−1} possesses a VU-displacement structure, and the relation

rank(A^{−1}V − UA^{−1}) = rank(AU − V A)

holds.

We want to get an estimate for the VU-displacement rank of the generalized inverse of a matrix with displacement structure. First we show that the displacement structure of A_{T,S}^{(1,2)} is the following representation.

Proposition 2.1. Let A ∈ C^{m×n}, U ∈ C^{n×n} and V ∈ C^{m×m}, and A_{T,S}^{(1,2)} is the (1, 2)-inverse of A. Then

A_{T,S}^{(1,2)}V − UA_{T,S}^{(1,2)} = A_{T,S}^{(1,2)}V P_{∗} − P UA_{T,S}^{(1,2)} − A_{T,S}^{(1,2)}(AU − V A)A_{T,S}^{(1,2)}, (5)

where Q, P, Q_{∗} and P_{∗} are defined in (4).

Proof. The relation is immediately proved by the following equation

A_{T,S}^{(1,2)}(AU − V A)A_{T,S}^{(1,2)} = (I − P)UA_{T,S}^{(1,2)} − A_{T,S}^{(1,2)}V (I − P_{∗}).  (6)

From (4) we obtain the following Corollary.

Corollary 2.1. The VU-displacement rank of A_{T,S}^{(1,2)} satisfies the following estimate:

rank(A_{T,S}^{(1,2)}V − UA_{T,S}^{(1,2)}) ≤ rank(AU − V A) + rank(Q_{∗}V P_{∗}) + rank(P UQ). (7)

Proof. We will prove dim(P UA_{T,S}^{(1,2)}) = rank(P UQ), and rank(A_{T,S}^{(1,2)}V P) = rank(QV P).

rank(P UA_{T,S}^{(1,2)} = dim[P UIm(A_{T,S}^{(1,2)})] = dim[Im(P UQ)] = rank(P UQ), (8)

the second equality can be proved similarly.

Taking these into account, we obtain the above estimate. Now we aim to obtain the estimate for the second and third terms on the

right-hand side.

Proposition 2.2. With the notation above, we get the estimate

rank(Q_{∗}V P_{∗}) + rank(P UQ) ≤ rank(UG − GV).  (9)

Proof. We set F = UG − GV and make partitions

NUN^{−1} = [ \begin{matrix}U_{11} & U_{12} \\ U_{21} & U_{22} \end{matrix} ] , RV R^{−1} = [ \begin{matrix}V_{11} & V_{12} \\ V_{21} & V_{22} \end{matrix} ] .  (10)

From (1) we write the matrix F in the following form

NF R^{−1} = NUN^{−1}NGR^{−1} − NGR^{−1}RV R^{−1}

= [ \begin{matrix}U_{11} & U_{12} \\ U_{21} & U_{22} \end{matrix} ] [ \begin{matrix}G_{11} & 0 \\ 0 & 0 \end{matrix} ] − [ \begin{matrix}G_{11} & 0 \\ 0 & 0 \end{matrix} ] [ \begin{matrix}V_{11} & V_{12} \\ V_{21} & V_{22} \end{matrix} ]

= [ \begin{matrix}U_{11}G_{11} − G_{11}V_{11} & −G_{11}V_{12} \\ U_{21}G_{11} & 0 \end{matrix} ] .

From [7] we know that

rank [ \begin{matrix}U_{11}G_{11} − G_{11}V_{11} & −G_{11}V_{12} \\ U_{21}G_{11} & 0 \end{matrix} ] ≥ rank(−G_{11}V_{12}) + rank(U_{21}G_{11})

= rank(V_{12}) + rank(U_{21}) = rank [ \begin{matrix}0 & V_{12} \\ 0 & 0 \end{matrix} ] + rank [ \begin{matrix}0 & 0 \\ U_{21} & 0 \end{matrix} ]

= rank(Q_{∗}V P_{∗}) + rank(P UQ).

where G_{11} is nonsingular. Then the proof is over.

From Propositions 2.1 and 2.2 we derive the first main result.

Theorem 2.1. Let A ∈ C^{m×n} and A_{T,S}^{(1,2)} be its (1, 2)-inverse. Then

rank(A_{T,S}^{(1,2)}V − UA_{T,S}^{(1,2)}) ≤ rank(AU − V A) + rank(UG − GV).

Proposition 2.3. If AU = UG, V A = GV, then we get the estimate:

rank(A_{T,S}^{(1,2)}V − UA_{T,S}^{(1,2)}) ≤ 2 rank(AU − V A).  (11)

3. Displacement structure for generalized displacement

In order to generalize Theorem 2.1 we introduce a generalized displacement concept [2]. Let a = [a_{ij}]_{0}^{1} denote a nonsingular 2 × 2 matrix. We associate a with the polynomial in two variables

a(λ, μ) = ∑_{i,j=0}^{1} a_{ij}λ^{i}μ^{j}

and the linear fractional function

f_{a}(λ) = \frac{a_{10} + a_{11}λ}{a_{00} + a_{01}λ}.  (12)

For any fixed U ∈ C^{n×n} and V ∈ C^{m×m}, the generalized (a, U, V) displacement of A ∈ C^{m×n} generated by a(λ, μ) is defined by

a(V, U)A = ∑_{i,j=0}^{1} a_{ij}V^{i}AU^{j}.

If a = d ≡ [ \begin{matrix}0 & 1 \\ −1 & 0 \end{matrix} ], we just get Sylvester displacement that we have discussed. If

a = d ≡ [ \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} ], we get Stein displacement.

Lemma 3.1. [2] Let a = [a_{ij}]_{0}^{1}, b = [b_{ij}]_{0}^{1}, c = [c_{ij}]_{0}^{1}, d = [d_{ij}]_{0}^{1} be nonsingular 2 × 2 matrices such that

a = b^{T} dc.  (13)

Then

(b_{00} + b_{01}λ)^{−1}a(λ, μ)(c_{00} + c_{01}μ)^{−1} = d(f_{b}(λ), f_{c}(μ))  (14)

for all λ, μ with b_{00} + b_{01}λ ≠ 0 and c_{00} + c_{01}μ ≠ 0.

Lemma 3.2. [2] If d = [ \begin{matrix}0 & 1 \\ −1 & 0 \end{matrix} ], then there exist 2 × 2 matrices b, c such that (13) holds and b_{00} + b_{01}V and c_{00} + c_{01}U are invertible.

Taking Lemma 3.1 and Lemma 3.2 together, we obtain the following

Proposition 3.1. [2] If b and c be matrices satisfying the conditions in Lemma 3.2, then for A ∈ C^{m×n},

a(V, U)A = (b_{00} + b_{01}V)[Af_{c}(U) − f_{b}(V)A](c_{00} + c_{01}U).

The following is very important to generalize Theorem 2.1 for general (a, U, V) displacement.

Proposition 3.2. (a) If ψ = [ψ_{ij}]_{0}^{1} is nonsingular and ψ_{00}+ψ_{01}V is invertible, then rank(Q_{∗}V P_{∗}) = rank(Q_{∗}Ṽ P_{∗}), where Ṽ ≡ f_{ψ}(V) is defined in (12).

(b) If ϕ = [ϕ_{ij}]_{0}^{1} is nonsingular and ϕ_{00} + ϕ_{01}U is invertible, then

rank(P UQ) = rank(P ŨQ),

where Ũ ≡ f_{ϕ}(U) is defined in (12).

Proof. We define

S = Ker(G) ∩ Ker(GV), S_{1} = Ker(G) ⊖ CalS.

We show that Q_{∗}V P_{∗} is one-to-one on S_{1}. If Q_{∗}V P_{∗}x = 0 and x ∈ S_{1}, then V P_{∗}x ∈ Ker(Q_{∗}) = Ker(G). That means GV P_{∗}x = GV x = 0. Noting that x ∈ Ker(G), we conclude x ∈ S. Thus x = 0.

Furthermore, Q_{∗}V P_{∗} vanishes on S. Since Q_{∗}V P_{∗}x = Q_{∗}V x = (AG)_{g}AGV x = 0 for all x ∈ S we have

rank(Q_{∗}V P_{∗}) = dim(S_{1}).  (15)

Analogously we define S̃ = Ker(G) ∩ Ker(GṼ), S̃_{1} = Ker(G) ⊖ S̃, and we get

rank(Q_{∗}Ṽ P_{∗}) = dim(S̃_{1}).  (16)

Now we show that the invertible matrix \overline{ψ}_{00} + \overline{ψ}_{01}V bijectively maps S onto S̃. Suppose that x ∈ S. Then x, V x ∈ Ker(G). Hence y ≡ (\overline{ψ}_{10} + \overline{ψ}_{11}V)x and z ≡ (\overline{ψ}_{00} + \overline{ψ}_{01}V)x are all contained in Ker(G). Thus y = Ṽ z and we conclude that z, Ṽ z ∈ Ker(G), which implies z ∈ S̃. Convesely, with the same arguments we get (\overline{ψ}_{00} + \overline{ψ}_{01}V)^{−1}z ∈ S for z ∈ S̃.

This implies

dim(S_{1}) = dim[Ker(G)] − dim(S) = dim[Ker(G)] − dim(S̃) = dim(S̃_{1}). According to (15) and (16), we get assertion (a).

Assertion (b) is proved analogously.

Now we can generalize Theorem 2.1 for general (a, U, V) displacement.

Theorem 3.1. If a, b are 2 × 2 nonsingular matrices, then

rank[a(U, V)A_{T,S}^{(1,2)})] ≤ rank[a^{T} (V, U)A] + rank[b(U, V)G].  (17)

Proof. According to Lemma 3.2 there exist 2 × 2 matrices w, x, y, z such that w_{00} + w_{01}U, x_{00} + x_{01}V, y_{00} + y_{01}U, z_{00} + z_{01}V are invertible and a = w^{T} dz, b = x^{T} dy. Hence,

rank[a(U, V)A_{T,S}^{(1,2)}] − rank[a^{T} (V, U)A]

= rank[f_{w}(U)A_{T,S}^{(1,2)} − A_{T,S}^{(1,2)}f_{z}(V)] − rank[f_{z}(V)A − Af_{w}(U)]

≤ rank[P f_{w}(U)Q] + rank[Q_{∗}f_{z}(V)P_{∗}] = rank[P f_{y}(U)Q] + rank[Q_{∗}f_{x}(V)P_{∗}] ≤ rank[f_{y}(U)G − Gf_{x}(V)] = rank[b(U, V)G].

4. Concluding remarks

In this paper we study the displacement structure of (1, 2)-inverse of a singular matrix. It is natural to ask if we can extend our results to linear operators in Hilbert space. This will be the future research.

REFERENCES

[1] A. Ben-Israel and T.N.E. Greville, Generalized Inverses: Theory and Applications, Wiley, New York, 1974.

[2] G. Heinig and F. Hellinger, Displacement structure of pseudoinverses, Linear Algebra Appl., 197/198 (1994), 623–649.

[3] G. Heinig and F. Hellinger, Displacement structure of generalized inverse matrices, Linear Algebra Appl., 211 (1994), 67–83.

[4] Jianfeng Cai and Yimin Wei, Displacement structure of weighted pseudoinverses, submitted.

[5] T. Kailath, S.Y. Kung and M. Morf, Displacement rank of matrices and linear equations, J. Math. Anal. Appl., 68 (1979), 395–407.

[6] T. Kailath and A. Sayed, Displacement structure: Theory and applications, SIAM Review, 37 (1995), 297–386.

[7] G. Marsaglia and G.P.H. Styan, Equalities and inequalities for ranks of matrices, Linear and Multilinear Algebra, 2 (1974), 269–292.

[8] V.Y. Pan, Structured Natrices and Polynomials: Unified Superfast Algorithms, Birkhäuser/ Springer, 2001.

[9] Yimin Wei, A characterization and representation of the generalized inverse A_{T,S}^{(2)}, Linear Algebra Appl., 258 (1998), 79–86.

[10] Yimin Wei and Hebing Wu, On the perturbation and subproper splittings for generalized inverse A_{T,S}^{(2)} of rectangular matrix A, J. Comput. Appl. Math., 137 (2001), 317–329.

[11] Yimin Wei and Hebing Wu, (T − S) splitting methods for computing the generalized inverse A_{T,S}^{(2)} and rectangular systems, Int. J. Computer Math., 77 (2001), 401–424.

[12] Yimin Wei and Hebing Wu, The representation and approximation for the generalized inverse A_{T,S}^{(2)}, Appl. Math. Comput., 135 (2003) 263–276.

[13] Yimin Wei and D.S. Djordjevic, On integral representation of the generalized inverse A_{T,S}^{(2)}, Appl. Math. Comput., to appear.

[14] Yimin Wei and Michael Ng, Displacement structure of group inverses, submitted.

[15] Yimin Wei and Naimin Zhang, Condition number related with generalized inverse A_{T,S}^{(2)} and constrained linear system, J. Comput. Appl. Math., revised version.

(received 12.12.2002)

Mei Qin, Institute of Mathematics, Fudan University, Shanghai, 200433, P.R.of China Yimin Wei, Department of Mathematics, Fudan University, Shanghai, 200433, P.R.of China E-mail: ymwei@fudan.edu.cn