Why does $\operatorname{tr}(A^k)=\operatorname{tr}(B^k)$ imply $\operatorname{Spec}(A)=\operatorname{Spec}(B)$? Suppose $A$ and $B$ are two square $n\times n$ matrices over some field. Why do the $n$ equations $$\operatorname{tr}(A^k)=\operatorname{tr}(B^k)\text{ for } 1\leq k\leq n$$
imply that $A$ and $B$ have the same spectra?
If $\operatorname{Spec}(A)=\{\lambda_1,\dots,\lambda_p\}$ and $\operatorname{Spec}(B)=\{\mu_1,\dots,\mu_r\}$, then I know $\operatorname{Spec}(A^k)=\{\lambda_1^k,\dots,\lambda_p^k\}$ and $\operatorname{Spec}(B^k)=\{\mu_1^k,\dots,\mu_r^k\}$, (some of these new eigenvalues may not be distinct). Since the trace is the sum of the eigenvalues, this would give a new set of equations
$$
\sum \lambda_i^k=\sum \mu_i^k
$$
but since these aren't linear I don't think it'll be possible to solve these and show the set of eigenvalues for $A$ and $B$ are the same.
 A: Power sums generate symmetric polynomials: See http://en.wikipedia.org/wiki/Newton's_identities
Therefore the characteristic polynomials of $A$ and $B$, which are symmetric polynomials of the spectra, must be the same. Therefore the two spectra are the same.
A: The spectrum of $A$ and $B$ are the multiset of roots of their characteristic polynomials. If one can show that their characteristic polynomials are equal over the algebraic closure of the base field, then their polynomials are equal over the base field itself and have the same spectra there.
Thus, it suffices to argue that the characteristic polynomial of an $n\times n$ matrix $A$ may be recovered from ($\Leftrightarrow$ is uniquely determined by) its power traces ${\rm tr}(A^k)$ for $1\le k\le n$.
Assume the base field is algebraically closed. Then ${\rm tr}(A^k)=p_k(\lambda_1,\cdots,\lambda_n)$ is the $k$th power sum polynomial in the full spectrum of $A$. In the theory of symmetric polynomials, Newton's identities as Serkan notes show that the elementary symmetric polynomials satisfy a linear recursion that allows them to be expressed as polynomials in the $p_k$. Vieta's formulas say that the coefficients of the characteristic polynomial of $A$ is determined by the elementary symmetric polynomials in the full spectrum, and in turn we have seen these $e_i$ are determined by the $p_k$ equal to the  traces.
Newton's identities can be proved using generating functions. Wikipedia even has a section on their application to matrices and their traces. However I am not sure if the desired conclusion here is true when the characteristic of the base field is positive $\le n$.
