Gröbner Bases for the Pseudo-Inverse and Application to Polynomial Reduction

J. William Helton, Jeff Ovall, Anthony Shaheen September 10, 2001

Contents

1 Definition of the Pseudo-Inverse 2 2 Motivation 2 3 Notation 3 4 A Finite Gröbner Basis for the Ideal Generated by Ψ(A) 3 5 A Finite Gröbner Basis for the

Ideal Generated by Ψ(A) ⋃ Ψ(B) ⋃ Ψ(A + B) 5 6 An Infinite Gröbner Basis for the

Ideal Generated by Ψ(A) ⋃ Ψ(B) ⋃ Ψ(AB)

(Four Recursion Laws) 6 7 Appendix A 8 8 Appendix A+B 10 9 Appendix AB 12

1 Definition of the Pseudo-Inverse

It is well known that, for any real or complex mxn matrix A, there exists a unique matrix X satisfiying the four Moore-Penrose conditions below:

MP1) AXA = A MP2) XAX = X MP3) (AX)^{T} = AX MP4) (XA)^{T} = XA

The superscript ^{T} should be interpreted as either the regular transpose of a real matrix, or as the hermitian adjoint of a complex matrix. The unique matrix X is called the pseudo-inverse of A and is denoted by A^{†}.

Although we have defined the pseudo-inverse in the context of matrices, we shall consider the pseudo-inverse in a purely algebraic setting, so that what will be said applies to, for example, operators on a Hilbert Space. We would still take the Moore-Penrose conditions as the defining properties, but we would have to interpret ^{T} as an abstract involution. In other words, ^{T} would merely be required to satisfy (A^{T})^{T} = A and (AB)^{T} = B^{T} A^{T} for arbitrary elements A and B in that setting. The results below will hold in an abstract algebraic setting in which each element has a (unique) pseudoinverse.

2 Motivation

The goal of this work is the reduction (to some canonical form) of polynomial expressions involving pseudo-inverses. To that end we employ Gröbner bases for ideals generated by certain polynomials related to the Moore-Penrose conditions. The most obvious choice to begin with is to find a Gröbner basis for the ideal generated by:

{AA^{†}A − A, A^{†}AA^{†} − A^{†}, A^{T} (A^{†})^{T} − A^{†}A, (A^{†})^{T} A^{T} − AA^{†}}

We use the graded lexographical ordering induced by the “alphabetical” order:

A < A^{T} < A^{†} < (A^{†})^{T}

The Gröbner basis for the ideal under this ordering (we do not argue this here) is:

{A^{†}A − A^{T} (A^{†})^{T} , (A^{†})^{T} A^{T} − AA^{†}, AA^{T} (A^{†})^{T} − A, A^{T} (A^{†})^{T} A^{†} − A^{†}, AA^{†}(A^{†})^{T} A^{†} − (A^{†})^{T} A^{†}, AA^{T} AA^{†} − AA^{T} , A^{T} AA^{†}(A^{†})^{T} − A^{T} (A^{†})^{T} }

Note that the first four of these polynomials are equivalent to those we started with, only differing according to the imposed order. The last three, however, are new. It will be shown later that AA^{†}(A^{†})^{T} = (A^{†})^{T} and A^{T} AA^{†} = A^{T}. Had these relations been added to our starting relations, the last three (fourth degree) polynomials in the above Gröbner basis would be replaced by the two (third degree) polynomials AA^{†}(A^{†})^{T} − (A^{†})^{T} and A^{T} AA^{†} − A^{T}. It is also true that (A^{†})^{T} = (A^{T})^{†}, and a choice was made to include the polynomial (A^{†})^{T} − (A^{T})^{†} with those for whose associated ideal we wish to find a Gröbner basis. We modified the “alphabetical” ordering so that “(A^{†})^{T} ” would always be replaced by “(A^{T})^{†}” - purely for aesthetic reasons. This will be explored more fully in what follows, and it does serve to motivate some notation which will be used throughout this paper.

3 Notation

Let Ψ(X) := {XX^{†}X −X, X^{†}XX^{†}−X^{†}, X^{T} (X^{†})^{T} −X^{†}X, (X^{†})^{T} X^{T} −XX^{†},

(X^{†})^{T} − (X^{T})^{†}, X^{T} XX^{†} − X^{T} , XX^{†}(X^{T})^{†} − (X^{T})^{†}}.

