These notes summarize what transpired in class during the discussion of how, given a ## About

A^{†}k×nmatrixA, to concoct a "bestn×kattempt"A^{†}at finding an inverse forA. The means used for concoctingA^{†}(to be described below, in a moment) include the techniques both of elementary row-reduction and of elementary column-reduction, and result in a matrixA^{†}for which the following two matrix equations hold:

(1)AA^{†}A=A,

(2)A^{†}AA^{†}=A^{†}.

Q.: How close can such a matrixA^{†}actually be to an inverse forA?

A. #1: WhenAhas rankn, it will follow from equation (1) that

Indeed, when(3)A^{†}A=I_{n×n}.

Ahas rankn, all the variables in any equationAx=bare bound, and so any such equation will never have more than one solution. Another way to say this is that fromAx=Ayit always follows thatx=y. Now equation (1) assures us at least that, for each column vectorxinR^{n}, we must haveand so it will follow further thatA(A^{†}Ax) =Ax,from which equation (3) follows.A^{†}Ax=x, for allxinR^{n},

A. #2: WhenAhas rankk, it will follow from equation (1) that

Indeed, when(4)AA^{†}=I_{k×k}.Ahas rankk, allkrows ofAare linearly independent, so that the only way two linear combinationsxAandyAcan be equal,xA=yA(withxandyrow vectors inR_{k}) is forxandyto have been equal:x=y. From (1), of course, it follows that (xAA^{†})A=xA, and soxAA^{†}=x, for allxinR_{n}, which establishes equation (4).

So how do we concoct ourn×kmatrixA^{†}, given an arbitraryk×nmatrixA? We begin by row-reducingAto its fully reduced row-echelon formfrref(A) , and keeping track of thek×kinvertible matrixEthat "records" that row-reduction, i.e., that achievesE A=frref(A) .

Nowfrref(A) has a certain number of non-zero rows --rof them, say (and of course rank(A) is exactly thatr) -- whose "leading 1s" appear in columnsj_{1},j_{2}, ...,j_{i}, ... ,j_{r}, say. Let us now elementarily column-reducefrref(A) by first exchanging columns # 1 and #j_{1}, then exchanging columns # 2 and #j_{2}, then exchanging ... columns #iand #j_{i}, ... and finally exchanging columns #randj_{r}.

The result is ak×nmatrix whose left upperr×rblock isI_{r×r}, whose bottomk−rrows are entirely filled with zeroes, and whose right upperr×(n−r) block is some matrixBor other. And there is ann×ninvertible matrixF_{1}that "records" this column-reduction:

But we're not quite done: further elementary column operations can eliminate the block

I_{r×r}B_{r×(n−r)}frref(A)F_{1}=E A F_{1}=. O_{(k−r)×r}O_{(k−r)×(n−r)}B. Indeed, if we letF_{2}be then×nmatrix given by

then

I_{r×r}− B_{r×(n−r)}F_{2}=, O_{(n−r)×r}I_{(n−r)×(n−r)}F_{2}is invertible (being superdiagonal, its determinant is easily seen to be just 1; as an aside, can you figure out its inverse?), and the fully column-reduced "column-echelon" form offrref(A) comes out, if we writeF=F_{1}F_{2}, as

We now divulge our recipe for

I_{r×r}O_{r×(n−r)}frref(A)F_{1}F_{2}=E A F=. O_{(k−r)×r}O_{(k−r)×(n−r)}A^{†}: asA^{†}take the matrix product of the matrixL_{r}(F) consisting of the first (left-most)rcolumns ofFwith the matrixT_{r}(E) consisting of the first (top-most)rrows ofE:

AsA^{†}=L_{r}(F)T_{r}(E) .L_{r}(F) is ann×rmatrix andT_{r}(E) is anr×kmatrix, their productA^{†}is indeedn×k, as desired, and it only remains to verify equations (1) and (2).

To this end, a little preliminary spade-work is needed. This can be summarized in the observations that, for products of two appropriately sized matricesMandN, we have

and that, so far as the productT_{r}(M N) =T_{r}(M)NandL_{r}(M N) =ML_{r}(N) ,EAFitself is concerned (and you should check this for yourself!),

As for computingL_{r}(EAF)T_{r}(EAF) =EAF.AA^{†}A, let's take on the seemingly harder task of evaluatingEAA^{†}AF:Once we remember thatEAA^{†}AF=EAL_{r}(F)T_{r}(E)AF=L_{r}(EAF)T_{r}(EAF) =EAF.EandFare invertible, with inversesE^{−1}andF^{−1}, respectively, we can finally conclude thatthus confirming equation (1).AA^{†}A=E^{−1}EAA^{†}AFF^{−1}=E^{−1}EAFF^{−1}=A,

Equation (2) is easier: the only preliminary spade-work needed is the observation thatWith this, we simply calculate:L_{r}(T_{r}(EAF)) =I_{r×r}=T_{r}(L_{r}(EAF)) .as needed to be shown.A^{†}AA^{†}= (L_{r}(F)T_{r}(E))A(L_{r}(F)T_{r}(E)) =

=L_{r}(F) (T_{r}(E)AL_{r}(F))T_{r}(E) =L_{r}(F)L_{r}(T_{r}(E)A F)T_{r}(E) =

=L_{r}(F)L_{r}(T_{r}(E A F))T_{r}(E) =L_{r}(F)I_{r×r}T_{r}(E) =L_{r}(F)T_{r}(E) =A^{†},

Amusingly enough,AandA^{†}have the same rank. This follows easily from equations (1) and (2) once one knows, in general, for appropriately sized matricesMandN, that both rank(M N)<rank(M) and rank(M N)<rank(N) . For from (1) you can thereby deduce that rank(A)<rank(A^{†}) , while from (2) you can deduce that rank(A^{†})<rank(A) . Moreover,Aand^{T}A^{†}have not only the same rank, but the same nullity as well (take that as an exercise :-) ).

Last revised: 26 April 2004