# Predicting eigenvalues of bigger matrices

Consider the following $(3 \times 3)$ matrix:

$K_3 = \left( \begin{array}{ccc} a & -1 & 0 \\ -1 & a+1 & -1 \\ 0 & -1 & a \end{array} \right)$

The question has a quantum physics context, so we'll assume that $a$ is such that $K$ is hermitian. This matrix has eigenvalues $-1 + a$, $a$, and $a+1$. Now consider growing the matrix to a $(4\times4)$ in the following way:

$K_4 = \left( \begin{array}{ccc} a & -1 & 0 & 0 \\ -1 & a+1 & -1 & 0 \\ 0 & -1 & a+1 & -1 \\ 0 & 0 & -1 & a \end{array} \right)$

Its eigenvalues are $-1 + a$, $1+a$, $1-\sqrt{2} + a$, and $1+\sqrt{2} + a$. There seems to be at least some structure in this. I was wondering whether there's a way to predict what the eigenvalues of increasingly bigger matrices of this form will be. Specifically, is it possible to find the eigenvalues of:

$K_n = \left( \begin{array}{ccccccc} a & -1 & 0 & \dots & 0 & 0 & 0 \\ -1 & a+1 & -1 & \dots & 0 & 0 & 0 \\ 0 & -1 & a+1 & \dots & 0 & 0 & 0 \\ 0 & 0 & -1 & \dots & -1 & 0 & 0 \\ 0 & 0 & 0 & \dots & a+1 & -1 & 0 \\ 0 & 0 & 0 & \dots & -1 & a+1 & -1 \\ 0 & 0 & 0 & \dots & 0 & -1 & a \end{array} \right)$

I can imagine the expressions become rather monstrous if it's at all possible, so taking something like $a = 1$ is fine for my purposes, if it simplifies matters.

With the help of mookid I managed to find a general form for the characteristic polynomials of $K - Ia$. Defining $P_n$ as the characteristic polynomial of the $(n \times n)$ matrix $K - Ia$, we have:

$P_n = -\lambda Q_{n-1} - Q_{n-2}$

Where $\lambda$ are the requested eigenvalues and $Q_n$ are the characteristic polynomials of the same matrix, where the zero on the $nn$-th entry has been replaced by a one:

$Q_n = (1-\lambda) Q_{n-1} - Q_{n-2}$

With boundary conditions $Q_1 = -\lambda$ and $Q_2 = \lambda^2 - \lambda - 1$.

Quoting wikipedia, with regards to invertibility of tridiagonal matrices: "Closed form solutions can be computed for special cases such as symmetric matrices with all off-diagonal elements equal". I'm hoping that means there also exists an analytic solution for the roots of these polynomials (and hence the eigenvalues for arbitrary $n$). Does anyone know if this is possible, and/or how to go about finding the solution?

You just have to go for the $a=0$ case; in general, the eigenvalues are $a+\lambda, \lambda$ eigenvalue of $\left( \begin{array}{ccccccc} 0 & -1 & 0 & \dots & 0 & 0 & 0 \\ -1 & 1 & -1 & \dots & 0 & 0 & 0 \\ 0 & -1 & 1 & \dots & 0 & 0 & 0 \\ 0 & 0 & -1 & \dots & -1 & 0 & 0 \\ 0 & 0 & 0 & \dots & 1 & -1 & 0 \\ 0 & 0 & 0 & \dots & -1 & 1 & -1 \\ 0 & 0 & 0 & \dots & 0 & -1 & 0 \end{array} \right)$
$$P_2 = X^2 - 1, P_3 = -X^3+X \\ P_{n+1} = X\times P_n - (-1)\times(-1)\times P_{n-1} =-XP_n - P_{n-1}$$
• Thanks! That's a really useful relation. What exactly is $X$ in your equations? I find: $P_2 = \lambda^2 - 1$, $P_3 = -\lambda^3 +\lambda^2 + 2\lambda$, and $P_n = -\lambda P_{n-1} - P_{n-2}$, where $\lambda$ are the eigenvalues of $K - Ia$. – Timsey Jun 25 '14 at 14:18
• There's one small problem with this method. To calculate $P_{n+1}$, you need $P_n$. Here $P_n$ isn't the characteristic polynomial of the matrix $K_n - Ia$, but of a matrix that has a 1 as its $nn$-th entry (instead of a zero). Defining $Q_n$ as the characteristic polynomials of these matrices, we find: $P_n = -\lambda Q_{n-1} - Q_{n-2}$, where $Q_n = (1 - \lambda) Q_{n-1} - Q_{n-2}$. Starting values are $Q_1 = - \lambda$ and $Q_2 = \lambda^2 - \lambda - 1$. – Timsey Jun 25 '14 at 17:18