By Schur's theorem, a unitary matrix $U$ and an upper triangular matrix $T$ exist such that $A=UTU^H$ , $T$ being diagonal if and only if $A$ is normal. Then $A^HA=UT^HU^HUTU^H=UT^HTU^H$ , which means $A^HA$ and $T^HT$ are similar; so they have the same trace. We have:

$\|A\|_F^2=\operatorname{Tr}(A^HA)=\operatorname{Tr}(T^HT)=\sum_{i=1}^n\left|\lambda_i\right|^2+\sum_{i<j}\left|t_{ij}\right|^2=$

$=\operatorname{Tr}(D^HD)+\sum_{i<j}\left|t_{ij}\right|^2\geq\operatorname{Tr}(D^HD)=\|D\|_F^2.$

If and only if $A$ is normal, $T=D$ and therefore equality holds.$\square$