# Trace of a Product of Finitely Many Matrices with Cosine Entry

Can someone help me prove the following identity? $$\mathop{\mathrm{Tr}}\left(\prod_{j=0}^{n-1}\begin{pmatrix} 2\cos\frac{2j\pi}{n} & -m \\ 1 & 0 \end{pmatrix}\right)= \begin{cases} 2 & \text{if } n=1\pmod{2}\\ 2m^{\frac{n}{2}} & \text{if } n=0\pmod{4}\\ -2m^{\frac{n}{2}}-4 & \text{if } n=2\pmod{4}\\ \end{cases},$$

For the 1st equality, since the product of $2\cos\frac{2j\pi}{n}$'s is 2 when $n$ is odd, we only need to prove that the trace is a constant polynomial in $m$. However, because of the cosine term, the approach of polynomial analysis given in my previous post does not seem to work here.

Situations are the same for the 2nd and 3rd equalities.

• The product is such that the first matrix is the one for $j=0$, etc.? – darij grinberg Aug 22 '15 at 11:45
• The first matrix (when $j=0$) is {{2,-m},{1,0}} – David Sun Aug 22 '15 at 11:49

I believe this can be evaluated by expanding cos as a sum of exponentials.

Let $\zeta=\exp(2i\pi/n)$. Consider the set $X$ of $n$-tuples $x_0,\dots,x_{n-1}\in\{+,-,1,-m\}$ where for each $j$ we require $x_j=1$ if and only if $x_{j-1}=-m$. Subscripts are modulo $n$.

Define $w_j(+)=\zeta^j$ and $w_j(-)=\zeta^{-j}$ and $w_j(1)=1$ and $w_j(-m)=-m$. Expanding $2\cos\frac{2j\pi}{n}=w_j(+)+w_j(-)$ gives the desired trace as $\sum_{x\in X}w(x)$ where $w(x)=\prod_{j=0}^{n-1}w_j(x_j)$.

Cyclicly permuting by moving the end element to the start has the effect of multiplying $w(x)$ by $\zeta^{N_+(x)-N_-(x)}$ where $N_+$ and $N_-$ are the number of $+$'s and $-$'s. The total weight from sequences with $N_+(x)-N_-(x)\not\in\{-n,0,n\}$ is therefore zero.

Now we need another group action. Given $x\in X$ that is not all $+$'s, for each maximal run of $+$'s, move the $-$ or $-m,1$ after the run to the beginning. Each replacement multiplies $w(x)$ by $\zeta^{2k}$ where $k$ is the length of the run, so this procedure gives a sequence $x'$ with $w(x')=w(x)\zeta^{2N_+(x)}$. This shows that the total contribution from all sequences with $(N_+(x),N_-(x))=(a,b)$ is zero whenever $a\not\in\{0,n/2,n\}$. A similar argument applies when $b\not\in\{0,n/2,n\}$.

The only non-constant terms not accounted for are those containing no $+$'s or $-$'s, i.e. $1,-m,1,-m,\dots,1,-m$ and $-m,1,-m,\dots,1,-m,1$ for even $n$, which contribute the $2(-m)^{n/2}$.

• Thanks! I have through your answer and think it makes sense. I have one question though: what does "restricting to $N_+(x)\in \{0,n/2,n\}$" in the final sentence of the penultimate paragraph mean? – David Sun Aug 24 '15 at 9:37
• @DavidSun: I've edited the answer to clarify - what I really wanted to say is that the argument applies for each fixed choice of $(N_+(x),N_-(x))$. I also found a simpler way to move the +'s; I don't think the action described before was quite what is needed. – Colin McQuillan Aug 24 '15 at 18:04
• thanks for the clarification. I still don't quite understand the 4th paragraph, why the effect of moving is multiplication by $\zeta^{N_+(x)-N_-(x)}$ and why the contribution of those sequences is zero? Also, how do you recover -4 from $w(x)$ when $n=2$ (mod 4)? – David Sun Aug 25 '15 at 6:12
• @DavidSun: for the cyclic permutation, consider the product over $w_{j+1}(x_j)=w_j(x_j)\zeta^{p_j}$ where $p_j$ is $1,-1,0,0$ for $+,-,1,-m$ respectively. The existence of any permutation $g$ of a set $Y$ with $w(gx)=Cw(x)$ for fixed $C\neq 1$ proves that $\sum_{x\in Y}w(x)=C\sum_{x\in Y}w(x)$ so $\sum_{x\in Y}w(x)=0$. For the constant term I'd just evaluate it by hand in terms of cos, using $\cos\frac{2\pi (j+n/2)}{n}=-\cos\frac{2\pi j}{n}$ to write the constant term as $(-1)^{n/2}\left[\prod_{j=0}^{n/2-1} 2\cos\frac{\pi j}{n/2}\right]^2=-4$ for $n=2$ (mod 4). – Colin McQuillan Aug 25 '15 at 6:49
• I see how the permutation works now. I've got the -4 term by hand, but confused it with those non-constant terms. Thank you very much! – David Sun Aug 25 '15 at 6:53