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 offdiagonal entries equal to 1. The spectrum of $B_n:=H_n+E_{11}$ is analytically wellknown. If we define $A_n^i:=H_nE_{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 $$22\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.
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_{j1} + (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 nonzero $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_{j1}$ 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 '14 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$ – Christian Remling Jul 15 '14 at 15:26