Let $n\geq2$ be an integer and $E_{ii}$ for an integer $2\leq i\leq n$ be the $n\times n$-matrix with its $ii$-entry equal to 1 and remaining entries equal zero. Furthermore, let $H_n:=\mathrm{tridiag}(-1,2,-1)$ denote a tridiagonal matrix with all main diagonal entries equal to 2 and off-diagonal entries equal to -1. The spectrum of $B_n:=H_n+E_{11}$ is analytically well-known. If we define $A_n^i:=H_n-E_{11}+2\cdot E_{ii}$, how can we show that for small values of $i$ (I assume $i\leq\mathrm{floor}(n/4)$), it holds $$2-2\cos\left(\frac{2\pi}{2n+1}\right)=\lambda_{\min}(B_n)<\lambda_\min(A_n^i)$$? At least some idea for $i=2$ would be helpful.


1 Answer 1


I'll assume that $n$ is large and $i\ll n$. However, I believe it should be possible to treat the general situation in the same way; as we'll see, we only need a certain simple property of the recursion (1) below.

By oscillation theory, we can characterize the smallest eigenvalue as follows: Let $u$ be the solution of the difference equation $$ -u_{j+1}-u_{j-1} + (2+V_j)u_j = \lambda u_j $$ with the initial values $u_0=0$, $u_1=1$. (Here $V_j$ records the changes made by the matrices $E$, so $V_1=1$ and $V_j=0$ otherwise for $B=B_n$, and the non-zero $V_j$'s for $A=A_n^i$ are $V_1=-1$, $V_i=2$.) Then the smallest eigenvalue is the first (= smallest) $\lambda$ for which $u_{n+1}=0$. Moreover, $\lambda$ is strictly smaller than the smallest eigenvalue precisely if $u$ is positive on $\{ 1,\ldots , n+1\}$.

The quotients $q_j=u_j/u_{j-1}$ solve $$ q_{j+1} =2-\lambda+V_j - \frac{1}{q_j} \quad\quad\quad (1) $$ Now consider this equation for $\lambda=\lambda_0\equiv \lambda_{\textrm{min}}(B)$. Since $\lambda_0\approx 0$ (more precisely, $\lambda_0\sim c/n^2$), we have that $q_2(B)\approx 3$, $q_2(A)\approx 1$. Next, approximately solving up to $i$, we find that $q_{i+1}(A)\approx 3$, $q_{i+1}(B)<2$.

From this point on, both $q$'s solve the same equation (1), with $V\equiv 0$. Now the inequality $q_j(A)>q_j(B)$ is preserved by (1), so the claim follows from the oscillation theory facts that I summarized above: $u_{n+1}(A)>0$ and $u_j(A)$ was positive on the whole interval $\{1,\ldots , n\}$, so we are still strictly below the spectrum of $A$.

  • $\begingroup$ Thank you very much, I appreciate your approach looking at those $q$-sequences $(1)$. So for plugging in $\lambda_0\approx0$ this looks easy to proof, but doesn't give any precise enough information about which values of $i$ fulfil $\lambda_\min(B_n)<\lambda_\min(A_n^i)$. If I understood the oscillation theory correctly, I have to plug $\lambda_\min(B_n)$ (or some upper approximation of it) into the $q$-sequence of $A_n^i$ and show $q_{j}(\lambda_\min(B_n))<0$ for all $j$? I think this remains not to be easy, or am I wrong? Perhaps there is some different approach? $\endgroup$
    – user56020
    Jul 15, 2014 at 15:13
  • $\begingroup$ The desired conclusion is equivalent to $q_{i+1}(A)>q_{i+1}(B)$, where $q_j$ solves (1) with $\lambda=\lambda_{\textrm{min}}(B)$ and the initial "value" $q_1=\infty$ (interpret this rigorously as $1/q_1=0$). As (1) can be solved explicitly, that looks quite tractable; I only used $n\gg 1$ for convenience, to quickly approximately solve (1). Oscillation theory is a standard approach to such problems, and I don't think you'll be able to make the problem much easier than that (of course, I might be wrong on this). $\endgroup$ Jul 15, 2014 at 15:26

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.