Prove that matrix $A\in \mathbb{R}^{n \times n}$ is invertible if $A^T = p(A)$

If $A^T=p(A)$, then $A=p(A^T)=p(p(A))$. Since $p$ and therefore $p\circ p$ has a non-zero constant term, we can rearrange $A=p(p(A))$ to have the constant term (times the identity matrix) alone on one side, and a multiple of $A$ on the other side. Divide by the constant term, and you have something of the form $I=A\cdot q(A)$.

Alternately, $p(p(A))-A=0$ implies that $p(p(x))-x$ must be a multiple of the minimal polynomial of $A$. Since the minimal polynomial thus has a non-zero constant term, $A$ can't have $0$ as an eigenvalue.