Diagonalize almost symmetric tridiagonal matrix

Question

I begin with an $n \times n$ real symmetric tridiagonal matrix. However, I replace the non-zero elements in the first and last rows with zeros, so it is no longer symmetric

$$M = \begin{bmatrix} 0 & 0 & & & \\ b_1 & a_2 & b_2 & & & \\ & & \ddots & & \\ & & b_{n-2} & a_{n-1} & b_{n-1} \\ & & & 0 & 0 \end{bmatrix}$$.

1. Is it possible to diagonalize this matrix to find $M = Q D Q^{-1}$ in $O(n^2)$ operations?
2. If the $b_i$ are all positive and the $a_i$ all negative, can we be sure that there are $n$ real (non-positive) eigenvalues?

The background is this is a numerical discretization of the Laplacian with specific boundary conditions. For this reason, in my example, the $b_i$ and $a_i$ are related approximately (not exactly) by $a_i \approx -2 b_i$.

Answer 1

Start with the matrix $$ M' = \begin{bmatrix} 0 & 0 \\ 0 & a_2 & b_2 \\ & & \ddots \\ & & b_{n-2} & a_{n-1} & 0 \\ & & & 0 & 0 \end{bmatrix}, $$ i.e. your matrix $M$ but with the two entries on the edges deleted. This is a symmetric tridiagonal matrix, so it can be diagonalized in $O(n^2)$ and has $n$ real eigenvalues. You can easily check that $M$ and $M'$ have the same eigenvalues ($tI-M$ can be transformed to $tI-M'$ with two elementary row operations).

Let $e_1,\dots,e_n$ be the standard basis vectors. The matrix $M'$ has $0$ as an eigenvalue with eigenvectors $e_1$ and $e_n$, and $n-2$ additional eigenvalues $\lambda_2,\dots,\lambda_{n-1}$ with corresponding orthonormal eigenvectors $v_2,\dots,v_{n-1}$. Since $M$ is nonsymmetric, its left and right eigenvectors are different. The right eigenvector corresponding to $\lambda_k$ is still $v_k$, but the left eigenvector changes to $$ u_k^*=\lambda_k v_k^* + b_1 (v_k^* e_2) e_1^* + b_n (v_k^* e_{n-1}) e_n^*. $$ Each of these vectors can obviously be computed in $O(n)$ once $\lambda_k$ and $v_k$ are known, for a total of $O(n^2)$ taking all $n-2$ such vectors into account. In order to prove that $u_k^*$ is really a left eigenvector, just write $M'=\sum_k \lambda_k v_k v_k^*$ and $M=M'+b_1 e_2 e_1^*+b_ne_{n-1}e_n^*$, then check that $u_k^* M = \lambda_k u_k^*$ (using the fact that $e_1,v_2,\dots,v_{n-1},e_n$ is an orthonormal basis).

Finally, we need to compute the left and right eigenvectors corresponding to the eigenvalue $0$. This time the left eigenvectors are unchanged, i.e. $e_1^*$ and $e_n^*$, but the right eigenvectors change. We are looking for vectors $x=(x_1,x_2,\dots,x_n)$ such that $Mx=0$, i.e. $$ \begin{align*} b_1 x_1 + a_2 x_2 + b_2 x_3 &= 0 \\ b_2 x_2 + a_3 x_3 + b_3 x_4 &= 0 \\ &\dots \\ b_{n-2} x_{n-2} + a_{n-1} x_{n-1} + b_{n-1} x_n &= 0. \end{align*} $$ We can thus recursively compute $x_k$ from $x_{k-1}$ and $x_{k-2}$. Starting with the two pairs of initial values $x_1=1,x_2=0$ and $x_1=0,x_2=1$ will therefore give us two eigenvectors corresponding to the eigenvalue $0$ in $O(n)$.

As to the question of whether the eigenvalues are nonpositive, here is a counterexample: $$ \begin{bmatrix} 0 & 0 & 0 & 0 \\ 2 & -1 & 2 & 0 \\ 0 & 2 & -1 & 2 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}. $$