# Eigenvalues of tridiagonal pseudo-Toeplitz matrices

Devadatta Kulkarni, Darrell Schmidt, Sze-Kai Tsui

► To cite this version:

Devadatta Kulkarni, Darrell Schmidt, Sze-Kai Tsui. Eigenvalues of tridiagonal pseudo-Toeplitz matrices. Linear Algebra and its Applications, 1999, 297, pp.63-80. 10.1016/S0024-3795(99)00114-7. hal-01461924

HAL Id: hal-01461924

https://hal.science/hal-01461924

Submitted on 8 Feb 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Eigenvalues of tridiagonal pseudo-Toeplitz matrices

Devadatta Kulkarni, Darrell Schmidt, Sze-Kai Tsui

Department of Mathematical Sciences, Oakland University, Rochester, MI 48309 4485, USA

In this article we determine the eigenvalues of sequences of tridiagonal matrices that contain a Toeplitz matrix in the upper left block.

*Keywords:* Eigenvalues; Toeplitz matrices; Tridiagonal matrices; Chebyshev polynomials; Graphical method for location of roots

## 1. Introduction

Although Hermitian matrices are known to have real eigenvalues only, the evaluation of these eigenvalues remains as misty as ever. For tridiagonal matrices there are several known methods describing their eigenvalues such as Gershgorin's theorem [5], Sturm sequences for Hermitian tridiagonal matrices [1,4], etc. The eigenvalues of a tridiagonal Toeplitz matrix can be completely determined [11]. Attempts have been made to resolve the eigenvalue problem for matrices which are like tridiagonal Toeplitz matrices but not entirely Toeplitz (see [2,3,12,13]). This paper falls in the same general direction of investigation.
We study tridiagonal matrices which contain a Toeplitz matrix in the upper left block. We call them pseudo-Toeplitz to make a distinction from all the matrices studied before in [2,3,12], etc. The major feature of our treatment is the connection between the characteristic polynomials of these tridiagonal pseudo-Toeplitz matrices and the Chebyshev polynomials of the second kind, whereby we can locate the eigenvalues that fall in the intervals determined by the roots of some Chebyshev polynomials of the second kind. In other words, we use these intervals derived from roots of some Chebyshev polynomial as a reference to determine the eigenvalues of the original pseudo-Toeplitz matrix. In fact, we are able to determine the location of all eigenvalues of some tridiagonal pseudo-Toeplitz matrices which have either all entries real with a nonnegative product from each off-diagonal pair or the entries on the main diagonal purely imaginary with a negative product from each off-diagonal pair (see Corollary 3.4). In Section 2, we lay down a basic tool for finding the eigenvalues of tridiagonal Toeplitz matrices, which is markedly different from the traditional approach used in [2,11,12]. In Section 3, we give a detailed account of the number of eigenvalues in each such interval whose end points are consecutive roots of a pair of Chebyshev polynomials related to the given tridiagonal pseudo-Toeplitz matrix. We also show that, for a sequence of (real) tridiagonal matrices with a positive product from each pair of off-diagonal entries, the eigenvalues of two consecutive matrices in the sequence interlace (see Proposition 3.1). Furthermore, we discuss a lower bound for the number of real eigenvalues for tridiagonal pseudo-Toeplitz matrices of a fixed dimension (see Theorem 3.6). In Section 4, we demonstrate examples of tridiagonal pseudo-Toeplitz matrices for which we can completely determine their real eigenvalues graphically.

These techniques have been also applied in infinite dimensional programming [10] and in numerical solutions of heat equations [3]. Standard references for the Chebyshev polynomials are [6,8,9].

## 2. Eigenvalues of tridiagonal Toeplitz matrices

It is known that the eigenvalues of tridiagonal Toeplitz matrices can be determined analytically. The method employs the boundary value difference equation [11]. In this section, we provide a different approach to the solution which will be extended to determine eigenvalues of several more general matrices in the later sections.

Let $T_n(a, b, c)$ be an $n \times n$ tridiagonal matrix defined by

$$ T_n(a, b, c) = \begin{bmatrix} a & c & \cdots & \cdots & \mathbf{0} \\ b & \ddots & \ddots & \ddots & c \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ \mathbf{0} & b & a & \cdots & c \end{bmatrix}. $$
When $b=c=1$ we denote $T_n(a, b, c)$ by $T_n(a)$. $T_n(a, b, c)$ is the same matrix denoted by $T_n^0(a, b, c)$ in the later sections. We denote the characteristic polynomial of $T_n(a)$ by $\phi_n(a)(\lambda)$, and it is related to the nth degree Chebyshev polynomial of the second kind. Indeed, expanding $\det(T_n(a) - \lambda I)$ by the last row, we have

$$ \phi_n(a)(\lambda) = (a - \lambda)\phi_{n-1}(a)(\lambda) - \phi_{n-2}(a)(\lambda) \quad (1) $$

for $n \ge 2$, with $\phi_0(a)(\lambda) = 1$, $\phi_1(a)(\lambda) = a - \lambda$. Substituting $a - \lambda = 2x$, (1) becomes

$$ \phi_n(a)(x) = 2x\phi_{n-1}(a)(x) - \phi_{n-2}(a)(x) \quad (2) $$

for $n \ge 2$, with $\phi_0(a)(x) = 1$, $\phi_1(a)(x) = 2x$. Thus, $\phi_n(a)(x)$ is the nth degree Chebyshev polynomial of the second kind, denoted by $U_n$. It is well-known that

$$ U_n(x) = \frac{\sin((n + 1) \cos^{-1}(x))}{\sin(\cos^{-1} x)} \quad \text{for } |x| \le 1, $$

and the roots of $U_n(x)$ are $\cos(k\pi/(n+1))$ ($k=1, 2, \dots, n$). Thus, we have the following proposition.

**Proposition 2.1.** The eigenvalues of $T_n(a)$ are

