Conversely, if $P \in \mathbb{C}[X]$, show, using a Euclidean division of $P$ by a suitably chosen polynomial, that $P(M_n)$ is a circulant matrix.