The Gröbner Basis for the ideal generated by the set S under the order induced by O will be denoted by G_{O}(S).

4 A Finite Gröbner Basis for the Ideal Generated by Ψ(A)

Below is a list of thirteen properties of the pseudo-inverse. Proofs for some of them are in Appendix A.

Property 4.1 (A^{†})^{T} = (A^{T})^{†}

Property 4.2 AA^{T} (A^{T})^{†} = A { MP1 }

Property 4.3 A^{T} AA^{†} = A^{T}

Property 4.4 A^{T} (A^{T})^{†}A^{†} = A^{†} { MP2 } Property 4.5 AA^{†}(A^{T})^{†} = (A^{T})^{†} Property 4.6 (A^{T})^{†}A^{T} = AA^{†} { MP3 } Property 4.7 A^{†}A = A^{T} (A^{T})^{†} { MP4 } Theorem 4.1 If Properties 4.1 through 4.7 are considered as polynomials of the form LHS − RHS (they are written above in the form LHS = RHS), then they form a (non-commutative) Gröbner Basis for the ideal generated by Ψ(A), under the graded lexographical order O_{A} induced by the “alphabetical” order:

{A < A^{T} < A^{†} < (A^{T})^{†} < (A^{†})^{T} }

As noted in section 3 this Gröbner Basis will be denoted by G_{O_{A}}(Ψ(A)).

The properties below, although not included in the Gröbner basis, are nonetheless usefull in reducing certain expressions involving the pseudoinverse to canonical form. Property 4.8 (A^{†})^{†} = A Property 4.9 0^{†} = 0, and for scalars k ≠ 0, (kA)^{†} = \frac{1}{k}A^{†} Property 4.10 (A^{T} A)^{†} = A^{†}(A^{T})^{†} Property 4.11 (AA^{T})^{†} = (A^{T})^{†}A^{†} Property 4.12 (A^{T} (A^{T})^{†})^{†} = A^{T} (A^{T})^{†} {(A^{†}A)^{†} = A^{†}A} Property 4.13 (AA^{†})^{†} = AA^{†}

5 A Finite Gröbner Basis for the

Ideal Generated by Ψ(A) ⋃ Ψ(B) ⋃ Ψ(A + B)

Below, we list several properties involving (A + B)^{†}. Proofs for some of them are in Appendix A + B. Property 5.1 B^{†}A(A + B)^{†}(A^{T} + B^{T})^{†} + B^{T} (B^{T})^{†}(A + B)^{†}(A^{T} + B^{T})^{†} = B^{†}(A^{T} + B^{T})^{†}

Property 5.2 (B^{T})^{†}A^{T} (A^{T} + B^{T})^{†}(A + B)^{†} + BB^{†})(A^{T} + B^{T})^{†}(A + B)^{†} = (B^{T})^{†}(A + B)^{†} Property 5.3

B^{T} (B^{T})^{†}A^{T} (A^{T} + B^{T})^{†} + B^{†}AA^{T} (A^{T} + B^{T})^{†} + B^{†}AB^{T} (A^{T} + B^{T})^{†} =
B^{†}A + B^{T} (B^{T})^{†} − B^{T} (A^{T} + B^{T})^{†}

Property 5.4

BB^{†}A(A + B)^{†} + (B^{T})^{†}A^{T} A(A + B)^{†} + (B^{T})^{†}A^{T} B(A + B)^{†} =
(B^{T})^{†}A^{T} + BB^{†} − B(A + B)^{†}

Property 5.5

A^{T} (A^{T} + B^{T})^{†}B^{†}(B^{T})^{†} + B^{T} (A^{T} + B^{T})^{†}B^{†}(B^{T})^{†} =
(A + B)^{†}AB^{†}(B^{T})^{†} + (A + B)^{†}(B^{T})^{†}

Property 5.6

A(A + B)^{†}(B^{T})^{†}B^{†} + B(A + B)^{†}(B^{T})^{†}B^{†} =
(A^{T} + B^{T})^{†}A^{T} (B^{T})^{†}B^{†} + (A^{T} + B^{T})^{†}B^{†}

