$AB=BA$ implies $AB^T=B^TA$ when $A$ is normal I am looking for an elementary proof (if such exists) of the following:
$$
AB=BA \quad\Longrightarrow\quad AB^T=B^TA,
$$
where $A$ and $B$ are $n\times n$ real matrices, and $A$ is a normal matrix, i.e., $AA^T=A^TA$  - it is true for complex matrices as well, with $A^T$ replaced by $A^*$.
There is a non-elementary proof of this using the exponential of a matrix and properties of entire functions.
Update. In the first version of the question, both $A$ and $B$ were supposed to be normal, but as Shlomi correctly pointed out, this is true even in the case when only one of them is normal. 
 A: It suffices to prove the complex case.
Since $A$ is normal, $Ax=\lambda x$ if and only if $A^\ast x=\overline{\lambda}x$.
Now, let $(\lambda,v)$ be an eigenpair of $A$. Then $ABv=BAv=B(\lambda v)=\lambda Bv$. By applying our previous argument to the cases $x=Bv$ and $x=v$ separately, we get $A^\ast Bv=\overline{\lambda}Bv$ and $A^\ast v=\overline{\lambda}v$. Combining the two, we obtain $A^\ast Bv=\overline{\lambda}Bv=B(\overline{\lambda}v)=BA^\ast v$.
Thus $A^\ast B$ and $BA^\ast$ agree at every eigenvector $v$ of $A$. Since $A$ is normal, it has a full eigenbasis. Therefore $A^\ast B=BA^\ast$ or equivalently, $AB^\ast=B^\ast A$.

Remark. Note that the "normality" of $A$ in terms of existence of an orthonormal eigenbasis is essential to the validity of the problem statement. On a vector space where no inner product is defined, the algebraic relations $AA^T=A^TA$ and $AB=BA$ do not lead to the conclusion $AB^T=B^TA$. E.g. over $GF(2)$, if one defines
$$
A=\pmatrix{1&1&1\\ 0&0&1\\ 0&0&1}\ \text{ and }\, B=\pmatrix{0&0&0\\ 0&0&1\\ 0&0&1},
$$
one may verify that $AA^T=A^TA$ (= the all-one matrix) and $AB=BA\,(=B)$, but
$$
AB^T=\pmatrix{0&1&1\\ 0&1&1\\ 0&1&1}\ne0=B^TA.
$$
A: I'm not sure whether this qualifies as "elementary", but here's one way:
Note that $A$ and $B$ form a commuting family of matrices, so that $A$ and $B$ are simultaneously upper-triangularizable. That is, there is some unitary $U$ such that $U^*AU$ and $U^*BU$ are both upper triangular.
Note that $U^*AU$ and $U^*B U$ are both normal and upper-triangular, which means that they are diagonal.  That is, we have
$$
A = U\pmatrix{
\lambda_1 & &\\
&\ddots&\\
&&\lambda_n}U^* \quad
B = U\pmatrix{
\mu_1 & &\\
&\ddots&\\
&&\mu_n}U^*
$$
From here, it is easy to verify that $AB^* = B^*A$.

Alternatively, there's a nice inductive proof here if we use the following two facts:


*

*Commuting matrices have a common eigenvector

*A matrix of the form $\pmatrix{A&B\\0&C}$ is only normal if $B = 0$


With that, we may use the fact that $A$ and $B$ have a common eigenvector to write
$$
A = U\pmatrix{
\lambda_1 & c^T\\
0&\tilde A}
U^* \quad
B = U\pmatrix{
\mu_1 & d^T\\
0&\tilde B}U^*
$$
for a unitary $U$ (whose first column is a common eigenvector to $A$ and $B$).  Because $A$ and $B$ are normal, we see that $c = d = 0$.  Because $A$ and $B$ are commuting normal matrices, $\tilde A$ and $\tilde B$ are (smaller) commuting normal matrices.
By induction, we may conclude (as before) that for some unitary $U$, we have
$$
A = U\pmatrix{
\lambda_1 & &\\
&\ddots&\\
&&\lambda_n}U^* \quad
B = U\pmatrix{
\mu_1 & &\\
&\ddots&\\
&&\mu_n}U^*
$$
and we may reach the desired conclusion, just like last time.
A: Proof when one of them is normal:
Assume that only $A$ is normal. So, there is an orthogonal matrix $P$ such that:
$A=P^*DP$, where $D$ is a diagonal matrix. We shall prove that there is a polynomial $q$, such that: $q(D)=D^*$. The fact, it is true from the interpolation polynomial. Hence, we conclude that: $q(A)=A^*$. Since $AB=BA$ we can prove that $q(A)B=Bq(A)$. Thus, $A^TB=BA^T$ and we are done.
