I need some help on showing that $A^TA$ has at least one positive eigenvalue if $A$ is not all-zero. $A$ is rectangular and can have dependent columns in general. I can show that it cannot have negative eigenvalues. Here is what I have now.
$$ A^TA\vec x=\lambda \vec x\\ \vec x^TA^TA\vec x=\vec x^T\lambda \vec x\\ ||A\vec x||^2=\lambda||\vec x||^2 $$ Because the two norms are strictly non-negative, $\lambda$ has to be non-negative. However, I cannot guarantee that $||A\vec x||\neq 0$ for at least one $\vec x$. If all eigenvectors of $A^TA$ lies in the null-space of $A$ (which I feel should not be the case), then $\lambda$ is indeed zero for all eigenvectors. So is my feeling wrong or how do I prove it?
Note that $A^TA$ is symmetric and positive semidefinite: for any conforming $v$, it follows that $v^TA^TAv=|Av|^2\geq0$. Thus, the eigenvalues of $A^TA$ are all nonnegative. (We can actually prove this directly by looking at $A^TAv=\lambda v\implies0\leq|Av|^2=\lambda|v|^2$).
So if $A^TA$ doesn't have a positive eigenvalue, then its eigenvalues are all $0$. By the diagonalisation of symmetric matrices, we can infer that $A^TA$ is $0$. But if we inspect the diagonal elements of $A^TA$ and use the matrix multiplication formula, it becomes evident that $A$ itself must be $0$. This is a contradiction, so the claim follows.