Eigenvalues of two related symmetric matrices

EDIT: I've fixed my work and computed a numerically verified closed-form solution.

Define the $n \times n$ matrices $$ \renewcommand{\arraystretch}{1.38} A_n(x) = \begin{bmatrix} -x & 0 & 1 & \cdots & 1 & 0 \\ 0 & -x & 1 \\ 1 & 1 & -x & 1 \\ \vdots & & \ddots & \ddots & \ddots \\ 1 & & & 1 & -x & 1 \\ 0 & & & & 1 & -x \end{bmatrix}, \qquad n \geq 4, $$ and $$ \renewcommand{\arraystretch}{1.38} B_n(x) = \begin{bmatrix} -x & 0 & 1 & \cdots &\cdots & 1 \\ 0 & -x & 1 \\ 1 & 1 & -x & 1 & \\ \vdots & & \ddots & \ddots & \ddots \\ & & & 1 & -x & 1 \\ 1 & & & & 1 & -x \end{bmatrix}, \qquad n \geq 3. $$ We'll keep defining matrices in this fashion. We also always define the corresponding sequences $a_n(x) := \det A_n(x)$, $b_n(x) = \det B_n(x)$, etc. Your desired characteristic polynomials (up to sign) are $a_n(x)$ and $b_n(x)$, and your desired eigenvalues are the roots of those polynomials. Going forward, we'll often omit $x$-dependence, writing for example $a_n$ and $A_n$.

The common idea is this: to evaluate $\det A_n(x)$, we do cofactor expansion and eventually are left with minors equal to matrices we recognize, e.g. $B_n(x)$. Hence we can set up some type of recursion for the $a_n$, $b_n$, etc., which we solve via generating functions. There's a ton of computations here (sorry for the long post, but I think it's cool that we can actually write down a closed-form answer), so I will only display the most relevant/tricky parts. These are: recognizing previously defined matrices when doing cofactor expansion, and being very careful about the $n$ for which our relations are well-defined. (The bold warning is where I made my previous mistake. Pay careful attention to side notes like "$n \geq 5$" and make sure you see why they are what they are.) If you're unfamiliar with the use of generating functions to solve recurrences, I'd be happy to show you one of them. I omitted all such computations to save space because they are more standard.

Here goes.

Recursion for $a_n$: by cofactor expansion up the right column of $A_n$, we have $$ \det A_n = - x \det B_{n-1} - \underbrace{\left| \begin{matrix} -x & 0 & 1 & \cdots & 1 & 1 \\ 0 & -x & 1 \\ 1 & 1 & -x & \ddots & \\ \vdots & & \ddots & \ddots & 1 \\ 1 & & & 1 & -x & 1 \\ & & & & & & 1 \end{matrix} \right|}_{(n-1)\times(n-1)}, $$ and evaluating the remaining determinant via cofactor expansion along the last column gives $$ a_n = -x b_{n-1} - b_{n-2}, \qquad n \geq 3. $$

Recursion for $b_n$: by cofactor expansion up the right column of $B_n$, \begin{align*} \det B_n &= - x \det B_{n-1} - \det C_{n-1} + (-1)^{n-1} \det D_{n-1} \\ \iff b_n &= - x b_{n-1} - c_{n-1} + (-1)^{n-1} d_{n-1}, \qquad n \geq 5 \text{ (for $C_{n-1}$ to be well-defined)}, \end{align*} where $$ \renewcommand{\arraystretch}{1.38} C_n(x) = \begin{bmatrix} -x & 0 & 1 & \cdots & \cdots & 1 \\ 0 & -x & 1 \\ 1 & 1 & -x & 1 \\ \vdots & & \ddots & \ddots & \ddots & \\ & & & 1 & - x & 1 \\ 1 & & & 0 & 0 & 1 \end{bmatrix}, \qquad n \geq 5, \qquad \renewcommand{\arraystretch}{1.38} D_n(x) = \begin{bmatrix} 0 & -x & 1 & \\ 1 & 1 & -x & 1 \\ \vdots & & \ddots & \ddots & \ddots \\ \vdots & & & 1 & -x & 1 \\ \vdots & & & & 1 & -x \\ 1 & & & & & 1 \end{bmatrix}, \qquad n \geq 3. $$

Recursion for $c_n$: by cofactor expansion along the bottom row, \begin{align*} \det C_n &= \det B_{n-1} + (-1)^{n-1} \det D_{n-1}^T \\ c_n &= b_{n-1} + (-1)^{n-1} d_{n-1}, \qquad n \geq 5 \text{ (for $C_{n}$ to be well-defined)} \end{align*} since determinants are invariant under matrix transpose.

Recursion for $d_n$: by cofactor expansion along the bottom row, \begin{align*} \det D_n &= \det D_{n-1} + (-1)^{n-1} \det E_{n-1}, \\ d_n &= d_{n-1} + (-1)^{n-1} e_{n-1}, \qquad n \geq 4 \text{ (for $D_{n-1}$ to be well-defined)} \end{align*} where $$ \renewcommand{\arraystretch}{1.38} E_n(x) = \begin{bmatrix} -x & 1 & \\ 1 & -x & 1 \\ & \ddots & \ddots & \ddots \\ & & 1 & -x & 1 \\ & & & 1 & -x \\ \end{bmatrix}. $$

