# Positivity of eigenvalues of tridiagonal, almost-Toeplitz matrix

How can one show that the following tridiagonal matrix

$$M_n= \begin{pmatrix} -1&3&0&\dots&\dots&\dots&0\\ 3&2&-1&0&&&\vdots\\ 0&-1&2&-1&\ddots&&\vdots\\ \vdots&0&-1&2&\ddots&0&\vdots\\ \vdots&&\ddots&\ddots&\ddots&-1&0\\ \vdots&&&0&-1&2&-1\\ 0&\dots&\dots&\dots&0&-1&2 \end{pmatrix}$$

has exactly one negative eigenvalue?

The initial problem was showing it has at least some number of real positive eigenvalues (not necessarily distinct) for sufficiently large $$n$$, which can be solved by using Gershgorin circle theorem:

Which implies $$-4\le \lambda\le6$$ if I'm not mistaken, since $$M_n$$ has real eigenvalues (it's hermitian),

Then since the trace $$\operatorname{Tr}M_n =2n-3$$ of a matrix is also the sum of its eigenvalues, we must have at least $$\frac{2n-3}{6}$$ real positive eigenvalues, otherwise $$\operatorname{Tr}M_n < 2n-3$$ would be a contradiction.

But I noticed $$M_n$$ seems to have exactly one negative real eigenvalue, and the rest positive real eigenvalues, for every $$n$$.

How can we prove this strict bound?

• seems a pretty good, provable, pattern in solving $P^T MP = D$ becoming diagonal, with $\det P = 1.$ By Sylvester's Law of Inertia, there is one negative eigenvalue, else positive Jun 7 '19 at 0:49

THREE:

$$P^T H P = D$$ $$\left( \begin{array}{rrr} 1 & 0 & 0 \\ 3 & 1 & 0 \\ \frac{ 3 }{ 11 } & \frac{ 1 }{ 11 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} - 1 & 3 & 0 \\ 3 & 2 & - 1 \\ 0 & - 1 & 2 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 3 & \frac{ 3 }{ 11 } \\ 0 & 1 & \frac{ 1 }{ 11 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} - 1 & 0 & 0 \\ 0 & 11 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } \\ \end{array} \right)$$ $$Q^T D Q = H$$ $$\left( \begin{array}{rrr} 1 & 0 & 0 \\ - 3 & 1 & 0 \\ 0 & - \frac{ 1 }{ 11 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} - 1 & 0 & 0 \\ 0 & 11 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & - 3 & 0 \\ 0 & 1 & - \frac{ 1 }{ 11 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} - 1 & 3 & 0 \\ 3 & 2 & - 1 \\ 0 & - 1 & 2 \\ \end{array} \right)$$

===========================================

FOUR:

$$P^T H P = D$$ $$\left( \begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 \\ \frac{ 3 }{ 11 } & \frac{ 1 }{ 11 } & 1 & 0 \\ \frac{ 1 }{ 7 } & \frac{ 1 }{ 21 } & \frac{ 11 }{ 21 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrr} - 1 & 3 & 0 & 0 \\ 3 & 2 & - 1 & 0 \\ 0 & - 1 & 2 & - 1 \\ 0 & 0 & - 1 & 2 \\ \end{array} \right) \left( \begin{array}{rrrr} 1 & 3 & \frac{ 3 }{ 11 } & \frac{ 1 }{ 7 } \\ 0 & 1 & \frac{ 1 }{ 11 } & \frac{ 1 }{ 21 } \\ 0 & 0 & 1 & \frac{ 11 }{ 21 } \\ 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrr} - 1 & 0 & 0 & 0 \\ 0 & 11 & 0 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } & 0 \\ 0 & 0 & 0 & \frac{ 31 }{ 21 } \\ \end{array} \right)$$ $$Q^T D Q = H$$ $$\left( \begin{array}{rrrr} 1 & 0 & 0 & 0 \\ - 3 & 1 & 0 & 0 \\ 0 & - \frac{ 1 }{ 11 } & 1 & 0 \\ 0 & 0 & - \frac{ 11 }{ 21 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrr} - 1 & 0 & 0 & 0 \\ 0 & 11 & 0 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } & 0 \\ 0 & 0 & 0 & \frac{ 31 }{ 21 } \\ \end{array} \right) \left( \begin{array}{rrrr} 1 & - 3 & 0 & 0 \\ 0 & 1 & - \frac{ 1 }{ 11 } & 0 \\ 0 & 0 & 1 & - \frac{ 11 }{ 21 } \\ 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrr} - 1 & 3 & 0 & 0 \\ 3 & 2 & - 1 & 0 \\ 0 & - 1 & 2 & - 1 \\ 0 & 0 & - 1 & 2 \\ \end{array} \right)$$