$$ a - 2 \cos(k\pi/(n+1)) \quad \text{for } k = 1, 2, \dots, n. $$

Next, we relate $T_n(a, b, c)$ to $T_n(a)$. Note that

$$ \frac{1}{\sqrt{bc}} T_n(a, b, c) = T_n\left(\frac{a}{\sqrt{bc}}, \frac{b}{\sqrt{bc}}, \frac{c}{\sqrt{bc}}\right), $$

and the eigenvalues of $\alpha T_n(a, b, c)$ are just $\alpha$ times the eigenvalues of $T_n(a, b, c)$. Thus, it suffices to consider the characteristic polynomial $\phi_n(a/\sqrt{bc}, b/\sqrt{bc}, c/\sqrt{bc})$ of $T_n(a/\sqrt{bc}, b/\sqrt{bc}, c/\sqrt{bc})$. As above, we can see that $\phi_n(a/\sqrt{bc}, b/\sqrt{bc}, c/\sqrt{bc})$ satisfies the same recurrence relation and initial conditions as $\phi_n(a/\sqrt{bc})$:

$$ \phi_n(\lambda) = \left( \frac{a}{\sqrt{bc}} - \lambda \right) \phi_{n-1}(\lambda) - \phi_{n-2}(\lambda) (n \le 2), $$

where $\phi_0(\lambda) = 1$ and $\phi_1(\lambda) = a/\sqrt{bc} - \lambda$. Thus,
$$ \phi_n \left( \frac{a}{\sqrt{bc}}, \frac{b}{\sqrt{bc}}, \frac{c}{\sqrt{bc}} \right) = \phi_n \left( \frac{a}{\sqrt{bc}} \right) = U_n. $$

From Proposition 2.1 we know that the eigenvalues for $T_n(a/\sqrt{bc})$ are $a/\sqrt{bc} - 2 \cos(k\pi/(n+1))$ ($k=1,2,\dots,n$). Hence, we have the following result.

**Theorem 2.2.** The eigenvalues of $T_n(a, b, c)$ are

$$ a - 2\sqrt{bc} \cos(k\pi/(n+1)) \quad \text{for } k = 1, 2, \dots, n. $$

### 3. Main results

In this section we study the eigenvalues of those tridiagonal matrices the upper left block of which are Toeplitz matrices. That is, we consider

$$ T_n^k(a,b,c) = \left[ \begin{array}{c|c} \overbrace{T_n(a,b,c)}^{n} & \overbrace{\left( \begin{array}{cccc} 0 & & & \\ & c_k & \cdot & \cdot \\ & \cdot & \ddots & \cdot \\ & & & a_1 \end{array} \right)}^{k} \\ \hline \mathbf{0} & b_k \end{array} \right] \left\{ \begin{array}{c} n \\ k \end{array} \right\} = \left[ \begin{array}{c|c} T_n(a,b,c) & \mathbf{0} \\ \hline b_k & B_k \end{array} \right] $$

where

$$ T_n(a, b, c) = \begin{bmatrix} a & c & \mathbf{0} \\ b & \ddots & \vdots \\ \ddots & \ddots & c \\ \mathbf{0} & b & a \end{bmatrix}, \quad B_k = \begin{bmatrix} a_k & c_{k-1} & \mathbf{0} \\ b_{k-1} & \ddots & \vdots \\ \mathbf{0} & b_1 & a_1 \end{bmatrix}. $$

In the previous section we have determined the eigenvalues of $T_n(a, b, c)$ completely. Now we consider $T_n^k(a/\sqrt{bc}, b/\sqrt{bc}, c/\sqrt{bc})$. We denote the characteristic polynomials of $T_n^k(a/\sqrt{bc}, b/\sqrt{bc}, c/\sqrt{bc})$ and $(1/\sqrt{bc})B_k$ by $\phi_n^k(\lambda)$ and $\psi_k(\lambda)$, $k \ge 1$, respectively, where $\phi_0^k(\lambda) = 1$, $\psi_0(\lambda) = 1$. Expanding $\det(T_n^k(a/\sqrt{bc}, b/\sqrt{bc}, c/\sqrt{bc}) - \lambda I)$ by the last $k$ rows using the Laplace development, we have for $n \ge 1$ and $k \ge 1$ that

$$ \phi_n^k(\lambda) = \phi_n^0(\lambda)\psi_k(\lambda) - \frac{b_k c_k}{bc} \phi_{n-1}^0(\lambda)\psi_{k-1}(\lambda). \quad (3) $$

It follows from Eq. (2) in Section 2 that $\phi_n^0(x)$ is the $n$th degree Chebyshev polynomial $U_n(x)$ of the second kind with
$$ \frac{a}{\sqrt{bc}} - \lambda = 2x. \quad (4) $$

If $\lambda$ is a root of (3) but not a common root of $U_{n-1}$ and $\psi_k$, then

$$ \frac{U_n(\lambda)}{U_{n-1}(\lambda)} = \frac{(b_k c_k / bc) \psi_{k-1}(\lambda)}{\psi_k(\lambda)}. $$

Let $U_n(x)/U_{n-1}(x) = p_n(x)$, $n \ge 1$ and $p_0(x) = 1$. Then

$$ p_n(x) = \frac{U_n(x)}{U_{n-1}(x)} = \frac{2xU_{n-1} - U_{n-2}(x)}{U_{n-1}} = 2x - \frac{1}{p_{n-1}(x)}, \quad n \ge 1, $$

and

$$ \begin{aligned} p'_{n}(x) = 2 + \frac{p'_{n-1}(x)}{p_{n-1}^{2}(x)} &= 2 + \sum_{k=1}^{n-1} \frac{2}{p_{n-1}^{2} p_{n-2}^{2} \cdots p_{n-k}^{2}}, \quad n \ge 1, \\ &= 2 + \frac{2}{U_{n-1}^{2}} \sum_{k=1}^{n-1} U_{n-1-k}^{2}. \end{aligned} \quad (5) $$

