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. Commented May 29, 2013 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? Commented Mar 25, 2013 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. Commented Mar 25, 2013 at 13:30
• Ah, I see! This is wonderful. Thanks! Commented Mar 25, 2013 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)$$ Commented May 29, 2013 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! Commented May 29, 2013 at 15:24