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$?

-
To clarify: A polynomial function $F:M_n(\mathbb C)\to \mathbb C$ is a polynomial in the entries of its argument? – joriki Nov 2 '11 at 5:36
@Joriki: Yes. I believe this is equivalent to viewing $M_n(\mathbb C)$ and $\mathbb C$ as algebraic varieties (affine spaces) and considering regular functions between them. – Aaron Nov 2 '11 at 5:43
Dear @joriki: I see that Aaron has already responded, but here is the (more naive) comment I prepared: Yes. You view $M_n(\mathbb C)$ as a (finite dimensional) vector space. – Pierre-Yves Gaillard Nov 2 '11 at 5:49
Dear Aaron: I answered your question as well as I could. I'm sure there will be better answers, and I'm expecting them with as much impatience as you. - I don't have the slightest idea about the conjugacy classes in $M_n(\mathbb Z)$. That's definitely too complicated form me! (Thanks for your very interesting question, which I upvoted.) – Pierre-Yves Gaillard Nov 2 '11 at 9:54
@Aaron: the proof using eigenvalues extends to non-algebraically closed fields (take the algebraic closure and extend a given polynomial function to the algebraic closure). Is this a sufficiently satisfying answer to your question? – Qiaochu Yuan Apr 30 '12 at 21:20

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

-
This seems very similar to the proof in the question -- it uses algebraic closure, topology and diagonalizability. I understood the question to be asking for a proof that doesn't use those and might apply to $\mathbb R$, $\mathbb Q$ and even $\mathbb Z$. – joriki Nov 2 '11 at 8:18
Dear @joriki: Thanks for your comment. I'm planning to edit the answer. I'll try to prove the statement for an infinite field, without using any word having a topological flavor. Traditionally, polynomial maps are not considered over finite fields. I'm definitely unable to prove the statement over $\mathbb Z$. (Do you think it holds over $\mathbb Z$?) – Pierre-Yves Gaillard Nov 2 '11 at 8:45
@Pierre-YvesGaillard: Thanks for the proof. It is very similar in spirit to my proof, except that you prove the observation in a more algebraic way than I do. However, could you expand your proof of the observation a little? I'm not sure how dg initially enters the picture. Additionally, while I don't know anything about conjugacy classes over Z, I found some notes which talk about how to find the number of conjugacy classes with a given (irreducible) characteristic polynomial, and may have more insight to offer. – Aaron Nov 2 '11 at 15:10
Dear @Aaron: You're welcome. Thanks for your comment. I agree with what you say. I'll take a look at Keith Conrad notes. (By the way, he's an MSE user. See, below this question, the comment to starting with @KCd: Dear Keith. I'm sure he'd have interesting things to say on your questions.) For the observation, if $d(A)\neq0$, then $A$, having $n$ distinct eigenvalues, is diagonalizable, and we have $g(A)=0$. – Pierre-Yves Gaillard Nov 2 '11 at 15:47