I have a question with respect to random walk penalties in statistics. In Bayesian statistics an adequate prior for modeling a $n$-dimensional random vector $\boldsymbol{x}$ as a random walk of order $d$ is given by $$ p(\boldsymbol{x}|\kappa) \propto \exp\left( -\frac{\kappa}{2}\boldsymbol{x}'\boldsymbol{K}_d\boldsymbol{x} \right) $$ where the $n\times n$ matrix $\boldsymbol{K}_d$ is the structure matrix. For random walks of order one and two we have
\begin{align*} \boldsymbol{K}_{1} & =\left(\begin{array}{ccccc} 1 & -1\\ -1 & 2 & -1\\ & \ddots & \ddots & \ddots\\ & & -1 & 2 & -1\\ & & & -1 & 1 \end{array}\right) & \text{and} & & \boldsymbol{K}_{2} & =\left(\begin{array}{ccccccc} 1 & -2 & 1\\ -2 & 5 & -4 & 1\\ 1 & -4 & 6 & -4 & 1\\ & \ddots & \ddots & \ddots & \ddots & \ddots \\ & & 1 & -4 & 6 & -4 & 1 \\ & & & 1 & -4 & 5 & -2 \\ & & & & 1 & -2 & 1 \\ \end{array}\right). \end{align*} I'm interested in the non-zero Eigenvalues $(\lambda_1,\dots,\lambda_n)$ of these matrices. For $d=1$ you can find the following formula in the literature: $$ \lambda_i = 2 - 2\cos(\pi(i-1)/n), \quad i=1,\dots,n. $$ I'm wondering (a) how this formula can be derived (the only sentence I found in the literature was "it is easily checked ...") and (b) if a similar statement can be made for $d=2$?
I'm thankful for any tips.
Eigenvectors of circulant matrices are Fourier modes. $\mathbf K_1$ isn't quite a circulant matrix, but you can arrange the phase such that the missing entries don't contribute. The eigenvalue formula then follows by
\begin{eqnarray} &&2\sin ax-\sin a(x+1)-\sin a(x-1)\\&=&2\sin ax-\sin ax\cos a-\cos ax\sin a-\sin ax\cos a+\cos ax\sin a\\&=&\sin ax(2-2\cos a)\;. \end{eqnarray}
Unfortunately the same thing won't work for $\mathbf K_2$ because you can't make all four boundary rows come out right with one phase shift. Wolfram|Alpha returns some not very nice eigenvalues for $n=6$ (which should have nice eigenvalues if they could be expressed in terms of multiples of $\pi/6$).