[proofplan]
We prove both directions of the equivalence. For the forward direction, we show that a nontrivial dependence relation among the columns of $A$ produces two distinct solutions from any single solution. For the reverse direction, we show that if the columns are independent and two solutions exist, then their difference lies in the null space, forcing them to be equal.
[/proofplan]
[step:Show that dependent columns produce multiple solutions from any single one]
Suppose the columns of $A$ are linearly dependent. We show that if $Ax = b$ has a solution, then it has at least two, contradicting the "at most one" condition.
Denote the columns of $A$ by $a_1, \ldots, a_n \in F^m$, so that for any $x = (x_1, \ldots, x_n)^\top \in F^n$,
\begin{align*}
Ax = x_1 a_1 + x_2 a_2 + \cdots + x_n a_n.
\end{align*}
Since the columns are linearly dependent, there exists a nonzero vector $c = (c_1, \ldots, c_n)^\top \in F^n$ such that
\begin{align*}
c_1 a_1 + c_2 a_2 + \cdots + c_n a_n = 0,
\end{align*}
i.e., $Ac = 0$ with $c \neq 0$.
Suppose $x_0 \in F^n$ is a solution to $Ax = b$, so $Ax_0 = b$. Define $x_1 := x_0 + c$. Then $x_1 \neq x_0$ since $c \neq 0$, and
\begin{align*}
Ax_1 = A(x_0 + c) = Ax_0 + Ac = b + 0 = b.
\end{align*}
So $x_1$ is also a solution. Therefore the system does not have at most one solution.
Taking the contrapositive: if $Ax = b$ has at most one solution, then the columns of $A$ must be linearly independent.
[guided]
We prove the forward direction by contrapositive: assume the columns of $A$ are linearly dependent, and show the system can have more than one solution.
Write $A = [a_1 \mid a_2 \mid \cdots \mid a_n]$ where $a_1, \ldots, a_n \in F^m$ are the columns. The equation $Ax = b$ can be written as $x_1 a_1 + \cdots + x_n a_n = b$, expressing $b$ as a linear combination of the columns of $A$ with coefficients given by the entries of $x$.
Linear dependence of the columns means there exists a nonzero $c \in F^n$ with $Ac = 0$. Why does this nonzero null-space vector create multiple solutions? Because if $x_0$ is any solution ($Ax_0 = b$), then for $x_1 := x_0 + c$:
\begin{align*}
Ax_1 = A(x_0 + c) = Ax_0 + Ac = b + 0 = b.
\end{align*}
Since $c \neq 0$, we have $x_1 \neq x_0$, so $x_0$ and $x_1$ are two distinct solutions. The key observation is that the solution set of $Ax = b$, when nonempty, is a coset $x_0 + \ker(A)$, and $\ker(A) \neq \{0\}$ precisely when the columns are dependent.
Taking the contrapositive: at most one solution implies linear independence of the columns.
[/guided]
[/step]
[step:Show that independent columns force uniqueness]
Suppose the columns of $A$ are linearly independent, and let $x_0, x_1 \in F^n$ both satisfy $Ax_0 = b$ and $Ax_1 = b$. Define $d := x_0 - x_1 \in F^n$. Then
\begin{align*}
Ad = A(x_0 - x_1) = Ax_0 - Ax_1 = b - b = 0.
\end{align*}
Writing $d = (d_1, \ldots, d_n)^\top$ and $A = [a_1 \mid \cdots \mid a_n]$, the equation $Ad = 0$ reads
\begin{align*}
d_1 a_1 + d_2 a_2 + \cdots + d_n a_n = 0.
\end{align*}
Since the columns $a_1, \ldots, a_n$ are linearly independent, the only solution to this equation is $d_1 = d_2 = \cdots = d_n = 0$, i.e., $d = 0$. Therefore $x_0 = x_1$.
Since any two solutions must be equal, the system has at most one solution.
[guided]
Now we prove the reverse: if the columns of $A$ are linearly independent, then $Ax = b$ has at most one solution.
Suppose for contradiction (or simply by direct argument) that $x_0$ and $x_1$ are both solutions: $Ax_0 = b$ and $Ax_1 = b$. Their difference $d := x_0 - x_1$ satisfies
\begin{align*}
Ad = A(x_0 - x_1) = Ax_0 - Ax_1 = b - b = 0.
\end{align*}
So $d \in \ker(A)$. Writing $A = [a_1 \mid \cdots \mid a_n]$, the equation $Ad = 0$ says $d_1 a_1 + \cdots + d_n a_n = 0$. Linear independence of the columns means the only scalars satisfying this equation are $d_1 = \cdots = d_n = 0$. Thus $d = 0$, i.e., $x_0 = x_1$.
The argument reveals the geometric picture: the solution set of $Ax = b$ (when nonempty) is the affine subspace $x_0 + \ker(A)$. Linear independence of the columns is equivalent to $\ker(A) = \{0\}$, which makes this affine subspace a single point.
[/guided]
[/step]
