Trace of power of a real matrix

For each eigenvalue $\lambda_j$ of $A$, write it as $r_je^{2\pi i\alpha_j}$ with $\alpha\in[0,1)$. Recalling that the eigenvalues of $A^k$ are $\lambda_j^k$, and that the trace is the sum of eigenvalues, we see that the real part of $\lambda_j^k$ contributes $r_j^k\cos2k\pi\alpha_j$ to $A^k$'s trace, the complex parts cancelling out.

By the simultaneous Dirichlet's approximation theorem, we can always find integers $n_j$ and a positive integer $k$ such that for all $j$ $$|k\alpha_j-n_j|\le\frac14$$ Rewriting this using $\bmod$, we can always find a single positive integer $k$ such that $$k\alpha_j\bmod1\in[0,1/4]\cup[3/4,1)$$ Once this $k$ is found, $\cos2k\pi\alpha_j\ge0$ for all $j$, whereby all the trace contributions, and thus $A^k$'s trace, become non-negative.

Parcly Taxel gave a pretty solution; Yet, there is an elementary one.

We use the notations of the wikipedia note about the Newton formula; cf.

https://en.wikipedia.org/wiki/Newton%27s_identities

Let $(x_i)_i$ be the roots of a real polynomial, $(e_i)_i$ be the associated elementary symmetric polynomials and $(p_i)_i$ be the associated power sums. Note that $e_k=0$ when $k>n$.

$\textbf{Proposition 1}$. If $p_1<0,\cdots, p_n<0$, then $p_{n+1}\geq 0$.

$\textbf{Proof}$. Assume that $p_{n+1}<0$. According to the newton formulae, $e_1<0,e_2>0,\cdots,(-1)^ne_n>0,(-1)^{n+1}e_{n+1}>0$. In particular, $e_{n+1}\not= 0$, a contradiction.

EDIT. Proposition 1 shows that at least one element of the $(tr(A^k))_{k\leq n+1}$ is $\geq 0$. The following shows that we cannot do better than $n+1$.

$\textbf{Proposition 2}$. The polynomial $Q_n(x)=x^n+x^{n-1}+\cdots+1$ satisfies $p_1=\cdots=p_n=-1,p_{n+1}=n$.