My problem concerns finding a reference in which the formulae for the eigenvalues and the corresponding eigenvectors ($n$ linearly independent eigenvectors!) for the transition matrix of a simple symmetric random walk on a discrete torus $(\mathbb{Z}/n)$ are given; in particular, I'm looking for a reference with the formula $(\star \star)$ below. Let me elaborate a bit more on my problem.
Let $n \in \mathbb{N}$. A simple symmetric random walk on a discrete torus $(\mathbb{Z}/n)$ has the transition matrix $P = [p_{ij}]_{i,j=0}^{n-1}$ given by $$ p_{ij} = \begin{cases}\frac{1}{2} & \mbox{ if } j \equiv i+1 \ ( \!\!\mod n) \\\frac{1}{2} & \mbox{ if } j \equiv i-1 \ (\! \!\mod n) \\0 & \mbox{otherwise} \end{cases}.$$
It is easy to show (cf. Section 12.3, Eigenvalues and Eigenfunctions of Some Simple Random Walks, in D. A. Levin, Y. Peres, and E. L. Wilmer, Markov chains and mixing times. American Mathematical Society, Providence, RI, 2009 that can be accessed from http://yuvalperes.com/) that the eigenvalues of $P$ are given by $$ \lambda_k = \cos\left(\frac{2\pi k}{n} \right)$$ and the corresponding eigenvectors $v_k = (v_k(0), \ldots, v_k(n-1))^T$are given by $$(\star) \ \qquad v_k(j) = \cos \left(\frac{2\pi jk }{n} \right) $$ for $k$, $j \in \{0, \ldots, n-1\}$.
However, $\lambda_k = \lambda_{n-k}$ and similarly $v_k = v_{n-k}$, so from the above result we do not obtain the full system of eigenvectors, that is, the set $\{ v_0, \ldots, v_{n-1}\}$ is linearly dependent and, in particular, it spans a $\lfloor \frac{n}{2}\rfloor +1$ dimensional vector space.
Furthermore, we have that $P$ has $\lfloor \frac{n}{2}\rfloor +1$ distinct eigenvalues, and for even $n$ only $\lambda_0=1$ and $\lambda_{\frac{n}{2}}=-1$ have multiplicity $1$ the other eigenvalues have multiplicity $2$, for odd $n$ only $\lambda_0=1$ has multiplicity $1$ and the other eigenvalue have multiplicity $2$.
One may show that if we replace formula $(\star)$ with $$(\star \star) \qquad v_k(j) = \cos \left( \frac{k(4j-1)}{2n}\pi\right)$$ then we obtain $n$ linearly independent eigenvectors which correspond to $\lambda_k$ for $k \in \{0, \ldots, n-1\}$.
I strongly suspect that this result is also known, but I cannot find any references to it. I would appreciate if someone could provide me with a reference.