\documentclass[12pt]{article}
\usepackage{amstex}
\title{Gr\"obner Bases for the Pseudo-Inverse and Application to Polynomial 
       Reduction} 
\author{J. William Helton, Jeff Ovall, Anthony Shaheen} 
\date{\today}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{property}{Property}[section]

\begin{document}

\maketitle

\tableofcontents

\newpage

\section{Definition of the Pseudo-Inverse}
\label{sec:defpinv}

\noindent
It is well known that, for any real or complex $m$x$n$ matrix $A$,
there exists a unique matrix $X$ satisfiying the four Moore-Penrose conditions
below: 


\vspace{3mm}
\noindent 
\textbf{MP1)} \quad $AXA=A$ \\ 
\textbf{MP2)} \quad $XAX=X$ \\ 
\textbf{MP3)} \quad $(AX)^{T}=AX$ \\ 
\textbf{MP4)} \quad $(XA)^{T}=XA$ \\


\noindent
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^{\dagger}$.


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) 
pseudo-inverse.

\section{Motivation}
\label{sec: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\"obner 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\"obner basis
for the ideal generated by:
$$ \{ AA^{\dagger}A-A, A^{\dagger}AA^{\dagger}-A^{\dagger}, 
      A^{T}(A^{\dagger})^{T}-A^{\dagger}A,
     (A^{\dagger})^{T}A^{ T }-AA^{\dagger} \} $$
We use the graded lexographical ordering induced by the ``alphabetical" order:
               $$A<A^{T}<A^{\dagger}<(A^{\dagger})^{T}$$ 
The Gr\"obner basis for the ideal under this ordering (we do not argue 
this here) is: \\

\vspace{3mm}

\noindent
$ \{ A^{\dagger}A-A^{T}(A^{\dagger})^{T}, (A^{\dagger})^{T}A^{T}-AA^{\dagger}, 
     AA^{T}(A^{\dagger})^{T}-A,A^{T}(A^{\dagger})^{T}A^{\dagger}-A^{\dagger},\\
     AA^{\dagger}(A^{\dagger})^{T}A^{\dagger}-(A^{\dagger})^{T}A^{\dagger},
     AA^{T}AA^{\dagger}-AA^{T}, 
     A^{T}AA^{\dagger}(A^{\dagger})^{T}-A^{T}(A^{\dagger})^{T} \} $ \\
     
\vspace{3mm}      
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^{\dagger}(A^{\dagger})^{T}=(A^{\dagger})^{T}$ and $A^{T}AA^{\dagger}=A^{T}$.
Had these relations been added to our starting relations, the last three 
(fourth degree) polynomials in the above Gr\"obner basis would be replaced by
the two (third degree) polynomials 
$AA^{\dagger}(A^{\dagger})^{T}-(A^{\dagger})^{T}$ and                           
$A^{T}AA^{\dagger}-A^{T}$.  It is also true that 
$(A^{\dagger})^{T}=(A^{T})^{\dagger}$, and a choice was made to include the
polynomial $(A^{\dagger})^{T}-(A^{T})^{\dagger}$ with those for whose associated
ideal we wish to find a Gr\"obner basis.  We modified the ``alphabetical" 
ordering so that ``$(A^{\dagger})^{T}$" would always be replaced by 
``$(A^{T})^{\dagger}$" - 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.

\section{Notation}
\label{sec:notation}

\noindent
Let $\Psi(X) := \{ XX^{\dagger}X-X, X^{\dagger}XX^{\dagger} - X^{\dagger},
    X^{T}(X^{\dagger})^{T}-X^{\dagger}X,
    (X^{\dagger})^{T}X^{T}-XX^{\dagger}, \\
    \hspace*{26mm} (X^{\dagger})^{T}-(X^{T})^{\dagger},X^{T}XX^{\dagger}-X^{T},
    XX^{\dagger}(X^{T})^{\dagger}-(X^{T})^{\dagger} \} $.

The Gr\"obner Basis for the ideal generated by the set $\mathcal{S}$
under the order induced by $\mathcal{O}$ will be denoted by 
$\mathcal{G}_{\mathcal{O}}(S)$.  


