Theorem. If $A\in M_m$ and $B\in M_n$ are both normal, so is $A\otimes B$. The converse is true if $A\otimes B\ne 0$.
Proof. Suppose that $A\in M_m$ and $B\in M_n$ are both normal. Then \begin{align*} (A\otimes B)^*(A\otimes B)=(A^*\otimes B^*)(A\otimes B)&=(A^*A)\otimes(B^*B) \\ &=(AA^*)\otimes(BB^*) \\ &=(A\otimes B)(A^*\otimes B^*)=(A\otimes B)(A\otimes B)^*. \end{align*} Therefore, $A\otimes B$ is normal.
Now suppose that $A\otimes B$ is nonzero and normal. Then both $A$ and $B$ are nonzero. Then we have \begin{equation*} (A^*A)\otimes(B^*B)=(AA^*)\otimes(BB^*). \end{equation*} Consider the $i$-th diagonal block of these two products: \begin{equation*} (A^*A)_{ii}(B^*B)=\left(\sum_{j=1}^{n}{|a_{ji}|^2}\right)(B^*B)=\left(\sum_{j=1}^{n}{|a_{ij}|^2}\right)(BB^*)=(AA^*)_{ii}(BB^*). \end{equation*} Summing over all $i$'s, we can get \begin{equation*} \sum_{i=1}^{n}{\left(\sum_{j=1}^{n}{|a_{ji}|^2}\right)(B^*B)}=\sum_{i=1}^{n}{\left(\sum_{j=1}^{n}{|a_{ij}|^2}\right)(BB^*)}, \end{equation*} That is, $$\operatorname{tr}(A^*A)\cdot(B^*B)=\operatorname{tr}(AA^*)\cdot(BB^*).$$ Since $A$ is nonzero, $\operatorname{tr}(A^*A)=\operatorname{tr}(AA^*)\ne 0$, which implies that $B^*B=BB^*$ and hence $A^*A=AA^*$. $\blacksquare$
Can anyone please help to check if my proof is valid? For the converse part, I am not confident whether such method indeed works. Besides, if you have any alternative elegant proofs for this theorem, I would be extraordinarily happy to hear from you!
Note: in what follows, eigenvalues and singular values are always assumed to be sorted by modulus, i.e. $\sigma_k\geq \sigma_{k+1}$ and $\big\vert\lambda_k\big\vert\geq \big\vert \lambda_{k+1}\big \vert$
The key fact is that that
$\sum_{k=1}^m \sigma_k^{(C)}\gt \sum_{k=1}^m \vert\lambda_k^{(C)}\vert $
if $C$ is not normal. (Conversely, of course, if $C$ is normal we have $\sigma_k^{(C)} =\vert\lambda_k^{(C)}\vert $ for all $k$.)
Using the above relationship we compare the singular values with (the modulus of) the eigenvalues of $A\otimes B$ noting that neither matrix is zero so e.g. their nuclear norms (Schatten 1-norms) are non-zero
$\sum_{k=1}^{m\cdot n}\sigma_{A\otimes B}$
$= \Big(\sum_{k=1}^m \sigma_k^{(A)}\big)\big(\sum_{j=1}^n \sigma_{j}^{(B)}\Big)$
$\geq \Big(\sum_{k=1}^m \big\vert \lambda_k^{(A)}\big\vert\Big)\Big(\sum_{j=1}^n \big\vert \lambda_{j}^{(B)}\big\vert\Big)$
$= \sum_{k=1}^{m\cdot n}\big\vert\lambda_{A\otimes B}\big\vert = \sum_{k=1}^{m\cdot n}\sigma_{A\otimes B}\gt 0$
where the final equality follows because $A\otimes B$ is normal. The inequality is met with equality, thus $A$ is normal and $B$ is normal.
deferred proof of the singular value inequality
Using Schur Triangularization we can map $C$ to an upper triangular matrix $T$ with eigenvalues on the diagonal ordered from largest modulus to smallest. Unitary multiplications don't change singular values so $T$ has the same singular values as $C$. Suppose that $C\in GL_m(\mathbb C)$. Further consider $T':=DT$ where $D$ is a unitary diagonal matrix chosen so that $T'$ has positive values on its diagonal.
Since it is invertible, the Polar Decomposition $T'=UP$ is unique. If $U$ and $P$ are simultaneously diagonalizable then $T'$ is unitarily similar to a diagonal matrix so $T'$ is normal which implies $T'$ is diagonal and hence $T$ is diagonal, i.e. $C$ is normal.
Now suppose $U$ and $P$ are not simultaneously diagonalizable: $0\lt \sum_{k=1}^m\vert \lambda_k\vert = \text{trace}\big(T'\big)= \text{trace}\big(UP\big)= \text{trace}\big(U(V\Sigma V^H)\big)= \text{trace}\big((V^HUV)\Sigma\big)$
$= \text{trace}\big(Q\Sigma\big)=\sum_{k=1}^m q_{k,k}\cdot \sigma_k=\big\vert\sum_{k=1}^m q_{k,k}\cdot \sigma_k\big \vert$
$\leq \sum_{k=1}^m \big\vert q_{k,k}\big \vert \cdot \sigma_k $
$\lt \sum_{k=1}^m \sigma_k$
where the inequalities are triangle inequality, and the fact that $Q$ is a unitary non-diagonal matrix, hence it has at least one diagonal component with modulus $\lt 1$ and each $\sigma_k\gt 0$
singular case:
Now suppose $C$ has $M \in\big\{1,2,..,m-1\big\}$ non-zero eigenvalues. (The nilpotent $C$ case is obvious.) $S^{-1}US = S^H CS= \begin{bmatrix} T_{M} &* \\ \mathbf 0& N \end{bmatrix} $ where $N$ is strictly upper triangular.
As before in the non-singular case we can left multiply by a diagonal unitary matrix such that the result is $ \begin{bmatrix} T_{M}' &* \\ \mathbf 0& N \end{bmatrix}$
where $T_{M}'$ is an upper triangular matrix with positive diagonal. This new matrix has the same singular values as before. Then
$\sum_{k=1}^{m} \vert \lambda_k^{(C)}\vert =\text{trace}\left(I \begin{bmatrix} T_{M}' &* \\ \mathbf 0& N \end{bmatrix}\right)\leq \sum_{k=1}^{m} \sigma_k^{(C)}\cdot 1$
by von Neumann Trace Inequality
examining the equality conditions:
$\sum_{k=1}^{m} \vert \lambda_k^{(C)}\vert =\sum_{k=1}^{m} \sigma_k^{(C)}\implies \begin{bmatrix} T_{M}' &* \\ \mathbf 0& N \end{bmatrix}$ must be diagonal
Suppose the above is met with equality.
$T':=\left( \begin{bmatrix} T_{M}' &* \\ \mathbf 0&N \end{bmatrix} + I\right)$
$\text{trace}\big(T'\big) =\sum_{k=1}^{m} \vert \lambda_k^{(C)}\vert + n$
and the sum of singular values (given by Schatten 1 norm which is subadditive):
$\Big \Vert T'\Big\Vert_{S_1} \leq \left \Vert\begin{bmatrix} T_{M}' &* \\ \mathbf 0& N \end{bmatrix}\right\Vert_{S_1} + \left \Vert I\right\Vert_{S_1} = \sum_{k=1}^{m} \sigma_k^{(C)} + n =\sum_{k=1}^m \vert \lambda_k^{(C)}\vert + n$
i.e. $\Big \Vert T'\Big \Vert_{S_1} \leq \text{trace}\big(T'\big)= \vert\text{trace}\big(T'\big)\big \vert $
But $ \vert\text{trace}\big(T'\big)\big \vert \leq \Big \Vert T'\Big \Vert_{S_1}$
(again by multiplying by $T'$ by identity matrix and applying von Neumann Trace Inequality)
$\implies \text{trace}\big(T'\big)= \Big \Vert T'\Big \Vert_{S_1}$
and since $T'$ is invertible, by our earlier argument it is normal, which implies it is diagonal which implies $C$ is normal.
thus
$\sum_{k=1}^{m}\vert \lambda_k^{(C)}\vert \leq \sum_{k=1}^{m} \sigma_k^{(C)}$
with equality iff $C$ is normal