A is a normal operator if $A A^* = A^* A$. This means for any matrix $M$ representing $A$, we have $MM^* = M^*M$. Let $M$ be one such matrix, and $P$ be an invertible but non-unitary matrix.
Then $N=PMP^{-1}$ is the matrix for the same operator wrt a different basis. But now it seems to me it is no longer true that $NN^* = N^*N$. I expand the two sides and get
$$N N^* = P M P^{-1} P^{-1*} M^* P^*$$
which is not the same as
$$N^* N = P^{-1*}M^*P^*PMP^{-1}$$
Where am I going wrong?