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 and general
approach is presented which allows for the general case of complex matrices.

The following definition is used to state the Fredholm alternative.

Lemma 4.5.2Let A be a real m × n matrix, let x ∈ ℝ^{n}and y ∈ ℝ^{m}. Then

( T )
(Ax ⋅y) = x ⋅A y

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

∑ ∑ ( T ) ( T )
(Ax ⋅y) = Aklxlyk = A lkxlyk = x ⋅A y .■
k,l k,l

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

Theorem 4.5.3Let A be a real m × n matrix and let b ∈ ℝ^{m}. There exists a solution, xto the equation Ax = bif and only if b ∈ ker

(AT )

^{⊥}.

Proof: First suppose b ∈ ker

( )
AT

^{⊥}. Then this says that if A^{T}x = 0, it follows that
b ⋅ x = x^{T}b = 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 k^{th} position, obtained from the k^{th} row of P times A,
then there is also a zero in the k^{th} position of Pb. This is because the k^{th} position in
Pb is just the k^{th} 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.4Let A be an m × n matrix. Then A maps ℝ^{n}onto ℝ^{m}if and only if theonly solution to A^{T}x = 0isx = 0.

Proof: If the only solution to A^{T}x = 0 is x = 0, then ker

(AT)

=

{0}

and so ker

(AT)

^{⊥} = ℝ^{m}
because every b ∈ ℝ^{m} has the property that b ⋅ 0 = 0. Therefore, Ax = b has a solution for any
b ∈ ℝ^{m} because the b for which there is a solution are those in ker

(AT )

^{⊥} by Theorem 4.5.3. In
other words, A maps ℝ^{n} onto ℝ^{m}.

Conversely if A is onto, then by Theorem 4.5.3 every b ∈ ℝ^{m} is in ker

(AT )

^{⊥} and so if
A^{T}x = 0, then b ⋅ x = 0 for every b. In particular, this holds for b = x. Hence if A^{T}x = 0, then
x = 0. ■

Here is an amusing example.

Example 4.5.5Let A be an m×n matrix in which m > n. Then A cannot map onto ℝ^{m}.

The reason for this is that A^{T} is an n × m where m > n and so in the augmented
matrix

( T )
A |0

there must be some free variables. Thus there exists a nonzero vector x such that A^{T}x = 0.