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$.

  • 3
    $\begingroup$ Hi, could you please add some explanation why this is the case, or give a reference? $\endgroup$ – Johannes Kloos Sep 17 '13 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.