Recursion for $e_n$: finally our hard work has paid off with a simple tri-diagonal matrix. I won't go into the details for this (it's the same type of argument we've been preparing to make in the above), but the wikipedia page on tri-diagonal matrices will tell you that $$ e_n = - x e_{n-1} - e_{n-2}, \qquad (e_{-1}, e_0) = (0, 1) $$ which can be solved in closed form via generating functions (I used mathematica): $$ 2^{n+1} \sqrt{x^2-4} \cdot e_n(x) = x \left[\left(-\sqrt{x^2-4}-x\right)^n-\left(\sqrt{x^2-4}-x\right)^n\right]+\sqrt{x^2-4} \left[\left(-\sqrt{x^2-4}-x\right)^n+\left(\sqrt{x^2-4}-x\right)^n\right]. $$

Now with this closed form for $e_n(x)$ we start back-solving into our previously found recursions.

Recursion for $d_n$: from $d_n = d_{n-1} + (-1)^{n-1} e_{n-1}$ for $n \geq 4$ and the initial condition $d_3 = x^2 + x - 1$ (computed by hand from $D_3$), we get $$ 2^{n+1} (x-2) \sqrt{x^2-4} \cdot d_n(x) = \left( x + \sqrt{x^2-4} \right)^n \left( x - 2 + \sqrt{x^2-4} \right) - \left( x - \sqrt{x^2-4} \right)^n \left( x - 2 - \sqrt{x^2-4} \right) + 2^{n+1} (1-x) \sqrt{x^2-4}. $$

Recursion for $b_n$: combining our recursions for $c_n$ and $b_n$, we find $$ b_n = - x b_{n-1} - b_{n-2} + (-1)^{n-1} \left[ d_{n-1} + d_{n-2} \right], \qquad n \geq 6, $$ and hence we need the initial conditions $(b_4, b_5) = (x^4-4 x^2-2 x+1,-x^5+6 x^3+4 x^2-3 x-2)$, computed by hand from $B_n$. This gives \begin{align*} 2^{n+1} (x-2)^2 \sqrt{x^2-4} \cdot b_n(x) = \left(-\sqrt{x^2-4}-x\right)^n \left[ (x-2) \left((x-2)^2-2 n\right) + \left(x^2 -2x + 2\right)\sqrt{x^2-4} \right] + \left(\sqrt{x^2-4}-x\right)^n \left[ - (x-2) \left((x-2)^2-2 n\right) + \left(x^2 -2 x + 2\right)\sqrt{x^2-4} \right] + (-1)^n 2^{n+2} (1-x) \sqrt{x^2-4}. \end{align*}

This determines our recursion for $a_n$, and solves your problem. (You will have to compute the first few values of $a_n$ and $b_n$ by hand.) I did this using Mathematica and verified everything I've written above for $n \leq 50$.


Here are the coefficients for the characteristic polynomial for $3\le n \le 16$ (arranged in order from the constant to $\lambda^n$). It looks like a recursive identity is lurking.

$$\matrix{ [0,-2,0,1]\cr [1,-2,-4,0,1]\cr [2,3,-4,-6,0,1]\cr [0,6,8,-6,-8,0,1]\cr [-2,-4,14,16,-8,-10,0,1]\cr [1,-12,-14,26,27,-10,-12,0,1]\cr [4,5,-34,-34,42,41,-12,-14,0,1]\cr [0,20,21,-74,-68,62,58,-14,-16,0,1]\cr [-4,-6,66,61,-138,-120,86,78,-16,-18,0,1]\cr [1,-30,-30,166,142,-232,-194,114,101,-18,-20,0,1]\cr [6,7,-114,-100,352,286,-362,-294,146,127,-20,-22,0,1]\cr [0,42,40,-324,-264,664,520,-534,-424,182,156,-22,-24,0,1]\cr [-6,-8,180,152,-768,-596,1150,876,-754,-588,222,188,-24,-26,0,1]\cr [1,-56,-52,572,450,-1604,-1202,1866,1391,-1028,-790,266,223,-26,-28,0,1]\cr }$$

(For some reason, Maple calculates the characteristic polynomial as $\det(\lambda I-A)$.)

The coefficient of $\lambda^n$ is $1$, the coefficient of $\lambda^{n-1}$ is $0$, the coefficient of $\lambda^{n-2}$ is $4-2n$.

The constant terms are $0, 1, -2, 0, 2, 1, -4, 0, 4, 1, -6, 0, 6, 1, -8, 0, 8, 1$, which is a repeating pattern of $1,-2k,0,2k$, once you get past $n=3$.

The coefficients of $\lambda^{n-3}$ are $1,3,8,16,27,41,\ldots$, whose first difference is $2,5,8,11,14,\ldots$. Similarly, the first difference of $2,6,14,26,42,62,86$ (the coefficient of $\lambda^{n-4}$) is $4,8,12,16,20,\ldots$.

Maple code to produce the matrices:

An := proc (n) local i, j, A;
   A := Matrix (n, n);
   for i from 3 to n-1 do: A[i, i+1] := 1: A [i, i-1] := 1: A [1,i] := 1: A [i,1] := 1: od:
   A[2,3] := 1: A[1,n] := 1: A [n,1] := 1: A [n, n-1] := 1: 
   A;
end proc:

This is not really an answer, but too long for a comment. Also, I don't think we can have images in comments.

I made some numerical tests with the computer and I thought that you might be interested in the results. In the plots below you see all eigenvalues of $A$ (first plot) and $B$ (second plot) as functions of the size of the matrices. It appears that you have two eigenvalues that grow (in absolute value), while all others are located inside the interval $[-2,2]$.

Eigenvalues for $A$: A

Eigenvalues for $B$: B