Kenneth Kuttler

4.5. FREDHOLM ALTERNATIVE 123

Proof: This follows right away from the definition of the inner product and matrixmultiplication.

(Ax · y) =∑k,l

Aklxlyk =∑k,l

(AT)lkxlyk =

(x ·ATy

). ■

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

Theorem 4.5.3 Let A be a real m× n matrix and let b ∈ Rm. There exists a solution, x

to the equation Ax = b if and only if b ∈ ker(AT)⊥

Proof: First suppose b ∈ ker(AT)⊥. Then this says that if ATx = 0, it follows that

b · x = xTb = 0. In other words, taking the transpose, if

xTA = 0, 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 is

just 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

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

(AT)and suppose Ax = b. I need to verify b · z = 0. By Lemma 4.5.2,

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

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

Corollary 4.5.4 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 ker(AT)= {0} and so

ker(AT)⊥

= Rm

because every b ∈ Rm has the property that b · 0 = 0. Therefore, Ax = b has a solution for

any b ∈ Rm because the b for which there is a solution are those in ker(AT)⊥

by Theorem4.5.3. In other words, A maps Rn onto Rm.

Conversely if A is onto, then by Theorem 4.5.3 every b ∈ Rm is in ker(AT)⊥

and so ifATx = 0, then b · x = 0 for every b. In particular, this holds for b = x. Hence if ATx = 0,then x = 0. ■

Here is an amusing example.

Example 4.5.5 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.

4.5. FREDHOLM ALTERNATIVE 123Proof: This follows right away from the definition of the inner product and matrixmultiplication.(Ax-y) = So Anitiyn = S- (A’) zy, = (x: Ay).kl klNow it is time to state the Fredholm alternative. The first version of this is the followingtheorem.Theorem 4.5.3 Let A be a realm x n matrix and let b € R™. There exists a solution, xto the equation Ax = b if and only if b € ker (AT).Proof: First suppose b € ker (AT). Then this says that if A7x = 0, it follows thatb-x =x’b=0. In other words, 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 k“” 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 | b )have the same number of zero rows. Thus rank ( A | b ) = rank (A). By Proposition4.4.1, there exists a solution x to the system Ax = b. It remains to prove the converse.Let z € ker (AT) and suppose Ax = b. I need to verify b-z = 0. By Lemma 4.5.2,b-z=Ax-z=x-A'’z=x-0=08This implies the following corollary which is also called the Fredholm alternative. The“alternative” becomes more clear in this corollary.Corollary 4.5.4 Let A be anm xn matrix. Then A maps R” onto R™ if and only if theonly solution to ATx = 0 isx =O.Proof: If the only solution to A?x = 0 is x = 0, then ker (A) = {0} and soker (AT)~ = R”because every b € R”™ has the property that b- 0 = 0. Therefore, Ax = b has a solution forany b € R™ because the b for which there is a solution are those in ker (AT)~ by Theorem4.5.3. In other words, A maps R” onto R™.Conversely if A is onto, then by Theorem 4.5.3 every b € R” is in ker (AT)~ and so ifA’x = 0, then b- x = 0 for every b. In particular, this holds for b = x. Hence if A7x = 0,then x = 0. HfHere is an amusing example.Example 4.5.5 Let A be anm xn matrix in which m >n. Then A cannot map onto R™.The reason for this is that A? is an n x m where m > n and so in the augmented matrix(A™|0)there must be some free variables. Thus there exists a nonzero vector x such that A? x = 0.