Property 5.7

(A + B)^{†}AB^{T} (B^{T})^{†} + A^{T} (A^{T} + B^{T})^{†}A^{T} (B^{T})^{†} + B^{T} (A^{T} + B^{T})^{†}A^{T} (B^{T})^{†} =

(A + B)^{†}A + A^{T} (B^{T})^{†} + B^{T} (B^{T})^{†} − A^{T} (A^{T} + B^{T})^{†} − B^{T} (A^{T} + B^{T})^{†} Property 5.8

(A^{T} + B^{T})^{†}A^{T} BB^{†} + A(A + B)^{†}AB^{†} + B(A + B)^{†}AB^{†} =
(A^{T} + B^{T})^{†}A^{T} + AB^{†} + BB^{†} − A(A + B)^{†} − B(A + B)^{†}

Theorem 5.1 If Properties 5.1 through 5.8 are considered as polynomials of the form LHS − RHS (they are written above in the form LHS = RHS), then they along with G_{O_{A}}(Ψ(A)) ∪ G_{O_{B}}(Ψ(B)) ∪ Ψ(A + B) form a (noncommutative) Gröbner Basis for the ideal generated by Ω_{1} = Ψ(A) ∪ Ψ(B) ∪ Ψ(A + B) under the graded lexographical order induced by the “alphabetical” order:

O = {A < B < A^{T} < B^{T} < A^{†} < B^{†} < (A^{T})^{†} < (B^{T})^{†} <

(A^{†})^{T} < (B^{†})^{T} < (A + B)^{†} < (A^{T} + B^{T})^{†} < ((A + B)^{†})^{T} }

This Gröbner Basis will be denoted by G_{O_{A+B}}(Ω_{1}).

6 An Infinite Gröbner Basis for the Ideal Generated by Ψ(A) ⋃ Ψ(B) ⋃ Ψ(AB) (Four Recursion Laws)

Below, we list several properties involving (AB)^{†}. Proofs for some of them will be in Appendix AB.

Property 6.1 (AB)^{†}AA^{†} = (AB)^{†}

Property 6.2 AA^{†}(B^{T} A^{T})^{†} = (B^{T} A^{T})^{†}

Property 6.3 B^{T} (B^{T})^{†}(AB)^{†} = (AB)^{†}

Property 6.4 (B^{T} A^{T})^{†}B^{T} (B^{T})^{†} = (B^{T} A^{T})^{†} Property 6.5 AB(AB)^{†}A(B^{T})^{†} = A(B^{T})^{†} Property 6.6 B^{†}A^{T} AB(AB)^{†} = B^{†}A^{T} Property 6.7 (A^{T})^{†}B(AB)^{†}A(B^{T})^{†} = (A^{T})^{†}(B^{T})^{†} Property 6.8 B^{†}A^{T} (B^{T} A^{T})^{†}B^{T} A^{†} = B^{†}A^{†} Property 6.9 (A^{T})^{†}BB^{T} A^{T} (B^{T} A^{T})^{†} = (A^{T})^{†}B Property 6.10 B^{T} A^{T} (B^{T} A^{T})^{†}B^{T} A^{†} = B^{T} A^{†} Property 6.11 B^{†}A^{T} (B^{T} A^{T})^{†}(AB)^{†} = B^{†}(B^{T})^{†}(AB)^{†} Property 6.12 (B^{T} A^{T})^{†}(AB)^{†}A(B^{T})^{†} = (B^{T} A^{T})^{†}B^{†}(B^{T})^{†} Property 6.13 (AB)^{†}(B^{T} A^{T})^{†}B^{T} A^{†} = (AB)^{†}(A^{T})^{†}A^{†} Property 6.14 (A^{T})^{†}B(AB)^{†}(B^{T} A^{T})^{†} = (A^{T})^{†}A^{†}(B^{T} A^{T})^{†} Property 6.15 B^{†}(B^{T})^{†}(AB)^{†}A(B^{T})^{†} = B^{†}A^{T} (B^{T} A^{T})^{†}B^{†}(B^{T})^{†} Property 6.16 (A^{T})^{†}A^{†}(B^{T} A^{T})^{†}B^{T} A^{†} = (A^{T})^{†}B(AB)^{†}(A^{T})^{†}A^{†}

