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?
 A: Not a complete answer, but a promising start. Just reformulating the problem using recurrences.
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
$$