\section{A Finite Gr\"obner Basis for the Ideal Generated by $\Psi(A)$}
\label{sec:gbfora}

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


\begin{property}
$(A^{\dagger})^{T}=(A^{T})^{\dagger}$
\label{a1}
\end{property}

\begin{property}
$AA^{T}(A^{T})^{\dagger}=A$  \quad \{ MP1 \}  
\label{a2}
\end{property}

\begin{property}
$A^{T}AA^{\dagger}=A^{T}$
\label{a3}
\end{property}

\begin{property}
$A^{T}(A^{T})^{\dagger}A^{\dagger}=A^{\dagger}$  \quad \{ MP2 \}
\label{a4}
\end{property}

\begin{property}
$AA^{\dagger}(A^{T})^{\dagger}=(A^{T})^{\dagger}$
\label{a5}
\end{property}

\begin{property}
$(A^{T})^{\dagger}A^{T}=AA^{\dagger}$  \quad \{ MP3 \}  
\label{a6}
\end{property}
 
\begin{property}
$A^{\dagger}A=A^{T}(A^{T})^{\dagger}$  \quad \{ MP4 \}
\label{a7}
\end{property}

\begin{theorem}
If Properties \ref{a1} through \ref{a7} 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\"obner Basis for the ideal generated by $\Psi(A)$, 
under the graded lexographical order $\mathcal{O}_{A}$ induced by the
``alphabetical'' order:  $$ \big \{A<A^{T}<A^{\dagger}<(A^{T})^{\dagger}<
                            (A^{\dagger})^{T} \big\}$$
As noted in section \ref{sec:notation} this Gr\"obner Basis will be
denoted by $\mathcal{G}_{\mathcal{O}_A}(\Psi(A))$.  

\end{theorem}

The properties below, although not included in the Gr\"obner basis,
are nonetheless usefull in reducing certain expressions involving the
pseudo-inverse to canonical form.

\begin{property}
$(A^{\dagger})^{\dagger} = A$
\end{property}

\begin{property}
$0^{\dagger}=0$, and for scalars $k \neq 0$, $(kA)^{\dagger}=\frac{1}{k} A^{\dagger}$
\end{property} 

\begin{property}
$(A^{T}A)^{\dagger}=A^{\dagger}(A^{T})^{\dagger}$
\end{property}

\begin{property}
$(AA^{T})^{\dagger}=(A^{T})^{\dagger}A^{\dagger}$
\end{property}

\begin{property}
$(A^{T}(A^{T})^{\dagger})^{\dagger}=A^{T}(A^{T})^{\dagger}
  \quad \{(A^{\dagger}A)^{\dagger}=A^{\dagger}A \}$
\end{property}

\begin{property}
$(AA^{\dagger})^{\dagger}=AA^{\dagger}$
\end{property}



\vspace{3mm}

\section{A Finite Gr\"obner Basis for the \\ Ideal Generated by 
         $\Psi(A) \bigcup \Psi(B) \bigcup \Psi(A+B)$}
\label{sec:gbforaplusb}

Below, we list several properties involving $(A+B)^{\dagger}$.  Proofs for some
of them are in Appendix $A+B$. 


\begin{property}
\begin{align*}
B^{\dagger}A(A+B)^{\dagger}(A^{T}+B^{T})^{\dagger}+B^{T}(B^{T})^{\dagger}(A+B)^{\dagger}(A^{T}+B^{T})^{\dagger} = 
                                                   B^{\dagger}(A^{T}+B^{T})^{\dagger}
\end{align*}
\label{aplusbpropfirst}
\end{property}

\begin{property}
\begin{align*}
(B^{T})^{\dagger}A^{T}(A^{T}+B^{T})^{\dagger}(A+B)^{\dagger}+BB^{\dagger})(A^{T}+B^{T})^{\dagger}(A+B)^{\dagger} = 
                                                    (B^{T})^{\dagger}(A+B)^{\dagger}
\end{align*}                                                    
\end{property}

\begin{property}
\begin{align*}
B^{T}(B^{T})^{\dagger}A^{T}(A^{T}+B^{T})^{\dagger}+B^{\dagger}AA^{T}(A^{T}+B^{T})^{\dagger} + 
                                     B^{\dagger}AB^{T}(A^{T}+B^{T})^{\dagger} &= \\ 
               B^{\dagger}A + B^{T}(B^{T})^{\dagger} - B^{T}(A^{T}+B^{T})^{\dagger}
\end{align*}
\end{property}

\begin{property}
\begin{align*}
BB^{\dagger}A(A+B)^{\dagger}+(B^{T})^{\dagger}A^{T}A(A+B)^{\dagger} +
                 (B^{T})^{\dagger}A^{T}B(A+B)^{\dagger} &= \\ 
     (B^{T})^{\dagger}A^{T} + BB^{\dagger} - B(A+B)^{\dagger}
\end{align*}     
\end{property}

\begin{property}
\begin{align*}
A^{T}(A^{T}+B^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger}+B^{T}(A^{T}+B^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger} &= \\  
                          (A+B)^{\dagger}AB^{\dagger}(B^{T})^{\dagger}+(A+B)^{\dagger}(B^{T})^{\dagger}
\end{align*}                          
\end{property}

\begin{property}
\begin{align*}
    A(A+B)^{\dagger}(B^{T})^{\dagger}B^{\dagger}+B(A+B)^{\dagger}(B^{T})^{\dagger}B^{\dagger} &= \\ 
(A^{T}+B^{T})^{\dagger}A^{T}(B^{T})^{\dagger}B^{\dagger}+(A^{T}+B^{T})^{\dagger}B^{\dagger}
\end{align*}
\end{property}

\begin{property}
\begin{align*}
(A+B)^{\dagger}AB^{T}(B^{T})^{\dagger}+A^{T}(A^{T}+B^{T})^{\dagger}A^{T}(B^{T})^{\dagger} + 
                           B^{T}(A^{T}+B^{T})^{\dagger}A^{T}(B^{T})^{\dagger} &= \\ 
                   (A+B)^{\dagger}A+A^{T}(B^{T})^{\dagger}+B^{T}(B^{T})^{\dagger} -
                      A^{T}(A^{T}+B^{T})^{\dagger}-B^{T}(A^{T}+B^{T})^{\dagger}
\end{align*}                      
\end{property}

\begin{property}
\begin{align*}
(A^{T}+B^{T})^{\dagger}A^{T}BB^{\dagger}+A(A+B)^{\dagger}AB^{\dagger}+ B(A+B)^{\dagger}AB^{\dagger} &= \\ 
     (A^{T}+B^{T})^{\dagger}A^{T}+AB^{\dagger}+BB^{\dagger}-A(A+B)^{\dagger}-B(A+B)^{\dagger}
