Product of a Finite Number of Matrices Related to Roots of Unity

Does anyone have an idea how to prove the following identity?

$$\mathop{\mathrm{Tr}}\left(\prod_{j=0}^{n-1}\begin{pmatrix} x^{-2j} & -x^{2j+1} \\ 1 & 0 \end{pmatrix}\right)= \begin{cases} 2 & \text{if } n=0\pmod{6}\\ 1 & \text{if } n=1,5\pmod{6}\\ -1 & \text{if } n=2,4\pmod{6}\\ 4 & \text{if } n=3\pmod{6} \end{cases},$$ where $x=e^{\frac{\pi i}{n}}$ and the product sign means usual matrix multiplication.

I have tried induction but there are too many terms in all of four entries as $n$ grows. I think maybe using generating functions is the way?

Let $$A_k = \begin{pmatrix} x^{-2k} & -x^{2k+1}\\1 & 0 \end{pmatrix}\\ B = A_0 A_1 \cdots A_{n-1}.$$ I'm going to find the eigenvalues of $B$, so $\operatorname{tr} B = \lambda_1 + \lambda_2$.
Consider a sequence $u_0, u_1, \dots$ and a related sequence $$F_k = \begin{pmatrix}u_k \\ u_{k+1}\end{pmatrix}.$$ Note that $$F_k = A_k F_{k+1}$$ is equivalent to $$u_k = x^{-2k} u_{k+1} - x^{2k+1} u_{k+2}\\ u_{k+1} = u_{k+1}.$$ If $F_n$ is an eigenvector of $B$ then $$\lambda F_n = B F_n = A_0 A_1 \cdots A_{n-1} F_n = \\ = A_0 A_1 \cdots A_{n-2} F_{n-1} = \cdots = A_0 F_1 = F_0$$ or $$\lambda u_n = u_0\\ \lambda u_{n+1} = u_1.$$ Eliminating $\lambda$ one gets the necessary condition $$\frac{u_n}{u_{n+1}} = \frac{u_0}{u_1}.$$ Let $\beta_k = \frac{u_k}{u_{k+1}}$. Then the condition becomes $$\beta_n = \beta_0$$ if $F_n$ is the eigenvector. We already have the recurrence equation for $u_k$, let's derive one for $\beta_k$ (dividing by $u_{k+1}$): $$u_k = x^{-2k} u_{k+1} - x^{2k+1} u_{k+2}\\ \beta_k = x^{-2k} - \frac{x^{2k+1}}{\beta_{k+1}}.$$ Introducing new $\gamma_k = (-x)^{-k}\beta_k,\; \omega \equiv -x^{-3} = x^{n-3}$, $$\gamma_k = \omega^k + \frac{1}{\gamma_{k+1}} \tag1.$$ If $\beta_0 = \beta_n$ then $$\gamma_0 = \beta_0 = \beta_n = (-1)^n x^n \gamma_n = (-1)^{n+1} \gamma_n\\ \gamma_0 = \gamma_{2n}.$$ The condition $\gamma_0 = \gamma_{2n}$ together with recurrence relation $(1)$ gives a quadratic equation for two possible values $\gamma_0, \gamma_0'$, each corresponding to an eigenvalue $\lambda, \lambda'$ of the matrix $B$. The eigenvalues $\lambda, \lambda'$ are related to $\gamma_k, \gamma_k'$ as following $$\lambda = \frac{u_0}{u_n} = \prod_{k=0}^{n-1} \frac{u_k}{u_{k+1}} = \prod_{k=0}^{n-1} \beta_k = \prod_{k=0}^{n-1} (-x)^k \gamma_k = (-x)^{n(n-1)/2}\prod_{k=0}^{n-1} \gamma_k$$
• Thank you very much, uranix! But I am not clear how do you get $\gamma_0$=$\gamma_{2n}$, and how to calculate the product of $\gamma_k$'s in the end. It seems that relation (1) results in a continued fraction. Aug 8 '15 at 6:11
• @DavidSun It's not a continuous fraction, generalized cf at best. Tried that way, but no luck (just getting another interpretation of the same matrix product). $\beta_k$ is $n$-periodic sequence and $\gamma_k = (-1)^{n+1} \gamma_{n + k}$, thus $\gamma_k$ is $2n$ periodic at worst. I see no way to evaluate the product yet Aug 8 '15 at 7:40