The coefficients of the characteristic polynomial of an $n\times n$ matrix $A$, which are invariant with respect to similarity transformations $T A T^{-1}$ (where $T\in GL(n)$), are given by polynomials of traces of powers of $A$.
However, these invariants do not completely characterize a matrix, since two matrices with different Jordan canonical forms can have a same characteristic polynomial. As far as I remember, one actually has to specify the elementary divisors or invariant polynomials of $A$ for a complete characterization.
My question is: can one express all invariants that completely characterize $A$ as polynomials of traces of powers $A^k$?
No. Take any two nilpotent matrices of the same order that are not similar, say $$ A = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}, B = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}. $$
The matrices $A^k$ and $B^k$ (for $k \geq 1$) are also nilpotent and so $\operatorname{tr}( A^k) = \operatorname{tr}(B^k) = 0$ but $A$ and $B$ are not similar.
More generally, if $\lambda_1, \dots, \lambda_n$ are the eigenvalues of $A \in M_n(\mathbb{F})$ (maybe over some splitting field), then $\operatorname{tr}(A^k) = \lambda_1^k + \dots + \lambda_n^k$ are symmetric functions in the eigenvalues of $A$ so any polynomial expression in them will be a polynomial symmetric function in the eigenvalues. The only invariants you'll be able to construct from them are related to the coefficients of the characteristic polynomial (which are also symmetric functions in the eigenvalues) but there are other similarity invariants which don't "depend symmetrically" on the eigenvalues.