Thus, $p'_n(x) > 0$ for all $n \ge 1$ and for all $x$ in the domain of $p_n$. Next we denote for $1 \le j \le k$,

$$ g_j(\lambda) = \frac{\psi_{j-1}(\lambda)b_j c_j / bc}{\psi_j(\lambda)}. $$

We compare their graphs.

Let $\eta_1, \dots, \eta_{n-1}$, be the zeros of $U_{n-1}$ and $\xi_1, \dots, \xi_n$ be the zeros of $U_n$. It is known that $-1 < \xi_1 < \eta_1 < \xi_2 < \eta_2 < \dots < \xi_{n-1} < \eta_{n-1} < \xi_n < 1$. Also denote $\eta_0 = \xi_0 = -\infty$ and $\eta_n = \xi_{n+1} = \infty$. It follows from (5) that $p_n$ is strictly increasing in each interval $(\eta_{j-1}, \eta_j)$, $1 \le j \le n$. The graph of $p_n(x)$ is shown in Fig. 1.

In order to describe the behavior of $g_j$, $1 \le j \le k$, we impose the following conditions for the ensuing paragraphs through Corollary 3.4

$$ \frac{a_j}{\sqrt{bc}}, \frac{a}{\sqrt{bc}} \text{ are real and } \frac{b_j c_j}{bc} \ge 0, \quad 1 \le j \le k. \quad (6) $$

For $2 \le j \le k$, expanding the determinant that generates $\psi_j(\lambda)$, by the first row, we have

$$ \psi_j(\lambda) = \left( \frac{a_j}{\sqrt{bc}} - \lambda \right) \psi_{j-1}(\lambda) - \frac{b_{j-1} c_{j-1}}{bc} \psi_{j-2}(\lambda). $$
<figure><img src="image_2.png" /><figcaption>Fig. 1. y $p_n(x)$.</figcaption></figure>

It follows that

$$
\begin{align*}
g_j(\lambda) &= \frac{(b_j c_j / bc) \psi_{j-1}(\lambda)}{(a_j / \sqrt{bc} - \lambda) \psi_{j-1}(\lambda) - (b_{j-1} c_{j-1} / bc) \psi_{j-2}(\lambda)} \\
&= \frac{b_j c_j / bc}{(a_j / \sqrt{bc} - \lambda) - g_{j-1}(\lambda)}
\end{align*}
$$

and

$$
\begin{align}
g'_{j}(\lambda) &= \frac{(b_j c_j / bc)(1 + g'_{j-1}(\lambda))}{((a_j / bc - \lambda) - g_{j-1}(\lambda))^2}, \quad 2 \le j \le k \\
g'_{1}(\lambda) &= \frac{b_1 c_1 / bc}{(a / \sqrt{bc} - \lambda)^2}. \tag{7}
\end{align}
$$

By induction, $g'_k(\lambda)$ is nonnegative, and hence $g'_k(x) \le 0$ in view of (4). Due to
(6) the tridiagonal matrices $(1/\sqrt{bc})B_k$ are similar to symmetric matrices and
hence they have exactly $k$ real eigenvalues, counting multiplicities (see [7,
p. 174]).

Next, we look into the situation where the eigenvalues of $(1/\sqrt{bc})B_k$ and the
eigenvalues of $(1/\sqrt{bc})B_{k-1}$ are interlacing. For this we prefer to denote

$$
A_k = \begin{bmatrix} a_1 & c_1 & \mathbf{0} \\ b_1 & \ddots & \vdots \\ \vdots & \ddots & c_{k-1} \\ \mathbf{0} & b_{k-1} & a_k \end{bmatrix}
$$

as a sequence of tridiagonal matrices satisfying $b_j c_j > 0, 1 \le j \le k-1$, and $a_j,
1 \le j \le n$, are real. In this notation we have the following proposition.
**Proposition 3.1.** The eigenvalues of $A_k$ are distinct and interlace strictly with eigenvalues of $A_{k-1}$ for $k \ge 2$.

**Proof.** The proof is by induction on $k$. We denote the characteristic polynomial of $A_k$ by $\varphi_k(\lambda)$. The root of $\varphi_1(\lambda)$ is $a_1$ and

$$ \varphi_2(\lambda) = (\lambda - a_1)(\lambda - a_2) - b_1 c_1. $$

It follows from $b_1c_1 > 0$ that $\varphi_2(\lambda)$ has one root in $(\max(a_1, a_2), \infty)$ and one root in $(-\infty, \min(a_1, a_2))$. Thus, the assertion holds for $k=2$. Assume that the assertion holds for order $k-1$. Let $\rho_1 < \rho_2 < \dots < \rho_{k-1}$ be the eigenvalues of $A_{k-1}$, and $\zeta_1, \dots, \zeta_{k-2}$ be the eigenvalues of $A_{k-2}$, where $\rho_1 < \zeta_1 < \rho_2 < \dots < \zeta_{n-2} < \rho_{n-1}$ by hypothesis. Now $\varphi_{k-2}(\lambda) = (-1)^{k-2}\lambda^{k-2} + \text{lower order terms so that } \varphi_{k-2}(\lambda) = \prod_{j=1}^{k-2}(\zeta_j - \lambda)$. It follows that $(-1)^{k-2+j}\varphi_{k-2} > 0$ on $(\zeta_{k-2-j}, \zeta_{k-1-j})$, $0 \le j \le k-2$, where $\zeta_0 = -\infty, \zeta_{k-1} = \infty$. Since $\rho_{k-1-j} \in (\zeta_{k-2-j}, \zeta_{k-1-j})$, $(-1)^{k+j}\varphi_{k-2}(\rho_{k-1-j}) > 0$, $0 \le j \le k-2$.

Expanding the determinant that generates $\varphi_k(\lambda)$ by the last row yields

