# 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?

• By a computer calculation, the determinants also repeat mod 6, and in fact for $n=0\mod 6$ the product is always the identity. Aug 7, 2015 at 19:34
• determinant equals $x^{1+\dots+(2n-1)}=x^{n^2}=(-1)^n$, or what do I miss? Aug 8, 2015 at 17:17

The following is a conjectured generalization of the claimed identity which may help in proving it. We prove this generalization (and hence also the identity from the question) in the case that $3$ does not divide $n$, and give a partial result in the remaining case.

The idea of the generalization 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 $$\mathop{\mathrm{Tr}}\left(\prod_{j=0}^{n-1}\begin{pmatrix} \zeta^{-j} & \zeta^jz \\ 1 & 0 \end{pmatrix}\right)= \begin{cases} -(-1)^n(1+3(\zeta z)^{n/3}) & \text{if } n\equiv0\pmod{3}\\ -(-1)^n & \text{if } n\not\equiv0\pmod{3} \end{cases}.$$ Let $P(z)$ the term on the left hand side. It is clear that $P(z)$ is a polynomial in $z$ of degree at most $n-1$. Cyclically permuting the factors on the left hand side does not change the trace, and neither does conjugating each factor with the same matrix. Set $\delta=\zeta^k$ for some $0\le k\le n-1$. Then $$\begin{pmatrix}1&0\\0&\delta\end{pmatrix} \begin{pmatrix}\zeta^{-j} & \zeta^jz \\1 & 0\end{pmatrix} \begin{pmatrix}1&0\\0&1/\delta\end{pmatrix} = \begin{pmatrix}\zeta^{-j} & \zeta^jz/\delta \\\delta & 0\end{pmatrix}= \delta\begin{pmatrix}\zeta^{-j-k} & \zeta^{j+k}(z\zeta^{-3k}) \\1 & 0\end{pmatrix}.$$ This is a cyclic permutation shifted by $k$, and shows $P(z)=P(z\zeta^{-3k})$ for all $0\le k\le n-1$.

So if $n\not\equiv0\pmod{3}$, then $P(z)$ must be a constant. One easily computes $P(0)$ and obtains the claim.

In the case $3\mid n$, we get that that $P(z)$ is a polynomial in $z^{n/3}$. Also, as the product of any two consecutive factors in $P(z)$ has each matrix entry of degree at most $1$, we see that $P(z)$ actually has degree at most $(n+1)/2$. Thus $P(z)=a_n+b_nz^{n/3}$. We get $a_n=P(0)$. Right now I do not see how to get $b_n$. Maybe one can analyze $P(z)$ for $z\to\infty$, or there is another trick to compute $P(1/\zeta)$ (which should be $\pm4$).

• Thank you very much Peter! Your approach solved the $n \neq 0$ (mod 3) case beautifully! While in your generalized identity, did you mean $3(\zeta z)^{n/3}+1$ on the 2nd line? Aug 8, 2015 at 15:34
• @David Sun: Yes, I fixed the typo. Aug 8, 2015 at 15:53

Lemma 1. Let $\eta$ denote primitive $m$-th root of 1. Consider all $m$-tuples $0\leq a_1<a_2<\dots< a_m\leq 2m$ such that either $a_1>0$ or $a_{m}<2m$. Take the sum of $\eta^{a_1+\dots+a_m}$ over all such $m$-tuples. It equals $3(-1)^{m+1}$.

Proof. Consider the polynomial $$f(x)=(1-x\eta)(1-x\eta^2)\dots (1-x\eta^{2m-1})\cdot \left((1-x)(1-x\eta^{2m})-x^2\eta^{2m}\right).$$ Our sums equals $(-1)^m$ times its coefficient of $x^m$. That is, we have to prove that this coefficient equals $-3$. It is straigthforward: since $(1-x)(1-x\eta)\dots (1-x\eta^{m-1})=1-x^{m}$ and $(1-x\eta)\dots (1-x\eta^{m-1})=1+x+\dots+x^{m-1}$, $$f(x)=(1-x)(1-x^m)^2-x^2(1+x+\dots+x^{m-1}),$$ coefficient of $x^m$ really equals $-3$.