Infinite properties: Property 6.17 BB^{†}{A^{T} (B^{T} A^{T})^{†}B^{†}}^{K}(B^{T})^{†} = (B^{T})^{†}{(AB)^{†}A(B^{T})^{†}}^{K}

K = 1, 2, 3, . . .. Property 6.18 A^{T} {(A^{T})^{†}B(AB)^{†}}^{K}(A^{T})^{†}A^{†} = A^{†}{B^{T} A^{T}^{†}B^{T} A^{†}}^{K}

K = 1, 2, 3, . . .. Property 6.19 A{B(AB)^{†}(A^{T})^{†}}^{K}A^{†} = (B^{T} A^{T})^{†}{B^{T} A^{†}(B^{T} A^{T})^{†}}^{K−1}B^{T} A^{†}

K = 1, 2, 3, . . .. Property 6.20 B^{T} {A^{T} (B^{T} A^{T})^{†}B^{†}}^{K}(B^{T})^{†} = (AB)^{†}{A(B^{T})^{†}(AB)^{†}}^{K−1}A(B^{T})^{†}

K = 1, 2, 3, . . ..

Theorem 6.1 If Properties 6.1 through 6.20 are considered as polynomials of the form LHS − RHS (they are written above in the form LHS = RHS), then they along with G_{O_{A}}(Ψ(A)) ∪ G_{O_{B}}(Ψ(B)) ∪ Ψ(AB) form a (noncommutative) Gröbner Basis for the ideal generated by Ω_{2} = Ψ(A) ∪ Ψ(B) ∪ Ψ(AB) under the graded lexographical order induced by the “alphabetical” order:

O = {A < B < A^{T} < B^{T} < A^{†} < B^{†} < (A^{T})^{†} < (B^{T})^{†} <

(A^{†})^{T} < (B^{†})^{T} < (AB)^{†} < (B^{T} A^{T})^{†} < ((AB)^{†})^{T} }

This Gröbner Basis will be denoted by G_{O_{AB}}(Ω_{2}).

7 Appendix A

Below are proofs of some of the propositions given above. Those for which proofs are not given either direct consequences of the Moore-Penrose conditions themselves, or can easily be deduced by substituting A^{T} for A in those that are proven below.

Proof of Property 4.1 The Moore-Penrose conditions for A^{T} are:

A^{T} XA^{T} = A^{T}
XA^{T} X = X
(A^{T} X)^{T} = A^{T} X
(XA^{T})^{T} = XA^{T}

We have, again by definition, that X = (A^{T})^{†}. So showing that (A^{†})^{T} also satisfies these relations is enough to prove the claim. Well, since AA^{†}A = A and A^{†}AA^{†} = A^{†}, we have (by taking ^{T}) that A^{T} (A^{†})^{T} A^{T} = A^{T} and (A^{†})^{T} A^{T} (A^{†})^{T} = (A^{†})^{T}. So (A^{†})^{T} satifies the first two conditions. We also have (A^{T} (A^{†})^{T})^{T} = A^{†}A = (A^{†}A)^{T} = A^{T} (A^{†})^{T} and ((A^{†})^{T} A^{T})^{T} = AA^{†} = (AA^{†})^{T} = (A^{†})^{T} A^{T}. Therefore, (A^{T})^{†} = (A^{†})^{T} . □

Proof of Property 4.8 The Moore-Penrose conditions for A^{†} are:

A^{†}XA^{†} = A^{†}
XA^{†}X = X
(A^{†}X)^{T} = A^{†}X
(XA^{†})^{T} = XA^{†}

By definition, we denote the unique element X by (A^{†})^{†}. But it is also clear from the definition of A^{†} that A also satisfies these properties. Therefore, (A^{†})^{†} = A. □

Proof of Property 4.10 We argue that A^{†}(A^{T})^{†} satisfies the Moore-Penrose conditions for A^{T} A.

(A^{T} A)(A^{†}(A^{T})^{†})(A^{T} A) = (A^{T} AA^{†})(A^{T})^{†}(A^{T} A)
= A^{T} (A^{T})^{†}A^{T} A
= A^{T} A.

