Kenneth Kuttler

11.6. APPROXIMATIONS 199

Proof: This follows right away from the definition of the dot product and matrix multi-plication.

(Ax ·y) = ∑k,l

Aklxlyk = ∑k,l

(AT )

lk xlyk =(x ·ATy

). ■

Now it is time to state the Fredholm alternative. The first version of this is the followingtheorem.

Theorem 11.6.4 Let A be a real m×n matrix and let b ∈Rm. There exists a solution x tothe equation Ax= b if and only if b ∈

(N(AT))⊥.

Proof: First suppose b ∈(N(AT))⊥

. Then this says that if ATx= 0, it follows that

b ·x= xTb= 0.

In other words, on taking the transpose, if

xT A = 0T then xTb= 0.

Thus, if P is a product of elementary matrices such that PA is in row reduced echelon form,then if PA has a row of zeros, in the kth position, obtained from the kth row of P times A,then there is also a zero in the kth position of Pb. This is because the kth position in Pb isjust the kth row of P times b. Thus the row reduced echelon forms of A and

(A | b

)have the same number of zero rows. Thus rank

(A | b

)= rank(A). By Proposition

11.6.1, there exists a solution x to the system Ax= b. It remains to prove the converse.Let z ∈ N

(AT)

and suppose Ax= b. I need to verify b ·z = 0. By Lemma 11.6.3,

b ·z = Ax ·z = x ·ATz = x ·0= 0 ■

This implies the following corollary which is also called the Fredholm alternative. The“alternative” becomes more clear in this corollary.

Corollary 11.6.5 Let A be an m× n matrix. Then A maps Rn onto Rm if and only if theonly solution to ATx= 0 is x= 0.

Proof: If the only solution to ATx= 0 is x= 0, then N(AT)= {0} and so N

(AT)⊥

=Rm because every b ∈Rm has the property that b ·0= 0. Therefore, Ax= b has a solutionfor any b∈Rm because the b for which there is a solution are those in N

(AT)⊥ by Theorem

11.6.4. In other words, A maps Rn onto Rm.Conversely if A is onto, then if ATx= 0, there exists y such that x = Ay and then

AT Ay = 0 and so |Ay|2 = Ay ·Ay = AT Ay ·y = 0 ·y = 0 and so x= Ay = 0. ■Here is an amusing example.

Example 11.6.6 Let A be an m×n matrix in which m > n. Then A cannot map onto Rm.

The reason for this is that AT is an n×m where m > n and so in the augmented matrix(AT |0

)there must be some free variables. Thus there exists a nonzero vector x such that ATx= 0.Hence AT is not one to one and so A is not onto.

11.6. APPROXIMATIONS 199Proof: This follows right away from the definition of the dot product and matrix multi-plication.(Aw-y) =) Auxiye = ¥(A") xiv = (@-ATy).kl klNow it is time to state the Fredholm alternative. The first version of this is the followingtheorem.Theorem 11.6.4 Let A be a real m x n matrix and letb € R”. There exists a solution x tothe equation Ax = b if and only if b € (N (A )) .Proof: First suppose b € (N (A’))~ . Then this says that if A’ 2 = 0, it follows thatb-a=a2'b=0.In other words, on taking the transpose, ifx’ A = 0" then x’ b =0.Thus, if P is a product of elementary matrices such that PA is in row reduced echelon form,then if PA has a row of zeros, in the k” position, obtained from the kK” row of P times A,then there is also a zero in the k"” position of Pb. This is because the k’” position in Pb isjust the k“” row of P times b. Thus the row reduced echelon forms of A and ( A | 6b )have the same number of zero rows. Thus rank ( A | b ) = rank(A). By Proposition11.6.1, there exists a solution x to the system Aw = b. It remains to prove the converse.LetzEN (A’) and suppose Ax = b. I need to verify b- z = 0. By Lemma 11.6.3,b-z=Axn-z=a2-A'z=2-0=08This implies the following corollary which is also called the Fredholm alternative. The“alternative” becomes more clear in this corollary.Corollary 11.6.5 Let A be an m xn matrix. Then A maps R" onto R" if and only if theonly solution to A’ a = 0 is x = 0.Proof: If the only solution to A’ x = 0 is x = 0, then N (A’) = {0} and soN (AT)~ =IR” because every b € IR” has the property that b-0 = 0. Therefore, Az = b has a solutionfor any b € R” because the b for which there is a solution are those in N (A’) + by Theorem11.6.4. In other words, A maps R” onto R”.Conversely if A is onto, then if A? a = 0, there exists y such that 2 = Ay and thenA’ Ay = 0 and so |Ay|" =Ay-Ay=A'Ay-y=0-y=Oandsox=Ay=0.Here is an amusing example.Example 11.6.6 Let A be an m x n matrix in which m > n. Then A cannot map onto R”.The reason for this is that A? is ann x m where m > n and so in the augmented matrix(4"|0)there must be some free variables. Thus there exists a nonzero vector a such that A? a = 0.Hence A? is not one to one and so A is not onto.