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$
7
  • $\begingroup$ How can this be unitary? Do you mean hermitian? $\endgroup$ Jun 25, 2015 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$ Jun 25, 2015 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, 2015 at 6:13
  • 1
    $\begingroup$ @Tgh, can you give us some numerical results about your question? $\endgroup$
    – Shahrooz
    Jun 27, 2015 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$ Jul 19, 2015 at 11:11

1 Answer 1

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?

$\endgroup$
5
  • $\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
    Jul 20, 2015 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, 2015 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, 2015 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$ Jul 20, 2015 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, 2015 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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