(A^{†}(A^{T})^{†})(A^{T} A)(A^{†}(A^{T})^{†}) = A^{†}((A^{T})^{†}A^{T})(AA^{†}(A^{T})^{†})
= A^{†}AA^{†}(A^{T})^{†}
= A^{†}(A^{T})^{†}.

((A^{T} A)(A^{†}(A^{T})^{†}))^{T} = ((A^{T} AA^{†})(A^{T})^{†})^{T}
= (A^{T} (A^{†})^{T})^{T}
= A^{†}A
= (A^{†}A)^{T}
= A^{T} (A^{T})^{†}
= (A^{T} A)(A^{†}(A^{T})^{†}).

MP4 is verified in the same fashion as MP3. Therefore, (A^{T} A)^{†} = A^{†}(A^{T})^{†}. □

Proof of Property 4.13 We argue that AA^{†} satisfies the Moore-Penrose conditions for itself.

(AA^{†})(AA^{†})(AA^{†}) = (AA^{†}A)(A^{†}AA^{†})
= AA^{†}.

This shows that AA^{†} satisfies the first two conditions.

((AA^{†})(AA^{†}))^{T} = (AA^{†})^{T}
= AA^{†}
= (AA^{†})(AA^{†}).

This shows that AA^{†} satisfies the second two conditions. Therefore, (AA^{†})^{†} = AA^{†}. □

8 Appendix A+B

Before getting to the proofs of Properties 5.1 - 5.8, we list those associated with Ψ(A + B): (They are Properties 4.1 - 4.7 with A + B substituted in for A) Property 8.1 ((A + B)^{†})^{T} = (A^{T} + B^{T})^{†} Property 8.2 AA^{T} (A^{T} + B^{T})^{†} + AB^{T} (A^{T} + B^{T})^{†} +

BA^{T} (A^{T} + B^{T})^{†} + BB^{T} (A^{T} + B^{T})^{†} = A + B

Property 8.3 A^{T} A(A + B)^{†} + A^{T} A(A + B)^{†} +

A^{T} A(A + B)^{†} + A^{T} A(A + B)^{†} = A^{T} + B^{T}

Property 8.4 A^{T} (A^{T} + B^{T})^{†}(A + B)^{†} + B^{T} (A^{T} + B^{T})^{†}(A + B)^{†} = (A + B)^{†} Property 8.5 A(A + B)^{†}(A^{T} + B^{T})^{†} + B(A + B)^{†}(A^{T} + B^{T})^{†} = (A^{T} + B^{T})^{†} Property 8.6 (A^{T} + B^{T})^{†}A^{T} + (A^{T} + B^{T})^{†}B^{T} + = A(A + B)^{†} + B(A + B)^{†} Property 8.7 (A + B)^{†}A + (A + B)^{†}B = A^{T} (A^{T} + B^{T})^{†} + B^{T} (A^{T} + B^{T})^{†}

Since Properties 5.2, 5.4, 5.6 and 5.8 can be gotten (respectively) from Properties 5.1, 5.3, 5.5, and 5.7 by substituting A^{T} for A and B^{T} for B, we only prove the odd numbered ones.

Properties 5.1 and 5.3 are easily deduced by expanding the identities B^{†}(A+B)(A+B)^{†}(A^{T} +B^{T})^{†} = B^{†}(A^{T} +B^{T})^{†} and B^{†}(A+B)(A+B)^{T} (A^{T} + B^{T})^{†} = B^{†}(A+B) respectively, and collecting terms on the appropriate sides of the “=” sign.

Proof of Property 5.5

A^{T} (A^{T} + B^{T})^{†}B^{†}(B^{T})^{†} + B^{T} (A^{T} + B^{T})^{†}B^{†}(B^{T})^{†} =
(A + B)^{T} (A^{T} + B^{T})^{†}B^{†}(B^{T})^{†} =
(A + B)^{†}(A + B)B^{†}(B^{T})^{†} =
(A + B)^{†}(AB^{†}(B^{T})^{†} + BB^{†}(B^{T})^{†}) =
(A + B)^{†}(AB^{†}(B^{T})^{†} + (B^{T})^{†}) =
(A + B)^{†}AB^{†}(B^{T})^{†} + (A + B)^{†}(B^{T})^{†}.