\end{align*}
\label{aplusbproplast}
\end{property}

\begin{theorem}
If Properties \ref{aplusbpropfirst} through \ref{aplusbproplast} are considered as polynomials of the form
$LHS - RHS$ (they are written above in the form $LHS=RHS$), then they
along with
$\mathcal{G}_{\mathcal{O}_A}(\Psi(A))\cup\mathcal{G}_{\mathcal{O}_B}(\Psi(B))\cup\Psi(A+B)$
form a (non-commutative) Gr\"obner Basis for the ideal generated by
$\Omega_1 = \Psi(A)\cup\Psi(B)\cup\Psi(A+B)$ under the graded lexographical order induced by the
``alphabetical'' order: \\

\vspace{3mm}
  
$\mathcal{O} = \big\{A<B<A^{T}<B^{T}<A^{\dagger}<B^{\dagger}<(A^{T})^{\dagger}< 
                     (B^{T})^{\dagger}< \\   
\hspace*{17mm}       (A^{\dagger})^{T}<(B^{\dagger})^{T}<(A+B)^{\dagger}<
                     (A^{T}+B^{T})^{\dagger}<((A+B)^{\dagger})^{T}\big\}$ \\
                     
\vspace{3mm}
                     
This Gr\"obner Basis will be denoted by $\mathcal{G}_{\mathcal{O}_{A+B}}(\Omega_1)$.  

\end{theorem}

\vspace{3mm}

\section{An Infinite Gr\"obner Basis for the \\ Ideal Generated by 
         $\Psi(A) \bigcup \Psi(B) \bigcup \Psi(AB)$ \\ (Four Recursion Laws)}
\label{sec:gbforab}

\vspace{1mm}

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

\vspace{2mm}


\begin{property}
   $(AB)^{\dagger}A A^{\dagger} = (AB)^{\dagger}$
\label{abpropfirst} 
\end{property}


\begin{property}
   $AA^{\dagger}(B^{T}A^{T})^{\dagger} = (B^{T}A^{T})^{\dagger}$
\end{property}


\begin{property}
   $B^{T}(B^{T})^{\dagger}(AB)^{\dagger} = (AB)^{\dagger}$
\end{property}


\begin{property}
   $(B^{T}A^{T})^{\dagger}B^{T}(B^{T})^{\dagger} = (B^{T}A^{T})^{\dagger}$
\end{property}


\begin{property}
   $AB(AB)^{\dagger}A(B^{T})^{\dagger} = A(B^{T})^{\dagger}$
\end{property}


\begin{property}
   $B^{\dagger}A^{T}AB(AB)^{\dagger} = B^{\dagger}A^{T}$
\end{property}


\begin{property}
   $(A^{T})^{\dagger}B(AB)^{\dagger}A(B^{T})^{\dagger} = 
                            (A^{T})^{\dagger}(B^{T})^{\dagger}$
\end{property}



\begin{property} 
   $B^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}B^{T}A^{\dagger} = 
                            B^{\dagger}A^{\dagger}$
\end{property}


\begin{property}
   $(A^{T})^{\dagger}BB^{T}A^{T}(B^{T}A^{T})^{\dagger} = (A^{T})^{\dagger}B$
\end{property}


\begin{property}
   $B^{T}A^{T}(B^{T}A^{T})^{\dagger}B^{T}A^{\dagger} = B^{T}A^{\dagger}$
\end{property}


\begin{property}
   $B^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}(AB)^{\dagger} = 
                     B^{\dagger}(B^{T})^{\dagger}(AB)^{\dagger}$
\end{property}


\begin{property}
   $(B^{T}A^{T})^{\dagger}(AB)^{\dagger}A(B^{T})^{\dagger} = 
                    (B^{T}A^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger}$
\end{property}


\begin{property}
   $(AB)^{\dagger}(B^{T}A^{T})^{\dagger}B^{T}A^{\dagger} = 
                            (AB)^{\dagger}(A^{T})^{\dagger}A^{\dagger}$
\end{property}



\begin{property}
   $(A^{T})^{\dagger}B(AB)^{\dagger}(B^{T}A^{T})^{\dagger} = 
                           (A^{T})^{\dagger}A^{\dagger}(B^{T}A^{T})^{\dagger}$
\end{property}


\begin{property}
   $B^{\dagger}(B^{T})^{\dagger}(AB)^{\dagger}A(B^{T})^{\dagger} = 
          B^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger}$
\end{property}

\begin{property}
   $(A^{T})^{\dagger}A^{\dagger}(B^{T}A^{T})^{\dagger}B^{T}A^{\dagger} = 
                (A^{T})^{\dagger}B(AB)^{\dagger}(A^{T})^{\dagger}A^{\dagger}$
\end{property}


Infinite properties:

\begin{property}
   $BB^{\dagger}\big\{A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}\big\}^{\bf K}(B^{T})^{\dagger} =
   (B^{T})^{\dagger}\big\{(AB)^{\dagger}A(B^{T})^{\dagger}\big\}^{\bf K }$

   $K=1,2,3,\dots$.
\end{property}

\begin{property}
   $A^{T}\big\{(A^{T})^{\dagger}B(AB)^{\dagger}\big\}^{\bf K}(A^{T})^{\dagger}A^{\dagger} =
   A^{\dagger}\big\{{B^{T}A^{T}}^{\dagger}B^{T}A^{\dagger}\big\}^{\bf K }$

   $K=1,2,3,\dots$.
