matrix_nuclear_norm_of_isHermitian
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
- matrix_nuclear_norm_eigenvalue_inequalityLet $n$ be a finite type with decidable equality. Let $A$ and $B$ be real symmetric matrices indexed by $n \times n$, with eigenvalues…
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|.
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.
uses
map_mul,diagonal_mul_diagonal,pow_twohave 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]
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.
uses
conjStarAlgAut_apply,charpoly_mul_comm,mul_assoc,charpoly_diagonalrw [h_sq] rw [conjStarAlgAut_apply, charpoly_mul_comm, ← mul_assoc] simp [charpoly_diagonal]
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.
uses
isHermitian_mul_conjTranspose_self,congr_fun,conjTranspose_applylet 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]
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.
uses
conjTranspose_conjTranspose,mul_applyhave hH_mat : Aᴴ * Aᴴᴴ = (M * M).map Complex.ofRealHom := by rw [conjTranspose_conjTranspose, hA] ext i j simp [A, mul_apply]
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.
uses
charpoly_map,matrix_nuclear_norm_of_isHermitian_charpoly_sq,Polynomial.map_prodhave 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]
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.
uses
Finset.prod_ne_zero_iff,X_sub_C_ne_zero,Polynomial.roots_prodhave 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]
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.
uses
Multiset.map_map,map_pow,Multiset.map_injective,Complex.ofReal_injectivehave 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
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|.
uses
Multiset.map_univ_eq_iff,congr_fun,Real.sqrt_sq_eq_abs,Equiv.sum_comprw [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|)
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.
uses
Equiv.sum_comp,Fintype.equivOfCardEq,Fintype.card_finhave 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
- The definition `matrix_nuclear_norm` is phrased via the singular values of the complex embedding of $M$, while `eigenvalues₀` indexes eigenvalues using `Fin (Fintype.card n)` rather than the arbitrary finite index type $n$; the proof bridges both representations using explicit reindexing along type equivalences.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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|)