Property 5.5 may also be written as (A + B)^{†}(A + B)B^{†}(B^{T})^{†} = (A + B)^{†}(I + AB^{†})(B^{T})^{†}. □

Proof of Property 5.7

A^{T} (A^{T} + B^{T})^{†}A^{T} (B^{T})^{†} + B^{T} (A^{T} + B^{T})^{†}A^{T} (B^{T})^{†} +

(A + B)^{†}AB^{T} (B^{T})^{†} + A^{T} (A^{T} + B^{T})^{†} + B^{T} (A^{T} + B^{T})^{†} =
(A + B)^{†}AB^{T} (B^{T})^{†} + (A + B)^{T} (A^{T} + B^{T})^{†}A^{T} (B^{T})^{†} + (A + B)^{T} (A^{T} + B^{T})^{†} =
(A + B)^{†}AB^{T} (B^{T})^{†} + (A + B)^{†}(A + B)A^{T} (B^{T})^{†} + (A + B)^{†}(A + B) =
(A + B)^{†}{AB^{T} (B^{T})^{†} + AA^{T} (B^{T})^{†} + BA^{T} (B^{T})^{†} + B} + (A + B)^{†}A =
(A + B)^{†}{AB^{T} (B^{T})^{†} + AA^{T} (B^{T})^{†} + BA^{T} (B^{T})^{†} + BB^{T} (B^{T})^{†}} + (A + B)^{†}A =
(A + B)^{†}{AB^{T} + AA^{T} + BA^{T} + BB^{T} }(B^{T})^{†} + (A + B)^{†}A =
(A + B)^{†}(A + B)(A + B)^{T} (B^{T})^{†} + (A + B)^{†}A =
(A + B)^{T} (B^{T})^{†} + (A + B)^{†}A =
A^{T} (B^{T})^{†} + B^{T} (B^{T})^{†} + (A + B)^{†}A.

Property 5.7 may also be written as (A + B)^{†}{A + (A + B)(A + B)^{T} (B^{T})^{†}} = (A + B)^{†}A + (A + B)^{T} (B^{T})^{†}. □

9 Appendix AB

Before getting to the proofs of Properties 6.1 - 6.20, we list those associated with Ψ(AB): (They are Properties 4.1 - 4.7 with AB substituted in for A) Property 9.1 ((AB)^{†})^{T} = (B^{T} A^{T})^{†} Property 9.2 ABB^{T} A^{T} (B^{T} A^{T})^{†} = AB Property 9.3 B^{T} A^{T} AB(AB)^{†} = B^{T} A^{T} Property 9.4 B^{T} A^{T} (B^{T} A^{T})^{†}(AB)^{†} = (AB)^{†} Property 9.5 AB(AB)^{†}(B^{T} A^{T})^{†} = (B^{T} A^{T})^{†} Property 9.6 (B^{T} A^{T})^{†}B^{T} A^{T} = AB(AB)^{†} Property 9.7 (AB)^{†}AB = B^{T} A^{T} (B^{T} A^{T})^{†} Properties 6.2, 6.4, ..., 6.14 are just the transposes of Properties 6.1, 6.3, ..., 6.13 respectively, so proofs will only be given for the odd numbered ones. Proof of Property 6.1 We argue that (AB)^{†}AA^{†} satisfies the Moore-Penrose conditions for AB.

AB{(AB)^{†}AA^{†}}AB = AB(AB)^{†}{AA^{†}A}B

= AB(AB)^{†}AB = AB.

{(AB)^{†}AA^{†}}AB{(AB)^{†}AA^{†}} = (AB)^{†}{AA^{†}A}B(AB)^{†}AA^{†}

= (AB)^{†}AB(AB)^{†}AA^{†} = (AB)^{†}AA^{†}.

(AB{(AB)^{†}AA^{†}})^{T} = ({AB(AB)^{†}}AA^{†})^{T}

= (AA^{†})^{T} (AB(AB)^{†})^{T} = AA^{†}AB(AB)^{†} = AB(AB)^{†} = ((AB)^{T})^{†}(AB)^{T} = ((AB)^{T})^{†}B^{T} A^{T} = ((AB)^{T})^{†}B^{T} A^{T} AA^{†} = AB{(AB)^{†}AA^{†}}.

