Prove that if the columns of the $m\times n$ matrix $A$ are linearly independent, then $Ax=b$ has at most one solution.

Prove that if the columns of the $m\times n$ matrix $A$ are linearly independent, then $Ax=b$ has at most one solution.

I was thinking that if the $n$ columns are linearly independent, then the dimension of the column space is $n$, which implies the dimension of the row space is $n$ also. Hence $A$ is $n\times n$, but wouldn't this imply there's exactly one solution of $Ax=b$ rather than at most one?

Is this logic correct, or am I missing something?

• As you say, you can restrict $A$ to a $n\times n$-matrix and find that the restricted system has exactly one solution. However, you are ignoring the extra equations by this restriction process. The system could still be false and have no solutions. Commented Sep 14, 2017 at 8:17

Let $A = \begin{bmatrix}\mathbf{a}_1 & \mathbf{a}_2 & \cdots & \mathbf{a}_n\end{bmatrix}$ and $\mathbf{x} = \begin{bmatrix}x_1\\x_2\\\vdots\\x_n\end{bmatrix}$ and $\mathbf{b} = \begin{bmatrix}b_1\\b_2\\\vdots\\b_m\end{bmatrix}$.

Now, $A\mathbf{x} = x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 + \cdots + x_n\mathbf{a}_n$.

Let $\mathbf{u}$ and $\mathbf{v}$ be two solutions of $A \mathbf{x} = \mathbf{b}$. Then, we have:

$$\begin{cases} u_1 \mathbf{a}_1 + u_2 \mathbf{a}_2 + \cdots + u_n\mathbf{a}_n &=& \mathbf{b} & (1)\\ v_1 \mathbf{a}_1 + v_2 \mathbf{a}_2 + \cdots + v_n\mathbf{a}_n &=& \mathbf{b} & (2) \end{cases}$$

Subtract $(2)$ from $(1)$ to get:

$$(u_1-v_1) \mathbf{a}_1 + (u_2-v_2) \mathbf{a}_2 + \cdots + (u_n-v_n) \mathbf{a}_n = 0$$

Using the fact that $\mathbf{a}_1$ through $\mathbf{a}_n$ are linearly independent, we get $u_1-v_1 = u_2-v_2 = \cdots = u_n-v_n = 0$, i.e. $u_i=v_i$, i.e. $\mathbf{u} = \mathbf{v}$.

• If $b \notin \mathrm{Im}(A)$, the equation $Ax=b$ has no solution. Indeed, the left-hand side of this equality, $Ax$, is by definition an element of $\mathrm{Im}(A)$ whereas the right-hand side is not.

• If $b \in \mathrm{Im}(A)$, you can find $x_0 \in \mathbb{R}^n$ such that $b = Ax_0$. Then, the equation $Ax=b$ becomes $A(x-x_0) = 0$. This means that $x - x_0 \in \mathrm{ker}(A)$. Because the columns of $A$ are linearly independent, the matrix $A$ is invertible ($A$ is a full-rank matrix). As a result, $\mathrm{ker}(A) = \lbrace 0 \rbrace$. It follows that : $x = x_0$.

Therefore, the equation $Ax=b$ has at most one solution.