198 CHAPTER 11. MATRICES AND THE INNER PRODUCT
11.6 Approximations
11.6.1 Fredholm AlternativeFirst is a useful proposition which tells when there is a solution to a system of equations.
Ax= b (11.5)
It is based on the simple observation that the equation has a solution if and only if the rowreduced echelon form of
(A | b
)has no row of the form
(0 · · · 0 ▼
).
Proposition 11.6.1 Let A be an m× n matrix and let b be an m× 1 column vector. Thenthere exists a solution to 11.5 if and only if
rank(
A | b)= rank(A) . (11.6)
Proof: Place(
A | b)
and A in row reduced echelon form, respectively B and C.
If the above condition on rank is true, then both B and C have the same number of nonzerorows. In particular, you cannot have in B a row of the form(
0 · · · 0 ▼)
where ▼ ̸= 0. Therefore, there will exist a solution to the system 11.5.Conversely, suppose there exists a solution. This means there cannot be such a row in B
described above. Therefore, B and C must have the same number of zero rows and so theyhave the same number of nonzero rows. Therefore, the rank of the two matrices in 11.6 isthe same.
Another way to see this is as follows. To say there is a solution to 11.5 is to say that b isin the span of the columns of A which is to say that the rank of A is the rank of
(A | b
)because to delete the vector b from the list of column vectors of
(A | b
)does not
change the rank. ■There is a very useful version of Proposition 11.6.1 known as the Fredholm alterna-
tive.The following definition is used to state the Fredholm alternative.
Definition 11.6.2 Let S⊆ Rm. Then S⊥ ≡ {z ∈ Rm : z ·s= 0 for every s ∈ S} . The funnyexponent, ⊥ is called “perp”.
Now note
N(AT )≡ {z : ATz = 0
}=
{z :
m
∑k=1
zkak = 0
}Here the ak are the rows of A because they are the columns of AT .
Lemma 11.6.3 Let A be a real m×n matrix, let x ∈ Rn and y ∈ Rm. Then
(Ax ·y) =(x·ATy
)