AFTD Auto-Formalizing Theoretical Domains

matrix_nuclear_norm_eigenvalue_inequality

theoremverifiedformalization

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

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.

  1. 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$.

    lines 1–6

    uses lt_trichotomy, max_eq_right, le_of_lt, max_eq_left

    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)]; ring
  2. 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|$.

    lines 8–13

    uses lt_trichotomy, max_eq_right, le_of_lt, max_eq_left, abs_of_neg, abs_of_pos

    lemma 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
  3. 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.

    lines 15–35

    uses Matrix.star_eq_conjTranspose, Matrix.diagonal_conjTranspose, pow_two, Real.sq_sqrt, Matrix.diagonal_mul_diagonal, star_mul, Matrix.posSemidef_conjTranspose_mul_self

    lemma 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
  4. 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$.

    lines 37–40

    uses Matrix.trace_mul_cycle, one_mul, Matrix.trace_diagonal

    lemma 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]
  5. 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.

    lines 42–47

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

    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))
  6. 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.

    lines 49–53

    uses Matrix.IsHermitian.trace_eq_sum_eigenvalues, matrix_nuclear_norm_eigenvalue_inequality_sum

    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 id
  7. 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.

    lines 55–76

    uses Unitary.conjStarAlgAut_apply, Matrix.diagonal_sub, matrix_nuclear_norm_eigenvalue_inequality_max_sub_max_neg

    lemma 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
  8. 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.

    lines 79–92

    uses matrix_nuclear_norm_eigenvalue_inequality_psd, le_max_right, Unitary.coe_star_mul_self, matrix_nuclear_norm_eigenvalue_inequality_decomp

    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
  9. 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.

    lines 93–100

      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
  10. 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.

    lines 101–109

    uses matrix_eigenvalues₀_le_of_sub_posSemidef, abs_le, Finset.sum_le_sum

      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)
  11. 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)$.

    lines 110–124

    uses matrix_nuclear_norm_eigenvalue_inequality_trace_eig, Finset.sum_add_distrib, Finset.sum_sub_distrib, Matrix.trace_add, Matrix.trace_sub

      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
  12. 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.

    lines 125–135

    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_isHermitian

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it