AFTD Auto-Formalizing Theoretical Domains

Matrix.IsHermitian.spectrum_subset_Ici_of_sub

theoremverifiedformalizationimported Lean

Matrix.IsHermitian.spectrum_subset_Ici_of_sub

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Matrix in
open BigOperators in
variable {n π•œ : Type*} in
variable [RCLike π•œ] [DecidableEq n] in
open scoped ComplexOrder MatrixOrder in
open ComplexOrder in
theorem Matrix.IsHermitian.spectrum_subset_Ici_of_sub {d π•œ : Type*} [Fintype d] [DecidableEq d] [RCLike π•œ]
  {A x : Matrix d d π•œ} (hA : A.IsHermitian) (hl : (x - A).PosSemidef) :
    spectrum ℝ x βŠ† Set.Ici (β¨… i, hA.eigenvalues i)
Formalizes
QuantumInfo, `Matrix.IsHermitian.spectrum_subset_Ici_of_sub`
Lean proof
By Alex Meiburg, from github.com/leanprover-community/physlib at e411c6e89692 (Copyright (c) 2025 Alex Meiburg. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.34.1.
Verified
17 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 2

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Matrix in
open BigOperators in
variable {n π•œ : Type*} in
variable [RCLike π•œ] [DecidableEq n] in
open scoped ComplexOrder MatrixOrder in
open ComplexOrder in
theorem Matrix.IsHermitian.spectrum_subset_Ici_of_sub {d π•œ : Type*} [Fintype d] [DecidableEq d] [RCLike π•œ]
  {A x : Matrix d d π•œ} (hA : A.IsHermitian) (hl : (x - A).PosSemidef) :
    spectrum ℝ x βŠ† Set.Ici (β¨… i, hA.eigenvalues i) := by
  --Thanks Aristotle
  intro ΞΌ hΞΌ
  obtain ⟨v, hv₁, hvβ‚‚βŸ© : βˆƒ v : d β†’ π•œ, v β‰  0 ∧ x.mulVec v = ΞΌ β€’ v := by
    have h_singular : βˆƒ v : d β†’ π•œ, v β‰  0 ∧ (ΞΌ β€’ 1 - x).mulVec v = 0 := by
      simp only [spectrum.mem_iff, Matrix.isUnit_iff_isUnit_det, isUnit_iff_ne_zero, ne_eq, Decidable.not_not] at hΞΌ
      convert Matrix.exists_mulVec_eq_zero_iff.mpr hΞΌ;
      simp [Algebra.smul_def]
    refine h_singular.imp fun v h ↦ ⟨h.left, ?_⟩
    simp_all [Matrix.sub_mulVec, sub_eq_iff_eq_add, funext_iff, Matrix.mulVec, dotProduct, Matrix.one_apply]
  -- Since $x - A$ is positive semidefinite, for any eigenvalue $\lambda$ of $x$, we have $\lambda \geq \min(\text{eigenvalues of } A)$.
  have h_lower_bound : βˆ€ (v : d β†’ π•œ), v β‰  0 β†’ (star v ⬝α΅₯ (x.mulVec v)) β‰₯ (β¨… i, (hA.eigenvalues i)) * (star v ⬝α΅₯ v) := by
    intro v hv_nonzero
    have h_eigenvalue : (star v ⬝α΅₯ (A.mulVec v)) β‰₯ (β¨… i, (hA.eigenvalues i)) * (star v ⬝α΅₯ v) := by
      have h_expand : (star v ⬝α΅₯ (A.mulVec v)) = βˆ‘ i, (hA.eigenvalues i) * (star (hA.eigenvectorBasis i) ⬝α΅₯ v) * (star v ⬝α΅₯ (hA.eigenvectorBasis i)) := by
        have h_decomp : A = βˆ‘ i, (hA.eigenvalues i) β€’ (Matrix.of (fun j k => (hA.eigenvectorBasis i j) * (star (hA.eigenvectorBasis i k)))) := by
          convert Matrix.IsHermitian.spectral_theorem hA using 1;
          ext i j
          simp only [RCLike.star_def, Matrix.smul_of, Matrix.sum_apply, Matrix.of_apply,
            Pi.smul_apply, Matrix.diagonal, Function.comp_apply, Matrix.mul_apply,
            Matrix.IsHermitian.eigenvectorUnitary_apply, mul_ite, mul_zero,
            Finset.sum_ite_eq', Finset.mem_univ, ↓reduceIte, Matrix.star_apply,
            Unitary.conjStarAlgAut_apply]
          simp [ mul_comm, mul_left_comm, Algebra.smul_def ]
          congr! 1
          simp [Algebra.algebraMap_eq_smul_one]
        -- Substitute the decomposition of $A$ into the expression $(star v ⬝α΅₯ (A.mulVec v))$.
        have h_subst : (star v ⬝α΅₯ (A.mulVec v)) = βˆ‘ i, (hA.eigenvalues i) * (star v ⬝α΅₯ (Matrix.mulVec (Matrix.of (fun j k => (hA.eigenvectorBasis i j) * (star (hA.eigenvectorBasis i k)))) v)) := by
          -- Substitute the decomposition of $A$ into the expression $(star v ⬝α΅₯ (A.mulVec v))$ and use the linearity of matrix multiplication.
          have h_subst : (star v ⬝α΅₯ (A.mulVec v)) = (star v ⬝α΅₯ ((βˆ‘ i, (hA.eigenvalues i) β€’ (Matrix.of (fun j k => (hA.eigenvectorBasis i j) * (star (hA.eigenvectorBasis i k))))).mulVec v)) := by
            rw [ ← h_decomp ];
          -- By the linearity of matrix multiplication and the dot product, we can distribute the sum over the dot product.
          have h_distribute : (star v ⬝α΅₯ (βˆ‘ i, (hA.eigenvalues i) β€’ (Matrix.of (fun j k => (hA.eigenvectorBasis i j) * (star (hA.eigenvectorBasis i k))))).mulVec v) = βˆ‘ i, (star v ⬝α΅₯ ((hA.eigenvalues i) β€’ (Matrix.of (fun j k => (hA.eigenvectorBasis i j) * (star (hA.eigenvectorBasis i k))))).mulVec v) := by
            -- By the linearity of matrix multiplication and the dot product, we can distribute the sum over the dot product. This follows from the fact that matrix multiplication is linear.
            have h_distribute : βˆ€ (M N : Matrix d d π•œ) (v : d β†’ π•œ), Star.star v ⬝α΅₯ (M + N).mulVec v = Star.star v ⬝α΅₯ M.mulVec v + Star.star v ⬝α΅₯ N.mulVec v := by
              simp [ Matrix.add_mulVec, dotProduct_add ];
            -- By induction on the number of terms in the sum, we can apply the distributive property repeatedly.
            have h_induction : βˆ€ (n : β„•) (M : Fin n β†’ Matrix d d π•œ) (v : d β†’ π•œ), Star.star v ⬝α΅₯ (βˆ‘ i, M i).mulVec v = βˆ‘ i, Star.star v ⬝α΅₯ (M i).mulVec v := by
              intro n M v
              induction n
              Β· simp [*]
              Β· simp [Fin.sum_univ_succ, *]
            convert h_induction ( Fintype.card d ) ( fun i => Matrix.of ( hA.eigenvalues ( Fintype.equivFin d |>.symm i ) β€’ fun j k => hA.eigenvectorBasis ( Fintype.equivFin d |>.symm i ) j * starRingEnd π•œ ( hA.eigenvectorBasis ( Fintype.equivFin d |>.symm i ) k ) ) ) v using 1;
            Β· rw [ ← Equiv.sum_comp ( Fintype.equivFin d ) ];
              simp [ Fintype.equivFin ];
            Β· rw [ ← Equiv.sum_comp ( Fintype.equivFin d ) ];
              simp [ Fintype.equivFin ];
          convert h_distribute using 1;
          simp only [dotProduct, Pi.star_apply, RCLike.star_def, Matrix.mulVec, Matrix.of_apply,
            Finset.mul_sum _ _ _, Matrix.smul_apply, Algebra.smul_mul_assoc,
            Algebra.mul_smul_comm];
          simp [ Algebra.smul_def ];
        convert h_subst using 2;
        simp only [dotProduct, Pi.star_apply, RCLike.star_def, mul_comm, mul_assoc, Matrix.mulVec,
          Matrix.of_apply, mul_eq_mul_left_iff, map_eq_zero];
        simp [ mul_comm, mul_left_comm, Finset.mul_sum _ _ _ ];
      -- Since $\lambda_i \geq \inf(\text{eigenvalues of } A)$ for all $i$, we can bound each term in the sum.
      have h_bound : βˆ€ i, (hA.eigenvalues i) * (star (hA.eigenvectorBasis i) ⬝α΅₯ v) * (star v ⬝α΅₯ (hA.eigenvectorBasis i)) β‰₯ (β¨… i, (hA.eigenvalues i)) * (star (hA.eigenvectorBasis i) ⬝α΅₯ v) * (star v ⬝α΅₯ (hA.eigenvectorBasis i)) := by
        intro i
        have h_eigenvalue_bound : (hA.eigenvalues i) β‰₯ (β¨… i, (hA.eigenvalues i)) :=
          ciInf_le (Set.finite_range _).bddBelow _
        -- Since the product of the inner products is real and non-negative, multiplying both sides of the inequality by this product preserves the inequality.
        have h_nonneg : 0 ≀ (star (hA.eigenvectorBasis i) ⬝α΅₯ v) * (star v ⬝α΅₯ (hA.eigenvectorBasis i)) := by
          -- Since the inner product is conjugate symmetric, we have star v ⬝α΅₯ (hA.eigenvectorBasis i) = conjugate(star (hA.eigenvectorBasis i) ⬝α΅₯ v).
          have h_conj_symm : star v ⬝α΅₯ (hA.eigenvectorBasis i) = star (star (hA.eigenvectorBasis i) ⬝α΅₯ v) := by
            simp [ dotProduct, mul_comm];
          rw [ h_conj_symm ];
          exact mul_star_self_nonneg (star (hA.eigenvectorBasis i) ⬝α΅₯ v);
        norm_num [ mul_assoc ];
        exact mul_le_mul_of_nonneg_right ( mod_cast h_eigenvalue_bound ) h_nonneg;
      -- Since $\sum_{i} (star (hA.eigenvectorBasis i) ⬝α΅₯ v) * (star v ⬝α΅₯ (hA.eigenvectorBasis i)) = star v ⬝α΅₯ v$, we can factor out $(β¨… i, (hA.eigenvalues i))$ from the sum.
      have h_sum : βˆ‘ i, (star (hA.eigenvectorBasis i) ⬝α΅₯ v) * (star v ⬝α΅₯ (hA.eigenvectorBasis i)) = star v ⬝α΅₯ v := by
        have h_sum : βˆ‘ i, (star (hA.eigenvectorBasis i) ⬝α΅₯ v) β€’ (hA.eigenvectorBasis i) = v := by
          have := hA.eigenvectorBasis.sum_repr (WithLp.toLp 2 v);
          convert this using 1;
          simp only [dotProduct, Pi.star_apply, RCLike.star_def, mul_comm,
            hA.eigenvectorBasis.repr_apply_apply, PiLp.inner_apply, RCLike.inner_apply];
          simp only [WithLp.ofLp_sum, WithLp.ofLp_smul]
          have key : βˆ€ (c : d β†’ π•œ) (f : d β†’ EuclideanSpace π•œ d) (w : d β†’ π•œ),
              (βˆ‘ x, c x β€’ (f x).ofLp = w) ↔ (βˆ‘ x, c x β€’ f x = WithLp.toLp 2 w) := by
            intro c f w
            conv_lhs => rw [show βˆ‘ x, c x β€’ (f x).ofLp = (βˆ‘ x, c x β€’ f x).ofLp from by
              rw [WithLp.ofLp_sum]; simp [WithLp.ofLp_smul]]
            constructor
            Β· intro h; apply_fun WithLp.toLp 2 at h; simpa using h
            Β· intro h; apply_fun WithLp.ofLp at h; simpa using h
          exact key _ _ _
        -- Taking the inner product of both sides of h_sum with star v, we get the desired equality.
        have h_inner : star v ⬝α΅₯ (βˆ‘ i, (star (hA.eigenvectorBasis i) ⬝α΅₯ v) β€’ (hA.eigenvectorBasis i)) = star v ⬝α΅₯ v := by
          congr 1
          simp_rw [← WithLp.ofLp_smul, ← WithLp.ofLp_sum, h_sum]
        convert h_inner using 1;
        simp [ dotProduct, Finset.mul_sum _ _ _ ];
        exact Finset.sum_comm.trans ( Finset.sum_congr rfl fun _ _ => Finset.sum_congr rfl fun _ _ => by ring );
      rw [ h_expand ];
      refine' le_trans _ ( Finset.sum_le_sum fun i _ => h_bound i );
      simp only [ mul_assoc];
      rw [ ← Finset.mul_sum _ _ _, h_sum ];
    rw [Matrix.posSemidef_iff_dotProduct_mulVec] at hl
    have := hl.2 v
    simp [Matrix.sub_mulVec] at this
    exact le_trans h_eigenvalue this;
  change (β¨… i, hA.eigenvalues i) ≀ ΞΌ
  have := h_lower_bound v hv₁
  simp_all only [ne_eq, star, RCLike.star_def, Matrix.dotProduct_mulVec, ge_iff_le,
    dotProduct_smul];
  simp_all only [dotProduct, mul_comm, RCLike.mul_conj];
  rw [ Algebra.smul_def ] at this;
  -- Since the sum of the squares of the norms of v is positive, we can divide both sides of the inequality by it.
  have h_sum_pos : 0 < βˆ‘ x : d, (β€–v xβ€– : ℝ) ^ 2 := by
    contrapose! hv₁;
    simp_all only [funext_iff, Pi.zero_apply, not_forall, forall_exists_index, Matrix.mulVec, Pi.smul_apply]
    intro i
    rw [← norm_eq_zero]
    simpa [ sq_nonneg ] using le_antisymm ( le_trans ( Finset.single_le_sum ( fun a _ => sq_nonneg ( β€–v aβ€– ) ) ( Finset.mem_univ i ) ) hv₁ ) ( sq_nonneg ( β€–v iβ€– ) )
  norm_cast at this;
  nlinarith
See it in the graphDiscuss this resultChallenge it