Proof: Let $A \in \mathbb{R}^{m \times n}$ a matrix. If $Ax=0$ has infinite solutions then exists $b$ such that $A^Ty=b$ do not have any solutions

Question

Let $A \in \mathbb{R}^{m \times n}$ a matrix and $b \in \mathbb{R}^m$. If $Ax=0$ have infinite solutions then exists $b$ such that the linear system $A^Ty=b$ has no solutions.

I'm very convinced of my first proof attempt, which follows:

Let $\tilde{x}$ be a solution for $Ax=0$. It follows that $A^Ty=b \iff y^TA=b^T \iff y^T(A\tilde{x})=b^T\tilde{x}$. The left-hand side is equal to $0$. Looking at the right-hand side, we have $b^T\tilde{x} = \langle \tilde{x},b \rangle$, which is known that $\forall \ b=\tilde{x} \neq 0, \langle \tilde{x},b \rangle > 0$. In other words, if $b \in \mathscr{N}(A)\backslash\{0\}$ the system has no solutions.

Few days later I tried to prove this again and get the following:

Take $b$ a solution for $Ax=0$, then $A^Ty=b \Rightarrow AA^Ty=Ab=0 \Rightarrow y^TAA^Ty=0 \Rightarrow \langle A^Ty,A^Ty \rangle=0 \iff A^Ty=0$, as $Ax=0$ has infinite solutions, we can take $b$ a non zero vector and there will be no $y$ such that $A^Ty=b$ and $A^Ty=0$.

I'm in a little doubt if my second proof is a valid one, as I could not state the recriprocal.

Answer 1

Your first proof is mostly correct and your second proof seems to be incorrect, as I've explained in my comment.

Here's how I recommend that you rewrite your first proof.

Let $x = \tilde{x}$ be a non-zero solution for $Ax=0$. It follows that for vectors $y \in \Bbb R^m, b \in \Bbb R^n$, $$ A^Ty=b \iff y^TA=b^T \implies y^T(A\tilde{x})=b^T\tilde{x}. $$ The left-hand side, $y^T(A\tilde{x})$, is equal to $0$. However, if we set $b = \tilde x$, then we find that the right-hand side satisfies $$ b^T\tilde x = \tilde x^T\tilde x = \langle \tilde x, \tilde x\rangle > 0. $$ Thus, there exists a vector $b \in \Bbb R^n$ such that $y^T(A\tilde{x})=b^T\tilde{x}$ cannot have a solution. Thus, there exists a vector $b \in \Bbb R^n$ such that the equation $A^Ty = b$ has no solution.