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.

Let me identify the matrix $A$ with the linear map $T_A \colon \mathbb{R}^n \rightarrow \mathbb{R}^m$ defined using left multiplication ($T_A(x) = Ax$). There are two basic relations between the kernel and image of $A$ (or, more precisely, $T_A$) and the kernel and image of $A^T$ given by
$$ \ker(A) = \operatorname{im}(A^T)^{\perp}, \operatorname{im}(A) = \ker(A^T)^{\perp}. $$
Let's assume for a second we know those relations. Then $Ax = b$ has no solution if and only if $b \notin \operatorname{im}(A)$ if and only if $b \notin \ker(A^T)^{\perp}$ if and only if there exists $y \in \mathbb{R}^m$ such that $A^T(y) = 0$ and $\left< b, y \right> = b^T y \neq 0$.
Thus, it is enough to prove that $\operatorname{im}(A) = \ker(A^T)^{\perp}$. We don't need the second relation but it is useful to remember and it follows from the first relation by taking $A = A^T$ and using $(A^T)^T = A$ and $(V^{\perp})^{\perp} = V$.
Let $y \in \ker(A^T)$ and let $b \in \operatorname{im}(A)$. Choose $x$ such that $Ax = b$. Then
$$ \left< Ax, y \right> = \left< x, A^T y \right> = 0 $$
which shows that $\operatorname{im}(A) \subseteq \ker(A^T)^{\perp}$. Since
$$ \dim \ker(A^T)^{\perp} = m - \dim(\ker(A^T)) = m - (m - \dim\operatorname{im}(A^T)) = \operatorname{rank}(A^T) = \operatorname{rank}(A) = \dim \operatorname{im}(A)$$
we see that the dimensions of both vectors spaces are equal and so we must have $\operatorname{im}(A) = \operatorname{ker}(A^T)^{\perp}$.
