Relationship between the eigenvalues of $A^T A$ and the maximum eigenvalue of $A$ Let $A$ be an $n\times n$ matrix and $\lambda_\max$ be the maximum eigenvalue of $A$. The trace of $A^T A$ is equal to the sum of its eigenvalues. I am trying to show that $$ \lambda_\max \le \text {tr}( A^TA)$$
It holds that $A$ and $A^T$ have the same eigenvalues. However, I don't know what to say about the eigenvalues of $A^T A$. I cannot come up with a relationship between them and the eigenvalues of $A$. Any ideas on where to start are appreciated. 
 A: This identity appears false in general. Consider $$A = \begin{pmatrix} \frac{1}{2} \ \  0 \\ 0 \ \ \frac{1}{3}\end{pmatrix}$$
Then $$\hbox{tr}(A^TA) = \hbox{tr}\begin{pmatrix} \frac{1}{4} \ \  0 \\ 0 \ \ \frac{1}{9}\end{pmatrix} = \frac{13}{36} < \frac{1}{2} = \lambda_{max}$$
Perhaps the result is recoverable if all eigenvalues $\lambda \geq 1$. But that may not be useful to you.
A: Here's a suggestion for where to start: let $v$ be an 
UNIT eigenvector for the largest eigenvalue. Look at 
$$
v^t A^t A v
$$
That simplifies to $\lambda_{max}^2$. 
Now extend $v$ to an orthonormal basis, and look at the matrix for $A$ in that basis, and its trace. Perhaps that'll get you somewhere. 
A: Try to prove $|\lambda_{\max}(A)|\leq\sqrt{\lambda_{\max}(A^TA)}$. That would be easier to do and also true :-)
This is due to the fact that $\lambda_{\max}(A^TA)=\|A\|_2^2$ and the fact that any norm of $A$ consistent with some vector norm  represents an upper bound for the eigenvalues. You can replace the $\lambda_{\max}$ in the square root by the trace of course but you'd get rather an overestimate.
