Calculating the eigenvalues of a matrix

How to find the eigenvalues of $$\begin{bmatrix} 0 & 1 & & &\\ k & 0 & 2 & &\\ & k-1 & 0 & 3 &\\ & &\ddots&\ddots&\ddots\\ & & &2 & 0 &k \\ & & & & 1 &0 \end{bmatrix}$$
I tried recurrence equation, but it doesn't work to find the characteristic polynomial. Any hint or solution are welcomed, thanks for your help!

PS:The missing parts are all zeroes.

• For searching purposes: these tridiagonal matrices are attributed to Kac, Clement, and Sylvester. – J. M. is a poor mathematician May 29 '13 at 13:12

Let your matrix be $A_{k+1}$ and let $P_{k+1}$ be the $(k+1)\times(k+1)$ matrix $$\begin{pmatrix}1&1\\&\ddots&\ddots\\&&\ddots&1\\ &&&1\end{pmatrix}.$$ Then $P_{k+1}^{-1}A_{k+1}P_{k+1}=B_{k+1}:=\begin{pmatrix}-k&0\\ ke_1&A_k+I_k\end{pmatrix}$, where $e_1=(1,0,0,\ldots,0)^T$ (you may verify that $A_{k+1}P_{k+1}=P_{k+1}B_{k+1}$). Therefore, if $\sigma(\cdot)$ denotes the spectrum of a matrix, we have the recurrence relation $\sigma(A_{k+1})=\{-k\}\cup\left(1+\sigma(A_k)\right)$. So, \begin{align*} \sigma(A_2)&=\{-1,1\},\\ \sigma(A_3)&=\{-2,0,2\},\\ \sigma(A_4)&=\{-3,-1,1,3\},\\ &\vdots\\ \sigma(A_{k+1})&=\{-k,\,-k+2,\,-k+4,\,\ldots,\,k-4,\,k-2,\,k\}. \end{align*}

Edit: There may be a better and more revealing proof. From WolframAlpha, some eigenvectors of $A_{k+1}$ are comprised of signed binomial coefficients (see the results for the cases $k=2$, $k=3$, $k=4$ and $k=5$), so $A_{k+1}$ may possess some interesting mathematical properties that are yet to be discovered.

Edit 2: It turns out that this matrix is called a Kac matrix or a Clement-Kac-Sylvester matrix, and was proposed by Clement (1959) as a matrix for test purposes. See a related question here.

Edit 3: According to Taussky and Todd (1991) (thanks to J.M. for the reference), two elementary proofs of the above result had been given by Muir and Metzler (1933, 1960) and Mazza (1923). Muir and Metzler's proof is strikingly similar to mine. Essentially, it says that if $$F_{k+1}=\begin{pmatrix}1&-1\\&\ddots&\ddots\\&&\ddots&-1\\ &&&1\end{pmatrix},$$ then $F_{k+1}^{-1}A_{k+1}F_{k+1}=\begin{pmatrix}k&0\\ ke_1&A_k-I_k\end{pmatrix}$. In contrast, Mazza's proof essentially says that if $$G_{k+1}=\begin{pmatrix}1&0&-1\\&\ddots&\ddots&\ddots\\&&\ddots&\ddots&-1\\ &&&\ddots&0\\ &&&&1\end{pmatrix},$$ then $G_{k+1}^{-1}A_{k+1}G_{k+1}= \left(\begin{array}{c|c} \begin{array}{cc}0&k\\ k&0\\ \end{array} &{\Large 0}_{2\times(n-2)}\\ \hline B_{k-1}&A_{k-1}\\ \end{array}\right)$ where $B_{k-1}=\begin{pmatrix}0&k-1\\ 0&0\\ \vdots&\vdots\\ 0&0\end{pmatrix}$.

Eigenvectors of $A_{k+1}$ are also well-studied. See J.M.'s comments (thanks to J.M. again).

• Nothing short of brilliance! May I ask how was the conjugation of $A_{k+1}$ with the $P_{k+1}$ matrix motivated? Is this a typical strategy dealing with triadiagonal matrices? – bonsoon Mar 25 '13 at 13:18
• @bonsoon It's a typical strategy to use elementary row operations to reduce the matrix in question to a simpler form, but it's trial and error to find the right operations. – user1551 Mar 25 '13 at 13:30
• Ah, I see! This is wonderful. Thanks! – bonsoon Mar 25 '13 at 13:37
• In particular, the proof in section 2 of this paper also relies on elementary row and column manipulations to prove the recurrence (letting $\mathbf T_n$ denote the $n\times n$ Kac matrix) $$\det(\mathbf T_n-\lambda\mathbf I)=(n-\lambda)\det(\mathbf T_{n-1}-(\lambda+1)\mathbf I)$$ – J. M. is a poor mathematician May 29 '13 at 15:20
• The matrix of eigenvectors of the matrix are also well-studied: they are referred to as the "binomial matrices" or "Krawtchouk matrices", since the entries of the eigenvector matrix can be expressed in terms of the Krawtchouk orthogonal polynomials. For something simple-looking, Kac's matrix is quite rich! – J. M. is a poor mathematician May 29 '13 at 15:24