This is *not* a solution, rather it is a conjectured generalization of the claimed identity which may help in proving it:

The idea is to observe that $x^2$ is a primitive $n$-th root of unity, and to replace the factor $-x$ in $-x^{2j+1}=(-x)(x^2)^j$ with a new variable $z$.

Thus let $\zeta$ be a primitive $n$-th root of unity and $z$ be a variable. Then it seems to be the case that
\begin{equation}
\mathop{\mathrm{Tr}}\left(\prod_{j=0}^{n-1}\begin{pmatrix}  
\zeta^{-j} & \zeta^jz \\
1 & 0
\end{pmatrix}\right)=
\begin{cases}
3(1-\zeta^{n/6})z^{n/3}-1 & \text{if } n\equiv0\pmod{6}\\
3(\zeta z)^{n/3} & \text{if } n\equiv3\pmod{6}\\
-(-1)^n & \text{if } n\not\equiv0,3\pmod{6}
\end{cases}.
\end{equation}
For instance, in the case $n\not\equiv0\pmod{3}$, if one could show (by some trick) that the expression does not depend on $z$, then setting $z=0$ would give the answer.