@HallsofIvy: is this meant to be a counter-example? With this A, I get A*A=I (the identity matrix), which has trace equal to 2.
My proof: for an arbitrary matrix A, the product A*A is self-adjoint (because (A*A)*=A*A) and positive semidefinite (because (A^*Av,v)=(A^*v,A^*v)=\|A^*v\|^2=\|Av\|^2). Hence A*A has an orthonormal basis of eigenvectors, i.e. is diagonalizable with non-negative eigenvalues. The trace is then the sum of the eigenvalues, which is non-negative.