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 what follows, it brings great notationaland conceptual 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 Some PropertiesTheorem: 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+= UD+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 be proved using the limit definition of the pseudoinverse.The pro of 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, com-pute the Moore-Penrose pseudoinverse of any matrix (since AATand ATA are symmet-ric). Alternatively, we could compute the pseudoinverse by first computing the SVD ofA as A = UΣVTand then by the first theorem of this section A+= V Σ+UTwhereΣ+="S−100 0#. This is the way it’s done in Matlab; the command is called mpp.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)5. 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#.4 Applications to the Solution of Arbitrary Linear SystemsThe first theorem is fundamental to using pseudoinverses effectively for studying the solutionof arbitrary systems of linear equations.3Theorem: Suppose A ∈ IRm×n, b ∈ IRm. Then R(b) ⊆ R(A) if and only if AA+b = b.Proof: Suppose R(b) ⊆ R(A). Take arbitrary γ ∈ IR so that γb ∈ R(b) ⊆ R(A). Thenthere exists a vector v ∈ IRnsuch that Av = γb. Thus we haveγb = Av = AA+Av = AA+γbwhere one of the Penrose properties is used above. Since γ ∈ IR was arbitrary, we haveshown that b = AA+b. To prove the converse, assume now that AA+b = b. Then it is clearthat b ∈ R(b) and henceb = AA+b ∈ R(A) .We close with some of the principal results concerning existence and uniqueness of solutionsto the general matrix linear system Ax = b, i.e., the solution of m equations in n unknowns.Theorem: (Existence) The linear systemAx = b ; A ∈ IRm×n, b ∈ IRm(3)has a solution if and only if R(b) ⊆ R(A); equivalently, there is a solution to these mequations in n unknowns if and only if AA+b = b.Proof: The subspace inclusion criterion follows essentially from the definition of the rangeof a matrix. The matrix criterion is from the previous theorem.Theorem: (Solution) Let A ∈ IRm×n, B ∈ IRmand suppose that AA+b = b. Then anyvector of the formx = A+b + (I − A+A)y where y ∈ IRnis arbitrary (4)is a solution ofAx = b. (5)Furthermore, all solutions of (5) are of this form.Proof: To verify that (4) is a solution, pre-multiply by A:Ax = AA+b + A(I − A+A)y= b + (A − AA+A)y by hypothesis= b since AA+A = A by the first Penrose condition.That all solutions are of this form can be seen as follows. Let z be an arbitrary solution of(5), i.e., Az = b. Then we can writez ≡ A+Az + (I − A+A)z= A+b + (I − A+A)z4and this is clearly of the form (4).Remark: When A is square and nonsingular, A+= A−1and so (I − A+A) = 0. Thus, thereis no “arbitrary” component, leaving only the unique solution x = A−1b.Theorem: (Uniqueness) A solution of the linear equationAx = b ; A ∈ IRm×n, B ∈ IRm(6)is unique if and only if A+A = I; equivalently, there is a unique solution if and only ifN (A) = 0.Proof: The first equivalence is immediate from the form of the general solution in (4). Thesecond follows by noting that the n × n matrix A+A = I only if r = n where r