AFTD Auto-Formalizing Theoretical Domains

matrix_nuclear_norm_of_isHermitian

theoremverifiedformalization

For a real symmetric matrix $M$, its nuclear norm equals the sum of the absolute values of its eigenvalues.

Statement

theorem matrix_nuclear_norm_of_isHermitian {n : Type*} [Fintype n] [DecidableEq n]
    (M : Matrix n n ℝ) (hM : M.IsHermitian) :
    matrix_nuclear_norm M = ∑ j : Fin (Fintype.card n), |hM.eigenvalues₀ j|
Formalizes
scout/2610-10618-the-hellinger-conjecture-for-antipodal-boolean-functions.md:315
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • matrix_nuclear_normThe nuclear norm of a square real matrix $M$ is the sum of its singular values, where $M$ is viewed as a complex matrix.
  • Multiset.map_univ_eq_iffIf two functions from finite types have the same multiset of values, there exists a bijection between the domains that commutes with the…
Used by 1

Read back from the Lean

For any finite type n with decidable equality, and any n × n real matrix M, if M is Hermitian (i.e., symmetric), then the nuclear norm of M equals the sum over all j : Fin (Fintype.card n) of the absolute values of the eigenvalues of M (|hM.eigenvalues₀ j|).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The nuclear norm of a real symmetric matrix M is defined as the sum of the singular values of its complex embedding A, which are the square roots of the eigenvalues of Aᴴ A = A^2. By the spectral theorem, the characteristic polynomial of M^2 factors as ∏ i, (X - λ_i^2), so the roots of the characteristic polynomial of Aᴴ A are the squares of the eigenvalues of M. Equating multisets of roots shows that the eigenvalues of Aᴴ A are the squared eigenvalues λ_i^2 up to a permutation, and summing their square roots yields the sum of the absolute values |λ_i|.

  1. M * M diagonalizes to the square of its eigenvalue matrix under unitary conjugation.

    By the spectral theorem, the real symmetric matrix M decomposes as U D U* where U is a unitary matrix of eigenvectors and D is diagonal with the eigenvalues. Because unitary conjugation is an algebra homomorphism (map_mul), M^2 = U D^2 U*, where D^2 has diagonal entries (λ_i)^2 by diagonal_mul_diagonal and pow_two.

    lines 7–14

    uses map_mul, diagonal_mul_diagonal, pow_two

      have h_sq : M * M = conjStarAlgAut ℝ _ hM.eigenvectorUnitary
          (diagonal (fun i => (hM.eigenvalues i)^2)) := by
        conv_lhs => rw [hM.spectral_theorem]
        rw [← map_mul]
        congr 1
        rw [diagonal_mul_diagonal]
        ext i j
        simp [pow_two]
  2. The characteristic polynomial of M * M is ∏ i, (X - C (λ_i^2)).

    Substituting M * M = U D^2 U*, cyclic commutativity of the characteristic polynomial (charpoly_mul_comm) allows shifting U* across to cancel U, reducing the characteristic polynomial of M^2 to that of the diagonal matrix D^2. By charpoly_diagonal, this evaluates to the product of linear factors X - λ_i^2.

    lines 15–17

    uses conjStarAlgAut_apply, charpoly_mul_comm, mul_assoc, charpoly_diagonal

      rw [h_sq]
      rw [conjStarAlgAut_apply, charpoly_mul_comm, ← mul_assoc]
      simp [charpoly_diagonal]
  3. The complex embedding A of M is Hermitian (Aᴴ = A).

    Let A be the matrix M embedded into the complex numbers. Since M is symmetric (M j i = M i j by congr_fun on hM), each entry of its conjugate transpose Aᴴ equals the conjugate of a real entry, which is just the original entry, so Aᴴ = A.

    lines 23–30

    uses isHermitian_mul_conjTranspose_self, congr_fun, conjTranspose_apply

      let A : Matrix n n ℂ := M.map Complex.ofReal
      let hH := isHermitian_mul_conjTranspose_self Aᴴ
      have hA : Aᴴ = A := by
        ext i j
        have : M j i = M i j := by
          have h := congr_fun (congr_fun hM i) j
          simpa [conjTranspose_apply] using h
        simp [A, conjTranspose_apply, this]
  4. Aᴴ * Aᴴᴴ equals (M * M) mapped to ℂ entrywise.

    Using Aᴴ = A and the involution property of the conjugate transpose (conjTranspose_conjTranspose), the product simplifies to A * A. Expanding entrywise with mul_apply matches the complexification of the real matrix product M * M.

    lines 31–34

    uses conjTranspose_conjTranspose, mul_apply

      have hH_mat : Aᴴ * Aᴴᴴ = (M * M).map Complex.ofRealHom := by
        rw [conjTranspose_conjTranspose, hA]
        ext i j
        simp [A, mul_apply]
  5. The characteristic polynomial of Aᴴ * Aᴴᴴ is ∏ i, (X - C ((λ_i : ℂ)^2)).

    Applying the complex embedding homomorphism to the characteristic polynomial of M * M via charpoly_map and rewriting with the helper lemma matrix_nuclear_norm_of_isHermitian_charpoly_sq gives the product of linear factors over ℂ by Polynomial.map_prod.

    lines 35–37

    uses charpoly_map, matrix_nuclear_norm_of_isHermitian_charpoly_sq, Polynomial.map_prod

      have h_char : (Aᴴ * Aᴴᴴ).charpoly = ∏ i, (X - C ((hM.eigenvalues i : ℂ)^2)) := by
        rw [hH_mat, charpoly_map (M * M) Complex.ofRealHom, matrix_nuclear_norm_of_isHermitian_charpoly_sq M hM]
        simp [Polynomial.map_prod]
  6. The multiset of roots of (Aᴴ * Aᴴᴴ).charpoly is {(λ_i : ℂ)^2 : i ∈ n}.

    Each linear factor X - C ((λ_i : ℂ)^2) is non-zero by X_sub_C_ne_zero, so the product polynomial is non-zero by Finset.prod_ne_zero_iff. By Polynomial.roots_prod, the multiset of complex roots of this product is the multiset of values (λ_i : ℂ)^2 over the index type n.

    lines 38–45

    uses Finset.prod_ne_zero_iff, X_sub_C_ne_zero, Polynomial.roots_prod

      have h_ne_zero : (∏ i, (X - C ((hM.eigenvalues i : ℂ)^2))) ≠ 0 := by
        rw [Finset.prod_ne_zero_iff]
        intro i _
        exact X_sub_C_ne_zero _
      have h_roots_char : (Aᴴ * Aᴴᴴ).charpoly.roots =
          Multiset.map (fun i => ((hM.eigenvalues i : ℂ)^2)) Finset.univ.val := by
        rw [h_char, Polynomial.roots_prod _ _ h_ne_zero]
        simp [-map_pow]
  7. As multisets of real numbers, the eigenvalues of Aᴴ * Aᴴᴴ are {λ_i^2 : i ∈ n}.

    The roots of the characteristic polynomial of the Hermitian matrix Aᴴ * Aᴴᴴ are its eigenvalues embedded into ℂ. Equating this with the roots from the previous step gives equality of multisets after mapping along Complex.ofReal. Since Complex.ofReal is injective, Multiset.map_injective yields equality of the underlying multisets of real numbers.

    lines 46–58

    uses Multiset.map_map, map_pow, Multiset.map_injective, Complex.ofReal_injective

      have h_roots_eig : (Aᴴ * Aᴴᴴ).charpoly.roots =
          Multiset.map (Complex.ofReal ∘ hH.eigenvalues) Finset.univ.val :=
        hH.roots_charpoly_eq_eigenvalues
      have h_map_eq : Multiset.map Complex.ofReal (Multiset.map hH.eigenvalues Finset.univ.val) =
          Multiset.map Complex.ofReal (Multiset.map (fun i => (hM.eigenvalues i)^2) Finset.univ.val) := by
        rw [Multiset.map_map, Multiset.map_map]
        rw [← h_roots_eig, h_roots_char]
        congr 1
        ext i
        exact (map_pow Complex.ofRealHom _ 2).symm
      have h_real_eq : Multiset.map hH.eigenvalues Finset.univ.val =
          Multiset.map (fun i => (hM.eigenvalues i)^2) Finset.univ.val :=
        Multiset.map_injective Complex.ofReal_injective h_map_eq
  8. The sum of the square roots of the eigenvalues of Aᴴ * Aᴴᴴ equals ∑ i, |λ_i|.

    By Multiset.map_univ_eq_iff, two functions producing equal multisets on a finite type differ by a permutation e of the domain. Taking square roots gives √(λ_{e i}^2) = |λ_{e i}| by Real.sqrt_sq_eq_abs. Reindexing the sum along the equivalence e using Equiv.sum_comp gives ∑ i, |λ_i|.

    lines 59–64

    uses Multiset.map_univ_eq_iff, congr_fun, Real.sqrt_sq_eq_abs, Equiv.sum_comp

      rw [Multiset.map_univ_eq_iff] at h_real_eq
      obtain ⟨e, he⟩ := h_real_eq
      have h_sum_sqrt : ∑ i : n, Real.sqrt (hH.eigenvalues i) = ∑ i : n, |hM.eigenvalues i| := by
        have he_app (i : n) : hH.eigenvalues i = (hM.eigenvalues (e i))^2 := congr_fun he i
        simp_rw [he_app, Real.sqrt_sq_eq_abs]
        exact Equiv.sum_comp e (fun x => |hM.eigenvalues x|)
  9. The nuclear norm of M equals ∑ j : Fin (card n), |eigenvalues₀ j|.

    By definition, the nuclear norm of M is the sum of the square roots of the eigenvalues of Aᴴ * Aᴴᴴ. Rewriting with the previous sum identity and reindexing along the canonical bijection between n and Fin (Fintype.card n) via Fintype.equivOfCardEq and Equiv.sum_comp yields the goal.

    lines 65–68

    uses Equiv.sum_comp, Fintype.equivOfCardEq, Fintype.card_fin

      have h_def : matrix_nuclear_norm M = ∑ i : n, Real.sqrt (hH.eigenvalues i) := rfl
      rw [h_def, h_sum_sqrt]
      change (∑ i : n, |hM.eigenvalues₀ ((Fintype.equivOfCardEq (Fintype.card_fin _)).symm i)|) = _
      exact Equiv.sum_comp (Fintype.equivOfCardEq (Fintype.card_fin _)).symm (fun j => |hM.eigenvalues₀ j|)
