Davis's lower bound on the change of eigenvalues

Let T and S be symmetric endomorphisms of an n-dimensional inner product space over ℝ or ℂ, with eigenvalues λ₀ ≥ ⋯ ≥ λₙ₋₁ and μ₀ ≥ ⋯ ≥ μₙ₋₁ listed in decreasing order, and let (vᵢ) be the orthonormal eigenbasis of T with T vᵢ = λᵢ vᵢ. Read in this basis, the perturbation H = S - T has diagonal entries hᵢ = Re⟪vᵢ, H vᵢ⟫, and S has diagonal entries dᵢ = Re⟪vᵢ, S vᵢ⟫ = λᵢ + hᵢ.

The Hoffman–Wielandt inequality bounds ∑ᵢ (μᵢ - λᵢ)² from above by the squared Frobenius norm of H. Davis's theorem is a matching lower bound: if the eigenvalues of S are pairwise at distance at least γ ≥ 0 and the diagonal part of H is small, ∑ᵢ hᵢ² ≤ (γ / √2)², then

∑ᵢ hᵢ² - (∑ᵢ μᵢ² - ∑ᵢ dᵢ²) ≤ ∑ᵢ (μᵢ - λᵢ)².

The first sum on the left is the squared Frobenius norm of the diagonal part of H in the basis (vᵢ), and ∑ᵢ μᵢ² - ∑ᵢ dᵢ² is the squared Frobenius norm of the off-diagonal part of S, which is also the off-diagonal part of H since T is diagonal in this basis. So the spectrum moves by at least the excess of the diagonal energy of the perturbation over its off-diagonal energy.

The proof combines two facts about the permutohedron of μ, the convex hull of the rearrangements of μ. The diagonal d of S lies in it, by Birkhoff's theorem applied to the doubly stochastic Schur weight matrix. And since μ has γ-separated coordinates, every point c of it satisfies (γ / √2) ‖μ - c‖ ≤ ⟪μ - c, μ⟫. With c = d and the Cauchy–Schwarz inequality |⟪μ - d, h⟫| ≤ ‖μ - d‖ ‖h‖ ≤ (γ / √2) ‖μ - d‖, this gives ⟪μ - d, μ + h⟫ ≥ 0, which is the bound after expanding μ - λ = (μ - d) + h.

Main results

• LinearMap.IsSymmetric.le_sum_sq_eigenvalues_sub: Davis's eigenvalue-change lower bound.

References

• C. Davis, The rotation of eigenvectors by a perturbation, J. Math. Anal. Appl. 6 (1963), 159–173, Theorem 4.1.

theorem LinearMap.IsSymmetric.le_sum_sq_eigenvalues_sub {𝕜 : Type u_1} {E : Type u_2} [RCLike 𝕜] [NormedAddCommGroup E] [InnerProductSpace 𝕜 E] [FiniteDimensional 𝕜 E] {T S : E →ₗ[𝕜] E} {n : ℕ} (hT : T.IsSymmetric) (hS : S.IsSymmetric) (hn : Module.finrank 𝕜 E = n) {γ : ℝ} (hγ : 0 ≤ γ) (hsep : Pairwise fun (i j : Fin n) => γ ≤ |hS.eigenvalues hn i - hS.eigenvalues hn j|) (hH : ∑ i : Fin n, RCLike.re (inner 𝕜 ((hT.eigenvectorBasis hn) i) ((S - T) ((hT.eigenvectorBasis hn) i))) ^ 2 ≤ (γ / √2) ^ 2) : ∑ i : Fin n, RCLike.re (inner 𝕜 ((hT.eigenvectorBasis hn) i) ((S - T) ((hT.eigenvectorBasis hn) i))) ^ 2 - (∑ i : Fin n, hS.eigenvalues hn i ^ 2 - ∑ i : Fin n, RCLike.re (inner 𝕜 ((hT.eigenvectorBasis hn) i) (S ((hT.eigenvectorBasis hn) i))) ^ 2) ≤ ∑ i : Fin n, (hS.eigenvalues hn i - hT.eigenvalues hn i) ^ 2

Davis's eigenvalue-change lower bound. Let T and S be symmetric, let (vᵢ) be the eigenbasis of T, and suppose the eigenvalues μᵢ of S are pairwise at distance at least γ ≥ 0. If the diagonal entries hᵢ = Re⟪vᵢ, (S - T) vᵢ⟫ of the perturbation satisfy ∑ᵢ hᵢ² ≤ (γ / √2)², then the sorted spectra satisfy

∑ᵢ hᵢ² - (∑ᵢ μᵢ² - ∑ᵢ Re⟪vᵢ, S vᵢ⟫²) ≤ ∑ᵢ (μᵢ - λᵢ)²,

where λᵢ are the eigenvalues of T. Here ∑ᵢ μᵢ² - ∑ᵢ Re⟪vᵢ, S vᵢ⟫² is the squared Frobenius norm of the off-diagonal part of S - T in the basis (vᵢ).