Cauchy's Interlacing Theorem says that given an $n \times n$ symmetric matrix $A$, let $B$ be an $(n-1) \times (n-1)$ principal submatrix of it, then the eigenvalues of $A$ and those of $B$ interlace.
Using this property, one can obtain a lower bound on the $k$-th largest eigenvalue of a $t \times t$ principal submatrix of $A$, using the $(k+n-t)$-th largest eigenvalue of $A$. This lower bound is best possible, for example when $A$ is diagonal. But for many interesting (fixed) matrices, such bound is usually far from being optimal. For example, let $$A=\begin{bmatrix}
0 & 1 & 1 & 0\\
1 & 0 & 0 & 1\\
1 & 0 & 0 & 1\\
0 & 1 & 1 & 0
\end{bmatrix}$$
The eigenvalues of $A$ are $2, 0, 0, -2$. So if we would like to bound from below the largest eigenvalue of its $3 \times 3$ principal submatrix using Cauchy's Theorem, we only get a lower bound of $0$. However it is straightforward to check that it is always at least $\sqrt{2}$.
I am wondering if there is a more "quantitative" Interlacing Theorem, say if your matrix satisfies some additional properties (non-negative, binary, etc.), then one can obtain a better lower bound on the $k$-th largest eigenvalue of a $t \times t$ principal submatrix of $A$?
Best Answer
This is only a partial answer to the case when the symmetric matrix is nonnegative and only applies for bounding the so-called Perron root (i.e., the spectral radius).
If $$r_i = r_i(A) := \sum_{k=1}^n a_{ik}$$ and $\rho = \rho(A) := \max_{\lambda \in \sigma(A)}\{|\lambda|\}$, then $$\min_{1 \le i \le n} r_i \le \rho \le \max_{1 \le i \le n} r_i.$$ This result is due to Frobenius [MR0235974].
For example, for the $3$-by-$3$ leading principal sub-matrix $$ B:= \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{bmatrix}, $$ we obtain $1 \le \rho(B) \le 2$.
One way to try and improve these bounds is by applying the same bounds to $D^{-1} A D$, where $D$ is a diagonal matrix with positive diagonal entries.
There are many other works in the literature that are dedicated to improving the Frobenius bounds above (too many to list here, but I would be happy to email you a list if you'd like), but many are quite complicated (it seems to me that you want to get $\sqrt{2}$ as a lower bound).