map_mul
a multiplicative homomorphism preserves multiplication: f(x * y) = f(x) * f(y)
diagonal_mul_diagonal
the product of two diagonal matrices is diagonal with pointwise multiplied entries
pow_two
the square of an element equals the element multiplied by itself: a^2 = a * a
conjStarAlgAut_apply
unitary conjugation of x by u equals u * x * star u
charpoly_mul_comm
the characteristic polynomial of a matrix product is invariant under cyclic permutation: charpoly (A * B) = charpoly (B * A)
mul_assoc
multiplication is associative: (a * b) * c = a * (b * c)
charpoly_diagonal
the characteristic polynomial of a diagonal matrix is the product of (X - C d_i) over all diagonal entries
isHermitian_mul_conjTranspose_self
for any matrix A, the product A * Aᴴ is Hermitian
congr_fun
equal functions produce equal values on any argument
conjTranspose_apply
the (i, j) entry of the conjugate transpose Aᴴ is the complex conjugate of A j i
conjTranspose_conjTranspose
conjugate transposition is an involution: (Aᴴ)ᴴ = A
mul_apply
the (i, k) entry of a matrix product is the sum of products of corresponding row and column entries
charpoly_map
applying a ring homomorphism to matrix entries applies the homomorphism to the characteristic polynomial
matrix_nuclear_norm_of_isHermitian_charpoly_sq
for a real symmetric matrix M, the characteristic polynomial of M * M is ∏ i, (X - C (λ_i^2))
Polynomial.map_prod
applying a ring homomorphism to a finite product of polynomials distributes over the product
Finset.prod_ne_zero_iff
a finite product in an integral domain is non-zero if and only if each factor is non-zero
X_sub_C_ne_zero
the linear polynomial X - C r is non-zero
Polynomial.roots_prod
the multiset of roots of a non-zero product of polynomials is the multiset sum of their individual roots
Multiset.map_map
mapping a multiset by f and then by g is equivalent to mapping by g ∘ f
map_pow
a monoid homomorphism preserves powers: f(a^n) = f(a)^n
Multiset.map_injective
mapping a multiset by an injective function is injective on multisets
Complex.ofReal_injective
the canonical inclusion of real numbers into complex numbers is injective
Multiset.map_univ_eq_iff
two functions on a finite type have equal multisets of values if and only if they differ by a permutation of the domain
Real.sqrt_sq_eq_abs
the real square root of x^2 is the absolute value |x|
Equiv.sum_comp
reindexing a finite sum along a bijection of index sets preserves the sum
Fintype.equivOfCardEq
two finite types with equal cardinalities are equivalent (in bijection)
Fintype.card_fin
the cardinality of Fin n is n

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open Matrix Unitary Polynomialopen scoped BigOperators Matrixlemma matrix_nuclear_norm_of_isHermitian_charpoly_sq {n : Type*} [Fintype n] [DecidableEq n]    (M : Matrix n n ℝ) (hM : M.IsHermitian) :    (M * M).charpoly = ∏ i, (X - C ((hM.eigenvalues i)^2)) := by  have h_sq : M * M = conjStarAlgAut ℝ _ hM.eigenvectorUnitary      (diagonal (fun i => (hM.eigenvalues i)^2)) := by    conv_lhs => rw [hM.spectral_theorem]    rw [← map_mul]    congr 1    rw [diagonal_mul_diagonal]    ext i j    simp [pow_two]  rw [h_sq]  rw [conjStarAlgAut_apply, charpoly_mul_comm, ← mul_assoc]  simp [charpoly_diagonal]/-- For a real symmetric matrix, the nuclear norm equals the sum of the absolute values of its eigenvalues. -/theorem matrix_nuclear_norm_of_isHermitian {n : Type*} [Fintype n] [DecidableEq n]    (M : Matrix n n ℝ) (hM : M.IsHermitian) :    matrix_nuclear_norm M = ∑ j : Fin (Fintype.card n), |hM.eigenvalues₀ j| := by  let A : Matrix n n ℂ := M.map Complex.ofReal  let hH := isHermitian_mul_conjTranspose_self Aᴴ  have hA : Aᴴ = A := by    ext i j    have : M j i = M i j := by      have h := congr_fun (congr_fun hM i) j      simpa [conjTranspose_apply] using h    simp [A, conjTranspose_apply, this]  have hH_mat : Aᴴ * Aᴴᴴ = (M * M).map Complex.ofRealHom := by    rw [conjTranspose_conjTranspose, hA]    ext i j    simp [A, mul_apply]  have h_char : (Aᴴ * Aᴴᴴ).charpoly = ∏ i, (X - C ((hM.eigenvalues i : ℂ)^2)) := by    rw [hH_mat, charpoly_map (M * M) Complex.ofRealHom, matrix_nuclear_norm_of_isHermitian_charpoly_sq M hM]    simp [Polynomial.map_prod]  have h_ne_zero : (∏ i, (X - C ((hM.eigenvalues i : ℂ)^2))) ≠ 0 := by    rw [Finset.prod_ne_zero_iff]    intro i _    exact X_sub_C_ne_zero _  have h_roots_char : (Aᴴ * Aᴴᴴ).charpoly.roots =      Multiset.map (fun i => ((hM.eigenvalues i : ℂ)^2)) Finset.univ.val := by    rw [h_char, Polynomial.roots_prod _ _ h_ne_zero]    simp [-map_pow]  have h_roots_eig : (Aᴴ * Aᴴᴴ).charpoly.roots =      Multiset.map (Complex.ofReal ∘ hH.eigenvalues) Finset.univ.val :=    hH.roots_charpoly_eq_eigenvalues  have h_map_eq : Multiset.map Complex.ofReal (Multiset.map hH.eigenvalues Finset.univ.val) =      Multiset.map Complex.ofReal (Multiset.map (fun i => (hM.eigenvalues i)^2) Finset.univ.val) := by    rw [Multiset.map_map, Multiset.map_map]    rw [← h_roots_eig, h_roots_char]    congr 1    ext i    exact (map_pow Complex.ofRealHom _ 2).symm  have h_real_eq : Multiset.map hH.eigenvalues Finset.univ.val =      Multiset.map (fun i => (hM.eigenvalues i)^2) Finset.univ.val :=    Multiset.map_injective Complex.ofReal_injective h_map_eq  rw [Multiset.map_univ_eq_iff] at h_real_eq  obtain ⟨e, he⟩ := h_real_eq  have h_sum_sqrt : ∑ i : n, Real.sqrt (hH.eigenvalues i) = ∑ i : n, |hM.eigenvalues i| := by    have he_app (i : n) : hH.eigenvalues i = (hM.eigenvalues (e i))^2 := congr_fun he i    simp_rw [he_app, Real.sqrt_sq_eq_abs]    exact Equiv.sum_comp e (fun x => |hM.eigenvalues x|)  have h_def : matrix_nuclear_norm M = ∑ i : n, Real.sqrt (hH.eigenvalues i) := rfl  rw [h_def, h_sum_sqrt]  change (∑ i : n, |hM.eigenvalues₀ ((Fintype.equivOfCardEq (Fintype.card_fin _)).symm i)|) = _  exact Equiv.sum_comp (Fintype.equivOfCardEq (Fintype.card_fin _)).symm (fun j => |hM.eigenvalues₀ j|)
See it in the graphDiscuss this resultChallenge it