Rewriting the Hermitian transpose of a normal matrix as a polynomial of that matrix In one of my tutorials today, the tutor said that he read somewhere that the  Hermitian transpose of a complex matrix $A^{H}$ can always be rewritten as a polynomial of $A$, i.e.
$$A^H = \sum_{i = 1}^{n} \alpha_i A^i $$
for some $n \in \mathbb{N}$ and $\alpha_i \in \mathbb{C}$. However he admitted that he has no idea as to why this would be true.
So afterwards, I started searching if I could find this statement somewhere, but to no avail.
So my question, does this statement hold? If not, does it hold if we change some of it slightly?
And if does hold, why?
EDIT: One thing that he or (more likely) I missed is that $A$ should be normal.
 A: This is not true in general. For instance, take
$$
A
=
\begin{bmatrix}
0&1\\
0&0
\end{bmatrix}
$$
Then $A^k = 0$ for $k>1$.
A somewhat similar result is the Caley Hamilton Theorem which states that a matrix satisfies its own characteristic polynomial.
EDIT: Here is a proof sketch of Omnomnomnom's claim.
Suppose $A\in\mathbb{C}^{n\times n}$ is normal so that it is unitarily diagonalizable as $A=UDU^*$. 
Then $A^* = UD^*U^*$ so it suffices to show that for some $m$,
$$
D^* = c_0I + c_1D + \cdots c_{m-1} D^{m-1}
$$
Indeed, let $m$ be the number of distinct entries of $D$ and let $D'$ be the $m\times m$ matrix where we delete duplicate entries of $D$. The set of diagonal matrices of size $m$ form a vector space over $\mathbb{C}$. Moreover, the Vandermonde matrix of size $m\times m$ will be full rank since all entries of $D'$ are distinct. Therefore we can write $D'^*$ as a linear combination of powers of $D'$.
Now, putting back the duplicate entries gives the result. 
If you want the linear combination to start with $D^1$ instead of $D^0$ you need to drop any zero entries of $D$ as well to use the result about Vandermonde matrices, but since these entries will be zero in $D^*$ and all powers of $D$ it is no problem.
Conversely, suppose that 
$$
A^* = \sum_{i=1}^{n} c_i A^i
$$
Then,
$$
AA^* 
= A\left( \sum_{i=1}^{n} c_i A^i \right)
= \left( \sum_{i=1}^{n} c_i A^i \right)A
= AA^*
$$
This proves $A$ is normal.
