122 CHAPTER 4. ROW OPERATIONS
4.4 Existence of Solutions to Linear Systems
Consider the linear system of equations,
Ax = b (4.4)
where A is an m× n matrix, x is a n× 1 column vector, and b is an m× 1 column vector.Suppose
A =(
a1 · · · an
)where the ak denote the columns of A. Then x = (x1, · · · , xn)T is a solution of the system4.4, if and only if
x1a1 + · · ·+ xnan = b
which says that b is a vector in span (a1, · · · ,an) . This shows that there exists a solutionto the system, 4.4 if and only if b is contained in span (a1, · · · ,an) . In words, there is asolution to 4.4 if and only if b is in the column space of A. In terms of rank, the followingproposition describes the situation.
Proposition 4.4.1 Let A be an m× n matrix and let b be an m× 1 column vector. Thenthere exists a solution to 4.4 if and only if
rank(A | b
)= rank (A) . (4.5)
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 a row of the form(
0 · · · 0 ⋆)
where ⋆ ̸= 0 in B. Therefore, there will exist a solution to the system 4.4.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 sothey have the same number of nonzero rows. Therefore, the rank of the two matrices in 4.5is the same. ■
4.5 Fredholm Alternative
There is a very useful version of Proposition 4.4.1 known as the Fredholm alternative.I will only present this for the case of real matrices here. Later a much more elegant andgeneral approach is presented which allows for the general case of complex matrices.
The following definition is used to state the Fredholm alternative.
Definition 4.5.1 Let S ⊆ Rm. Then S⊥ ≡ {z ∈ Rm : z · s = 0 for every s ∈ S} . The funnyexponent, ⊥ is called “perp”.
Now note
ker(AT)≡{z : AT z = 0
}=
{z :
m∑k=1
zkak = 0
}
Lemma 4.5.2 Let A be a real m× n matrix, let x ∈ Rn and y ∈ Rm. Then
(Ax · y) =(x·ATy
)