\end{property}

\begin{property}
   $A\big\{B(AB)^{\dagger}(A^{T})^{\dagger}\big\}^{\bf K}A^{\dagger} =
   (B^{T}A^{T})^{\dagger}\big\{B^{T}A^{\dagger}(B^{T}A^{T})^{\dagger}\big\}^{\bf K-1}B^{T}A^{\dagger}$

   $K=1,2,3,\dots$.
\end{property}

\begin{property}
   $B^{T}\big\{A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}\big\}^{\bf K}(B^{T})^{\dagger} =
   (AB)^{\dagger}\big\{A(B^{T})^{\dagger}(AB)^{\dagger}\big\}^{\bf K-1}A(B^{T})^{\dagger}$

   $K=1,2,3,\dots$.
\label{abproplast}
\end{property}


\begin{theorem}
If Properties \ref{abpropfirst} through \ref{abproplast} are considered as polynomials of the form
$LHS - RHS$ (they are written above in the form $LHS=RHS$), then they
along with
$\mathcal{G}_{\mathcal{O}_A}(\Psi(A))\cup\mathcal{G}_{\mathcal{O}_B}(\Psi(B))\cup\Psi(AB)$  
form a (non-commutative) Gr\"obner Basis for the ideal generated by
$\Omega_2 = \Psi(A)\cup\Psi(B)\cup\Psi(AB)$
 under the graded lexographical order induced by the
``alphabetical'' order:  

\vspace{3mm}
  
$\mathcal{O} = \big\{A<B<A^{T}<B^{T}<A^{\dagger}<B^{\dagger}<(A^{T})^{\dagger}< 
                     (B^{T})^{\dagger}< \\   
\hspace*{17mm}       (A^{\dagger})^{T}<(B^{\dagger})^{T}<(AB)^{\dagger}<
                     (B^{T}A^{T})^{\dagger}<((AB)^{\dagger})^{T}\big\}$ \\
                     
\vspace{3mm}

This Gr\"obner Basis will be denoted by $\mathcal{G}_{\mathcal{O}_{AB}}(\Omega_2)$.  

\end{theorem}


\section{Appendix A}
\label{sec:appa}

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.

\vspace{3mm}

\noindent  \textbf{Proof of Property $4.1$} \\
The Moore-Penrose conditions for $A^{T}$ are: 
\begin{align*}
  & A^{T}XA^{T}=A^{T} \\ 
  & XA^{T}X=X \\ 
  & (A^{T}X)^{T}=A^{T}X \\ 
  & (XA^{T})^{T}=XA^{T} 
\end{align*}   
We have, again by definition, that $X=(A^{T})^{\dagger}$.  So showing that 
$(A^{\dagger})^{T}$ also satisfies these relations is enough to prove the claim.
Well, since $AA^{\dagger}A=A$ and $A^{\dagger}AA^{\dagger}=A^{\dagger}$, we have (by taking $^{T}$) that
$A^{T}(A^{\dagger})^{T}A^{T}=A^{T}$ and $(A^{\dagger})^{T}A^{T}(A^{\dagger})^{T}=(A^{\dagger})^{T}$.  So
$(A^{\dagger})^{T}$ satifies the first two conditions.  We also have
$(A^{T}(A^{\dagger})^{T})^{T}=A^{\dagger}A=(A^{\dagger}A)^{T}=A^{T}(A^{\dagger})^{T}$ and
$((A^{\dagger})^{T}A^{T})^{T}=AA^{\dagger}=(AA^{\dagger})^{T}=(A^{\dagger})^{T}A^{T}$.  Therefore, 
$(A^{T})^{\dagger}=(A^{\dagger})^{T}.  \hspace{2mm}  \square$


\vspace{3mm}

\noindent \textbf{Proof of Property $4.8$} \\
The Moore-Penrose conditions for $A^{\dagger}$ are: 
\begin{align*}
 & A^{\dagger}XA^{\dagger}=A^{\dagger} \\ 
 & XA^{\dagger}X=X \\ 
 & (A^{\dagger}X)^{T}=A^{\dagger}X \\ 
 & (XA^{\dagger})^{T}=XA^{\dagger} 
\end{align*}
By definition, we denote the unique element $X$ by $(A^{\dagger})^{\dagger}$.  But
it is also clear from the definition of $A^{\dagger}$ that $A$ also satisfies these
properties.  Therefore, $(A^{\dagger})^{\dagger} = A.  \hspace{2mm}  \square$  


\vspace{3mm}

\noindent  \textbf{Proof of Property $4.10$} \\
We argue that $A^{\dagger}(A^{T})^{\dagger}$ satisfies the Moore-Penrose conditions for 
$A^{T}A$.
 
\begin{align*} 
 (A^{T}A)(A^{\dagger}(A^{T})^{\dagger})(A^{T}A) &=(A^{T}AA^{\dagger})(A^{T})^{\dagger}(A^{T}A) \\
	        		    &=A^{T}(A^{T})^{\dagger}A^{T}A \\
                                    &=A^{T}A.  
