Toeplitz tridiagonal matrix with $0$s on main diagonal and $1$s on sub/superdiagonal has distinct eigenvalues

Question

$$\begin{pmatrix}0&1&&&\\ 1&\ddots&\ddots&&\\ &\ddots&\ddots&\ddots&\\ &&\ddots&\ddots&1\\ &&&1&0\end{pmatrix}$$

has distinct eigenvalues. Why?

Clearly, the eigenvalues should be reals. How to show they are distinct? It seems hard to factor the eigenpolynomial.

Answer 1

In general, consider any Hermitian tridiagonal matrix $H\in M_n(\mathbb C)$ with an entrywise nonzero super-diagonal. If $H$ has a repeated eigenvalue $\lambda$, then $\operatorname{rank}(H-\lambda I)\le n-2$. (You may diagonalise $H$ to see this.) But this is impossible because the top-right $(n-1)\times(n-1)$ submatrix of $H-\lambda I$ is a nonsingular bidiagonal matrix. Hence all eigenvalues of $H$ are distinct.

Answer 2

Googling for eigenvalues and tridiagonal matrices led me to this MO post which then links to this paper:

Kulkarni, Devadatta; Schmidt, Darrell; Tsui, Sze-Kai, Eigenvalues of tridiagonal pseudo-Toeplitz matrices, Linear Algebra Appl. 297, No. 1-3, 63-80 (1999). ZBL0939.15002.

The answer to your question follows from Section 2 of this paper. The additional links below are to the relevant sections of Wikipedia.

The characteristic polynomial of your $n\times n$ matrix is basically the $n$th Chebyshev polynomial of the second kind. I illustrate this (for $n=4$ below, only for easy typing), by expanding the determinant along the bottom row and then the rightmost column: $$p_n(\lambda) := \left|\begin{matrix} -\lambda & 1 \\ 1 & -\lambda & 1 \\&1 & -\lambda & 1 \\&&\color{red}1 & \color{darkgreen}{-\lambda } \end{matrix}\right|=\color{darkgreen}{-\lambda} p_{n-1} - \color{red}1\left|\begin{matrix} -\lambda & 1 \\ 1 & -\lambda & \\& 1& 1 \end{matrix}\right| = -\lambda p_{n-1}(\lambda)-p_{n-2}(\lambda)$$ writing $-\lambda = 2x$ and $U_n(x):=p_n(-2x)$, we find $$ U_n(x) = 2x U_{n-1}(x) - U_{n-2}(x)$$ Which is the three-term recurrence for the Cheybyshev polynomials of the second kind. Combining with the initial data that is directly verified $U_2(x) = p_2(-2x) = 4x^2-1$ and $U_3(x) = 8x^3-4x$, $U_n$ are precisely these polynomials.

The roots of the Chebyshev polynomials of the second kind are well known to be $\cos(k\pi/(n+1)),\ k=1,2,\dots,n$: this follows from the formula $U_n(\cos \theta)=\sin((n+1)\theta)/\sin(\theta)$. This immediately gives the eigenvalues as $$-2\cos(k\pi/(n+1)),\quad k=1,2,\dots,n$$ (The minus sign can be dropped by symmetry.)

So one reason why the roots are distinct is because cosine is injective on $(0,\pi)$.