Moore-Penrose pseudoinverse/Proofs

Relations

Preliminaries

These lemmata do not concern the pseudoinverse itself, they are AbOUT complex matrices in general.

As always, they also hold for matrices with only real elements, in which case the conjugation operator (*) May Be replaced by transposition (^T).

=== L3: A*A = 0 ⇒ A = 0 . === A is a matrix with complex elements, m rows and n columns. The assumption says that all elements of A*A are zero, including the diagonal elements. The j^th diagonal element of A*A is $\sum_{i=1...m} a_{ij}a_{ji}^*=\sum_{i=1...m}a_{ij}\overline{a_{ij}}$. Since $x \overline{x}\ \ge \ 0$ for all x, and equal to zero only for x = 0, the sum can only be 0 if all a_ij are 0. Since this holds for all j, all a_ij are 0, thus A=0.

=== L4: BAA* = CAA* => BA = CA. === A is a matrix with complex elements and m rows. B and C are matrices with complex elements and m columns.

BAA* = CAA* <=> 0 = BAA*-CAA* = (BA-CA)A* => 0 = (BA-CA)A*(B-C)* = (BA-CA)(BA-CA)* L3=> 0 = BA-CA <=> BA = CA.

Note that since BA = CA => BAA* = CAA* also holds, in effect equivalence results: BA = CA ⇔ BAA* = CAA*.

=== L5: A*AB = A*AC => AB = AC. === A is a matrix with complex elements and n columns. B and C are matrices with complex elements and n rows.

A*AB = A*AC <=> 0 = A*AB-A*AC = A*(AB-AC) => 0 = (B-C)*A*(AB-AC) = (AB-AC)*(AB-AC) L3=> 0 = AB-AC <=> AB = AC.

Note that since AB = AC => A*AB = A*AC also holds, in effect equivalence results: AB = AC ⇔ A*AB = A*AC.

== L1: A*⁺=A^+*. ==

The proof works by showing that A^+* satisfies the four criteria for the Pseudoinverse of A*. Since this amounts to just substitution, it is not shown here.

This relation is given to prove as Exercise 18b in .

Identity Transformations

=== A+ = A+ A+* A* ===

A+ = A+ A A+ and A A+ = (A A+)* imply that A+ = A+ (A A+)* = A+ A+* A*.

=== A+ = A* A+* A+ ===

A+ = A+ A A+ and A+ A = (A+ A)* imply that A+ = (A+ A)* A+ = A* A+* A+.

=== A = A+* A* A ===

A = A A+ A and A A+ = (A A+)* imply that A = (A A+)* A = A+* A* A.

=== A = A A* A+* ===

A = A A+ A and A+ A = (A+ A)* imply that A = A (A+ A)* = A A* A+*.

=== A* = A* A A+ ===

This is the conjugate transpose of A = A+* A* A above.

=== A* = A+ A A* ===

This is the conjugate transpose of A = A A* A+* above.

== A⁺ = (A* A)⁺ A*. ==

In , this relation, together with A+=A*(AA*)+ is given as exercise 18(d) for the reader to prove, "for every matrix A". It might also be found in , possibly chapters 5 or 7, but this was not verified. The relation is proven here by showing that the right-hand side satisfies the defining criteria of the pseudoinverse of A.

Further lemmata: For any A, (A*A)+ exists and is unique, so that criteria 1 to 4 hold for it:

B1:  A*A  (A*A)+ A*A   =  A*A;
B2: (A*A)+ A*A  (A*A)+ = (A*A)+;
B3:   ( A*A  (A*A)+)*  =  A*A  (A*A)+; <=> (A*A)+* A*A    =  A*A  (A*A)+ L1=>= (A*A)+ A*A (not used here)
B4:   ((A*A)+ A*A  )*  = (A*A)+ A*A;   <=>  A*A   (A*A)+* = (A*A)+ A*A   L1=>=  A*A  (A*A)+

Above, "L1=>=" means "from L1 follows equality with". B2 is used in the proof of 2 below, B4 is used in the proof of 4.

L6: A (A* A)+ A* A = A.

L6 follows from applying L5 to B1. Note that L2 may not be applied to B1, since the X in L2 may in this case not be chosen independently of Y and Z, it is fixed (the A* in B1) .

Below, '*=>=' means 'applying complex conjugation'.