Lemma 2. Let $\eta$ denote primitive $m$-th root of 1. Consider all $m$-tuples $0\leq b_1<b_2<\dots< b_m\leq 3m-1$ such that $b_{i+1}\geq b_i+2$ for $i=1,\dots,m-1$; and either $b_1>0$ or $b_{m}<3m-1$. In other words, pairs $(b_i,b_i+1)$ must be disjont modulo $3m$. Take the sum of $\eta^{b_1+\dots+b_m}$ over all such $m$-tuples. It equals $3$.

Proof. Denote $a_i=b_i-i+1$. It reduces to the previous lemma (and obvious equality $(-1)^{m+1}\eta^{m(m-1)/2}=1$.)

I claim that Peter Mueller's case $n=3m$, $P(z)=a_n+b_nz$ reduces to Lemma 2. Indeed, consider how diagonal element of the product of our matrices may appear and contain $z$ in exponent $m=n/3$. For $m$ matrices we should choose elements
$\zeta^j z$, let them be matrices indexed by $b_1<\dots<b_m$. Then for matrices indexed by $b_1+1,\dots,b_m+1$ we must choose 1, for other matrices $\zeta^{-j}$. This is so if $b_m<n-1$, if $b_m=n-1$, then our diagonal element is in second row and column, hence $b_1\ne 0$. Totally $\zeta$ is taken in a power $$b_1+\dots+b_m-(0+\dots+n-1- (b_1+\dots+b_m+(b_1+1)+\dots+(b_m+1))=m+3(b_1+\dots+b_m)-n(n-1)/2.$$ It remains to denote $\eta=\zeta^3$ and apply Lemma 2.

• Thanks a lot Fedor! These nicely constructed lemmas finish the proof of the $n=3m$ case indeed! BTW, should "$a_{2m}$" in Lemma 1 be "$a_{m}$"? Aug 9, 2015 at 15:32

UPDATE: As pointed out by Peter Mueller in the comments below, this reduction to continuants does not quite work as stated. I still believe that there is some connection with (possibly generalized) continuants and leave this answer as an unsuccessful attempt to demonstrate it (in hope to fix it later).

Notice that $$\begin{pmatrix} x^{-2j} & -x^{2j+1} \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} -x^{2j+1} & 0 \\ 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} -x^{-4j-1} & 1 \\ 1 & 0 \end{pmatrix}.$$ Since diagonal matrices commute with others and $\prod_{j=0}^{n-1} (-x^{2j+1}) = (-1)^n x^{n^2} = 1$, we have $$\prod_{j=0}^{n-1} \begin{pmatrix} x^{-2j} & -x^{2j+1} \\ 1 & 0 \end{pmatrix} = \prod_{j=0}^{n-1} \begin{pmatrix} -x^{-4j-1} & 1 \\ 1 & 0 \end{pmatrix}.$$ The last product can be expressed in terms of continuants $K_m(a_1,\dots,a_m)$. Namely, for $j=0,\dots,n-1$, let $a_{j+1} = -x^{-4j-1}$. Then $$\prod_{j=0}^{n-1} \begin{pmatrix} -x^{-4j-1} & 1 \\ 1 & 0 \end{pmatrix}= \begin{pmatrix} K_n(a_1,\ldots,a_n) & K_{n-1}(a_1,\ldots,a_{n-1}) \\ K_{n-1}(a_2,\ldots,a_n) & K_{n-2}(a_2,\ldots,a_{n-1}) \end{pmatrix}.$$ So, it remains to compute values of these continuats.

P.S. Fedor's answer provides a way to compute the continuants, using Euler's rule.

• @Max Alekseyev: I'm not sure that I believe in this approach. For your identity to hold, it does not suffice that diagonal matrices commute with each other, rather they should also commute with the matrices $\begin{pmatrix} -x^{-4j-1} & 1 \\ 1 & 0 \end{pmatrix}$ which isn't the case though. Aug 10, 2015 at 11:33
• @PeterMueller: Indeed, I was too quick in my derivation. I still believe though that there is a connection with (generalized?) continuants, it may be just deeper and not so straightforward than I anticipated. Aug 10, 2015 at 11:50