({(AB)^{†}AA^{†}}AB)^{T} = ((AB)^{†}{AA^{†}A}B)^{T}

= ((AB)^{†}AB)^{T} = (AB)^{†}AB = {(AB)^{†}AA^{†}}AB.

The uniquness of (AB)^{†} then tells us that (AB)^{†}AA^{†} = (AB)^{†}. □ Property 6.3 can be gotten from Property 6.2 by substituting B^{T} for A (and hence B for A^{T}). Proof of Property 6.5

AB(AB)^{†}A(B^{T})^{†} = AB(AB)^{†}ABB^{†}(B^{T})^{†}

= ABB^{†}(B^{T})^{†} = A(B^{T})^{†}.

Therefore, AB(AB)^{†}A(B^{T})^{†} = A(B^{T})^{†}. □ Proof of Property 6.7

We begin by noting the identity (A^{T})^{†} = (A^{T})^{†}A^{†}A. It can be clearly seen by substituting A^{†} for A in Property 4.3, and this identity will be used again in the proof of Properties 6.9 and 6.19.

(A^{T})^{†}B(AB)^{†}A(B^{T})^{†} = (A^{T})^{†}A^{†}AB(AB)^{†}ABB^{†}(B^{T})^{†}
= (A^{T})^{†}A^{†}ABB^{†}(B^{T})^{†}
= (A^{T})^{†}(B^{T})^{†}.

Therefore, (A^{T})^{†}B(AB)^{†}A(B^{T})^{†} = (A^{T})^{†}(B^{T})^{†}. □ Proof of Property 6.9

(A^{T})^{†}BB^{T} A^{T} (B^{T} A^{T})^{†} = (A^{T})^{†}B(AB)^{†}AB
= (A^{T})^{†}A^{†}AB(AB)^{†}AB
= (A^{T})^{†}A^{†}AB
= (A^{T})^{†}B.

Therefore, (A^{T})^{†}BB^{T} A^{T} (B^{T} A^{T})^{†} = (A^{T})^{†}B. □ Proof of Property 6.11

We begin by noting that B^{†} = B^{†}(B^{T})^{†}B^{T}. This identity will also be used in the proof of property 15.

B^{†}A^{T} (B^{T} A^{T})^{†}(AB)^{†} = B^{†}(B^{T})^{†}B^{T} A^{T} (B^{T} A^{T})^{†}(AB)^{†}
= B^{†}(B^{T})^{†}(AB)^{†}.

Therefore, B^{†}A^{T} (B^{T} A^{T})^{†}(AB)^{†} = B^{†}(B^{T})^{†}(AB)^{†} □. Property 6.13 can be gotten from Property 6.12 by substituting A for B^{T}, and hence A^{T} for B etc. Proof of Property 6.15

B^{†}(B^{T})^{†}(AB)^{†}A(B^{T})^{†} = B^{†}(B^{T})^{†}B^{T} A^{T} (B^{T} A^{T})^{†}(AB)^{†}A(B^{T})^{†}
= B^{†}A^{T} (B^{T} A^{T})^{†}(AB)^{†}A(B^{T})^{†}
= B^{†}A^{T} (B^{T} A^{T})^{†}(AB)^{†}ABB^{†}(B^{T})^{†}
= B^{†}A^{T} (B^{T} A^{T})^{†}B^{†}(B^{T})^{†}.

Therefore, B^{†}(B^{T})^{†}(AB)^{†}A(B^{T})^{†} = B^{†}A^{T} (B^{T} A^{T})^{†}B^{†}(B^{T})^{†}. Note that this says that either of these expressions is its own transpose. □

Property 6.16 can be gotten from 6.15 by substituting A^{T} for B etc.

In the proofs of the recursion laws below, instead of doing induction in any formal sense, we will just show the identies for K = 1, 2. The induction should be obvious from there. It should be noted that, for Properties 6.17 and 6.18, the case K = 0 also holds, but is just a restatement of Properties 4.5 and 4.4 respectively.

Proof of Property 6.17

K=1.