====================================

FIVE:

$$P^T H P = D$$ $$\left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 \\ \frac{ 3 }{ 11 } & \frac{ 1 }{ 11 } & 1 & 0 & 0 \\ \frac{ 1 }{ 7 } & \frac{ 1 }{ 21 } & \frac{ 11 }{ 21 } & 1 & 0 \\ \frac{ 3 }{ 31 } & \frac{ 1 }{ 31 } & \frac{ 11 }{ 31 } & \frac{ 21 }{ 31 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrr} - 1 & 3 & 0 & 0 & 0 \\ 3 & 2 & - 1 & 0 & 0 \\ 0 & - 1 & 2 & - 1 & 0 \\ 0 & 0 & - 1 & 2 & - 1 \\ 0 & 0 & 0 & - 1 & 2 \\ \end{array} \right) \left( \begin{array}{rrrrr} 1 & 3 & \frac{ 3 }{ 11 } & \frac{ 1 }{ 7 } & \frac{ 3 }{ 31 } \\ 0 & 1 & \frac{ 1 }{ 11 } & \frac{ 1 }{ 21 } & \frac{ 1 }{ 31 } \\ 0 & 0 & 1 & \frac{ 11 }{ 21 } & \frac{ 11 }{ 31 } \\ 0 & 0 & 0 & 1 & \frac{ 21 }{ 31 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrr} - 1 & 0 & 0 & 0 & 0 \\ 0 & 11 & 0 & 0 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } & 0 & 0 \\ 0 & 0 & 0 & \frac{ 31 }{ 21 } & 0 \\ 0 & 0 & 0 & 0 & \frac{ 41 }{ 31 } \\ \end{array} \right)$$ $$Q^T D Q = H$$ $$\left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ - 3 & 1 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 11 } & 1 & 0 & 0 \\ 0 & 0 & - \frac{ 11 }{ 21 } & 1 & 0 \\ 0 & 0 & 0 & - \frac{ 21 }{ 31 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrr} - 1 & 0 & 0 & 0 & 0 \\ 0 & 11 & 0 & 0 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } & 0 & 0 \\ 0 & 0 & 0 & \frac{ 31 }{ 21 } & 0 \\ 0 & 0 & 0 & 0 & \frac{ 41 }{ 31 } \\ \end{array} \right) \left( \begin{array}{rrrrr} 1 & - 3 & 0 & 0 & 0 \\ 0 & 1 & - \frac{ 1 }{ 11 } & 0 & 0 \\ 0 & 0 & 1 & - \frac{ 11 }{ 21 } & 0 \\ 0 & 0 & 0 & 1 & - \frac{ 21 }{ 31 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrr} - 1 & 3 & 0 & 0 & 0 \\ 3 & 2 & - 1 & 0 & 0 \\ 0 & - 1 & 2 & - 1 & 0 \\ 0 & 0 & - 1 & 2 & - 1 \\ 0 & 0 & 0 & - 1 & 2 \\ \end{array} \right)$$

=================================

SIX:

