Kenneth Kuttler

174 CHAPTER 8. RANK OF A MATRIX

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 ·AT y

). ■

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

Theorem 8.6.3 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 ∈ ker

(AT)⊥.

Proof: First suppose b ∈ ker(AT)⊥

. Then this says that if AT x = 0, it follows that

b ·x = xT b = 0.

In other words, taking the transpose, if

xT A = 0 then xT 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 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

8.5.28, 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 8.6.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 8.6.4 Let A be an m×n matrix. Then A maps Rn onto Rm if and only if the onlysolution to AT x = 0 is x = 0.

Proof: If the only solution to AT x = 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 solutionfor any b ∈Rm because the b for which there is a solution are those in ker

(AT)⊥ by Theo-

rem 8.6.3. In other words, A maps Rn onto Rm.Conversely if A is onto, then if AT x = 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 8.6.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 AT x = 0.

174 CHAPTER 8. RANK OF A MATRIXProof: This follows right away from the definition of the dot product and matrix multi-plication.(Ax-y) = VAuxiye = y? (A), x1YK = (x-A’y).kl klNow it is time to state the Fredholm alternative. The first version of this is the followingtheorem.Theorem 8.6.3 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 € ker (A’) .Proof: First suppose b € ker (A’) ~ Then this says that if A?x = 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 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 | b )have the same number of zero rows. Thus rank ( A | b ) = rank (A). By Proposition8.5.28, there exists a solution x to the system Ax = b. It remains to prove the converse.Let z € ker (A’) and suppose Ax = b. I need to verify b-z = 0. By Lemma 8.6.2,b-z=Ax-z=x-A’z=x-0=00This implies the following corollary which is also called the Fredholm alternative. The“alternative” becomes more clear in this corollary.Corollary 8.6.4 Let A be anm x n matrix. Then A maps R" onto R" if and only if the onlysolution to A’x = 0 isx =0.Proof: If the only solution to A’ x = 0 is x = 0, then ker (A’ ) = {0} and so ker (A’) t=IR” because every b € IR” has the property that b- 0 = 0. Therefore, Ax = b has a solutionfor any b € R” because the b for which there is a solution are those in ker (A” ) + by Theo-rem 8.6.3. In other words, A maps IR” onto R”.Conversely if A is onto, then if Ax = 0, there exists y such that x = Ay and thenA™ Ay = and so |Ay|” = Ay -Ay = A? Ay-y =0-y =0 and sox=Ay=0.Here is an amusing example.Example 8.6.5 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 an n 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 x such that A? x = 0.