Let $M_n(\mathbb C)$ be the algebra of $n\times n$ complex matrices. The coefficients of the characteristic polynomial $\det(\lambda I-A)=\sum f_i(A)\lambda^i$ are polynomials in the entries of $A\in M_n(\mathbb C)$, and are conjugation invariant. Moreover, every conjugation invariant polynomial function $F:M_n(\mathbb C)\to \mathbb C$ is of the form $P(f_0,f_1,\ldots, f_{n-1})$ for $P\in \mathbb C[x_0,\ldots,x_{n-1}]$.
Here is a proof (hover mouse over to view):
Given a group action on a space, any continuous invariant function must be constant on the closure of each orbit. Because the closure of every conjugacy class contains a diagonal matrix, the entries of which are the eigenvalues of the matrices in the conjugacy class, invariant functions must be polynomials in the eigenvalues. Given any permutation $\sigma\in S_n$, we have that $\operatorname{diag}(a_1,\ldots, a_n)$ is conjugate to $\operatorname{diag}(a_{\sigma(1)},\ldots, a_{\sigma(n)})$, and hence an invariant function must be a symmetric function in the eigenvalues. The coefficient $f_i(A)$ is up to a sign the $(n-i)$th elementary symmetric function in the eigenvalues of $A$, and since the elementary symmetric functions generate the ring of all symmetric functions, the result follows.
Is there a proof that doesn't require reducing the problem to eigenvalues and symmetric functions? Perhaps more important, can the result be extended to non-algebraically closed fields or other base rings where this particular proof fails because we don't have diagonalization? If not, what additional conjugation-invariant polynomial functions are there over $\mathbb R$, $\mathbb Q$, or $\mathbb Z$?