$$ \varphi_k(\lambda) = (a_k - \lambda)\varphi_{k-1}(\lambda) - b_{k-1}c_{k-1}\varphi_{k-2}(\lambda), \quad k \ge 2. \quad (8) $$

Then it follows from (8) and $b_{k-1}c_{k-1} > 0$ that $(-1)^{k+j}\varphi_k(\rho_{k-1-j}) < 0$, $0 \le j \le k-2$. So $\varphi_k$ has a zero in $(\rho_{j-1}, \rho_j)$, $2 \le j \le k-1$. It remains to show that $\varphi_k$ has a zero in each of $(-\infty, \rho_1)$ and $(\rho_{k-1}, \infty)$. Observe that $(-1)^k\varphi_k(\lambda) = \lambda^k + \text{lower terms, so } (-1)^k\varphi_k(\rho_{k-1}) < 0 < (-1)^k\varphi_k(\lambda)$ for $\lambda$ sufficiently larger than $\rho_{n-1}$. Thus, $\varphi_k$ has a zero in $(\rho_{k-1}, \infty)$. Also $\varphi_k(\rho_1) < 0 < \varphi_k(\lambda)$ for $\lambda$ sufficiently smaller than $\rho_1$. Thus, $\varphi_k$ has a zero in $(-\infty, \rho_1)$. $\square$

Now, let $\zeta_1 \le \dots \le \zeta_k$ be the roots of $\psi_k(x)$ and $\rho_1 \le \dots \le \rho_{k-1}$ be the roots of $\psi_{k-1}(x)$. Then, it follows from Proposition 3.1 that $\zeta_1 < \rho_1 < \zeta_2 < \rho_2 < \dots < \rho_{k-1} < \zeta_k$ if $b_jc_j/bc > 0$ for $1 \le j \le k$. However, if $b_jc_j = 0$ for some $1 \le j \le k$, then $\psi_k$ and $\psi_{k-1}$ have common root(s). Let $l$ be the largest index, $j$, such that $b_jc_j = 0$. Then, expanding the determinant that yields $\phi_n^k(\lambda)$ by the last $l$ rows according to the Laplace development, we have

$$ \phi_n^k(\lambda) = \tilde{\phi}_n^{k-l}(\lambda)\psi_l(\lambda), $$

where $\tilde{\phi}_n^{k-l}(\lambda)$ is the characteristic polynomial of $\tilde{T}_n^k$ which is the $n + (k-l)$ order square matrix in the upper left corner of $T_n^k$. $\tilde{T}_n^k$ is of the form $T_n^k$ if we reindex the entries in the lower right corner of $\tilde{T}_n^k$. We also note that $g_k(x)$, in its reduced form, has exactly $k-l$ poles and $k-1-l$ zeros. The $l$ real roots of $\psi_l(x)$ are roots of $\phi_n^k(\lambda)$. In this decoupled case, we may focus our attention on determining roots of $\tilde{\phi}_n^{k-l}(\lambda)$. We also have an equation analogous to (3)

$$ \tilde{\phi}_n^{k-l}(\lambda) = \phi_n^0(\lambda)\tilde{\psi}_{k-l}(\lambda) - \frac{b_k c_k}{bc} \phi_{n-1}^0(\lambda)\tilde{\psi}_{k-1-l}(\lambda), $$
where for $0 \le j \le k - l - 1$, $\tilde{\psi}_{k-j-l}(\lambda)$ is the characteristic polynomial of the matrix $(1/\sqrt{bc})\tilde{B}_{k-j-l}$, where

$$ \tilde{B}_{k-j-l} = \begin{bmatrix} a_{k-j} & c_{k-j-1} & \cdots & \cdots & \mathbf{0} \\ b_{k-j-1} & \ddots & \ddots & \ddots & \vdots \\ \vdots & \ddots & \ddots & c_{l+1} & \vdots \\ \mathbf{0} & b_{l+1} & \cdots & a_{l+1} & \mathbf{0} \end{bmatrix}. $$

Thus $g_k$, in its reduced form, is $\tilde{g}_{k-l} = (b_k c_k / bc) \tilde{\psi}_{k-1-l} / \tilde{\psi}_{k-l}$.

It follows from the intermediate value theorem that $p_n(x)$ and $g_k(x)$, in its reduced form, must agree with each other at least once in every interval $(\eta_{j-1}, \eta_j)$, $1 \le j \le n$, for $p_n(x)$ is strictly increasing and $g'_k(x) < 0$ wherever $g_k(x)$ is defined in $(\eta_{j-1}, \eta_j)$, $1 \le j \le n$ from (7). If a pole of $g_k(x)$, $\zeta_i$, $1 \le i \le k - l$ is not a pole of $p_n(x)$, then $\zeta_i$ must fall in an interval $(\eta_{j-1}, \eta_j)$, for some $j$, $1 \le j \le n$. If $\zeta_i, \zeta_{i+1}, \dots, \zeta_{i+r}$ are the poles of $g_k(x)$ that lie in $(\eta_{j-1}, \eta_j)$ for some $j$, then by the intermediate value theorem, $p_n(x)$ and $g_k(x)$ must agree exactly once in each of the following intervals, $(\eta_{j-i}, \zeta_i)$, $(\zeta_i, \zeta_{i+1})$, $\dots$, $(\zeta_{i+r}, \eta_j)$, giving rise to $r + 1$ roots of $\phi_n^k(\lambda)$ in Eq. (3). In this notation we have the following theorem.

**Theorem 3.2.** Suppose that $g_k(x)$ is in the reduced form. Then

(i) for $1 \le j \le n$, $(\eta_{j-1}, \eta_j)$ contains one more root of $\phi_n^k(x)$ than poles of $g_k(x)$;

(ii) $\phi_n^k(x)$ has $n+k$ real roots. Furthermore, these roots are distinct, if $b_j c_j \ne 0$, $1 \le j \le k$.

