I recently found a paper which detailed a method of finding the eigenvalues of the $n\times n$ banded Toeplitz matrix
$$ \left[ \begin{array}{ccccccc}
a_0 & a_1 & a_2 & \dots & a_s & 0 & \dots & 0 \\
a_{-1} & a_0 & \dots & & & & & 0 \\
a_{-2} & \dots & & & & & & 0 \\
\vdots &&&&&& & \vdots \\
a_{-s} &\dots &&&& && \vdots \\
0 & \dots &&&&& & \vdots \\
\vdots &&&&&& a_0 & a_1\\
0 & \dots & & & & & a_{-1} & a_0
\end{array} \right]_.$$
The problem was reduced to finding the zeros of a much smaller determinant, of dimension $(2s) \times (2s)$. As an example the authors compute the well-known formula for eigenvalues of a tridiagonal Toeplitz matrix, and the associated determinant had a form along the lines of
$$ \left[ \begin{array}{cc}
a & b \\ a^{n+1} & b^{n+1}
\end{array} \right] $$
That's just about all I can recall from the reading – I managed to misplace the paper/pdf and am having trouble finding any references that might point to it in the literature.
I'm hoping a MSE reader recognizes this and can point me in the direction of the source. Any leads would be much appreciated.
Best Answer
I found in Bottcher and Grudsky's "Spectral Properties of Toeplitz Matrices" a reference to the paper by W.F. Trench. It is a 1985 article, "On the eigenvalue problem for Toeplitz band matrices," and the result I was interested in follows:
If $T_n$ is an $n\times n$ Toeplitz band matrix with $s$ diagonals below the main and $r$ diagonals above ($r+s < n$ and $c_{-s}c_r rs \neq 0$), whose diagonal values are ordered $c_{-s}, c_{-s+1}, \dots, c_{r-1}, c_r$, then let $$P(z;\lambda) = \sum_{\mu = -s}^r c_{\mu} z^{\mu + s} - \lambda z^s.$$ Fix a $\lambda \in \mathbb{C}$ and define $z_1, \dots, z_k$ to be the zeros of $P(z;\lambda)$. Defining the matrix $A_n$ as $$A_n = \left[ \begin{array}{cccc} 1 & 1 & \dots & 1 \\ \vdots & \vdots & & \vdots \\ z_1^{s-1} & z_2^{s-1} & \dots & z_k^{s-1} \\ z_1^{n+s} & z_2^{n+s} & \dots & z_k^{n+s} \\ \vdots & \vdots & & \vdots \\ z_1^{n+k-1} & z_2^{n+k-1} & \dots & z_k^{n+k-1} \end{array} \right] $$ then $\lambda$ is an eigenvalue of $T_n$ if and only if $\det(A) = 0$.
Apparently this is fairly well known, but my search terms (banded rather than band, matrix rather than matrices, etc.) missed the mark.
In the tridiagonal case, $r = s = 1$ and $P(z;\lambda) = c_{-1} + (c_0 -\lambda) z + c_1 z^2$. From this one can find $z_1$ and $z_2$ explicitly. Then $$ A_n = \left[ \begin{array}{cc} 1 & 1 \\ z_1^{n+1} & z_2^{n+1} \end{array} \right] $$ and the determination of the eigenvalues is straightforward.