# Generalization of Cauchy's eigenvalue interlacing theorem?

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$$?

## 1 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).