**Proof.** (i) Follows immediately from the discussion before the theorem. For (ii) it suffices to show that $\tilde{\phi}_n^{k-l}$ has $n + (k - l)$ real roots. We note that each common pole of $g_k(x)$ and $p_n(x)$ gives rise to a root of $\phi_n^k(x)$ in Eq. (3). We may now assume that $\tilde{g}_{k-l}(x)$ and $p_n(x)$ have no common poles. Thus, it follows from part (i) that the $\phi_n^{k-l}(x)$ must have $n + (k - l)$ real roots. If $b_j c_j \ne 0$ for all $1 \le j \le k$, then it follows from Proposition 3.1 that $\phi_n^k(x)$ has $n + k$ distinct real roots. $\square$

A similar analysis of the location of roots of $\phi_n^k(x)$ can be done with regards to intervals $(\xi_{j-1}, \xi_j)$, $1 \le j \le n + 1$, which is in the following theorem.

**Theorem 3.3.** Suppose $b_j c_j \ne 0$, $1 \le j \le k$. Each $(\xi_{j-1}, \xi_j)$ for $1 \le j \le n + 1$ contains one more root of $\phi_n^k(x)$ than zeros of $g_k(x)$.

**Proof.** The graph of $p_n(x)$ in $[\xi_{j-1}, \xi_j]$ is depicted in Fig. 2.

If $g_k(x)$ has no zeros in $(\xi_{j-1}, \xi_j)$, then it follows from Proposition 3.1 that $g_k(x)$ can have at most one pole, $\rho_l$, in $[\xi_{j-1}, \xi_j]$. In addition, if $g_k(x)$ has no pole in $[\xi_{j-1}, \xi_j]$, then the graph of $g_k(x)$ is strictly decreasing on this interval, and $g_k(x) > 0$ or $g_k(x) < 0$ for all $x$ in $[\xi_{j-1}, \xi_j]$, and hence $g_k(x)$ and $p_n(x)$ agree
<figure><img src="image_3.png" /><figcaption>Fig. 2. y $p_n(x)$.</figcaption></figure>

exactly once in $(\xi_{j-1}, \xi_j)$. If there is exactly one pole, $\zeta_i$, of $g_k(x)$ such that
$\xi_{j-1} \le \zeta_i \le \xi_j$, then $g_k(x)$ is strictly decreasing and $g_k(x) < 0$ in $(\xi_{j-1}, \zeta_i)$, and is
strictly decreasing and $g_k(x) > 0$ in $(\zeta_i, \xi_j)$. If $\xi_{j-1} \le \zeta_i < \eta_{j-1}$, $g_k(x)$ and $p_n(x)$
agree exactly once in $(\zeta_i, \xi_j)$. If $\eta_{j-1} < \zeta_i \le \xi_j$, then $g_k(x)$ and $p_n(x)$ agree exactly
once in $(\xi_{j-1}, \zeta_i)$. If $\zeta_i = \eta_{j-1}$, then $g_k(x)$ and $p_n(x)$ are not equal for all $x$ in
$(\xi_{j-1}, \xi_j)$. But, $\zeta_i = \eta_{j-1}$ is a root of $\phi_n^k(x)$.

In general, suppose $g_k(x)$ has $r$ zeros, $\rho_i < \rho_{i+1} \cdots < \rho_{i+(r-1)}$, in $(\xi_{j-1}, \xi_j)$.
Then $p_n(x)$ has no zeros in each of $(\xi_j, \rho_i)$, $(\rho_i, \rho_{i+1})$, \dots, $(\rho_{i+(r-1)}, \xi_j)$.
Repeating the argument in the previous paragraph with the roles of $p_n(x)$ and $g_k(x)$ reversed, we conclude that there is exactly one root of $\phi_n^k(x)$ in
each of the intervals $(\xi_j, \rho_i)$, $(\rho_i, \rho_{i+1})$, \dots, $(\rho_{i+(r-1)}, \xi_j)$, a total of $r+1$
roots. $\square$

**Corollary 3.4.** (i) If $b_j c_j \ge 0$, $1 \le j \le k$, $bc > 0$ and $a, a_j$ are real, $1 \le j \le k$, then $T_n^k(a, b, c)$ has $n+k$ real eigenvalues. Furthermore, these eigenvalues are distinct if $b_j c_j > 0$, $1 \le j \le k$.

(ii) If $bc < 0$, $b_j c_j < 0$, and $a, a_j$ are purely imaginary complex numbers for $1 \le j \le k$, then $T_n^k(a, b, c)$ has $n+k$ distinct eigenvalues.

**Proof.** If $x_0$ is a root of $\phi_n^k(x)$, then $a/\sqrt{bc} - 2x_0(\equiv \lambda_0)$ is a root of $\phi_n^k(\lambda)$, and thus $a - 2\sqrt{bc}x_0$ is an eigenvalue of $T_n^k(a, b, c)$. If $b_j c_j \ge 0$, $1 \le j \le k$, $bc > 0$ and $a, a_j$ are real $1 \le j \le k$, then condition (6) is satisfied. If $bc < 0$ and $b_j c_j < 0$, and $a, a_j$ are purely imaginary complex numbers for $1 \le j \le k$, then condition (6) is also satisfied. The result follows from Theorem 3.2. The eigenvalues of $T_n^k(a, b, c)$ are of the form $a - 2\sqrt{bc}x_i$, $1 \le i \le n \le k$, where the $x_i$'s are distinct real roots of $\phi_n^k(x). $ $\square$
By (2), $2xU_j(x) = U_{j+1}(x) + U_{j-1}(x)$ and hence

$$ \sum_j \alpha_j 2x U_j(x) = \sum_j \alpha_j [U_{j+1}(x) + U_{j-1}(x)] = \sum_{n-k \le j \le n+k} \beta_j U_j(x) $$

with $\beta_j$ real. Thus, $\phi_n^k(x)$ is a linear combination of $U_{n+k}(x), \dots, U_{n-k}(x)$. We summarize this result in a proposition.

