24
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.