Let $A \in M_n$. Show that $A^*A = AA^*$ if and only if there exists a polynomial $p(t)$ with $p(A) = A^*$.
PROOF: For the forward direction, we want to show that $A$ is normal implies that there exists a polynomial $p(t)$ with $p(A) = A^*$. So, let $A$ be normal, i.e. $A^*A=AA^*$.
We know that $A$ being normal means that it is unitarily diagonalizable, i.e. for some unitary matrix $Q$, we have $A = Q^*\Lambda Q$, where $\Lambda = \text{diag}(\lambda_1, \ldots, \lambda_n)$, and $\lambda_1, \ldots, \lambda_n$ are $n$ pairwise distinct eigenvalues for $A$.
Thus, $A = Q^*\Lambda Q \implies A^* = Q^*\Lambda^*Q$ (just take conjugate transpose of both sides).
Now, from Lagrange interpolation, there exists a unique polynomial $p(t)$ of at most degree $n-1$ such that for each $\lambda_i$, we have $p(\lambda_i) = \bar \lambda_i$ for $i = 1, \ldots, n$. Hence we may write $\displaystyle p(t) = \sum_{i = 0}^{n-1}c_it^i$ for some constants $c_i$. Now, observe that
$$\begin{align}A^* &= Q^*\Lambda^*Q\\ &= Q^*\pmatrix{\bar\lambda_1 & & & \\ & \bar\lambda_2 & & \\ & & \ddots & \\ & & & \bar\lambda_n}Q \\ &=Q^*\pmatrix{p(\lambda_1) & & & \\ & p(\lambda_2) & & \\ & & \ddots & \\ & & & p(\lambda_n)}Q \\ &= Q^*p(\Lambda)Q \\ &= Q^*\left(\sum_{i=0}^{n-1}c_i\Lambda^i\right)Q \\ &= \sum_{i=0}^{n-1}c_i(Q^*\Lambda Q)^i \\&= \sum_{i=0}^{n-1}c_iA^i \\ &= p(A).\end{align}$$ Conversely, assume that there exists a polynomial $p(t)$ with $p(A) = A^*$. Take $\displaystyle p(t) = \sum_{i=0}^{n-1}c_it^i$. Then, $$\begin{align}A^*A &= p(A)A\\&= \left(\sum_{i=0}^{n-1}c_iA^i\right)A \\&= \sum_{i=0}^{n-1}c_iA^{i+1} \\ &= A\sum_{i=0}^{n-1}c_iA^i \\ &= Ap(A) \\&= AA^*.\end{align}$$
Is someone able to verify my proof? Specifically, I want to know... In the forward direction, am I allowed to just say $c_i$ are some constants for my Lagrange interpolating polynomial without finding what they are? After all, it's just a polynomial which has coefficients, so let them be something that gets the job done. Likewise, in the converse, I assume that there exists a polynomial such that $p(A) = A^*$. Am I allowed to just pull $p(t) = \displaystyle \sum_{i=0}^{n-1}c_it^i$ out of thin air and say it's the polynomial that gets the job done?
The use of Lagrange interpolation in this proof was not unmotivated. It is actually a hint given to us to make the problem easier.
Your proof is correct, and to my eyes this appears to be exactly the kind of proof one should provide for a problem like this. I don't think you need to find the $c_i$ or otherwise discuss the existence of a Lagrange interpolating polynomial.
If you find that you'd like to say something about it, it may be worth putting a sentence in there about the invertibility of Vandermonde matrices.