First is a useful proposition which tells when there is a solution to a system of equations.
 (7.5) 
It is based on the simple observation that the equation has a solution if and only if the row reduced echelon form of
Proposition 7.6.1 Let A be an m × n matrix and let b be an m × 1 column vector. Then there exists a solution to 7.5 if and only if
 (7.6) 
Proof: Place

where ▾≠0. Therefore, there will exist a solution to the system 7.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 they have the same number of nonzero rows. Therefore, the rank of the two matrices in 7.6 is the same.
Another way to see this is as follows. To say there is a solution to 7.5 is to say that b is in the span of the columns of A which is to say that the rank of A is the rank of
There is a very useful version of Proposition 7.6.1 known as the Fredholm alternative.
The following definition is used to state the Fredholm alternative.
Now note

Here the a_{k} are the rows of A because they are the columns of A^{T}.
Proof: This follows right away from the definition of the dot product and matrix multiplication.

Now it is time to state the Fredholm alternative. The first version of this is the following theorem.
Theorem 7.6.4 Let A be a real m × n matrix and let b ∈ ℝ^{m}. There exists a solution x to the equation Ax = b if and only if b ∈
Proof: First suppose b ∈

In other words, on taking the transpose, if

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
Let z ∈ N

This implies the following corollary which is also called the Fredholm alternative. The “alternative” becomes more clear in this corollary.
Corollary 7.6.5 Let A be an m × n matrix. Then A maps ℝ^{n} onto ℝ^{m} if and only if the only solution to A^{T}x = 0 is x = 0.
Proof: If the only solution to A^{T}x = 0 is x = 0, then N
Conversely if A is onto, then if A^{T}x = 0, there exists y such that x = Ay and then A^{T}Ay = 0 and so
Here is an amusing example.
Example 7.6.6 Let 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

there must be some free variables. Thus there exists a nonzero vector x such that A^{T}x = 0. Hence A^{T} is not one to one and so A is not onto.