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?

  • $\begingroup$ 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. $\endgroup$ – Mathematician 42 Sep 14 '17 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}$.

| cite | improve this answer | |
  • 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.