Let we are given with a matrix A and a vector $b$. Given that there exists a solution of $Ax\leq b$. Show that the solution of $$AA^Ty\leq b$$ also exists.
My Effort: I tried to prove it by contradiction. Suppose that the system $AA^Ty\leq b$ has no solution. This means that for all y, we have that $$AA^Ty>b.$$ This means $$Ax>b\ \forall\ x=A^Ty.$$ How to arrive at a contradiction? Or otherwise how to approach this problem.
1.) in general you have a very useful inequality
$\text{rank}\big(AB\big)\leq \text{rank}\big(A\big)$
this holds because we always have $\text{column space}\big(AB\big) \subseteq \text{column space}\big(A\big)$.
The inequality is met with equality iff $\text{column space}\big(A\big) \subseteq \text{column space}\big(AB\big)$ i.e. iff $\text{column space}\big(A\big) = \text{column space}\big(AB\big)$
2.) set $B:=A^T$ and
$\text{rank}\big(AA^T\big)= \text{rank}\big(A\big)\implies \text{column space}\big(A\big) = \text{column space}\big(AA^T\big)$
(use inner product argument or SVD for LHS)
note: I infer/assume we are working over $\mathbb R$ here
3.) Thus the existence of some $\mathbf x$ such that
$A\mathbf x \leq \mathbf b$ reads: there is a vector in the column space / image of $A$ that is component-wise $\leq \mathbf b$
but since $A$ and $AA^T$ have the same column space / image, then there is a vector in the the column space / image of $AA^T$ that is component-wise $\leq \mathbf b$ (for avoidance of doubt: since said vector exists in the image of $AA^T$, then there is at least one vector in its pre-image, and call this $\mathbf y$.)