**Proposition 3.5.** $\phi_n^k(x)$ is a linear combination of $U_{n+k}(x), U_{n+k-1}(x), \dots, U_{n-k}(x)$ with real coefficients.

**Theorem 3.6.** $\phi_n^k(\lambda)$ has at least $n-k$ real roots located in $(a-2, a+2)$.

**Proof.** Suppose that $\phi_n^k(x)$ has fewer than $n-k$ real roots in $(-1, 1)$, say $\zeta_1 \le \zeta_2 \le \dots \le \zeta_m$, $m < n-k$. Consider a polynomial $f(x) = \prod_{j=1}^m (x - \zeta_j)$ of degree $m$ on $(-1, 1)$. $f(x)$ can be written as a linear combination of $U_0(x), U_1(x), \dots, U_m(x)$, i.e., $f(x) = \sum_{j=0}^m \alpha_j U_j(x)$. Next consider the weighted inner product

$$ \langle \phi_n^k(x), f(x) \rangle = \int_{-1}^{1} (1-x^2)^{-1/2} \phi_n^k(x) f(x) \, dx, $$

which is nonzero since $\phi_n^k(x)$ and $f(x)$ are of either the same sign or the opposite sign over each of the following intervals $(-1, \zeta_1)$, $(\zeta_1, \zeta_2)$, \dots, $(\zeta_m, 1)$. On the other hand, it follows from Proposition 3.5 that

$$ \phi_n^k(x) = \sum_{n-k \le j \le n+k} \beta_j U_j(x) $$

and hence

$$ \langle \phi_n^k, f \rangle = \left\langle \sum_{n-k \le j \le n+k} \beta_j U_j(x), \sum_{j=0}^{m} \alpha_j U_j(x) \right\rangle = 0, \quad m < n-k, $$

a contradiction since the polynomials $u_j(x)$ are orthogonal with respect to this inner product. Hence, $\phi_n^k(x)$ has at least $n-k$ real roots in $(-1, 1)$, and therefore, $\phi_n^k(\lambda)$ has at least $n-k$ real roots in $(a-2, a+2)$. $\square$

## 4. Examples

For the sake of simplicity, we require $bc > 0$ in this section. We study the eigenvalues of a matrix
$$T_n^1(a,b,c) = \begin{bmatrix} T_n(a,b,c) & \begin{bmatrix} 0 \\ b_1 \\ a_1 \end{bmatrix} \\ \begin{bmatrix} 0 \\ c_1 \end{bmatrix} & \end{bmatrix}$$

which corresponds to the case of $k = 1$.

By examining the roots of the characteristic polynomial of $(1/\sqrt{bc})T_n^1(a, b, c)$ and using the substitution $a/\sqrt{bc} - \lambda = 2x$, we get from (3) that, for $n \ge 1$, the roots $x$ of $\phi_n^k(a)(x)$ satisfy the equation

$$bc(e_1 + 2x)U_n(x) - b_1c_1U_{n-1}(x) = 0, \quad (11)$$

and if $x$ is not a common root of $U_{n-1}(x)$ and $e_1 + 2x$, then

$$\frac{U_n(x)}{U_{n-1}(x)} = \frac{b_1 c_1}{bc(e_1 + 2x)}, \quad (12)$$

where $e_1 = (a_1 - a)/\sqrt{bc}$ and $U_n(x)$ denotes the nth degree Chebyshev polynomial of the second kind. We have seen in Corollary 3.4 that if $b_1c_1 > 0$ and $bc > 0$, $T_n^1(a, b, c)$ has $n + 1$ real distinct eigenvalues, obtained by studying the intersection of the graphs

$$g_1(x) = b_1 c_1 / bc (e_1 + 2x) \text{ with } p_n(x) = U_n(x) / U_{n-1}(x)$$

in the xy-plane. By looking at the graph of $y = g_1(x)$, we can determine the location of eigenvalues of $T_n^1(a, b, c)$ precisely.

Let $\eta_0 < \xi_1 < \eta_1 < \xi_2 < \dots < \eta_{i-1} < \xi_i < \eta_i < \dots < \eta_{n-1} < \xi_n < \eta_n$ where $\eta_0 = -\infty$, $\eta_n = \infty$ and $\xi_1, \xi_2, \dots, \xi_n$ are the roots of $U_n(x)$ and $\eta_1, \eta_2, \dots, \eta_{n-1}$ are the roots of $U_{n-1}(x)$. If $bc > 0$ and $(a - a_1)/2\sqrt{bc}$ coincides with one of the $\eta_i$'s, it is a root of (11). Otherwise, we call the interval $(\eta_{i-1}, \eta_i)$ the distinguished interval if $\eta_{i-1} < (a - a_1)/2\sqrt{bc} < \eta_i$. With this notation we have the following result.

**Theorem 4.1.** If $bc > 0$ and $\eta_{i-1} < (a - a_1)/2\sqrt{bc} < \eta_i$ for some $i$, there is exactly one root of (12) in each of the $n-1$ intervals $(\eta_{j-1}, \eta_j)$ where $j \ne i$, $1 \le j \le n$. If $b_1c_1 > 0$, then there are precisely two additional roots of (12), exactly one lying in each of the intervals

$$\left( \eta_{i-1}, \frac{a - a_1}{2\sqrt{bc}} \right) \quad \text{and} \quad \left( \frac{a - a_1}{2\sqrt{bc}}, \eta_i \right).$$

