$Ax=b$ has solution for all $b\in\mathbb{R}^m$ iff $A^Tx=0$ has only trivial solution

Question

$A$ is $m\times n$ matrix, I need to show that: $Ax=b$ has solution for all $b\in\mathbb{R}^m$ if and only if $A^Tx=0$ has only trivial solution.

I was trying to apply rank nullity theorem to $A^T$:

$A^T:\mathbb{R}^m\to\mathbb{R}^n$

$\dim\ker(A^T)+\dim \text{Im}(A^T)=m$

now when $A^Tx=0$ has only trivial solution$\Rightarrow\dim\ker(A^T)=0\Rightarrow\dim\text{Im}A^T=m$

Answer 1

Well, first it's important to remember that a linear equation system is only solvable under one of the following conditions:

We denote r := rank(A)

i. r = m

ii. r < m, but $c_i=0$ with $i=r+1,...,m$. Those $c_i$ are the values in $b$ after you used the Gauss-method to get an equation system of the form $Rx=c$.

Since we want to prove your statement for all $b \in \mathbb{R}^n$ we forget about the latter case.

Now we know that we want to have a matrix with rank = m.

Now remember that rank(A) = rank($A^T$). But a matrix has full rank if and only, if the homogenuous system has only the trivial solution. That leads us to the condition $A^Tx = 0$, having the trivial solution only.

Edit: As a small exercise, try to figure out why the condition, to be solvable for any $b$, of a linear equation system is independant of n and what happens in case of n ≠ m = r.

Answer 2

Let $v_1, v_, \dots, v_n$ denote the columns of $A$. Because $Ax = b$ has a solution for all $b\in \mathbb{R}^n$, you must have $\text{span}\{v_i\}_i = \mathbb{R}^n$.

You can also verify that $$ \ker A^T = (\text{span}\{v_i\}_i)^{\perp} = \text{Im}(A)^{\perp}, $$ where $\perp$ denotes the orthogonal complement.

You can conclude from there (what is the complement of $\mathbb{R}^n$ in $\mathbb{R}^n$?)