Ax=b has no solution - version 3 I am struggling to prove the following theorem which is popped up in a linear optimization textbook,
Theorem : For $A \in \mathbb{R}^{m \times n}, b\in \mathbb{R}^{m}$, $ \quad Ax=b $ has no solution  if and only if there exists a vector $y \in \mathbb{R}^m $ with $ A^Ty =0 $ and $ b^Ty \ne 0.$
Proof : $(\Longleftarrow)$ 
Assuming such a vector $y \in \mathbb{R}^m$ exists, suppose $Ax=b$ has a solution. Then , consider $$ A^Ty = 0  $$
Multiply both sides by $x^T$ and get,
$$ (Ax)^Ty =0$$
Since $Ax=b$,
$$ b^Ty = 0. $$This is a contradiction with $b^Ty\ne0.$ Therefore, our assumption that $Ax=b$ has a solution is wrong.
I could not prove the other way around.($ \Longrightarrow)$. I think that by Gauss-Jordan elimination we should find such vector $y$ with desired property, but I could not proceed. Any help will be appreciated.

Suppose that $A x = b $ has no solution. Consider the column space 
$$U = \{A x \:|\: x \in \Bbb R^n\} \subseteq \Bbb R^m$$
and the vector space $V$ generated by $U$ and $b$. By our assumption, $U$ is a proper subspace of $V$. It follows that the quotient $V/U$ is not trivial and so there exists a nontrivial linear map $V/U \to \Bbb R$. Since linear maps from $V/U$ correspond to linear maps from $V$ which vanish on $U$, you get a nontrivial linear map $V \to \Bbb R$ vanishing on $U$. Since $V$ is generated by $U$ and $b$, this map cannot vanish on $b$. Extending this map to a linear map $f : \Bbb R^m \to \Bbb R$ we find that $f(v) = y^T v$ for some $y \in \Bbb R^m$. We have $y^T A x = 0$ for all $x \in \Bbb R^n$, thus $y^T A = 0$. On the other hand you have $y^T b \neq 0$. Transposing both equations gives you the desired relations.
