The Moore-Penrose Pseudoinverse (Math 33A: Laub)In these notes we give a brief introduction to the Moore-Penrose pseudoinverse, a gen-eralization of the inverse of a matrix. The Moore-Penrose pseudoinverse is defined for anymatrix and is unique. Moreover, as is shown in the sequel, it brings great notational andconceptual clarity to the study of solutions to arbitrary systems of linear equations andlinear least squares problems.1 Definition and CharacterizationsWe consider the case of A ∈ IRm×nr. Every A ∈ IRm×nrhas a pseudoinverse and, moreover,the pseudoinverse, denoted A+∈ IRn×mr, is unique. A purely algebraic characterization ofA+is given in the next theorem proved by Penrose in 1956.Theorem: Let A ∈ IRm×nr. Then G = A+if and only if(P1) AGA = A(P2) GAG = G(P3) (AG)T= AG(P4) (GA)T= GAFurthermore, A+always exists and is unique.Note that the above theorem is not constructive. But it does provide a checkable cri-terion, i.e., given a matrix G that purports to be the pseudoinverse of A, one need simplyverify the four Penrose conditions (P1)–(P4) above. This verification is often relativelystraightforward.Example: Consider A ="12#. Verify directly that A+= [15,25]. Note that other leftinverses (for example, A−L= [3 , −1]) satisfy properties (P1), (P2), and (P4) but not (P3).Still another characterization of A+is given in the following theorem whose proof canbe found on p. 19 in Albert, A., Regression and the Moore-Penrose Pseudoinverse, Aca-demic Press, New York, 1972. We refer to this as the “limit definition of the pseudoinverse.”Theorem: Let A ∈ IRm×nr. ThenA+= limδ→0(ATA + δ2I)−1AT(1)= limδ→0AT(AAT+ δ2I)−1(2)12 ExamplesEach of the following can be derived or verified by using the above theorems or characteri-zations.Example 1: A+= AT(AAT)−1if A is onto, i.e., has linearly independent rows (A is rightinvertible)Example 2: A+= (ATA)−1ATif A is 1-1, i.e., has linearly independent columns (A is leftinvertible)Example 3: For any scalar α,α+=(α−1if α 6= 00 if α = 0Example 4: For any vector v ∈ IRn,v+= (vTv)+vT=(vTvTvif v 6= 00 if v = 0Example 5:"1 00 0#+="1 00 0#This example was computed via the limit definition of the pseudoinverse.Example 6:"1 11 1#+="14141414#This example was computed via the limit definition of the pseudoinverse.3 Properties and ApplicationsTheorem: Let A ∈ IRm×nand suppose U ∈ IRm×m, V ∈ IRn×nare orthogonal (M isorthogonal if MT= M−1). Then(UAV )+= VTA+UT.Proof: Simply verify that the expression above does indeed satisfy each of the four Penroseconditions.Theorem: Let S ∈ IRn×nbe symmetric with UTSU = D, where U is orthogonal and Dis diagonal. Then S+= U D+UTwhere D+is again a diagonal matrix whose diagonalelements are determined according to Example 3.Theorem: For all A ∈ IRm×n,1. A+= (ATA)+AT= AT(AAT)+2. (AT)+= (A+)T2Both of the above two results can b e proved using the limit definition of the pseudoinverse.The proof of the first result is not particularly easy nor does it have the virtue of beingespecially illuminating. The interested reader can consult the proof in Albert, p. 27. Theproof of the second result is as follows:(AT)+= limδ→0(AAT+ δ2I)−1A= limδ→0[AT(AAT+ δ2I)−1]T= [limδ→0AT(AAT+ δ2I)−1]T= (A+)TNote now that by combining the last two theorems we can, in theory at least, computethe Moore-Penrose pseudoinverse of any matrix (since AATand ATA are symmetric). Al-ternatively, we could compute the pseudoinverse (and this is the way it’s done in Matlab)by first computing the SVD of A as A = UΣVTand then by the first theorem of thissubsection A+= V Σ+UTwhere Σ+="S−100 0#.The first theorem is also suggestive of a “reverse-order” property for pseudoinverses asfor inverses. Unfortunately, in general,(AB)+6= B+A+.As an example consider A = [0 , 1] and B ="11#. Then(AB)+= 1+= 1whileB+A+= [12,12]"01#=12.However, necessary and sufficient conditions under which the reverse-order property doeshold are known and you can consult the literature for useful results. One particular resultis worth mentioning here.Theorem: If A ∈ IRn×rr, B ∈ IRr×mr, then (AB)+= B+A+.Additional useful properties of pseudoinverses:1. (A+)+= A2. (ATA)+= A+(AT)+, (AAT)+= (AT)+A+3. R(A+) = R(AT) = R(A+A) = R(ATA)4. N (A+) = N (AA+) = N ((AAT)+) = N (AAT) = N (AT)35. If A is normal then AkA+= A+Akfor all k > 0, and (Ak)+= (A+)kfor all k > 0.Note: Recall that A ∈ IRn×nis normal if AAT= ATA. Thus if A is symmetric, skew-symmetric, or orthogonal, for example, it is normal. However, a matrix can be none of thepreceding but still be normal such asA ="1 −11 1#.The next theorem is fundamental to using pseudoinverses effectively for studying thesolution of systems of linear equations.Theorem: Suppose A ∈ IRn×p, B ∈ IRn×m. Then R(B) ⊆ R(A) if and only if AA+B = B.Proof: Suppose R(B) ⊆ R(A) and take arbitrary x ∈ IRm. Then Bx ∈ R(B) ⊆ R(A) sothere exists a vector y ∈ IRpsuch that Ay = Bx. Then we haveBx = Ay = AA+Ay = AA+Bxwhere one of the Penrose properties is used above. Since x was arbitrary, we have shownthat B = AA+B. To prove the converse, assume now that AA+B = B and take arbitraryy ∈ R(B). Then there exists a vector x ∈ IRmsuch that Bx = y, whereupony = Bx = AA+Bx ∈ R(A) .EXERCISES:1. Use the limit definition of the pseudoinverse to compute the pseudoinverse of"1 12 2#.2. If x, y ∈ IRn, show that (xyT)+= (xTx)+(yTy)+yxT.3. For A ∈ IRm×n, prove that R(A) = R(AAT) using only definitions and elementaryproperties of the Moore-Penrose pseudoinverse.4. For A ∈ IRm×n, prove that R(A+) = R(AT).5. For A ∈ IRp×nand B ∈ IRm×nshow that N (A) ⊆ N (B) if and only if BA+A = B.6. Let A ∈ IRn×n, B ∈ IRn×m, and D ∈ IRm×mand suppose further that D is nonsingu-lar.(a) Prove or disprove that"A AB0 D#+="A+−A+ABD−10 D−1#.(b) Prove or disprove that"A B0 D#+="A+−A+BD−10