$$P^T H P = D$$ $$\left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ \frac{ 3 }{ 11 } & \frac{ 1 }{ 11 } & 1 & 0 & 0 & 0 \\ \frac{ 1 }{ 7 } & \frac{ 1 }{ 21 } & \frac{ 11 }{ 21 } & 1 & 0 & 0 \\ \frac{ 3 }{ 31 } & \frac{ 1 }{ 31 } & \frac{ 11 }{ 31 } & \frac{ 21 }{ 31 } & 1 & 0 \\ \frac{ 3 }{ 41 } & \frac{ 1 }{ 41 } & \frac{ 11 }{ 41 } & \frac{ 21 }{ 41 } & \frac{ 31 }{ 41 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrr} - 1 & 3 & 0 & 0 & 0 & 0 \\ 3 & 2 & - 1 & 0 & 0 & 0 \\ 0 & - 1 & 2 & - 1 & 0 & 0 \\ 0 & 0 & - 1 & 2 & - 1 & 0 \\ 0 & 0 & 0 & - 1 & 2 & - 1 \\ 0 & 0 & 0 & 0 & - 1 & 2 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & 3 & \frac{ 3 }{ 11 } & \frac{ 1 }{ 7 } & \frac{ 3 }{ 31 } & \frac{ 3 }{ 41 } \\ 0 & 1 & \frac{ 1 }{ 11 } & \frac{ 1 }{ 21 } & \frac{ 1 }{ 31 } & \frac{ 1 }{ 41 } \\ 0 & 0 & 1 & \frac{ 11 }{ 21 } & \frac{ 11 }{ 31 } & \frac{ 11 }{ 41 } \\ 0 & 0 & 0 & 1 & \frac{ 21 }{ 31 } & \frac{ 21 }{ 41 } \\ 0 & 0 & 0 & 0 & 1 & \frac{ 31 }{ 41 } \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrr} - 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 11 & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 31 }{ 21 } & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{ 41 }{ 31 } & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{ 51 }{ 41 } \\ \end{array} \right)$$ $$Q^T D Q = H$$ $$\left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ - 3 & 1 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 11 } & 1 & 0 & 0 & 0 \\ 0 & 0 & - \frac{ 11 }{ 21 } & 1 & 0 & 0 \\ 0 & 0 & 0 & - \frac{ 21 }{ 31 } & 1 & 0 \\ 0 & 0 & 0 & 0 & - \frac{ 31 }{ 41 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrr} - 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 11 & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{ 21 }{ 11 } & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 31 }{ 21 } & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{ 41 }{ 31 } & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{ 51 }{ 41 } \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & - 3 & 0 & 0 & 0 & 0 \\ 0 & 1 & - \frac{ 1 }{ 11 } & 0 & 0 & 0 \\ 0 & 0 & 1 & - \frac{ 11 }{ 21 } & 0 & 0 \\ 0 & 0 & 0 & 1 & - \frac{ 21 }{ 31 } & 0 \\ 0 & 0 & 0 & 0 & 1 & - \frac{ 31 }{ 41 } \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrr} - 1 & 3 & 0 & 0 & 0 & 0 \\ 3 & 2 & - 1 & 0 & 0 & 0 \\ 0 & - 1 & 2 & - 1 & 0 & 0 \\ 0 & 0 & - 1 & 2 & - 1 & 0 \\ 0 & 0 & 0 & - 1 & 2 & - 1 \\ 0 & 0 & 0 & 0 & - 1 & 2 \\ \end{array} \right)$$

=============================

For convenience, let us drop the subscript in $$M_n$$. The trailing principal $$(n-1)\times(n-1)$$ submatrix $$P$$ of $$M$$ is a symmetric tridiagonal Toeplitz matrix whose diagonal entries are $$a=2$$ and whose subdiagonal entries are $$b=-1$$. The eigenvalues of $$P$$ are therefore $$\lambda_k(P)=a+2b\cos\left(\frac{k\pi}{n}\right)=2\left(1-\cos\left(\frac{k\pi}{n}\right)\right)$$ for $$k=1,2,\ldots,n-1$$. Hence $$\lambda_k(P)>0$$ for every $$k$$ and $$P$$ is positive definite. However, by Cauchy's interlacing inequality for bordered matrix, $$\lambda_1(M)\le\lambda_1(P)\le\lambda_2(M)\le\lambda_2(P)\le \cdots\le\lambda_{n-1}(M)\le\lambda_{n-1}(P)\le\lambda_n(M).$$ Thus $$M_n$$ has at most one non-positive eigenvalue. This eigenvalue must be negative, otherwise $$M$$ would be positive semidefinite, which is a contradiction to the fact that the first entry of $$M$$ is negative.