\end{align*}
\begin{align*}
 (A^{\dagger}(A^{T})^{\dagger})(A^{T}A)(A^{\dagger}(A^{T})^{\dagger}) &=A^{\dagger}((A^{T})^{\dagger}A^{T})(AA^{\dagger}(A^{T})^{\dagger}) \\
                                              &=A^{\dagger}AA^{\dagger}(A^{T})^{\dagger} \\
                                              &=A^{\dagger}(A^{T})^{\dagger}. 
\end{align*}
\begin{align*}
 ((A^{T}A)(A^{\dagger}(A^{T})^{\dagger}))^{T} &=((A^{T}AA^{\dagger})(A^{T})^{\dagger})^{T} \\
                                  &=(A^{T}(A^{\dagger})^{T})^{T} \\
                                  &=A^{\dagger}A  \\
                                  &=(A^{\dagger}A)^{T} \\
                                  &=A^{T}(A^{T})^{\dagger} \\
                                  &=(A^{T}A)(A^{\dagger}(A^{T})^{\dagger}).  
\end{align*}

\noindent
MP4 is verified in the same fashion as MP3.  Therefore, 
$(A^{T}A)^{\dagger}=A^{\dagger}(A^{T})^{\dagger}.  \hspace{2mm}  \square$

\vspace{3mm}

\noindent  \textbf{Proof of Property $4.13$} \\
We argue that $AA^{\dagger}$ satisfies the Moore-Penrose conditions for itself.
 
\begin{align*} 
 (AA^{\dagger})(AA^{\dagger})(AA^{\dagger}) &=(AA^{\dagger}A)(A^{\dagger}AA^{\dagger}) \\
                          &=AA^{\dagger}.  
\end{align*}

This shows that $AA^{\dagger}$ satisfies the first \textbf{two} conditions.

\begin{align*}
 ((AA^{\dagger})(AA^{\dagger}))^{T} &=(AA^{\dagger})^{T} \\
                        &=AA^{\dagger} \\
                        &=(AA^{\dagger})(AA^{\dagger}). 
\end{align*}

This shows that $AA^{\dagger}$ satisfies the second two conditions. \\
Therefore, $(AA^{\dagger})^{\dagger}=AA^{\dagger}.  \hspace{2mm}  \square$

\section{Appendix A+B}
\label{sec:appaplusb}

Before getting to the proofs of Properties 5.1 - 5.8, we list those associated
with $\Psi(A+B)$: (They are Properties 4.1 - 4.7 with $A+B$ substituted in for $A$)

\begin{property}
  $((A+B)^{\dagger})^{T} = (A^{T}+B^{T})^{\dagger}$ 
\end{property} 


\begin{property}
   $AA^{T}(A^{T}+B^{T})^{\dagger}+AB^{T}(A^{T}+B^{T})^{\dagger}+ \\
\hspace*{28mm}    BA^{T}(A^{T}+B^{T})^{\dagger}+BB^{T}(A^{T}+B^{T})^{\dagger} 
                  = A+B$   
\end{property}


\begin{property}
   $A^{T}A(A+B)^{\dagger}+A^{T}A(A+B)^{\dagger}+ \\
\hspace*{28mm}   A^{T}A(A+B)^{\dagger}+A^{T}A(A+B)^{\dagger} = A^{T}+B^{T}$
\end{property}


\begin{property}
   $A^{T}(A^{T}+B^{T})^{\dagger}(A+B)^{\dagger}+
    B^{T}(A^{T}+B^{T})^{\dagger}(A+B)^{\dagger}= (A+B)^{\dagger}$   
\end{property}


\begin{property}
   $A(A+B)^{\dagger}(A^{T}+B^{T})^{\dagger}+
    B(A+B)^{\dagger}(A^{T}+B^{T})^{\dagger} = (A^{T}+B^{T})^{\dagger}$
\end{property}
 

\begin{property}
   $(A^{T}+B^{T})^{\dagger}A^{T}+(A^{T}+B^{T})^{\dagger}B^{T}+ = 
    A(A+B)^{\dagger}+B(A+B)^{\dagger}$
\end{property}


\begin{property}
   $(A+B)^{\dagger}A+(A+B)^{\dagger}B = 
    A^{T}(A^{T}+B^{T})^{\dagger}+B^{T}(A^{T}+B^{T})^{\dagger}$
\end{property}

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^{\dagger}(A+B)(A+B)^{\dagger}(A^{T}+B^{T})^{\dagger} = 
                                     B^{\dagger}(A^{T}+B^{T})^{\dagger}$ and 
$B^{\dagger}(A+B)(A+B)^{T}(A^{T}+B^{T})^{\dagger} = B^{\dagger}(A+B)$ 
respectively, and collecting terms on the appropriate sides of the ``=" sign.

\vspace{3mm}

\noindent  \textbf{Proof of Property $5.5$} 
   
\begin{align*} 
A^{T}(A^{T}+B^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger}+B^{T}(A^{T}+B^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger} &= \\
                                 (A+B)^{T}(A^{T}+B^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger} &= \\
                                           (A+B)^{\dagger}(A+B)B^{\dagger}(B^{T})^{\dagger} &= \\
                           (A+B)^{\dagger}(AB^{\dagger}(B^{T})^{\dagger}+BB^{\dagger}(B^{T})^{\dagger}) &= \\
                                 (A+B)^{\dagger}(AB^{\dagger}(B^{T})^{\dagger}+(B^{T})^{\dagger}) &= \\
                         (A+B)^{\dagger}AB^{\dagger}(B^{T})^{\dagger}+(A+B)^{\dagger}(B^{T})^{\dagger}.                  
