Diagonalizable matrices A and B with $\mathrm{Tr}(A^k)=\mathrm{Tr}(B^k)$ have the same characteristic polynomial? Let $A$ and $B$ be $n \times n$ matrices with entries in a field F. Suppose $A$ and $B$ are diagonalizable in some extension field E of F and that $\mathrm{Tr}(A^k)=\mathrm{Tr}(B^k)$ for all integers $k>0$. Show that A and $B$ have the same characteristic polynomial.
$A$ and $B$ are diagonalizable over the field E, so there are invertible matrices $R$ and $S$, and diagonal matrices $D_A$ and $D_B$ with entries in E such that $RAR^{-1}=D_A$ and $SBS^{-1}=D_B$
Similar Matrices have the same characteristic polynomial, so if $P_X(\lambda)$ denotes the characteristic polynomial of a matrix X in variable $\lambda$, 
$P_A(\lambda)=P_{D_A}(\lambda)$ and $P_B(\lambda)=P_{D_B}(\lambda)$. We also have
$\mathrm{Tr}(D_A^k)=\mathrm{Tr}((RAR^{-1})^k)=\mathrm{Tr}(RA^kR^{-1})=\mathrm{Tr}(A^k)=\mathrm{Tr}(B^k)=\mathrm{Tr}(D_B^k)$ for all integers $k>0$.
I tried using the Cayley-Hamilton theorem on $P_{D_A}(\lambda)$ and taking the trace, but couldn't get anything out of it.
 A: The statement is false. Consider $A=I_2$ and $B=0$ over $GF(2)$, the field with two elements $1$ and $0$ (with $1+1=0$). Both $A$ and $B$ are diagonal matrices, hence diagonalisable. Also, $\newcommand{\tr}{\operatorname{tr}}\tr(A^k)=\tr(I_2)=1+1=0=\tr(B^k)$ for every positive integer $k$. Yet $A$ and $B$ are not similar to each other. Similar counterexamples apply to other fields and other dimensions when $\tr(I_n)=0$.
The statement is true when the underlying field is infinite. See Martin's or Igor's answers. Martin's answer does not work in all finite fields because we can have $\tr(P(A))=0$ even when $P(A)=I$. Igor's answer does not work in all finite fields because writing the characteristic polynomial of a matrix $X$ in terms of $\tr(X^k)$ requires integer division, which can fail when the field is finite. To illustrate, consider the characteristic polynomial of a $2\times2$ matrix $X$ with eigenvalues $\lambda_1$ and $\lambda_2$. The characteristic polynomial is $x^2 - (\lambda_1+\lambda_2) + \lambda_1\lambda_2$. Formally,
$$
\lambda_1\lambda_2
= \frac12\left[(\lambda_1+\lambda_2)^2 - (\lambda_1^2+\lambda_2^2)\right]
= \frac12\left( \tr(X)^2 - \tr(X^2) \right),
$$
but you cannot divide by $2$ over $GF(2)$ because $2=0$.
A: Since the elementary symmetric functions can expressed through power symmetric functions (in a completely algorithmic way), and the power symmetric functions of the eigenvalues are precisely the traces of $A^k,$ while the elementary symmetric functions are the coefficients of the characteristic polynomial, we are done. What is amusing is that the Newton relations can be proved from the Cayley-Hamilton theorem by taking traces.
A: The equalities $\text{Tr}(A^k)=\text{Tr}(B^k)$ for all $k$ imply that $\text{Tr}(P(A))=\text{Tr}(P(B))$ for all polynomials $P$. 
Let $\lambda$ be an eigenvalue of $A$. If $\lambda$ is not an eigenvalue of $B$, then we can choose a polynomial such that $P(\lambda)=1$, and $P(\mu)=0$ for every other eigenvalue of $A$ and all eigenvalues of $B$. Then we would get $\text{Tr}(P(A))>0$, $\text{Tr}(P(B))=0$, a contradiction. This reasoning implies that $A$ and $B$ have the same lists of eigenvalues. And they have to appear with the same multipliticites: because if $\lambda$ is an eigenvalue of $A$ with multiplicity $n$ and of $B$ with multiplicity $m$, then choosing $P$ with $P(\lambda)=1$ and $P=0$ on all other eigenvalues we have 
$$
n=\text{Tr}(P(A))=\text{Tr}(P(B))=m.
$$
So $A,B$ have the same eigenvalues, with the same multiplicities. In particular, they have the same characteristic polynomial. 
Edit: of course, as user1551 points out in his answer, my answer only works for fields where polynomials separate points. 