BB^{†}A^{T} (B^{T} A^{T})^{†}B^{†}(B^{T})^{†} = (B^{T})^{†}B^{T} A^{T} (B^{T} A^{T})^{†}B^{†}(B^{T})^{†}
= (B^{T})^{†}(AB)^{†}ABB^{†}(B^{T})^{†}
= (B^{T})^{†}(AB)^{†}A(B^{T})^{†}.

K=2.

BB^{†}A^{T} (B^{T} A^{T})^{†}B^{†}A^{T} (B^{T} A^{T})^{†}B^{†}(B^{T})^{†} = BB^{†}A^{T} (B^{T} A^{T})^{†}B^{†}BB^{†}A^{T} (B^{T} A^{T})^{†}B^{†}(B^{T})^{†}
= BB^{†}A^{T} (B^{T} A^{T})^{†}B^{†}{BB^{†}A^{T} (B^{T} A^{T})^{†}B^{†}(B^{T})^{†}}
= BB^{†}A^{T} (B^{T} A^{T})^{†}B^{†}{(B^{T})^{†}(AB)^{†}A(B^{T})^{†}}
= BB^{†}A^{T} (B^{T} A^{T})^{†}B^{†}(B^{T})^{†}{(AB)^{†}A(B^{T})^{†}}
= (B^{T})^{†}{(AB)^{†}A(B^{T})^{†}}^{2}.

Therefore, BB^{†}{A^{T} (B^{T} A^{T})^{†}B^{†}}^{K}(B^{T})^{†} = (B^{T})^{†}{(AB)^{†}A(B^{T})^{†}}^{K} K = 1, 2, 3, …. □

Proof of Property 6.18

K=1.

A^{T} (A^{T})^{†}B(AB)^{†}(A^{T})^{†}A^{†} = A^{†}AB(AB)^{†}(A^{T})^{†}A^{†}

= A^{†}(B^{T} A^{T})^{†}B^{T} A^{T} (A^{T})^{†}A^{†}

= A^{†}(B^{T} A^{T})^{†}B^{T} A^{†}.

K=2.

A^{T} (A^{T})^{†}B(AB)^{†}(A^{T})^{†}B(AB)^{†}(A^{T})^{†}A^{†} = A^{T} (A^{T})^{†}B(AB)^{†}(A^{T})^{†}A^{T} (A^{T})^{†}B(AB)^{†}(A^{T})^{†}A^{†}
= A^{T} (A^{T})^{†}B(AB)^{†}(A^{T})^{†}{A^{†}(B^{T} A^{T})^{†}B^{T} A^{†}}
= A^{T} (A^{T})^{†}B(AB)^{†}(A^{T})^{†}A^{†}{(B^{T} A^{T})^{†}B^{T} A^{†}}
= A^{†}{(B^{T} A^{T})^{†}B^{T} A^{†}}^{2}.

Therefore, A^{T} {(A^{T})^{†}B(AB)^{†}}^{K}(A^{T})^{†}A^{†} = A^{†}{B^{T} A^{T}^{†}B^{T} A^{†}}^{K} K = 1, 2, 3, …. □

Proof of Property 6.19

K=1.

AB(AB)^{†}(A^{T})^{†}A^{†} = (B^{T} A^{T})^{†}B^{T} A^{T} (A^{T})^{†}A^{†}
= (B^{T} A^{T})^{†}B^{T} A^{†}.

K=2.

AB(AB)^{†}(A^{T})^{†}B(AB)^{†}(A^{T})^{†}A^{†} = AB(AB)^{†}(A^{T})^{†}A^{†}AB(AB)^{†}(A^{T})^{†}A^{†}
= (B^{T} A^{T})^{†}B^{T} A^{†}(B^{T} A^{T})^{†}B^{T} A^{†}
= (B^{T} A^{T})^{†}{B^{T} A^{†}(B^{T} A^{T})^{†}}^{2−1}B^{T} A^{†}.

Therefore, A{B(AB)^{†}(A^{T})^{†}}^{K}A^{†} = (B^{T} A^{T})^{†}{B^{T} A^{†}(B^{T} A^{T})^{†}}^{K−1}B^{T} A^{†} K = 1, 2, 3, …. □

Property 6.20 can be gotten from Property 6.19 by substituting B^{T} for A etc.