Worked solution: Huang's signed hypercube adjacency matrix proof of the sensitivity conjecture (2019)

Step 2 of 7: The tool: Cauchy's interlacing theorem

In plain words

If you delete some rows and the matching columns from a symmetric matrix, the eigenvalues of the smaller matrix cannot stray far from the eigenvalues of the original: each one is squeezed between two eigenvalues of the big matrix. In particular, the top eigenvalue of any principal submatrix can never be larger than the top eigenvalue of the whole matrix, but it also cannot fall below a specific eigenvalue further down the list, depending on how many rows were deleted.

A \text{ symmetric } n\times n,\ B \text{ an } m\times m \text{ principal submatrix} \implies \lambda_i(A) \ge \lambda_i(B) \ge \lambda_{i+n-m}(A)

Detailed analysis

Huang's proof (2019, Section 2) rests on a classical fact from linear algebra: Cauchy's interlacing theorem. If $A$ is a symmetric $n \times n$ matrix with eigenvalues $\lambda_1 \ge \cdots \ge \lambda_n$ , and $B$ is an $m \times m$ principal submatrix of $A$ (obtained by deleting the same set of rows and columns) with eigenvalues $\mu_1 \ge \cdots \ge \mu_m$ , then for every $1 \le i \le m$ : $\lambda_i \ge \mu_i \ge \lambda_{i+n-m}$ . Huang cites this as Lemma 2.1, noting it follows from the Courant-Fischer-Weyl min-max principle.

Terms in this step

Eigenvalue: A scalar $\lambda$ such that $Av = \lambda v$ for some nonzero vector $v$ ; for a symmetric real matrix all eigenvalues are real and can be listed in decreasing order.
Principal submatrix: The matrix left after deleting the same set of row indices and column indices from a square matrix $A$ .

Knowledge used in this step

Eigenvalues and diagonalization