# Eigenvalues of a tridiagonal stochastic matrix

I've tried to calculate the eigenvalues of this tridiagonal (stochastic) matrix of dimension $n \times n$, but I had some problems to find an explicit form. I only know that 1 is the largest eigenvalue.

$$M=\dfrac{1}{2}\begin{pmatrix} 1& 1 & & & & \\ 1& 0 &1 & & & \\ & 1 & 0 &1 & & \\ & & & \dots & & \\ & & & 1 & 0 & 1\\ & & & & 1 & 1 \end{pmatrix}$$

(Here, the matrix takes the value 0 where there is no number.)

I'm interested in the value of the second largest eigenvalue as a function of the dimension $n$ of this matrix. I would appreciate any help.

For a matrix so nicely structured, I will bet that it has been studied thoroughly, but we can do the analysis by ourselves. Let $$P=\pmatrix{1&-1\\ &\ddots&\ddots\\ &&\ddots&\ddots\\ &&&\ddots&-1\\ &&&&1}.$$ Then $$PMP^{-1}=\left(\begin{array}{cccc|c} 0&\tfrac12&&\\ \tfrac12&\ddots&\ddots\\ &\ddots&\ddots&\tfrac12\\ &&\tfrac12&0\\ \hline &&&\tfrac12&1\\ \end{array}\right) =\pmatrix{C&0\\ \tfrac12e_{n-1}^\top&1}.$$ $C$ belongs to the class of symmetric tridiagonal Toeplitz matrices. Explicit formula for eigen-decompositions of such matrices are known (cf. the lecture notes written by the late Gene Golub). In particular, the eigenvalues of $C$ are $\cos(k\pi/n)\ (k=1,\,2,\,\ldots,\,n-1)$ and hence the two second largest-sized eigenvalues of $M$ are $\pm\cos(\pi/n)$.
The second largest eigenvalue is $\cos(\pi /n)$.
hint: show that the eigenvalues are the $\cos(k\pi/n), k=0\cdots n-1$.