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.
 A: 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}$.
A: 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.
A: Let $z\in\mathbb{R}^n$ satisfy the following equation:
$$\|Az-b\|^2=\min_{x\in\mathbb{R}^n}\|Ax-b\|^2>0. $$
By differentiating you obtain as a necessary condition
$$A^TAz-A^Tb=0$$
Define $y\in\mathbb{R}^m$ by
$$y=Az-b.$$
The necessary condition yields
$$A^Ty=0$$
and
$$0<\|Az-b\|^2=\langle Az,Az\rangle-2\langle Az,b\rangle+\langle b,b\rangle=\langle z,A^T(Az-b)\rangle + \langle b,Az-b\rangle$$
By inserting the necessary condition you obtain
$$0<\langle b,Az-b\rangle=b^Ty.$$
