For linear equation $\bf A x = b$, why can't there be more than one but less than infinitely many solutions for a particular $\bf b$?

Question

I am reading Ian Goodfellow's Deep Learning. I am in chapter 1 about Linear Algebra. There is the section called Linear Dependence and Span, they say that for a linear equation $\bf Ax = b$ there can be only one solution, no solution or infinitely many solutions. But there can't be more than one solution and less than infinitely many solutions. How so?

Here, $\bf A$ is a matrix, whereas $\bf b$ and $\bf x$ are vectors.

Answer 1

It is easy to find some examples for the case with $0$, $1$, or $\infty$ many solutions. We will rule out all other cases by using proof via contradiction.

Now, let us assume that we have at least two distinct but not infinitely many solutions for the given equation. Then let us pick $\boldsymbol{x}_1$ and $\boldsymbol{x}_2$ as solutions. Then we construct $\boldsymbol{z} = \boldsymbol{x}_1 +\mu \left[ \boldsymbol{x}_1-\boldsymbol{x}_2\right]$ and show that $\boldsymbol{z}$ allows us to construct infinitely many solutions by only using the two solutions $\boldsymbol{x}_1$ and $\boldsymbol{x}_2$. We can check this by plugging in $\boldsymbol{z}$ into the equation

$$\boldsymbol{A}\boldsymbol{z}=\boldsymbol{A}\boldsymbol{x}_1+\mu\boldsymbol{A}\left[ \boldsymbol{x}_1-\boldsymbol{x}_2\right]=\boldsymbol{b}+\mu \left[\boldsymbol{b}-\boldsymbol{b} \right]=\boldsymbol{b}.$$

We have used $\boldsymbol{Ax}_1=\boldsymbol{Ax}_2=\boldsymbol{b}$ in this derivation. But that is a contradiction that we only have finitely many solutions. Hence, we can conclude that we can only have $0$, $1$ or $\infty$ many solutions.

Answer 2

Think a moment about the 2 dimensional case. What are the possible orientations of two linear equations?

1. They're parallel -- no solution

2. They're on top of eachother -- infinite solutions

3. They intersect at a point -- one solution.

This result is a main theorem in linear algebra, and generalizes to higher dimensions (although they get a little more complicated thinking of the orientations of 3 planes in 3d)

Answer 3

Here is a more general approach, but still not too over the top with mathematical formalism. We can show that:

$Ax=b$ has more than one solution if and only if $Ax=b$ has one solution and $Av=0$ has a non-zero solution. In that case both have infinitely many solutions.

---

Proof: Suppose $Ax=b$ has more than one solution, say $Ax_1=Ax_2=b$. Then $$ A(x_1-x_2)=0 $$ shows that $v=x_1-x_2$ is a non-zero solution to $Av=0$.

For the other implications, suppose $Av=0$ has one non-zero solution $v\neq 0$. Then $A(sv)=0$ and $A(x+sv)=b$ for any scalar $s$ shows that both have infinitely many solutions as promised.

---

In fact, this approach gives us the insight, that the dimensions of the null-space (the solution space to $Av=0$) is precisely what defines the dimensions of the affine subspace that is called the solution set of $Ax=b$.