# Can I find the gap between the two least eigenvalues of this special matrix A(t)?‎

I am interested in finding the gap between the two least eigenvalues of $A(t)$, a Hermitian $N\times N$ sparse ‎matrix whose diagonal elements are $a_it+b_i\,(1\leq i\leq N)$, and all off-diagonal non-zero elements ‎are the same and equal to $ct+d$. Furthermore, $A(t)$ is a banded matrix, that is, $a_{ij}=0$ for $( 1\leq i\leq N) \& (j>i+k)$ and $(1\leq j\leq N) \& (i> j+k)$, with $k<N$ fixed. Since real-scaled $N$ is larger than $10^6$, determining ‎the eigenvalues and then calculating the gap $(g)$ is not practical. Thus, even bounding the gap can ‎be satisfactory.‎

However, interlacing theorem and Courant-Weyl inequalities provide some bounds for the ‎eigenvalues, but it is not enough since they involve the most and the least eigenvalues, so the ‎bounds are to some extent wide. Another note I should mention is that while I need to calculate $g$ ‎for a range of values for $t$, so my main (and optimistic) goal is to derive $g$ in terms of $t$. However, ‎calculation of the gap (or its bounds) for some fixed $t_0 \neq 0$ can also do some good.

Now my question is that, according to the structure of $A(t)$, can I calculate $g$ or derive any better bound ‎for it? Is there any sharp inequality that can help?‎
Any other useful comment would be appreciated. ‎

Edit: To be more illustrative, here is an example of $A(t)$ (with $N=8$): ‎ ‎$$\begin{bmatrix}‎ ‎ 3-t & t-1 & t-1 & 0 & t-1 & 0 & 0 & 0 \\‎ ‎ t-1 & 3 (t+1) & 0 & t-1 & 0 & t-1 & 0 & 0 \\‎ ‎ t-1 & 0 & 3 (t+1) & t-1 & 0 & 0 & t-1 & 0 \\‎ ‎ 0 & t-1 & t-1 & 3-3 t & 0 & 0 & 0 & t-1 \\‎ ‎ t-1 & 0 & 0 & 0 & 7 t+3 & t-1 & t-1 & 0 \\‎ ‎ 0 & t-1 & 0 & 0 & t-1 & 3-t & 0 & t-1 \\‎ ‎ 0 & 0 & t-1 & 0 & t-1 & 0 & t+3 & t-1 \\‎ ‎ 0 & 0 & 0 & t-1 & 0 & t-1 & t-1 & 5 t+3 \\‎ ‎\end{bmatrix}$$‎

and the plot for $g(t)$ for this example with $-1\leq t\leq 1$ is:‎ Edit: Here is a long shot of an almost real-scaled example of $A(t)$ (with $N=32768$). While all off-‎diagonal non-zero elements are the same, Indeed, diagonal elements still vary from others (and ‎may be from each other) -- though this is not visible at this scale.‎ • How can this be unitary? Do you mean hermitian? – Robert Israel Jun 25 '15 at 15:15
• Are all the values inside the band equal to $ct+d$, or can there be zeros also inside the band? – Federico Poloni Jun 25 '15 at 15:41
• @FedericoPoloni Yes, most of the elements inside the band are equal to zero. I edited the question, A is Hermitian. – Toughee Jun 26 '15 at 6:13
• @Tgh, can you give us some numerical results about your question? – Shahrooz Janbaz Jun 27 '15 at 10:34
• why not just use the Lanczos algorithm to numerically find the two smallest eigenvalues as function of $t$? for a sparse/banded matrix this should be quick. – Carlo Beenakker Jul 19 '15 at 11:11

You say that computing the gap for a fixed $t_0$ could also be good. I think I can do $t_0=0$ in a way that generalizes to examples of larger dimensions. (You haven't defined your matrix exactly for larger dimensions, but that is how I assume it works).

That matrix for $t=0$ is $A(0) = B\otimes I\otimes I + I\otimes B \otimes I + I\otimes I \otimes B$, where $I$ is the ($2\times 2$ in this example) identity matrix and $B=\begin{bmatrix}1 & -1\\ -1 & 1\end{bmatrix}$. Here $\otimes$ is the Kronecker product. By the properties of the Kronecker product, The eigenvalues of such a matrix are given by $\{\lambda_i+\lambda_j+\lambda_k: i,j,k \in \{1,2\}\}$, where $\lambda_1,\lambda_2$ are the eigenvalues of $B$. So in this case you get 0,2,2,2,4,4,4,6.

I imagine that what happens for larger dimensions is that $B$ is $I+L$, where $L$ is the tridiagonal matrix with (-1,0,-1), for which eigenvalues are known explicitly as $\lambda_j = 2\cos(j\pi/(n+1))+2$, $j=1,2,\dots,n$. So all eigenvalues are known and the gap is $\lambda_n-\lambda_{n-1}$.

This stuff is quite standard in numerical analysis (the key terms are "3d finite difference Laplace matrix").

I suspect that a similar trick may work for a generic $t$, but it looks tricky to make sense of the coefficients of $t$ on the diagonal. Do they come out of a formula?

• Nice View @Poloni, but I suspect that the general form of the question can be reduces to the $I+L$, where $L$ is tridiagonal. – Shahrooz Janbaz Jul 20 '15 at 11:54
• @Poloni, Thanks for your attention. The structure of $A(0)$ is the sum of the $n$ Kronecker products of $2 \times 2$ matrices ($B$ and $n-1$ Identities $I$), as you considered first. However the structure based on the tridiagonal $L$ may include that (I didn't test it). But, as you mentioned... – Toughee Jul 20 '15 at 14:38
• @Poloni, ...But, as you mentioned, the problem is about the coefficients of $t$ on diagonal, which are elements of an unsorted sequence. Is there any way to employ your method to predict the gap for some non-zero $t$, especially to predict the above plot. – Toughee Jul 20 '15 at 14:38
• @Toughee If the diagonal elements are completely arbitrary, I am afraid no. That's why I asked if you have a formula for them. Where do they come from? – Federico Poloni Jul 20 '15 at 14:57
• @Poloni, They are values of a function applied to a set of $N$ different integers. Since for different instances of the problem, the order of these integers as the input to the function can be chosen deliberately, I said they are elements of an unsorted sequence. – Toughee Jul 20 '15 at 15:28