\end{align*}

Property 5.5 may also be written as 
$(A+B)^{\dagger}(A+B)B^{\dagger}(B^{T})^{\dagger}= \\
(A+B)^{\dagger}(I+AB^{\dagger})(B^{T})^{\dagger}.
\hspace{2mm}  \square$

\vspace{3mm}

\noindent  \textbf{Proof of Property $5.7$} 
   
\begin{align*} 
A^{T}(A^{T}+B^{T})^{\dagger}A^{T}(B^{T})^{\dagger}+B^{T}(A^{T}+B^{T})^{\dagger}A^{T}(B^{T})^{\dagger}+ \\
     (A+B)^{\dagger}AB^{T}(B^{T})^{\dagger}+A^{T}(A^{T}+B^{T})^{\dagger}+B^{T}(A^{T}+B^{T})^{\dagger} &= \\
(A+B)^{\dagger}AB^{T}(B^{T})^{\dagger}+(A+B)^{T}(A^{T}+B^{T})^{\dagger}A^{T}(B^{T})^{\dagger}
                                                +(A+B)^{T}(A^{T}+B^{T})^{\dagger} &= \\
(A+B)^{\dagger}AB^{T}(B^{T})^{\dagger}+(A+B)^{\dagger}(A+B)A^{T}(B^{T})^{\dagger} +(A+B)^{\dagger}(A+B) &= \\
(A+B)^{\dagger} \{AB^{T}(B^{T})^{\dagger}+AA^{T}(B^{T})^{\dagger}+BA^{T}(B^{T})^{\dagger}+B \} +
                                                               (A+B)^{\dagger}A &= \\
(A+B)^{\dagger} \{AB^{T}(B^{T})^{\dagger}+AA^{T}(B^{T})^{\dagger}+BA^{T}(B^{T})^{\dagger}+
                                        BB^{T}(B^{T})^{\dagger} \} + (A+B)^{\dagger}A &= \\
       (A+B)^{\dagger} \{AB^{T}+AA^{T}+BA^{T}+BB^{T} \}(B^{T})^{\dagger} + (A+B)^{\dagger}A &= \\
                          (A+B)^{\dagger}(A+B)(A+B)^{T}(B^{T})^{\dagger} + (A+B)^{\dagger}A &= \\
                                        (A+B)^{T}(B^{T})^{\dagger} + (A+B)^{\dagger}A &= \\
                        A^{T}(B^{T})^{\dagger} + B^{T}(B^{T})^{\dagger} + (A+B)^{\dagger}A.           
\end{align*}

\noindent Property 5.7 may also be written as \\
$(A+B)^{\dagger} \{ A+(A+B)(A+B)^{T}(B^{T})^{\dagger} \}= 
(A+B)^{\dagger}A+(A+B)^{T}(B^{T})^{\dagger}.
\hspace{2mm}  \square$


\section{Appendix AB}
\label{sec:appab}

Before getting to the proofs of Properties 6.1 - 6.20, we list those associated
with $\Psi(AB)$: (They are Properties 4.1 - 4.7 with $AB$ substituted in for $A$)

\begin{property}
  $((AB)^{\dagger})^{T} = (B^{T}A^{T})^{\dagger}$ 
\end{property} 


\begin{property}
   $ABB^{T}A^{T}(B^{T}A^{T})^{\dagger} = AB$
\end{property}


\begin{property}
   $B^{T}A^{T}AB(AB)^{\dagger} = B^{T}A^{T}$
\end{property}


\begin{property}
   $B^{T}A^{T}(B^{T}A^{T})^{\dagger}(AB)^{\dagger} = (AB)^{\dagger}$
\end{property}


\begin{property}
   $AB(AB)^{\dagger}(B^{T}A^{T})^{\dagger} = (B^{T}A^{T})^{\dagger}$
\end{property}
 

\begin{property}
   $(B^{T}A^{T})^{\dagger}B^{T}A^{T} = AB(AB)^{\dagger}$
\end{property}


\begin{property}
   $(AB)^{\dagger}AB = B^{T}A^{T}(B^{T}A^{T})^{\dagger}$
\end{property}

\noindent
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.

\vspace{3mm}

\noindent  \textbf{Proof of Property $6.1$} \\
We argue that $(AB)^{\dagger}AA^{\dagger}$ satisfies the Moore-Penrose 
conditions for $AB$.
 
\begin{align*} 
 AB\{(AB)^{\dagger}AA^{\dagger}\}AB &=AB(AB)^{\dagger}\{AA^{\dagger}A\}B \\
	        		      &=AB(AB)^{\dagger}AB \\
                                      &=AB.  
\end{align*}

\begin{align*} 
 \{(AB)^{\dagger}AA^{\dagger}\}AB\{(AB)^{\dagger}AA^{\dagger}\} &=
 (AB)^{\dagger}\{AA^{\dagger}A\}B(AB)^{\dagger}AA^{\dagger}  \\
	                      &=(AB)^{\dagger}AB(AB)^{\dagger}AA^{\dagger} \\
                              &=(AB)^{\dagger}AA^{\dagger}.  
\end{align*}

