If $A\in M_n$ is normal, $A = [A_{ij}]_{i,j=1}^k$, and the eigenvalues of $A$ are those of $A_{ii}\in M_{n_i}$, then $A_{ij}=0,i\neq j$ Let $A\in M_n$ be normal, and partition it into blocks such that $A = [A_{ij}]_{i,j=1}^k$. Now let the eigenvalues of $A$ be those of all $A_{ii}\in M_{n_i}$ combined, in the sense that $p_A(t) = p_{A_{11}}(t)\cdots p_{A_{kk}}(t)$, where $p_A$ is the characteristic polynomial of $A$. Then prove that $A_{ij}=0$ for $i\neq j$, and $A_{ii}$ is normal for each $i=1,\ldots,k$, i.e. that $A$ is block diagonal. This is problem 2.5.P43 form Horn and Johnson's Matrix Analysis.
Honestly I don't know how to properly attack this problem. It is sufficient to prove the $k=2$ case, since the general case follows by induction. The hint suggests using the normality defect, i.e. $A$ normal implies that
$$
\sum_{i=1}^{n_1}|\lambda_i(A_{11})|^2 + \sum_{i=1}^{n_2}|\lambda_i(A_{22})|^2 =\sum_{i=1}^n|\lambda_i(A)|^2= \operatorname{tr}(A^*A)=\operatorname{tr}(A_{11}^*A_{11})+\operatorname{tr}(A_{22}^*A_{22}) + 2\operatorname{tr}(A_{21}^*A_{21}),
$$
but I don't see how this helps. Also, if $A,B$ are given matrices, where $A$ is normal, $p_A\equiv p_B$ and $\operatorname{tr}(A^*A)=\operatorname{tr}(B^*B)$, then $B$ is also normal, but not sure how to use that.
Any additional hints, and not necessarily full solutions, would be greatly appreciated.
 A: I assume we are working over $\mathbb C$.  Consider
$A(\tau) := \begin{bmatrix}A_{1,1} &\tau\cdot  A_{1,2} \\ \tau\cdot A_{2,1} &A_{2,2}\end{bmatrix}$
for $\tau \in [0,1]$
$p_{A(0)}(t) = p_{A_{11}}(t)\cdot p_{A_{2,2}}(t)$
as a basic property of block diagonal matrices.  (Lazy proof: look at block diagonal multiplication and apply Newton's Identities.)
$p_{A(1)}(t) = p_{A_{11}}(t)\cdot p_{A_{2,2}}(t)$
by assumption / the problem statement
$\implies A(1)$ and $A(0)$ have the same eigenvalues.
$\big\Vert A(\tau)\big\Vert_F^2 = \big \Vert A_{1,1}\big \Vert_F^2 + \big \Vert A_{2,2}\big \Vert_F^2 + \tau^2\cdot \big \Vert A_{1,2}\big \Vert_F^2 + \tau^2\cdot \big \Vert A_{2,1}\big \Vert_F^2$ is a monotone increasing function of $\tau$ -- and this is strict when $A(0)\neq A(1)$.
$\big\Vert A(1)\big\Vert_F^2\geq \big\Vert A(0)\big\Vert_F^2\geq \sum_{k=1}^n \vert \lambda_k\vert^2$
where the RHS is Schur's Inequality applied to $A(0)$. But
$\sum_{k=1}^n \vert \lambda_k\vert^2=\big\Vert A(1)\big\Vert_F^2$
by the problem statement since $A(1)$ is normal.
$\implies \big\Vert A(1)\big\Vert_F^2= \big\Vert A(0)\big\Vert_F^2= \sum_{k=1}^n \vert \lambda_k\vert^2\implies A(1)=A(0)$
and since $A(0)=A(1)$ is normal
$\begin{bmatrix}A_{1,1}^*A_{1,1} &\mathbf 0 \\ \mathbf 0 &A_{2,2}^*A_{2,2}\end{bmatrix}=A(0)^*A(0)=A(0)A(0)^*=\begin{bmatrix}A_{1,1}A_{1,1}^* &\mathbf 0 \\ \mathbf 0 &A_{2,2}A_{2,2}^*\end{bmatrix}$
i.e. the diagonal blocks are normal