If $b_1c_1 < 0$, then there may be zero, one or two additional roots of (12) in the interval $(\eta_{i-1}, \eta_i)$.
**Proof.** Let $\delta_1$ and $\delta_2$ be the parts of the graph of $g_1(x)$ for $x < -e_1/2$ and for $x > e_1/2$, respectively. We observe that if $\eta_{i-1} < -e_1/2 < \eta_i$, from Fig. 1, we see that $\delta_1$ meets each component of the graph $y = U_n(x)/U_{n-1}(x)$ once in the $i-2$ intervals on the left of $(\eta_{i-1}, \eta_1)$, and $\delta_2$ meets each component in $n-i+1$ intervals once on the right of $(\eta_{i-1}, \eta_1)$, producing $n-1$ roots of (12). This holds, if $b_1c_1 > 0$, then $y = g_1(x) = b_1c_1/\sqrt{bc}(e_1+2x)$ is decreasing on each interval $(-\infty, -e_1/2)$ and $(-e_1/2, \infty)$ as depicted in Fig. 3; or if $b_1c_1 \le 0$. Now if $b_1c_1 > 0$, the component of the graph of $y = U_n(x)/U_{n-1}(x)$ in the distinguished interval, $(\eta_{i-1}, \eta_i)$, meets both $\delta_1$ and $\delta_2$, and we get two additional roots of (12) (see Fig. 1 along with Fig. 3). If $b_1c_1 < 0$, the graph of $y = g_1(x)$ is increasing on $(-\infty, -e_1/2)$ and on $(-e_1/2, \infty)$. With $bc, a$ and $a_1$ fixed, $b_1$ and $c_1$ can be chosen so that $b_1c_1 < 0$ and each of the three illustrations in Fig. 4 occurs. $\square$

Now we study the eigenvalues of a matrix

$$ T_n^2(a,b,c) = \begin{bmatrix} T_n(a,b,c) & \mathbf{0} \\ \hline \mathbf{0} & \begin{matrix} b_2 & 0 \\ a_2 & b_1 \\ c_2 & a_1 \end{matrix} \end{bmatrix} $$

which is the case $k=2$.

By examining the roots of the characteristic polynomial of $(1/\sqrt{bc})T_n^2(a, b, c)$ and using the substitution $a/\sqrt{bc} - \lambda = 2x$, we get from (3), for $n \ge 1$,

<figure><img src="image_4.png" /><figcaption>Fig. 3. $y$ $g_1(x)$.</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Fig. 4. Intersections when $b_1c_1 < 0$.</figcaption></figure>

$$bc(4x^2 + (e_1 + e_2)2x + e_1e_2 - d)U_n(x) - b_2c_2(e_1 + 2x)U_{n-1}(x) = 0. \quad (13)$$

If $x$ is not a common root of factors in two summands,

$$\frac{U_n(x)}{U_{n-1}(x)} = \frac{b_2c_2(e_1 + 2x)}{bc(4x^2 + (e_1 + e_2)2x + e_1e_2 - d)}, \quad (14)$$

where

$$\frac{a_1 - a}{\sqrt{bc}} = e_1, \quad \frac{a_2 - a}{\sqrt{bc}} = e_2, \quad \frac{b_1c_1}{bc} = d$$

and $U_n(x)$ denotes the $n$th degree Chebyshev polynomial of the second kind. We have seen in Corollary 3.4, that if $b_2c_2 > 0$, $b_1c_1 > 0$ and $bc > 0$, $T_n^2(a, b, c)$ has $n+2$ real distinct eigenvalues.

With the help of the graph of

$$y = g_2(x) = \frac{b_2c_2(e_1 + 2x)}{bc(4x^2 + (e_1 + e_2)2x + e_1e_2 - d)},$$

we can determine the locations of roots of (14). Let $\eta_0 < \xi_1 < \eta_1 < \cdots < \eta_{i-1} < \xi_i < \eta_i < \cdots < \eta_{n-1} < \xi_n < \eta_n$, where $\eta_0 = -\infty$, $\eta_n = \infty$ and $\xi_1, \xi_2, \ldots, \xi_n$ are the roots of $U_n(\lambda)$ and $\eta_1, \eta_2, \ldots, \eta_{n-1}$ are the roots of $U_{n-1}(\lambda)$. We set
$$ \theta_1 = \frac{-(e_1 + e_2) - \sqrt{(e_1 - e_2)^2 + 4d}}{4}, $$

$$ \theta_2 = \frac{-(e_1 + e_2) + \sqrt{(e_1 - e_2)^2 + 4d}}{4} $$

and

$$ \Delta = (e_1 - e_2)^2 + 4d. $$

Note that $x = \theta_1$ and $x = \theta_2$ are vertical asymptotes of $y = g_2(x)$ if $\Delta \ge 0$. If $\Delta > 0$ and $\theta_1$ or $\theta_2$ is a root of $U_{n-1}(x)$, it is a root of (13); otherwise, let us denote by $J_1$ and $J_2$ the intervals to which $\theta_1$ and $\theta_2$ belong respectively, amongst intervals $(\eta_{i-1}, \eta_i)$ for $i = 1, 2, \dots, n$. In this notation, we have the following result.

<figure><img src="image_6.png" /><figcaption>Fig. 5. $g_2(x)$</figcaption></figure>
**Theorem 4.2.** If $\Delta < 0$, the Eq. (14) has $n$ real roots, at least one lying in each interval $(\eta_{j-1}, \eta_j)$ for $j = 1, 2, \dots, n$.

**Proof.** The result follows from looking at the graphs given in Fig. 5 comparing them with the graph of $y = U_n(x)/U_{n-1}(x)$ in Fig. 1. $\square$

**Theorem 4.3.** Suppose $\Delta > 0$, and $\theta_1, \theta_2$ are not roots of $U_{n-1}(x)$.

(i) Then Eq. (15) has at least one real root in each interval $(\eta_{j-1}, \eta_j)$, for $1 \le j \le n$, which is not distinguished, accounting for at least $n-2$ or $n-1$ roots of (14) depending on whether $J_1 \ne J_2$ or $J_1 = J_2$.

(ii) If $b_2c_2 > 0$, $b_1c_1 > 0$, then there are exactly $n+2$ distinct real roots of (14) and each nondistinguished interval $(\eta_{j-1}, \eta_j)$, $1 \le i \le n$, contains exactly one root of (14). If $b_2c_2 > 0$, $b_1c_1 < 0$, then there are at least $n$ real roots of (14).