\begin{align*}
 (AB\{(AB)^{\dagger}AA^{\dagger}\})^{T} &=(\{AB(AB)^{\dagger}\}AA^{\dagger})^{T} \\
            &=(AA^{\dagger})^{T}(AB(AB)^{\dagger})^{T} \\
            &=AA^{\dagger}AB(AB)^{\dagger} \\
            &=AB(AB)^{\dagger} \\
            &=((AB)^{T})^{\dagger}(AB)^{T} \\
            &=((AB)^{T})^{\dagger}B^{T}A^{T} \\
            &=((AB)^{T})^{\dagger}B^{T}A^{T}AA^{\dagger} \\
            &=AB\{(AB)^{\dagger}AA^{\dagger}\}.  
\end{align*}

\begin{align*}
 (\{(AB)^{\dagger}AA^{\dagger}\}AB)^{T} &=((AB)^{\dagger}\{AA^{\dagger}A\}B)^{T} \\
            &=((AB)^{\dagger}AB)^{T} \\
            &=(AB)^{\dagger}AB \\
            &=\{(AB)^{\dagger}AA^{\dagger}\}AB.  
\end{align*}

The uniquness of $(AB)^{\dagger}$ then tells us that 
$(AB)^{\dagger}AA^{\dagger}=(AB)^{\dagger}. \quad \square$

\vspace{3mm}
\noindent
Property 6.3 can be gotten from Property 6.2 by substituting $B^{T}$ for $A$ 
(and hence $B$ for $A^{T}$).

\vspace{3mm}

\noindent  \textbf{Proof of Property $6.5$} \\


\begin{align*} 
 AB(AB)^{\dagger}A(B^{T})^{\dagger} &=AB(AB)^{\dagger}ABB^{\dagger}(B^{T})^{\dagger}\\
	        		    &=ABB^{\dagger}(B^{T})^{\dagger} \\
                                    &=A(B^{T})^{\dagger}.  
\end{align*}


\noindent
Therefore, $AB(AB)^{\dagger}A(B^{T})^{\dagger}=A(B^{T})^{\dagger}.  \quad \square$

\vspace{3mm}

\noindent  \textbf{Proof of Property $6.7$} \\

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

\begin{align*} 
 (A^{T})^{\dagger}B(AB)^{\dagger}A(B^{T})^{\dagger} &=
 (A^{T})^{\dagger}A^{\dagger}AB(AB)^{\dagger}ABB^{\dagger}(B^{T})^{\dagger}\\
	  &=(A^{T})^{\dagger}A^{\dagger}ABB^{\dagger}(B^{T})^{\dagger} \\
          &=(A^{T})^{\dagger}(B^{T})^{\dagger}.  
\end{align*}


\noindent
Therefore, $(A^{T})^{\dagger}B(AB)^{\dagger}A(B^{T})^{\dagger}=
            (A^{T})^{\dagger}(B^{T})^{\dagger}.  \quad \square$


\vspace{3mm}

\noindent  \textbf{Proof of Property $6.9$} \\

\begin{align*} 
 (A^{T})^{\dagger}BB^{T}A^{T}(B^{T}A^{T})^{\dagger} &=
                                        (A^{T})^{\dagger}B(AB)^{\dagger}AB\\
	                 &=(A^{T})^{\dagger}A^{\dagger}AB(AB)^{\dagger}AB \\
                         &=(A^{T})^{\dagger}A^{\dagger}AB \\
                         &=(A^{T})^{\dagger}B.  
\end{align*}


\noindent
Therefore, $(A^{T})^{\dagger}BB^{T}A^{T}(B^{T}A^{T})^{\dagger}=
            (A^{T})^{\dagger}B.  \quad \square$


\vspace{3mm}

\noindent  \textbf{Proof of Property $6.11$} \\


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

\begin{align*} 
  B^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}(AB)^{\dagger} &=
   B^{\dagger}(B^{T})^{\dagger}B^{T}A^{T}(B^{T}A^{T})^{\dagger}(AB)^{\dagger}\\
	                 &=B^{\dagger}(B^{T})^{\dagger}(AB)^{\dagger}.                          
\end{align*}


\noindent
Therefore, $B^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}(AB)^{\dagger}=
            B^{\dagger}(B^{T})^{\dagger}(AB)^{\dagger}  \quad \square$.
            
\vspace{3mm}
\noindent
Property 6.13 can be gotten from Property 6.12 by substituting $A$ for $B^{T}$,
and hence $A^{T}$ for $B$ etc.


\vspace{3mm}

\noindent  \textbf{Proof of Property $6.15$} \\

\begin{align*} 
 B^{\dagger}(B^{T})^{\dagger}(AB)^{\dagger}A(B^{T})^{\dagger} &=
 B^{\dagger}(B^{T})^{\dagger}B^{T}A^{T}(B^{T}A^{T})^{\dagger}(AB)^{\dagger}A(B^{T})^{\dagger}\\
  &=B^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}(AB)^{\dagger}A(B^{T})^{\dagger} \\
  &=B^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}(AB)^{\dagger}ABB^{\dagger}(B^{T})^{\dagger} \\
  &=B^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger}.  
\end{align*}


\noindent
Therefore, $B^{\dagger}(B^{T})^{\dagger}(AB)^{\dagger}A(B^{T})^{\dagger}=
            B^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger}$.
            Note that this says that either of these expressions is its own
            transpose.  $\quad \square$ 
            
\vspace{3mm}
\noindent
Property 6.16 can be gotten from 6.15 by substituting $A^{T}$ for $B$ etc.

\vspace{3mm}
\noindent
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.


\vspace{3mm}

\noindent  \textbf{Proof of Property $6.17$} \\