0.  A+ = (A* A)+ A* . (That's what we suppose)
1.  AA+A  = A  ; AA+A   0=>= A(A*A)+ A*A                    L6=>= A            =<=0 A   -> OK.
2.  A+AA+ = A+ ; A+AA+  0=>= (A*A)+ A* A (A*A)+ A*          B2=>= (A*A)+A*     =<=0 A+  -> OK.
3. (AA+)* = AA+; (AA+)* 0=>= (A(A*A)+ A*)* *=>= A(A*A)+* A* L1,*=>= A(A*A)+ A* =<=0 AA+ -> OK.
4. (A+A)* = A+A; (A+A)* 0=>= ((A*A)+ A*A)* *=>= A*A(A*A)+*  B4=>= (A*A)+ A*A   =<=0 A+A -> OK.

== A⁺ = A* (A A*)⁺ ==

This proof works along a similar line as the above one. The relation is proven by showing that the right-hand side satisfies the defining criteria of the pseudoinverse of A:

A1: AA⁺A = A .
A2: A⁺AA⁺ = A⁺ .
A3: (AA⁺)* = AA⁺.
A4: (A⁺A)* = A⁺A.

First, some basic relations are named:

M1: B=C => DB=DC.
T0: (A*)* = A.
T1: (AB)* = B*A*.

Further lemmata: For any A, (AA*)⁺ exists and is unique, so that criteria 1 to 4 hold for it:

C1:  AA*  (AA*)⁺ AA*   =  AA*        .
C2: (AA*)⁺ AA*  (AA*)⁺ = (AA*)⁺      .
C3:   ( AA*  (AA*)⁺)*  =  AA*  (AA*)⁺. (unused here)
C4:   ((AA*)⁺ AA*  )*  = (AA*)⁺ AA*  .

More auxiliary results:

I3: C4 and T1 (twice) and T0 => AA* (AA*)⁺* = (AA*)⁺ AA*.
I4: I3 and L1 and T1 and T0 => AA* (AA*)⁺ = (AA*)⁺ AA*.

Applying A+ = A* (A A*)⁺ to A1 to A4, we have to prove these four relations:

G1: AA* (AA*)⁺ A = A,
G2: A* (AA*)⁺ AA* (AA*)⁺ = A* (AA*)⁺,
G3: (AA* (AA*)⁺)* = AA* (AA*)⁺,
G4: (A* (AA*)⁺ A)* = A* (AA*)+ A.

C1 and L4 (BAA* = CAA* => BA = CA) imply G1.

C2 and M1 imply G2.

I5: Equality holds:     A* (AA*)⁺  A   = A* (AA*)⁺ A
I6: I5 and T0 and T1 => A* (AA*)*⁺ A   = A* (AA*)⁺ A
I7: I6 and L1        => A* (AA*)⁺* A   = A* (AA*)⁺ A
I8: I7 and T1        =>(A* (AA*)⁺  A)* = A* (AA*)⁺ A, proving G4.

I9: Equality holds: (AA* (AA*)⁺)* = (AA* (AA*)⁺)*
I10: I9 and T1 (twice) and T0 => (AA* (AA*)⁺)* = (AA*)⁺* AA*
I11: I10 and L1 and T1 and T0 => (AA* (AA*)⁺)* = (AA*)⁺ AA*
I12: I11 and I4 => (AA* (AA*)⁺)* = AA* (AA*)⁺, proving G3.

Thus the hypothesis satisfies A1 to A4.

Uniqueness of the pseudoinverse

Given the matrix A, assume you have two matrices B and C, both fulfilling the pseudoinverse properties:

AB = (AB)^T, AC = (AC)^T
BA = (BA)^T, CA = (CA)^T
ABA = A, ACA = A
BAB = B, CAC = C

We will show that B = C.

As a first step we show AB = AC:

AB = B^TA^T = B^TA^TC^TA^T = ABC^TA^T = ABAC = AC Analogously we conclude that BA = CA.

We complete the proof with:

B = BAB = BAC = CAC = C

The following Haskell program computes all shortest proofs in form of a tree. 1 It outputs only half of the proofs, which can be composed to full proofs easily.

module PseudoInverseUniqueness (main) where

import Data.Tree (Tree(Node), Forest, drawForest)
import Data.List (inits, tails, isPrefixOf)
import Data.Map (Map)
import qualified Data.Map as Map

data Matrix = A | AT | B | BT | C | CT
   deriving (Eq, Ord, Enum, Show)

type Product = [Matrix]
type Rule = (Product, Product)

basicRulesB :: [Rule]
basicRulesB =
   ([A,B], [BT, AT]) :
   ([B,A], [AT, BT]) :
   ([A,B,A],    [A]) :
   ([B,A,B],    [B]) :
   ([AT,BT,AT], [AT]) :
   ([BT,AT,BT], [BT]) :
   []

basicRulesC :: [Rule]
basicRulesC =
   let btoc = map (\m -> case m of B -> C; BT -> CT; _ -> m)
   in  map (\(src,dst) -> (btoc src, btoc dst)) basicRulesB

rules :: [Rule]
rules =
   let basicRules = basicRulesB ++ basicRulesC
   in  basicRules ++ map (\(x,y) -> (y,x)) basicRules

replaceAll :: (Eq a) => ([a], [a]) -> [a] -> [ [a] ]
replaceAll (src,dst) xs =
   map (\(prefix,suffix) ->
           prefix ++ dst ++ drop (length src) suffix) $
   filter (isPrefixOf src . snd) $
   zip (inits xs) (tails xs)

transformAll ::
   [(Product, Forest Product)] -> [(Product, Forest Product)]
transformAll xs =
   do (prod, proofs) <- xs
      let newProof = Node prod proofs
      rule <- rules
      newProd <- replaceAll rule prod
      return (newProd, [newProof])

proof :: Map Product (Forest Product, Forest Product)
proof =
   let step = Map.fromListWith (++) . transformAll . Map.toList
       proofB = iterate step (Map.singleton [B] [])
       proofC = iterate step (Map.singleton [C] [])
   in  head $
       filter (not . Map.null) $
       zipWith (Map.intersectionWith (,)) proofB proofC

main :: IO ()
main =
   putStrLn $ drawForest $
   map (fmap show) $ map (uncurry Node) $
   Map.toList $ fmap fst proof

Main Menu

Moore-Penrose pseudoinverse/Proofs

Relations

Preliminaries

Identity Transformations

Uniqueness of the pseudoinverse

References