7
$\begingroup$

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.‎

           

$\endgroup$
  • $\begingroup$ How can this be unitary? Do you mean hermitian? $\endgroup$ – Robert Israel Jun 25 '15 at 15:15
  • $\begingroup$ Are all the values inside the band equal to $ct+d$, or can there be zeros also inside the band? $\endgroup$ – Federico Poloni Jun 25 '15 at 15:41
  • $\begingroup$ @FedericoPoloni Yes, most of the elements inside the band are equal to zero. I edited the question, A is Hermitian. $\endgroup$ – Toughee Jun 26 '15 at 6:13
  • 1
    $\begingroup$ @Tgh, can you give us some numerical results about your question? $\endgroup$ – Shahrooz Janbaz Jun 27 '15 at 10:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Carlo Beenakker Jul 19 '15 at 11:11
5
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice View @Poloni, but I suspect that the general form of the question can be reduces to the $I+L$, where $L$ is tridiagonal. $\endgroup$ – Shahrooz Janbaz Jul 20 '15 at 11:54
  • $\begingroup$ @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... $\endgroup$ – Toughee Jul 20 '15 at 14:38
  • $\begingroup$ @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. $\endgroup$ – Toughee Jul 20 '15 at 14:38
  • $\begingroup$ @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? $\endgroup$ – Federico Poloni Jul 20 '15 at 14:57
  • $\begingroup$ @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. $\endgroup$ – Toughee Jul 20 '15 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.