Block Lanczos successive-iteration interlacing conjecture

Strict block-Lanczos interlacing at every subsequent iteration

We prove the conjecture posed in Section 2.1 of D. Šimonová and P. Tichý, On finite precision block Lanczos computations, BIT Numerical Mathematics 65 (2025), Article 47, doi:10.1007/s10543-025-01089-2, arXiv:2507.16484. In fact, a stronger sharp spectral-gap theorem holds for every irreducible symmetric block-tridiagonal matrix.

A sharp spectral-gap theorem

Fix a block size $p\ge1$, and let

$$T_j= \begin{pmatrix} A_1&B_2^{\mathsf T}&&&0\\ B_2&A_2&B_3^{\mathsf T}&&\\ &B_3&A_3&\ddots&\\ &&\ddots&\ddots&B_j^{\mathsf T}\\ 0&&&B_j&A_j \end{pmatrix}, \tag{1}$$

where every $A_r\in\mathbb R^{p\times p}$ is symmetric and every $B_r\in\mathbb R^{p\times p}$ is invertible. Write $T_k$ for its leading $kp\times kp$ principal block submatrix, with $1\le k<j$.

Spectral-gap theorem. If $a<b$ and

$$\sigma(T_j)\cap(a,b)=\varnothing, \tag{2}$$

then $T_k$ has at most $p$ eigenvalues in $[a,b]$, counted with algebraic multiplicity.

Proof. Suppose instead that $T_k$ has at least $p+1$ eigenvalues in $[a,b]$. Let $E$ be a $(p+1)$-dimensional subspace spanned by orthonormal eigenvectors corresponding to such eigenvalues. Projection onto the last $p$-dimensional block defines a linear map

$$\pi_k:E\longrightarrow\mathbb R^p. \tag{3}$$

By rank–nullity, there exists a nonzero $q\in E$ with

$$q_k=0. \tag{4}$$

Extend $q$ by zero blocks to a vector in $\mathbb R^{jp}$. Block tridiagonality and (4) imply

$$T_jq= \begin{pmatrix}T_kq\\0\end{pmatrix}. \tag{5}$$

Consequently, for the quadratic polynomial

$$f(x)=(x-a)(x-b), \tag{6}$$

we obtain

$$\begin{aligned} \langle q,f(T_j)q\rangle &=\|T_jq\|^2-(a+b)\langle q,T_jq\rangle +ab\|q\|^2\\ &=\langle q,f(T_k)q\rangle. \end{aligned} \tag{7}$$

By (2), $f(\lambda)\ge0$ for every $\lambda\in\sigma(T_j)$. Therefore $f(T_j)$ is positive semidefinite. On the other hand, since $q\in E$, the spectral expansion for $T_k$ gives

$$\langle q,f(T_k)q\rangle =\sum_{\lambda\in\sigma(T_k)\cap[a,b]} (\lambda-a)(\lambda-b)\,\|P_\lambda q\|^2 \le0, \tag{8}$$

where $P_\lambda$ denotes the orthogonal spectral projection. Hence both sides of (7) vanish. Positive semidefiniteness then implies

$$f(T_j)q=0. \tag{9}$$

Let $t$ be the largest block index for which $q_t\ne0$. By (4),

$$t\le k-1, \qquad t+2\le j. \tag{10}$$

The $(t+2)$-nd block of $q$ and of $T_jq$ vanishes. The corresponding block of $T_j^2q$ is obtained by taking the unique two-step block path from $t$ to $t+2$. Thus

$$\bigl(f(T_j)q\bigr)_{t+2} =\bigl(T_j^2q\bigr)_{t+2} =B_{t+2}B_{t+1}q_t\ne0, \tag{11}$$

because both off-diagonal blocks are invertible. This contradicts (9), proving the spectral-gap theorem.

The bound $p$ cannot be improved. Take

$$T_2= \begin{pmatrix}0&I_p\\I_p&0\end{pmatrix}, \qquad T_3= \begin{pmatrix} 0&I_p&0\\ I_p&0&I_p\\ 0&I_p&0 \end{pmatrix}. \tag{12}$$

Their respective spectra are

$$\sigma(T_2)=\{-1,1\}, \qquad \sigma(T_3)=\{-\sqrt2,0,\sqrt2\}, \tag{13}$$

with each displayed eigenvalue having multiplicity $p$. The open spectral gap $(0,\sqrt2)$ of $T_3$ contains exactly $p$ eigenvalues of $T_2$, all equal to $1$.

Proof of the block-Lanczos conjecture

Write the ordered Ritz values of $T_k$ as

$$\theta_1^{(k)}\le\theta_2^{(k)}\le\cdots\le\theta_{kp}^{(k)}. \tag{14}$$

Every eigenvalue of an irreducible symmetric block-tridiagonal matrix has multiplicity at most $p$. Indeed, the eigenvector equation determines every subsequent block uniquely from the first block, since each $B_r$ is invertible. The map sending an eigenvector to its first block is therefore injective into $\mathbb R^p$. In particular,

$$\theta_i^{(k)}<\theta_{i+p}^{(k)} \qquad \bigl(1\le i\le(k-1)p\bigr). \tag{15}$$

Fix any later iteration $j$ with $k<j\le s$, and set

$$a=\theta_i^{(k)}, \qquad b=\theta_{i+p}^{(k)}. \tag{16}$$

The closed interval $[a,b]$ contains at least the $p+1$ Ritz values

$$\theta_i^{(k)},\theta_{i+1}^{(k)},\ldots, \theta_{i+p}^{(k)}, \tag{17}$$

counted with multiplicity. The spectral-gap theorem therefore rules out $\sigma(T_j)\cap(a,b)=\varnothing$. Hence

$$\boxed{ \sigma(T_j)\cap \bigl(\theta_i^{(k)},\theta_{i+p}^{(k)}\bigr) \ne\varnothing \quad \text{for every }k<j\le s \text{ and }1\le i\le(k-1)p. } \tag{18}$$

The full-dimension block-Krylov assumption in the conjecture guarantees precisely the invertibility of the off-diagonal blocks required above. Thus the conjecture holds for every block size and every subsequent Lanczos iteration, and the stronger spectral-gap count $p$ is optimal.