# Overdetermined linear system solutions

Let $A\in M_{m\times n}(R)$ with $m>n$. Consider that the only solution of the linear homogeneous system $Ax=0_{R^m}$ is the trivial solution $x=0_{R^n}$. Show that linear system $A^ty= b$ have solution $\forall b\in R^n$.

I know that $A$ is a overdetermined system and these are often inconsistent and have no solution, on the other hand $A^t$ is subdeterminated system and generally has at least one solution, but do not know how to prove it.

What is the idea to prove it?

• $\mathbb{R}^n=\mathrm{Im}(A^T)\oplus\mathrm{Ker}(A)$ – Algebraic Pavel Apr 25 '15 at 2:46
• @AlgebraicPavel Honestly I can not see what that would help. – Roland Apr 25 '15 at 12:04

In the following I suppose that $R$ is a field.
Since the only solution of the linear homogeneous system $Ax=0_{R^m}$ is the trivial solution, the columns of $A$ are linearly independent, so the rank of $A$ is $n$. But you know that the rank of $A$ equals the rank of $A^t$, so the rank of $A^t$ is also $n$. (Note that $n$ is the maximum possible rank which $A^t$ can have.) Now notice that the augumented matrix $(A^t\mid b)$ is an $n\times(m+1)$ matrix whose (maximal) rank is $n$ and use the Rouché–Capelli theorem.
• I understand that $rank(A^t)=rank(A)=n$ but how can you ensure that the $rank(A^t|b)=n$? – Roland Apr 25 '15 at 22:19