Find conjugation invariant functions without using eigenvalues? 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$?
 A: Let $K$ be an infinite field and $f:M_n(K)\to K$ a polynomial map which is constant on the conjugacy classes. 
Claim. $f$ is a polynomial in the coefficients of the characteristic polynomial. 
We can (and will) assume that $K$ is algebraically closed.
Observation. If a polynomial map $g:M_n(K)\to K$ vanishes on the diagonalizable matrices, then $g=0$. 
Proof of the observation. We have $dg=0$, where $d$ is the discriminant of the characteristic polynomial. As $K$ is infinite, this implies $g=0$. QED
Proof of the claim. 
By the observation, $f$ is determined by its restriction to the diagonal matrices. 
This restriction is invariant by permutation of the diagonal entries. 
Thus, this restriction is a polynomial in the elementary symmetric polynomials in the diagonal entries. 
But these elementary symmetric polynomials are the coefficients of the characteristic polynomial. 
Using again the observation, we see that $f$ itself is a polynomial in the coefficients of the characteristic polynomial. QED