(iii) If $b_2c_2 < 0$ and $J_1 \ne J_2$, then there are at least $n$ real roots of (14) when $b_1c_1 < 0$, and at least $n-2$ real roots of (14), when $b_1c_1 > 0$.

<figure><img src="image_7.png" /><figcaption>Fig. 6. $y = g_2(x)$, $\Delta > 0$.</figcaption></figure>
**Proof.** (i) Fig. 6 depicts the graph of $y = g_2(x)$ for four cases. From Figs. 1 and 6, it can be seen that $g_2(x)$ and $p_n(x)$ have at least one intersection in any given nondistinguished interval $(\eta_{j-1}, \eta_j)$, for some $1 \le j \le n$, for $x = \eta_{j-1}$, and $x = \eta_j$ are vertical asymptotes of $p_n(x)$, and the x-axis is a horizontal asymptote of $g_2(x)$.

(ii) Suppose $b_2c_2 > 0$ and $b_1c_1 > 0$. Then $g'_2(x) < 0$ for all $x \ne \theta_1, \theta_2$. If $J_1 \ne J_2$, then each $J_j, j$ contains two roots accounting for all $2+2+(n-2) = n+2$ roots using (i). If $\sigma_1 = J_2$, then $J_1$ contains three roots accounting for all $3+(n-1) = n+2$ roots using (i). In either case, all roots of (14) are accounted for, and thus all nondistinguished intervals contain exactly one root of (14) again. Suppose $b_2c_2 > 0$ and $b_1c_1 > 0$ and $b_1c_1 < 0$. The distinguished interval $J_1$ or $J_2$ that contains $\theta_2$ contain two roots (Fig. 6). If $J_1 \ne J_2$, this interval contains at least two roots of (14) accounting for $2+(n-2) = n$ roots, using (i). If $J_1 = J_2$, $J_1$ contains at least one root of (14) in $J_1 \cap (\theta_1, \infty)$ accounting for $1+(n-1) = n$ roots, by (i) again.

(iii) The number of real roots is at least $n-2$ by Theorem 3.6. In addition, if $b_2c_2 < 0$, $b_1c_1 < 0$ and $J_1 \ne J_2$, then it can be seen from Fig. 6 that the distinguished interval that contains $\theta_1$ necessarily contains two roots of (14) accounting for $2+(n-2) = n$ roots. Finally, if $J_1 = J_2$, then one root of (14) is guaranteed in $J_1 \cap (-\infty, \theta_1)$ of (14), accounting for $1+(n-1) = n$ roots. $\square$

**Theorem 4.4.** If $\Delta = 0$, then there are at least $n$ distinct real roots of (13).

**Proof.** The graph of $g_2(x)$ is given in Fig. 7, where $x = \theta_1$ is the vertical asymptote of $g_2(x)$.

If $\Delta = 0$, then $c_1b_1 < 0$. If $\theta_1$ does not lie in the interval $[\eta_{j-1}, \eta_j]$, $1 \le j \le n$, then Eq. (14) has at least one root in $[\eta_{j-1}, \eta_j]$. If $\theta_1 \in (\eta_{j-1}, \eta_j)$, it can be seen easily from Fig. 7 that only one root is guaranteed in any open interval $(\eta_{j-1}, \eta_j)$ that contains $\theta_1$. Note that if $\theta_1$ coincides with $\eta_j$, then one of the intervals $[\eta_{j-1}, \eta_j]$ and $(\eta_j, \eta_{j+1})$ necessarily contains a root of (14) while the other might not contain a root. In this case, $\theta_1$ is a root of (13). $\square$

<figure><img src="image_8.png" /><figcaption>Fig. 7. $y = g_2(x)$, $\Delta = 0$.</figcaption></figure>
**Remark 4.5.** The positions of the real roots discussed in Theorems (4.2) (4.4) can be determined completely by the graphs of $p_n(x)$ and $g_2(x)$.

**References**

[1] K.E. Atkinson, An Introduction to Numerical Analysis, Wiley, New York, 1978.

[2] R.M. Beam, R.F. Warming, The asymptotic spectra of banded Toeplitz and quasi Toeplitz matrices, SIAM J. Sci. Comput. 14 (4) (1993) 971–1006.

[3] B. Cahlon, D.M. Kulkarni, P. Shi, Stepwise stability for the heat equation with a nonlocal constraint, SIAM J. Numer. Anal. 32 (2) (1995) 571–593.

[4] J.M. Franklin, Matrix Theory, Prentice Hall, New Jersey, 1968.

[5] G.H. Golub, C.F. van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, MD, 1989.

[6] U.W. Hochstrasser, Orthogonal polynomials, in: M. Abramowitz, I.A. Stegun, (Eds.), Handbook of Mathematical Functions with Formulas, Graphs and Mathematical Tables, 1966, pp. 771–802.

[7] R.A. Horn, C.A. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985.

[8] A. Korsak, C. Schubert, A determinant expression of Chebychev polynomials, Canad. Math. Bull. 3 (1960) 243–246.

[9] T.J. Rivlin, Chebychev Polynomials, Wiley, New York, 1974.

[10] I.E. Schochetman, R.L. Smith, S. K. Tsui, in: A.V. Fiacco (Ed.), Solutions existence for infinite quadratic programming, the positive semi definite case, to appear in Mathematical Programming with Data Perturbations, Marcel Dekker, 1997.

[11] G.D. Smith, Numerical Solution of Partial Differential Equations: Finite Difference Methods, 3rd ed., Clarendon Press, Oxford, 1985.

[12] W.F. Trench, On the eigenvalue problem for Toeplitz band matrices, Linear Algebra Appl. 64 (1985) 199–214.

[13] S. K. Tsui, Matrices related to orthogonal polynomials, Preprint 1995.