Trace of Product of Powers of $A$ and $A^\ast$ Let $n$ be odd, $\displaystyle v=1,...,\frac{n-1}{2}$ and $\displaystyle \zeta=e^{2\pi i/n}$. 
Define the following matrices:
$$A(0,v)=\left(\begin{array}{cc}1+\zeta^{-v} & \zeta^v+\zeta^{2v}\\ \zeta^{-v}+\zeta^{-2v}&1+\zeta^{v}\end{array}\right),$$
$$A(1,v)=\left(\begin{array}{cc}\zeta^{-1}+\zeta^{-v} & \zeta^{v}\\ \zeta^{-v}&\zeta^{-1}+\zeta^{v}\end{array}\right).$$
$$A(n-1,v)=\left(\begin{array}{cc}\zeta+\zeta^{-v} & \zeta^{2v}\\ \zeta^{-2v}&\zeta+\zeta^v\end{array}\right).$$
I am hoping to calculate for each of these $A$
$$\text{Tr}\left[\left(A^k\right)^*A^k\right]=\text{Tr}\left[\left(A^*\right)^kA^k\right].$$
All I have is that $A$ and $A^*$ in general do not commute so I can't simultaneously diagonalise them necessarily. 
I do know that if we write $A=D+(A-D)$ (with $D$ diagonal), that
$$A^*=\overline{D}+(A-D).$$
I suppose anybody who knows anything about calculating $$\text{Tr}(A^kB^k)$$ can help.
Context: I need to calculate or rather bound these traces to calculate a distance to random for the convolution powers of a $\nu\in M_p(\mathbb{G}_n)$ for $\mathbb{G}_n$ a series of quantum groups of dimension $2n^2$ ($n$ odd). For $u=2,...,k-2$, $A(u,v)$ is diagonal so no problems there.
 A: The first case is easy. Let $A:=A(0,v)$ and write
$$A=
\left(1+\zeta^v\right)\left(\begin{array}{cc}\zeta^{-v} & \zeta^v \\
\zeta^{-2v} & 1\end{array}\right)=\left(1+\zeta^v\right) \alpha^T\otimes \beta
,$$
where $\alpha=\left(1\;\;\zeta^{-v}\right)$, $\beta=\left(\zeta^{-v}\;\; \zeta^v\right)$. This implies that 
$$A^*=\left(1+\zeta^{-v}\right)\bar{\beta}^T\otimes\bar{\alpha}.$$
That both matrices have rank $1$ reduces the computation of traces to scalar products of $\alpha,\bar{\alpha},\beta,\bar{\beta}$. One has for instance
\begin{align}
\operatorname{Tr}\left(\left(A^*\right)^kA^k\right)&=
\left(1+\zeta^v\right)^k\left(1+\zeta^{-v}\right)^k \left(\bar\alpha \cdot \bar{\beta}^T\right)^{k-1}\left(\bar{\alpha}\cdot \alpha^T\right)\left(\beta\cdot \alpha^T\right)^{k-1}\left(\beta\cdot\bar{\beta}^T\right)=\\
&=4\left(1+\zeta^v\right)^{2k-1}\left(1+\zeta^{-v}\right)^{2k-1}.
\end{align}
In the other two cases, I do not see a clever method, but a straightforward approach would work as well. Diagonalize $A,A^*$ as
$$A=PDP^{-1},\qquad A^*=P^{-*}\bar{D}P^*,$$
then
$$\operatorname{Tr}\left(\left(A^*\right)^kA^k\right)=
\operatorname{Tr}\left(PD^kP^{-1}P^{-*}\bar{D}^kP^*\right),$$
with $D$, $\bar{D}$ diagonal. Thus one only needs to compute diagonalizing transformation $P$ built from the eigenvectors of $A$ and then to compute the trace of the product of six matrices.
A: Solution for $A_0 = A(0,v)$
\begin{align*}
 A_0 &= 
 \begin{pmatrix}
 1+\zeta^{-v} & \zeta^v + \zeta^{2v} \\ 
 \zeta^{-v}+\zeta^{-2v}  & 1+\zeta^v
 \end{pmatrix}
 =
 (\zeta^{-\frac{1}{2}v}+\zeta^{+\frac{1}{2}v})
 \begin{pmatrix}
 \zeta^{-\frac{1}{2}v}  & \zeta^{\frac{3}{2}v}  \\ 
 \zeta^{-\frac{3}{2}v}  & \zeta^{\frac{1}{2}v}
 \end{pmatrix}
 \\
 &=: \lambda \hat{A}_0
 \\
 \hat{A}^2_0
 &= 
 \begin{pmatrix}
 \zeta^{-\frac{1}{2}v}  & \zeta^{\frac{3}{2}v}  \\ 
 \zeta^{-\frac{3}{2}v}  & \zeta^{\frac{1}{2}v}
 \end{pmatrix}^2
 =
 \begin{pmatrix}
 1+\zeta^{-v} & \zeta^v + \zeta^{2v} \\ 
 \zeta^{-v}+\zeta^{-2v} & 1+\zeta^v
 \end{pmatrix}
 \\
 &= A_0
 \\
 \implies A_0^2 &= \lambda^2 \hat{A}_0^2 = \lambda^2 A_0
 \\
 \implies A_0^k &= \lambda^{2(k-1)} A_0