K=1.

\begin{align*} 
 BB^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger} &=
 (B^{T})^{\dagger}B^{T}A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger}\\
  &=(B^{T})^{\dagger}(AB)^{\dagger}ABB^{\dagger}(B^{T})^{\dagger} \\
  &=(B^{T})^{\dagger}(AB)^{\dagger}A(B^{T})^{\dagger}.   
\end{align*}

K=2.

\begin{align*} 
 BB^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger} &=
 BB^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}BB^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger}\\
 &=BB^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger} \{ BB^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger} \} \\
 &=BB^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger} \{ (B^{T})^{\dagger}(AB)^{\dagger}A(B^{T})^{\dagger} \} \\   
 &=BB^{\dagger}A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}(B^{T})^{\dagger} \{ (AB)^{\dagger}A(B^{T})^{\dagger} \} \\
 &=(B^{T})^{\dagger} \{ (AB)^{\dagger}A(B^{T})^{\dagger} \}^{2}.
\end{align*}


\noindent
Therefore,  $BB^{\dagger}\big\{A^{T}(B^{T}A^{T})^{\dagger}B^{\dagger}\big\}^{\bf K}(B^{T})^{\dagger} =
   (B^{T})^{\dagger}\big\{(AB)^{\dagger}A(B^{T})^{\dagger}\big\}^{\bf K }$

   $K=1,2,3,\dots. \quad \square$                       


\vspace{3mm}

\noindent  \textbf{Proof of Property $6.18$} \\

K=1.

\begin{align*} 
 A^{T}(A^{T})^{\dagger}B(AB)^{\dagger}(A^{T})^{\dagger}A^{\dagger} &=
 A^{\dagger}AB(AB)^{\dagger}(A^{T})^{\dagger}A^{\dagger}\\
  &=A^{\dagger}(B^{T}A^{T})^{\dagger}B^{T}A^{T}(A^{T})^{\dagger}A^{\dagger} \\
  &=A^{\dagger}(B^{T}A^{T})^{\dagger}B^{T}A^{\dagger}.   
\end{align*}

K=2.

\begin{align*} 
 A^{T}(A^{T})^{\dagger}B(AB)^{\dagger}(A^{T})^{\dagger}B(AB)^{\dagger}(A^{T})^{\dagger}A^{\dagger} &=
 A^{T}(A^{T})^{\dagger}B(AB)^{\dagger}(A^{T})^{\dagger}A^{T}(A^{T})^{\dagger}B(AB)^{\dagger}(A^{T})^{\dagger}A^{\dagger}\\
 &=A^{T}(A^{T})^{\dagger}B(AB)^{\dagger}(A^{T})^{\dagger} \{ A^{\dagger}(B^{T}A^{T})^{\dagger}B^{T}A^{\dagger} \} \\
 &=A^{T}(A^{T})^{\dagger}B(AB)^{\dagger}(A^{T})^{\dagger}A^{\dagger} \{ (B^{T}A^{T})^{\dagger}B^{T}A^{\dagger} \} \\   
 &=A^{\dagger} \{ (B^{T}A^{T})^{\dagger}B^{T}A^{\dagger} \}^{2}.
\end{align*}


\noindent
Therefore, $A^{T}\big\{(A^{T})^{\dagger}B(AB)^{\dagger}\big\}^{\bf K}(A^{T})^{\dagger}A^{\dagger} =
   A^{\dagger}\big\{{B^{T}A^{T}}^{\dagger}B^{T}A^{\dagger}\big\}^{\bf K }$

   $K=1,2,3,\dots.  \quad \square$
   
   
\vspace{3mm}

\noindent  \textbf{Proof of Property $6.19$} \\

K=1.

\begin{align*} 
 AB(AB)^{\dagger}(A^{T})^{\dagger}A^{\dagger} &=
 (B^{T}A^{T})^{\dagger}B^{T}A^{T}(A^{T})^{\dagger}A^{\dagger}\\
  &=(B^{T}A^{T})^{\dagger}B^{T}A^{\dagger}. 
\end{align*}

K=2.

\begin{align*} 
 AB(AB)^{\dagger}(A^{T})^{\dagger}B(AB)^{\dagger}(A^{T})^{\dagger}A^{\dagger} &=
 AB(AB)^{\dagger}(A^{T})^{\dagger}A^{\dagger}AB(AB)^{\dagger}(A^{T})^{\dagger}A^{\dagger} \\
 &=(B^{T}A^{T})^{\dagger}B^{T}A^{\dagger}(B^{T}A^{T})^{\dagger}B^{T}A^{\dagger} \\
 &=(B^{T}A^{T})^{\dagger} \{ B^{T}A^{\dagger}(B^{T}A^{T})^{\dagger} \}^{2-1} B^{T}A^{\dagger}.
\end{align*}


\noindent
Therefore, $A\big\{B(AB)^{\dagger}(A^{T})^{\dagger}\big\}^{\bf K}A^{\dagger} =
   (B^{T}A^{T})^{\dagger}\big\{B^{T}A^{\dagger}(B^{T}A^{T})^{\dagger}\big\}^{\bf K-1}B^{T}A^{\dagger}$

   $K=1,2,3,\dots.  \quad \square$
   
\vspace{3mm}
\noindent
Property 6.20 can be gotten from Property 6.19 by substituting $B^{T}$ for $A$
etc.   
      

\end{document}