Question
Let $A\in\mathbb{R}_{d\times d}$ be some square, non-invertible matrix. Prove that if $b\perp\ker(A^T)$, then the non-homogenous system $Ax=b$ has $\infty$ solutions.
Background
I got this as an "$\iff$" question in my Intro to Machine Learning course in university. I was able to prove the other direction, but no luck on this one. I have previously proved these two lemmas:
$Im(A)=\ker(A^T)^\perp$,
$\ker(A^T)=\ker(AA^T)$.
What I've tried
I got here, but didn't know how to get to continue or if I even should.
$b\perp\ker\left(A^{T}\right)\iff b\perp\ker\left(AA^{T}\right)\\\iff b\perp\ker\left(\left(A^{T}A\right)^{T}\right)\\\iff b\in\ker\left(\left(A^{T}A\right)^{T}\right)^{\perp}\\\iff b\in im\left(A^{T}A\right)$
Any help appreciated, thank!
-Alon
You don't want to bring in $AA^\top$ here. What's relevant is this: Since $A$ is non-invertible, if $Ax=b$ is consistent, it will have infinitely many solutions. Namely: To any particular solution $x_0$ you add any vector $u\in \ker(A)$, and then $A(x_0+u)=A(x_0)+A(u)=b$. Since $\ker(A)$ is at least one-dimensional, there are your infinitely many solutions. But your statement #1 tells you precisely that $b\in\text{Im}(A)$, so the equation $Ax=b$ is consistent (i.e., has at least one solution).