\end{align*}
Moreover note that $\lambda$ is real. In fact, $\lambda=2\cos(\frac{v}{n}\pi)$. Therefore:
\begin{equation*}
{\tt tr}((A_0^*)^kA_0^k)) = \lambda^{4(k-1)}{\tt tr}(A_0^* A_0) = 4\lambda^{4(k-1)}
\end{equation*}
Note that $\lambda^2 = (\zeta^{-\frac{1}{2}v}+\zeta^{+\frac{1}{2}v})^2 = (1+\zeta^v) (1+\zeta^{-v})$, hence the solution is equivalent to one by Start wearing purple.
Solution for $A_1 = A(1,v)$
\begin{align*}
 A_1 &= 
 \begin{pmatrix}
 \zeta^{-1}+\zeta^{-v}& \zeta^v \\ 
 \zeta^{-v}  & \zeta^{-1}+\zeta^v
 \end{pmatrix}
 =
 \zeta^{-1}\begin{pmatrix} 1&0\\0&1 \end{pmatrix}
 +
 \begin{pmatrix}
 \zeta^{-v} & \zeta^{v} \\ 
 \zeta^{-v}  & \zeta^{v}
 \end{pmatrix}
 \\
 &=: \zeta^{-1} I + \hat{A}_1
 \\
 \hat{A}_1^2
 &=
 \begin{pmatrix}
 \zeta^{-2v}+1 & \zeta^{2v}+1 \\ \zeta^{-2v}+1 & \zeta^{2v}+1
 \end{pmatrix}
 =
 (\zeta^{-v} + \zeta^v)
 \begin{pmatrix}
 \zeta^{-v} & \zeta^v \\ \zeta^{-v} & \zeta^v
 \end{pmatrix}
 \\
 &=:
 \mu \hat{A}_1
 \\
 \implies \hat{A}_1^k
 &=
 \mu^{k-1} \hat{A}_1
 \\
 \implies A_1^k
 &=
 \big(\zeta^{-1}I + \hat{A}_1\big)^k
 = \sum_{j=0}^{k}\binom{k}{j} \zeta^{j-k}\hat{A}_1^j
 = \zeta^{-k}\bigg(I + \hat{A}_1 \sum_{j=1}^{k}\binom{k}{j} \zeta^{j}\mu^{j-1}\bigg)
 \\&=
 \zeta^{-k}\bigg(I + \frac{1}{\mu}\hat{A}_1\bigg[-1 + \sum_{j=0}^{k}\binom{k}{j} \zeta^{j}\mu^{j}\bigg] \bigg)
 \\&=
 \zeta^{-k}\bigg(I + \frac{(1-\zeta\mu)^k - 1}{\mu}\hat{A}_1\bigg)
\end{align*}
Here we again have that $\mu=2\cos(2\pi\frac{v}{n})$ is real; moreover we have ${\tt tr}(\hat{A}_1^*) = {\tt tr}(\hat{A}_1) = \mu$ and ${\tt tr}(\hat{A}_1^*\hat{A}_1)=4 $. Hence if we let $\alpha_k = (1-\zeta\mu)^k - 1$ the trace is
\begin{equation*}
{\tt tr}((A_1^*)^kA_1^k)) = 1 + \alpha_k + \bar\alpha_k + \frac{4}{\mu^2}\alpha_k\bar\alpha_k
\end{equation*}
Solution for $A_{n-1} = A(n-1,v)$
\begin{align*}
 A_{n-1} &=
 \begin{pmatrix}
 \zeta+\zeta^{-v}& \zeta^{2v} \\
 \zeta^{-2v} & \zeta + \zeta^{v}
 \end{pmatrix}
 = \zeta \begin{pmatrix} 1&0\\0&1 \end{pmatrix}
 +
 \begin{pmatrix}
 \zeta^{-v}& \zeta^{2v} \\
 \zeta^{-2v} & \zeta^{v}
 \end{pmatrix}
 \\&=:
 \zeta I + \hat{A}_{n-1}
 \\
 \hat{A}_{n-1}^2
 &=
 \begin{pmatrix}
 \zeta^{-2v} + 1   & \zeta^{v}+\zeta^{3v} \\
 \zeta^{-3v} + \zeta^{-v} & \zeta^{2v}+1
 \end{pmatrix}
 =
 (\zeta^{-v} + \zeta^{v})
 \begin{pmatrix}
 \zeta^{-v}& \zeta^{2v} \\
 \zeta^{-2v} & \zeta^{v}
 \end{pmatrix}
 \\&=:
 \mu \hat{A}_{n-1}
 \\
 \implies \hat{A}_{n-1}^k &= \mu^{k-1}\hat{A}_{n-1}
 \\
 \implies A_{n-1}^k &=
 (\zeta I + \hat{A}_{n-1})^k = \ldots\\
 &= \zeta^{k}\bigg(I + \frac{(1-\zeta^{-1}\mu)^k - 1}{\mu}\hat{A}_{n-1}\bigg)
\end{align*}
Here we immediately observe that this is remarkably similar to the previous solution. In fact, since ${\tt tr}(\hat{A}_{n-1}) = \mu$ and ${\tt tr}(\hat{A}_{n-1}^*\hat{A}_{n-1})=4$ aswell, the traces are the same!!
\begin{equation*}
{\tt tr}((A_{n-1}^*)^kA_{n-1}^k)) = 1 + \alpha_k + \bar\alpha_k + \frac{4}{\mu^2}\alpha_k\bar\alpha_k = {\tt tr}((A_1^*)^kA_1^k))
\end{equation*}
