Cauchy interlacing

The eigenvalues of a Hermitian matrix and of any principal submatrix of one smaller size interlace, and so do the characteristic polynomials in the real symmetric case.

Results

Theorem (Cauchy). Let $A$ be a Hermitian $(n+1)\times(n+1)$ matrix over $\mathbb R$ or $\mathbb C$ with eigenvalues $\lambda_0\ge\dots\ge\lambda_n$. Let $A'$ be obtained by deleting the $i$-th row and column, with eigenvalues $\mu_0\ge\dots\ge\mu_{n-1}$. Then $$ \lambda_{k+1}\le\mu_k\le\lambda_k\qquad(0\le k<n). $$ If $A$ is real symmetric, then $\chi_{A'}\ll\chi_A$ for the characteristic polynomials.

Theorem (Weyl, rank-one update). Let $A$ be an $N\times N$ Hermitian matrix and $v$ a vector, with eigenvalues of $A$ and $B=A+vv^*$ listed in decreasing order. Then $\lambda_k(A)\le\lambda_k(B)$ for all $k$, and $\lambda_k(B)\le\lambda_{k-1}(A)$ for $k\ge1$. If $A$ is real symmetric and $v$ is real, then $\chi_A\ll\chi_{A+vv^T}$.

Proof

Both statements follow from the Courant–Fischer theorem.

References

See [God17]; [Fis05] and the Cauchy interlacing entry on symmetricfunctions.com.

  1. [God17] C. D. Godsil. Algebraic combinatorics. 2017.
    BibTeX
    @book{Godsil2017,
      doi = {10.1201/9781315137131},
      url2 = {https://doi.org/10.1201/9781315137131},
      year = {2017},
      month = oct,
      publisher = {Routledge},
      author = {C.D. Godsil},
      title = {Algebraic Combinatorics}
    }
  2. [Fis05] Steve Fisk. A very short proof of Cauchy's interlace theorem for eigenvalues of Hermitian matrices. arXiv e-prints, 2005.
    BibTeX
    @article{Fisk2005x,
      author = {Steve Fisk},
      title = {A very short proof of {C}auchy's interlace theorem for eigenvalues of {H}ermitian matrices},
      year = {2005},
      eprint = {math/0502408},
      url = {https://arxiv.org/abs/math/0502408},
      journal = {arXiv e-prints},
      journalref = {Amer. Math. Monthly, Vol 112, No. 2, Feb. 2005, page 118}
    }

Theorems

  • Eigenvalues of a principal submatrix interlaceMain result

    theorem cauchy_interlacing (𝕜 : Type*) [RCLike 𝕜] :
        ∀ {n : ℕ} (A : Matrix (Fin (n + 1)) (Fin (n + 1)) 𝕜) (hA : A.IsHermitian)
          (i : Fin (n + 1)),
          Interlace
            (sortedEigenvalues (A.submatrix i.succAbove i.succAbove)
              (hA.submatrix i.succAbove))
            (sortedEigenvalues A hA)
  • Characteristic polynomials of a principal submatrix interlace

    RealRooted.principalSubmatrix_charpoly_interlacessource
    theorem principalSubmatrix_charpoly_interlaces {n : ℕ}
        (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ)
        (hA : A.IsHermitian) (i : Fin (n + 1)) :
        Interlaces (A.submatrix i.succAbove i.succAbove).charpoly A.charpoly
  • Weyl: eigenvalues of A + vv* are at most the previous eigenvalues of A

    RealRooted.sortedEigenvalues_add_vecMulVec_succ_lesource
    theorem sortedEigenvalues_add_vecMulVec_succ_le {n : ℕ}
        {A : Matrix (Fin (n + 1)) (Fin (n + 1)) 𝕜} (hA : A.IsHermitian) (v : Fin (n + 1) → 𝕜)
        (hB : (A + vecMulVec v (star v)).IsHermitian) (k : Fin n) :
        sortedEigenvalues _ hB k.succ ≤ sortedEigenvalues A hA k.castSucc
  • Weyl: rank-one updates raise eigenvalues

    RealRooted.sortedEigenvalues_le_add_vecMulVecsource
    theorem sortedEigenvalues_le_add_vecMulVec {N : ℕ} {A : Matrix (Fin N) (Fin N) 𝕜}
        (hA : A.IsHermitian) (v : Fin N → 𝕜) (hB : (A + vecMulVec v (star v)).IsHermitian)
        (k : Fin N) : sortedEigenvalues A hA k ≤ sortedEigenvalues _ hB k
  • Weyl: characteristic polynomials of A and A + vvᵀ interlace

    RealRooted.charpoly_strictInterl_add_vecMulVecsource
    theorem charpoly_strictInterl_add_vecMulVec {N : ℕ} {A : Matrix (Fin N) (Fin N) ℝ}
        (hA : A.IsHermitian) (v : Fin N → ℝ) :
        StrictInterl A.charpoly (A + vecMulVec v v).charpoly

Lean source RealRooted/Challenges/Matrices/CauchyInterlacing.lean at revision d6670742. Formalized 2026-07-10.