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.