Let A be an m by n matrix. Prove that there exists an n by m matrix B such that ABA = A.

Step-by-step solution

1. 1

   Reduce to a canonical form. Let $r=\operatorname{rank}(A)$. Every matrix is equivalent to its rank normal form: there exist invertible $P$ ($m\times m$) and $Q$ ($n\times n$) with

   $PAQ=D:=\begin{pmatrix}I_{r}&0\\ 0&0\end{pmatrix}_{m\times n}$

   $P$ and $Q$ record the row and column operations that clear $A$ down to this block form.

2. 2

   Solve the problem for $D$ first. Define the $n\times m$ matrix

   $D^{-}:=\begin{pmatrix}I_{r}&0\\ 0&0\end{pmatrix}_{n\times m}$

   — the same block pattern with the dimensions swapped, which is what makes the products conformable. Block multiplication gives $DD^{-}=\begin{pmatrix}I_{r}&0\\0&0\end{pmatrix}_{m\times m}$ and hence

   $DD^{-}D=D$

   since multiplying $D$ on the left by that idempotent projector leaves its only nonzero block untouched.

3. 3

   Transport the solution back to $A$. From $PAQ=D$ we get $A=P^{-1}DQ^{-1}$. Define

   $B:=QD^{-}P$

   which is $(n\times n)(n\times m)(m\times m)=n\times m$, exactly the required shape. Note $B=QD^{-}P$, not $QDP$ — the transpose-shaped block matrix is essential for the dimensions to match.

4. 4

   Verify $ABA=A$ by substitution. Substituting both expressions and cancelling the inverse pairs:

   $ABA=\left(P^{-1}DQ^{-1}\right)\left(QD^{-}P\right)\left(P^{-1}DQ^{-1}\right)=P^{-1}D\,D^{-}D\,Q^{-1}=P^{-1}DQ^{-1}=A$

   using $Q^{-1}Q=I_{n}$, $PP^{-1}=I_{m}$ and the identity $DD^{-}D=D$ from step 2. This completes the proof.

5. 5

   Note what the statement does and does not claim. $B$ is called a generalized inverse (or $\{1\}$-inverse) of $A$. It is generally not unique — any $B$ of the form $QD^{-}P$ built from a different choice of $P,Q$ works, and when $r<\min(m,n)$ the free blocks give infinitely many. It coincides with $A^{-1}$ only when $A$ is square and invertible ($r=m=n$).

6. 6

   Numerical confirmation. The Moore–Penrose pseudoinverse is one explicit such $B$. For random matrices of shapes $4\times 3$ (rank 2), $3\times 5$ (rank 3) and $5\times 5$ (rank 1), computing $A\,A^{+}A-A$ gives entries of size $10^{-15}$ or smaller — machine zero, as the theorem predicts.