matrix_nuclear_norm_eigenvalue_inequality
Let $n$ be a finite type with decidable equality. Let $A$ and $B$ be real symmetric matrices indexed by $n \times n$, with eigenvalues $a_j$ and $b_j$ in nonincreasing order. Then the sum over $j \in \mathrm{Fin}(|n|)$ of $|a_j - b_j|$ is at most the nuclear norm of $A - B$.
Statement
theorem matrix_nuclear_norm_eigenvalue_inequality {n : Type*} [Fintype n] [DecidableEq n] (A B : Matrix n n ℝ) (hA : A.IsHermitian) (hB : B.IsHermitian) : ∑ j : Fin (Fintype.card n), |hA.eigenvalues₀ j - hB.eigenvalues₀ j| ≤ matrix_nuclear_norm (A - B)
- Formalizes
- arXiv:2610.10618 Lemma 2.2 -- The Hellinger Conjecture for Antipodal Boolean Functions
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- matrix_eigenvalues₀_le_of_sub_posSemidefIf $A$ and $C$ are real symmetric matrices such that $C - A$ is positive semidefinite, then each ordered eigenvalue of $A$ is at most the…
- matrix_nuclear_norm_of_isHermitianFor a real symmetric matrix $M$, its nuclear norm equals the sum of the absolute values of its eigenvalues.
Read back from the Lean
Let n be a finite type with decidable equality, and let A and B be n × n matrices over ℝ. Assuming that A is Hermitian (hA : A.IsHermitian) and B is Hermitian (hB : B.IsHermitian), the sum over all j : Fin (Fintype.card n) of the absolute differences between the corresponding eigenvalues |hA.eigenvalues₀ j - hB.eigenvalues₀ j| is less than or equal to matrix_nuclear_norm (A - B).
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 theorem bounds the sum of absolute differences between ordered eigenvalues of two real symmetric matrices $A$ and $B$ by the nuclear norm $\|A - B\|_*$. The proof uses the Jordan decomposition $A - B = P - N$ into positive semidefinite matrices $P, N \ge 0$ to construct an interpolating matrix $C = B + P = A + N$. By Weyl's monotonicity theorem, the eigenvalues of $C$ dominate those of both $A$ and $B$, which yields the pointwise bound $|a_j - b_j| \le (c_j - a_j) + (c_j - b_j)$. Summing over all eigenvalues turns the bound into traces, $( \operatorname{tr}(C) - \operatorname{tr}(A) ) + ( \operatorname{tr}(C) - \operatorname{tr}(B) ) = \operatorname{tr}(N) + \operatorname{tr}(P)$, which evaluates to the sum of the absolute eigenvalues of $A - B$, exactly the nuclear norm.
For any real number $x$, $\max(x, 0) - \max(-x, 0) = x$.
By trichotomy on the sign of $x$: if $x < 0$, then $\max(x, 0) = 0$ and $\max(-x, 0) = -x$, so $0 - (-x) = x$; if $x = 0$, both terms vanish; and if $x > 0$, $\max(x, 0) = x$ and $\max(-x, 0) = 0$, giving $x - 0 = x$.
uses
lt_trichotomy,max_eq_right,le_of_lt,max_eq_leftlemma matrix_nuclear_norm_eigenvalue_inequality_max_sub_max_neg (x : ℝ) : max x 0 - max (-x) 0 = x := by rcases lt_trichotomy x 0 with h | h | h · rw [max_eq_right (le_of_lt h), max_eq_left (by linarith : (0:ℝ) ≤ -x)]; ring · rw [h]; simp · rw [max_eq_left (le_of_lt h), max_eq_right (by linarith : -x ≤ 0)]; ring
For any real number $x$, $\max(x, 0) + \max(-x, 0) = |x|$.
Again by trichotomy on the sign of $x$: if $x < 0$, the sum is $0 + (-x) = -x = |x|$; if $x = 0$, both terms are 0; and if $x > 0$, the sum is $x + 0 = x = |x|$.
uses
lt_trichotomy,max_eq_right,le_of_lt,max_eq_left,abs_of_neg,abs_of_poslemma matrix_nuclear_norm_eigenvalue_inequality_max_add_max_neg (x : ℝ) : max x 0 + max (-x) 0 = |x| := by rcases lt_trichotomy x 0 with h | h | h · rw [max_eq_right (le_of_lt h), max_eq_left (by linarith : (0:ℝ) ≤ -x), abs_of_neg h]; ring · rw [h]; simp · rw [max_eq_left (le_of_lt h), max_eq_right (by linarith : -x ≤ 0), abs_of_pos h]; ring
Conjugating a diagonal matrix with non-negative entries $v_i \ge 0$ by any matrix $U$ yields a positive semidefinite matrix $U \operatorname{diag}(v) U^* \ge 0$.
Let $s_i = \sqrt{v_i}$, so $s_i^2 = v_i$, allowing $\operatorname{diag}(v)$ to factor as $\operatorname{diag}(s) \operatorname{diag}(s)$. Setting $M = \operatorname{diag}(s) U^*$, its adjoint is $M^* = U \operatorname{diag}(s)$ because real diagonal matrices are self-adjoint. Thus $U \operatorname{diag}(v) U^* = M^* M$, which is positive semidefinite.
uses
Matrix.star_eq_conjTranspose,Matrix.diagonal_conjTranspose,pow_two,Real.sq_sqrt,Matrix.diagonal_mul_diagonal,star_mul,Matrix.posSemidef_conjTranspose_mul_selflemma matrix_nuclear_norm_eigenvalue_inequality_psd {n : Type*} [Fintype n] [DecidableEq n] (U : Matrix n n ℝ) (v : n → ℝ) (hv : ∀ i, 0 ≤ v i) : (U * Matrix.diagonal v * star U).PosSemidef := by set s : n → ℝ := fun i => Real.sqrt (v i) with hs set M : Matrix n n ℝ := Matrix.diagonal s * star U with hM have hstarU : star (star U) = U := by simp have hstardiag : star (Matrix.diagonal s) = Matrix.diagonal s := by rw [Matrix.star_eq_conjTranspose, Matrix.diagonal_conjTranspose] simp have hss : (fun i => s i * s i) = v := by funext i simp only [hs] rw [← pow_two] exact Real.sq_sqrt (hv i) have hdiagsq : Matrix.diagonal v = Matrix.diagonal s * Matrix.diagonal s := by rw [← hss, Matrix.diagonal_mul_diagonal] have hPP : U * Matrix.diagonal v * star U = star M * M := by rw [hM, star_mul, hstarU, hstardiag, hdiagsq] noncomm_ring rw [hPP] exact Matrix.posSemidef_conjTranspose_mul_self M
If $U$ is unitary ($U^* U = 1$), the trace of $U \operatorname{diag}(v) U^*$ equals the sum of the entries $\sum_i v_i$.
By the cyclic property of the trace, $\operatorname{tr}(U \operatorname{diag}(v) U^*) = \operatorname{tr}(U^* U \operatorname{diag}(v)) = \operatorname{tr}(1 \cdot \operatorname{diag}(v)) = \operatorname{tr}(\operatorname{diag}(v)) = \sum_i v_i$.
uses
Matrix.trace_mul_cycle,one_mul,Matrix.trace_diagonallemma matrix_nuclear_norm_eigenvalue_inequality_trace {n : Type*} [Fintype n] [DecidableEq n] (U : Matrix n n ℝ) (v : n → ℝ) (hU : star U * U = 1) : (U * Matrix.diagonal v * star U).trace = ∑ i, v i := by rw [Matrix.trace_mul_cycle U (Matrix.diagonal v) (star U), hU, one_mul, Matrix.trace_diagonal]
For any function $f$ and Hermitian matrix $H$, the sum of $f$ over the unordered eigenvalues equals the sum of $f$ over the ordered eigenvalues.
The unordered eigenvalues are defined by precomposing the ordered eigenvalues with an equivalence between the indexing type $n$ and $\mathrm{Fin}(|n|)$. Reindexing the sum along this bijection preserves the total sum.
uses
Equiv.sum_comp,Fintype.equivOfCardEq,Fintype.card_finlemma matrix_nuclear_norm_eigenvalue_inequality_sum {n : Type*} [Fintype n] [DecidableEq n] (H : Matrix n n ℝ) (hH : H.IsHermitian) (f : ℝ → ℝ) : ∑ i : n, f (hH.eigenvalues i) = ∑ j : Fin (Fintype.card n), f (hH.eigenvalues₀ j) := by unfold Matrix.IsHermitian.eigenvalues exact Equiv.sum_comp (Fintype.equivOfCardEq (Fintype.card_fin _)).symm (fun j => f (hH.eigenvalues₀ j))
The trace of a real symmetric matrix $A$ equals the sum of its ordered eigenvalues.
The trace equals the sum of the unordered eigenvalues by the standard spectral identity. Reindexing this sum using the identity function $f = \mathrm{id}$ rewrites it as the sum of the ordered eigenvalues.
uses
Matrix.IsHermitian.trace_eq_sum_eigenvalues,matrix_nuclear_norm_eigenvalue_inequality_sumlemma matrix_nuclear_norm_eigenvalue_inequality_trace_eig {n : Type*} [Fintype n] [DecidableEq n] (A : Matrix n n ℝ) (hA : A.IsHermitian) : A.trace = ∑ j : Fin (Fintype.card n), hA.eigenvalues₀ j := by rw [Matrix.IsHermitian.trace_eq_sum_eigenvalues hA] exact matrix_nuclear_norm_eigenvalue_inequality_sum A hA id
Any Hermitian matrix $H$ decomposes as $H = U \operatorname{diag}(\max(\lambda, 0)) U^* - U \operatorname{diag}(\max(-\lambda, 0)) U^*$, where $U$ is its unitary eigenvector matrix and $\lambda$ are its eigenvalues.
By the spectral theorem, $H = U \operatorname{diag}(\lambda) U^*$. Since $\lambda_i = \max(\lambda_i, 0) - \max(-\lambda_i, 0)$, we can decompose $\operatorname{diag}(\lambda) = \operatorname{diag}(\max(\lambda, 0)) - \operatorname{diag}(\max(-\lambda, 0))$. Distributing the conjugation by $U$ across the difference yields the desired decomposition.
uses
Unitary.conjStarAlgAut_apply,Matrix.diagonal_sub,matrix_nuclear_norm_eigenvalue_inequality_max_sub_max_neglemma matrix_nuclear_norm_eigenvalue_inequality_decomp {n : Type*} [Fintype n] [DecidableEq n] (H : Matrix n n ℝ) (hH : H.IsHermitian) : H = (↑hH.eigenvectorUnitary : Matrix n n ℝ) * Matrix.diagonal (fun i => max (hH.eigenvalues i) 0) * star (↑hH.eigenvectorUnitary : Matrix n n ℝ) - (↑hH.eigenvectorUnitary : Matrix n n ℝ) * Matrix.diagonal (fun i => max (-(hH.eigenvalues i)) 0) * star (↑hH.eigenvectorUnitary : Matrix n n ℝ) := by have hspec := hH.spectral_theorem rw [Unitary.conjStarAlgAut_apply] at hspec conv_lhs => rw [hspec] have hdiag : Matrix.diagonal (fun i => max (hH.eigenvalues i) 0) - Matrix.diagonal (fun i => max (-(hH.eigenvalues i)) 0) = Matrix.diagonal (hH.eigenvalues) := by rw [Matrix.diagonal_sub] congr 1 funext i exact matrix_nuclear_norm_eigenvalue_inequality_max_sub_max_neg (hH.eigenvalues i) have hd : RCLike.ofReal ∘ hH.eigenvalues = hH.eigenvalues := by funext i; simp rw [hd, ← hdiag] noncomm_ring
The symmetric difference $A - B$ decomposes into positive and negative parts $A - B = P - N$, where $P, N \ge 0$ are positive semidefinite and $U$ is unitary.
Let $H = A - B$, which is Hermitian. Using the unitary matrix $U$ of eigenvectors of $H$ and the non-negative vectors $d^+_i = \max(\lambda_i, 0)$ and $d^-_i = \max(-\lambda_i, 0)$, define $P = U \operatorname{diag}(d^+) U^*$ and $N = U \operatorname{diag}(d^-) U^*$. Both $P$ and $N$ are positive semidefinite by conjugation of non-negative diagonal matrices, $U^* U = 1$, and $A - B = P - N$ by the decomposition lemma.
uses
matrix_nuclear_norm_eigenvalue_inequality_psd,le_max_right,Unitary.coe_star_mul_self,matrix_nuclear_norm_eigenvalue_inequality_decomptheorem matrix_nuclear_norm_eigenvalue_inequality {n : Type*} [Fintype n] [DecidableEq n] (A B : Matrix n n ℝ) (hA : A.IsHermitian) (hB : B.IsHermitian) : ∑ j : Fin (Fintype.card n), |hA.eigenvalues₀ j - hB.eigenvalues₀ j| ≤ matrix_nuclear_norm (A - B) := by classical set hH : (A - B).IsHermitian := hA.sub hB with hhH set U : Matrix n n ℝ := ↑hH.eigenvectorUnitary with hU set dp : n → ℝ := fun i => max (hH.eigenvalues i) 0 with hdp set dn : n → ℝ := fun i => max (-(hH.eigenvalues i)) 0 with hdn set P : Matrix n n ℝ := U * Matrix.diagonal dp * star U with hPdef set N : Matrix n n ℝ := U * Matrix.diagonal dn * star U with hNdef have hP : P.PosSemidef := matrix_nuclear_norm_eigenvalue_inequality_psd U dp (fun i => le_max_right _ _) have hN : N.PosSemidef := matrix_nuclear_norm_eigenvalue_inequality_psd U dn (fun i => le_max_right _ _) have hUun : star U * U = 1 := Unitary.coe_star_mul_self hH.eigenvectorUnitary have hdecomp : A - B = P - N := matrix_nuclear_norm_eigenvalue_inequality_decomp (A - B) hH
The matrix $C = B + P$ is Hermitian and satisfies $C - A = N \ge 0$ and $C - B = P \ge 0$.
Defining $C = B + P$, it is Hermitian as the sum of Hermitian matrices. Directly, $C - B = P \ge 0$. Substituting $A - B = P - N$ gives $C - A = (B + P) - A = P - (A - B) = N \ge 0$. Hence both $C - A$ and $C - B$ are positive semidefinite.
set C : Matrix n n ℝ := B + P with hCdef have hC : C.IsHermitian := hB.add hP.isHermitian have hCAeq : C - A = N := by have h' : N = P - (A - B) := by rw [hdecomp]; abel rw [hCdef, h']; abel have hCBeq : C - B = P := by rw [hCdef]; abel have hCA : (C - A).PosSemidef := hCAeq ▸ hN have hCB : (C - B).PosSemidef := hCBeq ▸ hP
For every index $j$, $|a_j - b_j| \le (c_j - a_j) + (c_j - b_j)$, and this inequality sums across all $j$.
Since $C - A \ge 0$ and $C - B \ge 0$, Weyl's monotonicity theorem (`matrix_eigenvalues₀_le_of_sub_posSemidef`) implies $a_j \le c_j$ and $b_j \le c_j$ for every ordered eigenvalue index $j$. Linear arithmetic with these inequalities yields $|a_j - b_j| \le (c_j - a_j) + (c_j - b_j)$. Summing these pointwise inequalities over all $j \in \mathrm{Fin}(|n|)$ bounds the total sum of eigenvalue differences.
uses
matrix_eigenvalues₀_le_of_sub_posSemidef,abs_le,Finset.sum_le_sumhave hle : ∀ j, |hA.eigenvalues₀ j - hB.eigenvalues₀ j| ≤ (hC.eigenvalues₀ j - hA.eigenvalues₀ j) + (hC.eigenvalues₀ j - hB.eigenvalues₀ j) := by intro j have h1 := matrix_eigenvalues₀_le_of_sub_posSemidef A C hA hC hCA j have h2 := matrix_eigenvalues₀_le_of_sub_posSemidef B C hB hC hCB j rw [abs_le] constructor <;> linarith have hbound := Finset.sum_le_sum (s := Finset.univ) (fun j (_ : j ∈ (Finset.univ : Finset (Fin (Fintype.card n)))) => hle j)
The sum $\sum_j ((c_j - a_j) + (c_j - b_j))$ equals $\operatorname{tr}(P) + \operatorname{tr}(N)$.
Distributing the sum and replacing each sum of ordered eigenvalues with the corresponding matrix trace expresses the bound as $(\operatorname{tr}(C) - \operatorname{tr}(A)) + (\operatorname{tr}(C) - \operatorname{tr}(B))$. By linearity of trace, $\operatorname{tr}(C) - \operatorname{tr}(B) = \operatorname{tr}(C - B) = \operatorname{tr}(P)$ and $\operatorname{tr}(C) - \operatorname{tr}(A) = \operatorname{tr}(C - A) = \operatorname{tr}(N)$, so the sum evaluates to $\operatorname{tr}(P) + \operatorname{tr}(N)$.
uses
matrix_nuclear_norm_eigenvalue_inequality_trace_eig,Finset.sum_add_distrib,Finset.sum_sub_distrib,Matrix.trace_add,Matrix.trace_subhave htrC : ∑ j : Fin (Fintype.card n), hC.eigenvalues₀ j = C.trace := (matrix_nuclear_norm_eigenvalue_inequality_trace_eig C hC).symm have htrA : ∑ j : Fin (Fintype.card n), hA.eigenvalues₀ j = A.trace := (matrix_nuclear_norm_eigenvalue_inequality_trace_eig A hA).symm have htrB : ∑ j : Fin (Fintype.card n), hB.eigenvalues₀ j = B.trace := (matrix_nuclear_norm_eigenvalue_inequality_trace_eig B hB).symm have hsum : ∑ j : Fin (Fintype.card n), ((hC.eigenvalues₀ j - hA.eigenvalues₀ j) + (hC.eigenvalues₀ j - hB.eigenvalues₀ j)) = P.trace + N.trace := by rw [Finset.sum_add_distrib, Finset.sum_sub_distrib, Finset.sum_sub_distrib, htrC, htrA, htrB] have h1 : C.trace - B.trace = P.trace := by rw [hCdef, Matrix.trace_add]; ring have h2 : C.trace - A.trace = N.trace := by rw [← Matrix.trace_sub, hCAeq] rw [h1, h2]; ring
The trace sum $\operatorname{tr}(P) + \operatorname{tr}(N)$ equals the nuclear norm $\|A - B\|_*$, establishing $\sum_j |a_j - b_j| \le \|A - B\|_*$.
Using the cyclic trace identity for $P$ and $N$, $\operatorname{tr}(P) + \operatorname{tr}(N) = \sum_i (d^+_i + d^-_i) = \sum_i |\lambda_i(A - B)|$. Reindexing this sum over the ordered eigenvalues gives $\sum_j |\lambda_{0, j}(A - B)|$, which equals the nuclear norm $\|A - B\|_*$ for a Hermitian matrix. Combining this equality with the upper bound from the previous steps completes the proof.
uses
matrix_nuclear_norm_eigenvalue_inequality_trace,Finset.sum_add_distrib,matrix_nuclear_norm_eigenvalue_inequality_max_add_max_neg,matrix_nuclear_norm_eigenvalue_inequality_sum,matrix_nuclear_norm_of_isHermitianhave htrP : P.trace = ∑ i : n, dp i := matrix_nuclear_norm_eigenvalue_inequality_trace U dp hUun have htrN : N.trace = ∑ i : n, dn i := matrix_nuclear_norm_eigenvalue_inequality_trace U dn hUun have htot : P.trace + N.trace = matrix_nuclear_norm (A - B) := by rw [htrP, htrN, ← Finset.sum_add_distrib] have hpt : (∑ i : n, (dp i + dn i)) = ∑ i : n, |hH.eigenvalues i| := by congr 1 funext i exact matrix_nuclear_norm_eigenvalue_inequality_max_add_max_neg (hH.eigenvalues i) rw [hpt, matrix_nuclear_norm_eigenvalue_inequality_sum (A - B) hH (fun x => |x|)] exact (matrix_nuclear_norm_of_isHermitian (A - B) hH).symm linarith
lt_trichotomy- Every real number satisfies exactly one of $x < 0$, $x = 0$, or $0 < x$.
max_eq_right- If $a \le b$, then $\max(a, b) = b$.
le_of_lt- If $a < b$, then $a \le b$.
max_eq_left- If $b \le a$, then $\max(a, b) = a$.
abs_of_neg- If $a < 0$, then $|a| = -a$.
abs_of_pos- If $0 < a$, then $|a| = a$.
Matrix.star_eq_conjTranspose- For any matrix $M$, $\operatorname{star}(M)$ is its conjugate transpose $M^*$.
Matrix.diagonal_conjTranspose- The conjugate transpose of a diagonal matrix is the diagonal matrix of the conjugate entries.
pow_two- In any monoid, $a^2 = a \cdot a$.
Real.sq_sqrt- For $x \ge 0$, $(\sqrt{x})^2 = x$.
Matrix.diagonal_mul_diagonal- The product of two diagonal matrices is the diagonal matrix of their componentwise products.
star_mul- The adjoint of a product is the reversed product of the adjoints: $(r s)^* = s^* r^*$.
Matrix.posSemidef_conjTranspose_mul_self- For any matrix $A$, $A^* A$ is positive semidefinite.
Matrix.trace_mul_cycle- The trace of a product of matrices is invariant under cyclic permutation: $\operatorname{tr}(A B C) = \operatorname{tr}(C A B)$.
one_mul- Multiplying on the left by the identity matrix gives the original matrix: $1 \cdot a = a$.
Matrix.trace_diagonal- The trace of a diagonal matrix is the sum of its diagonal entries.
Equiv.sum_comp- Summing a function over a finite type is invariant under precomposition with an equivalence.
Fintype.equivOfCardEq- Any two finite types of equal cardinality are in bijection.
Fintype.card_fin- The cardinality of $\mathrm{Fin}(n)$ is $n$.
Matrix.IsHermitian.trace_eq_sum_eigenvalues- The trace of a Hermitian matrix equals the sum of its eigenvalues.
matrix_nuclear_norm_eigenvalue_inequality_sum- For any Hermitian matrix and function $f$, the sum of $f$ applied to its unordered eigenvalues equals the sum over its ordered eigenvalues.
Unitary.conjStarAlgAut_apply- Unitary conjugation of a matrix $x$ by a unitary element $u$ is $u x u^*$.
Matrix.diagonal_sub- The difference of two diagonal matrices is the diagonal matrix of their componentwise differences.
matrix_nuclear_norm_eigenvalue_inequality_max_sub_max_neg- For any real number $x$, $\max(x, 0) - \max(-x, 0) = x$.
matrix_nuclear_norm_eigenvalue_inequality_psd- Conjugating a diagonal matrix with non-negative entries by any matrix yields a positive semidefinite matrix.
le_max_right- For any elements $a$ and $b$ in a linear order, $b \le \max(a, b)$.
Unitary.coe_star_mul_self- For any unitary matrix $U$, $U^* U = 1$.
matrix_nuclear_norm_eigenvalue_inequality_decomp- Every Hermitian matrix decomposes as the difference of its positive and negative eigenvalue parts $U \operatorname{diag}(\max(\lambda, 0)) U^* - U \operatorname{diag}(\max(-\lambda, 0)) U^*$.
matrix_eigenvalues₀_le_of_sub_posSemidef- If $C - A$ is positive semidefinite for Hermitian matrices $A$ and $C$, then each ordered eigenvalue of $A$ is bounded above by the corresponding ordered eigenvalue of $C$.
abs_le- $|a| \le b$ if and only if $-b \le a$ and $a \le b$.
Finset.sum_le_sum- If $f(i) \le g(i)$ for all indices $i$ in a finite set, then $\sum_i f(i) \le \sum_i g(i)$.
matrix_nuclear_norm_eigenvalue_inequality_trace_eig- The trace of a real symmetric matrix equals the sum of its ordered eigenvalues.
Finset.sum_add_distrib- The sum of a sum of functions over a finite set equals the sum of the individual sums.
Finset.sum_sub_distrib- The sum of a difference of functions over a finite set equals the difference of the individual sums.
Matrix.trace_add- The trace of the sum of two matrices is the sum of their traces.
Matrix.trace_sub- The trace of the difference of two matrices is the difference of their traces.
matrix_nuclear_norm_eigenvalue_inequality_trace- For a unitary matrix $U$, the trace of $U \operatorname{diag}(v) U^*$ equals $\sum_i v_i$.
matrix_nuclear_norm_eigenvalue_inequality_max_add_max_neg- For any real number $x$, $\max(x, 0) + \max(-x, 0) = |x|$.
matrix_nuclear_norm_of_isHermitian- The nuclear norm of a Hermitian matrix equals the sum of the absolute values of its ordered eigenvalues.
- The proof distinguishes between arbitrary indexing of eigenvalues (`eigenvalues`, indexed by $n$) and sorted indexing (`eigenvalues₀`, indexed by `Fin (Fintype.card n)` in nonincreasing order). Several helper lemmas bridge sums across these two indexings using the cardinality equivalence between $n$ and `Fin |n|`.
- The pointwise bound $|a_j - b_j| \le (c_j - a_j) + (c_j - b_j)$ follows from $a_j \le c_j$ and $b_j \le c_j$, which Lean closes via the linear arithmetic tactic `linarith`.
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.
lemma matrix_nuclear_norm_eigenvalue_inequality_max_sub_max_neg (x : ℝ) : max x 0 - max (-x) 0 = x := by rcases lt_trichotomy x 0 with h | h | h · rw [max_eq_right (le_of_lt h), max_eq_left (by linarith : (0:ℝ) ≤ -x)]; ring · rw [h]; simp · rw [max_eq_left (le_of_lt h), max_eq_right (by linarith : -x ≤ 0)]; ringlemma matrix_nuclear_norm_eigenvalue_inequality_max_add_max_neg (x : ℝ) : max x 0 + max (-x) 0 = |x| := by rcases lt_trichotomy x 0 with h | h | h · rw [max_eq_right (le_of_lt h), max_eq_left (by linarith : (0:ℝ) ≤ -x), abs_of_neg h]; ring · rw [h]; simp · rw [max_eq_left (le_of_lt h), max_eq_right (by linarith : -x ≤ 0), abs_of_pos h]; ringlemma matrix_nuclear_norm_eigenvalue_inequality_psd {n : Type*} [Fintype n] [DecidableEq n] (U : Matrix n n ℝ) (v : n → ℝ) (hv : ∀ i, 0 ≤ v i) : (U * Matrix.diagonal v * star U).PosSemidef := by set s : n → ℝ := fun i => Real.sqrt (v i) with hs set M : Matrix n n ℝ := Matrix.diagonal s * star U with hM have hstarU : star (star U) = U := by simp have hstardiag : star (Matrix.diagonal s) = Matrix.diagonal s := by rw [Matrix.star_eq_conjTranspose, Matrix.diagonal_conjTranspose] simp have hss : (fun i => s i * s i) = v := by funext i simp only [hs] rw [← pow_two] exact Real.sq_sqrt (hv i) have hdiagsq : Matrix.diagonal v = Matrix.diagonal s * Matrix.diagonal s := by rw [← hss, Matrix.diagonal_mul_diagonal] have hPP : U * Matrix.diagonal v * star U = star M * M := by rw [hM, star_mul, hstarU, hstardiag, hdiagsq] noncomm_ring rw [hPP] exact Matrix.posSemidef_conjTranspose_mul_self Mlemma matrix_nuclear_norm_eigenvalue_inequality_trace {n : Type*} [Fintype n] [DecidableEq n] (U : Matrix n n ℝ) (v : n → ℝ) (hU : star U * U = 1) : (U * Matrix.diagonal v * star U).trace = ∑ i, v i := by rw [Matrix.trace_mul_cycle U (Matrix.diagonal v) (star U), hU, one_mul, Matrix.trace_diagonal]lemma matrix_nuclear_norm_eigenvalue_inequality_sum {n : Type*} [Fintype n] [DecidableEq n] (H : Matrix n n ℝ) (hH : H.IsHermitian) (f : ℝ → ℝ) : ∑ i : n, f (hH.eigenvalues i) = ∑ j : Fin (Fintype.card n), f (hH.eigenvalues₀ j) := by unfold Matrix.IsHermitian.eigenvalues exact Equiv.sum_comp (Fintype.equivOfCardEq (Fintype.card_fin _)).symm (fun j => f (hH.eigenvalues₀ j))lemma matrix_nuclear_norm_eigenvalue_inequality_trace_eig {n : Type*} [Fintype n] [DecidableEq n] (A : Matrix n n ℝ) (hA : A.IsHermitian) : A.trace = ∑ j : Fin (Fintype.card n), hA.eigenvalues₀ j := by rw [Matrix.IsHermitian.trace_eq_sum_eigenvalues hA] exact matrix_nuclear_norm_eigenvalue_inequality_sum A hA idlemma matrix_nuclear_norm_eigenvalue_inequality_decomp {n : Type*} [Fintype n] [DecidableEq n] (H : Matrix n n ℝ) (hH : H.IsHermitian) : H = (↑hH.eigenvectorUnitary : Matrix n n ℝ) * Matrix.diagonal (fun i => max (hH.eigenvalues i) 0) * star (↑hH.eigenvectorUnitary : Matrix n n ℝ) - (↑hH.eigenvectorUnitary : Matrix n n ℝ) * Matrix.diagonal (fun i => max (-(hH.eigenvalues i)) 0) * star (↑hH.eigenvectorUnitary : Matrix n n ℝ) := by have hspec := hH.spectral_theorem rw [Unitary.conjStarAlgAut_apply] at hspec conv_lhs => rw [hspec] have hdiag : Matrix.diagonal (fun i => max (hH.eigenvalues i) 0) - Matrix.diagonal (fun i => max (-(hH.eigenvalues i)) 0) = Matrix.diagonal (hH.eigenvalues) := by rw [Matrix.diagonal_sub] congr 1 funext i exact matrix_nuclear_norm_eigenvalue_inequality_max_sub_max_neg (hH.eigenvalues i) have hd : RCLike.ofReal ∘ hH.eigenvalues = hH.eigenvalues := by funext i; simp rw [hd, ← hdiag] noncomm_ring/-- Nuclear-norm eigenvalue inequality: for real symmetric matrices with ordered eigenvalues, the sum of absolute differences between paired eigenvalues is bounded by the nuclear norm of their difference. -/theorem matrix_nuclear_norm_eigenvalue_inequality {n : Type*} [Fintype n] [DecidableEq n] (A B : Matrix n n ℝ) (hA : A.IsHermitian) (hB : B.IsHermitian) : ∑ j : Fin (Fintype.card n), |hA.eigenvalues₀ j - hB.eigenvalues₀ j| ≤ matrix_nuclear_norm (A - B) := by classical set hH : (A - B).IsHermitian := hA.sub hB with hhH set U : Matrix n n ℝ := ↑hH.eigenvectorUnitary with hU set dp : n → ℝ := fun i => max (hH.eigenvalues i) 0 with hdp set dn : n → ℝ := fun i => max (-(hH.eigenvalues i)) 0 with hdn set P : Matrix n n ℝ := U * Matrix.diagonal dp * star U with hPdef set N : Matrix n n ℝ := U * Matrix.diagonal dn * star U with hNdef have hP : P.PosSemidef := matrix_nuclear_norm_eigenvalue_inequality_psd U dp (fun i => le_max_right _ _) have hN : N.PosSemidef := matrix_nuclear_norm_eigenvalue_inequality_psd U dn (fun i => le_max_right _ _) have hUun : star U * U = 1 := Unitary.coe_star_mul_self hH.eigenvectorUnitary have hdecomp : A - B = P - N := matrix_nuclear_norm_eigenvalue_inequality_decomp (A - B) hH set C : Matrix n n ℝ := B + P with hCdef have hC : C.IsHermitian := hB.add hP.isHermitian have hCAeq : C - A = N := by have h' : N = P - (A - B) := by rw [hdecomp]; abel rw [hCdef, h']; abel have hCBeq : C - B = P := by rw [hCdef]; abel have hCA : (C - A).PosSemidef := hCAeq ▸ hN have hCB : (C - B).PosSemidef := hCBeq ▸ hP have hle : ∀ j, |hA.eigenvalues₀ j - hB.eigenvalues₀ j| ≤ (hC.eigenvalues₀ j - hA.eigenvalues₀ j) + (hC.eigenvalues₀ j - hB.eigenvalues₀ j) := by intro j have h1 := matrix_eigenvalues₀_le_of_sub_posSemidef A C hA hC hCA j have h2 := matrix_eigenvalues₀_le_of_sub_posSemidef B C hB hC hCB j rw [abs_le] constructor <;> linarith have hbound := Finset.sum_le_sum (s := Finset.univ) (fun j (_ : j ∈ (Finset.univ : Finset (Fin (Fintype.card n)))) => hle j) have htrC : ∑ j : Fin (Fintype.card n), hC.eigenvalues₀ j = C.trace := (matrix_nuclear_norm_eigenvalue_inequality_trace_eig C hC).symm have htrA : ∑ j : Fin (Fintype.card n), hA.eigenvalues₀ j = A.trace := (matrix_nuclear_norm_eigenvalue_inequality_trace_eig A hA).symm have htrB : ∑ j : Fin (Fintype.card n), hB.eigenvalues₀ j = B.trace := (matrix_nuclear_norm_eigenvalue_inequality_trace_eig B hB).symm have hsum : ∑ j : Fin (Fintype.card n), ((hC.eigenvalues₀ j - hA.eigenvalues₀ j) + (hC.eigenvalues₀ j - hB.eigenvalues₀ j)) = P.trace + N.trace := by rw [Finset.sum_add_distrib, Finset.sum_sub_distrib, Finset.sum_sub_distrib, htrC, htrA, htrB] have h1 : C.trace - B.trace = P.trace := by rw [hCdef, Matrix.trace_add]; ring have h2 : C.trace - A.trace = N.trace := by rw [← Matrix.trace_sub, hCAeq] rw [h1, h2]; ring have htrP : P.trace = ∑ i : n, dp i := matrix_nuclear_norm_eigenvalue_inequality_trace U dp hUun have htrN : N.trace = ∑ i : n, dn i := matrix_nuclear_norm_eigenvalue_inequality_trace U dn hUun have htot : P.trace + N.trace = matrix_nuclear_norm (A - B) := by rw [htrP, htrN, ← Finset.sum_add_distrib] have hpt : (∑ i : n, (dp i + dn i)) = ∑ i : n, |hH.eigenvalues i| := by congr 1 funext i exact matrix_nuclear_norm_eigenvalue_inequality_max_add_max_neg (hH.eigenvalues i) rw [hpt, matrix_nuclear_norm_eigenvalue_inequality_sum (A - B) hH (fun x => |x|)] exact (matrix_nuclear_norm_of_isHermitian (A - B) hH).symm linarith