AFTD Auto-Formalizing Theoretical Domains

p_star_transpose_handicap_invariance

theoremverifiedformalization

For every natural number n and every real n-by-n matrix M indexed by Fin n in the class P*, its transpose M.transpose belongs to the class P*, and their handicap numbers coincide: handicap_number n M.transpose = handicap_number n M.

Statement

theorem p_star_transpose_handicap_invariance (n : ℕ) (M : Matrix (Fin n) (Fin n) ℝ) (hM : is_p_star n M) :
    is_p_star n M.transpose ∧ handicap_number n M.transpose = handicap_number n M
Formalizes
arXiv:2611.07815 Theorem 2.6
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • is_p_starA real n-by-n matrix M indexed by Fin n belongs to the class P* if there exists a real number κ ≥ 0 such that is_p_star_kappa n M κ holds.
  • handicap_numberThe handicap number of a matrix M is the infimum of all κ ≥ 0 such that M belongs to P*(κ).
  • is_p_star_kappaA square real matrix M belongs to the class P*(κ) for a parameter κ ≥ 0 if for all x, the sum (1 + 4κ) ∑_{i: x_i (Mx)_i > 0} x_i (Mx)_i +…

Read back from the Lean

For any natural number $n$ and any $n \times n$ real matrix $M$, if $M$ is a $P_*$-matrix (that is, there exists $\kappa \ge 0$ such that $M$ is a $P_*(\kappa)$-matrix), then the transpose $M^T$ is also a $P_*$-matrix, and the handicap number of $M^T$ equals the handicap number of $M$.

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 is proved by showing that the class P*(κ) is invariant under transposition for every κ ≥ 0, which guarantees that M and its transpose share the same set of admissible handicap parameters and therefore the same handicap number. First, the condition M ∈ P*(κ) is rewritten as the nonnegativity of an unweighted sum ∑ (x_i (M x)_i + α |x_i (M x)_i|) with parameter α = 2κ / (1 + 2κ) ∈ [0, 1). Via the arithmetic mean–geometric mean inequality, this is shown to be equivalent to the nonnegativity of a family of diagonally weighted quadratic forms W_e(M, x) for all positive weight vectors e. An exact norm identity identifies 2α W_e(M, D⁻¹ u) with ‖B u‖² - (1 - α²)‖u‖² for the scaled matrix B = 1 + α D⁻¹ M D⁻¹; since the lower bound ‖B u‖² ≥ (1 - α²)‖u‖² transfers to Bᵀ by Cauchy–Schwarz, the weighted forms for Mᵀ are also nonnegative. Finally, choosing the weights e_i as an optimal function of x and a small parameter t > 0 recovers the unweighted condition for Mᵀ in the limit, establishing Mᵀ ∈ P*(κ).

  1. If a square matrix B satisfies c ‖u‖² ≤ ‖B u‖² for all u with c > 0, then the linear map u ↦ B u is injective and surjective.

    Given B a = B b, applying the hypothesis to u = a - b gives c ‖a - b‖² ≤ ‖B(a - b)‖² = 0. Since c > 0 and ‖a - b‖² ≥ 0, we must have ‖a - b‖² = 0, which implies a - b = 0 and hence a = b, establishing injectivity. In finite dimensions, an injective linear endomorphism is automatically surjective.

    lines 6–16

    uses Matrix.mulVec_sub, Finset.sum_nonneg, mul_self_nonneg, dotProduct_self_eq_zero

      have hinj : Function.Injective (Matrix.mulVec B) := by
        intro a b hab
        have h0 := h (a - b)
        rw [Matrix.mulVec_sub, hab, sub_self, dotProduct_zero] at h0
        have h1 : 0 ≤ dotProduct (a - b) (a - b) := by
          unfold dotProduct; exact Finset.sum_nonneg (fun i _ => mul_self_nonneg _)
        have h2 : dotProduct (a - b) (a - b) = 0 := by nlinarith
        rw [dotProduct_self_eq_zero] at h2
        exact sub_eq_zero.mp h2
      have hsurj : Function.Surjective (Matrix.mulVec B) :=
        Matrix.mulVec_surjective_iff_isUnit.mpr (Matrix.mulVec_injective_iff_isUnit.mp hinj)
  2. The lower bound passes to the transpose: c ‖v‖² ≤ ‖Bᵀ v‖² for all v.

    For any v, surjectivity provides u such that v = B u. Setting w = Bᵀ (B u) = Bᵀ v, the dual pairing gives w ⬝ u = (B u) ⬝ (B u) = ‖v‖². By the Cauchy–Schwarz inequality, ‖v‖⁴ = (w ⬝ u)² ≤ ‖w‖² ‖u‖² = ‖Bᵀ v‖² ‖u‖². Using c ‖u‖² ≤ ‖B u‖² = ‖v‖², if ‖v‖² > 0 we can divide by ‖u‖² to conclude c ‖v‖² ≤ ‖Bᵀ v‖², while the case ‖v‖² = 0 is immediate.

    lines 17–39

    uses Matrix.mulVec_transpose, Matrix.dotProduct_mulVec, Finset.sum_mul_sq_le_sq_mul_sq

      intro v
      obtain ⟨u, rfl⟩ := hsurj v
      set w := Matrix.mulVec B.transpose (Matrix.mulVec B u) with hw
      have hdual : dotProduct w u = dotProduct (Matrix.mulVec B u) (Matrix.mulVec B u) := by
        rw [hw, Matrix.mulVec_transpose, ← Matrix.dotProduct_mulVec]
      have hcs : (dotProduct w u) ^ 2 ≤ dotProduct w w * dotProduct u u := by
        have := Finset.sum_mul_sq_le_sq_mul_sq Finset.univ w u
        simpa [dotProduct, sq] using this
      set a := dotProduct (Matrix.mulVec B u) (Matrix.mulVec B u)
      set b := dotProduct w w
      set s := dotProduct u u
      have ha : 0 ≤ a := by
        simp only [a, dotProduct]; exact Finset.sum_nonneg (fun i _ => mul_self_nonneg _)
      have hb : 0 ≤ b := by
        simp only [b, dotProduct]; exact Finset.sum_nonneg (fun i _ => mul_self_nonneg _)
      have hs : 0 ≤ s := by
        simp only [s, dotProduct]; exact Finset.sum_nonneg (fun i _ => mul_self_nonneg _)
      have hcsa : c * s ≤ a := h u
      rw [hdual] at hcs
      rcases ha.lt_or_eq with ha' | ha'
      · have : c * a * a ≤ b * a := by nlinarith
        nlinarith
      · rw [← ha']; simpa using hb
  3. The diagonally scaled matrix B = 1 + α D⁻¹ M D⁻¹ acts on vectors coordinate-wise by (B u)_i = u_i + α e_i⁻¹ (M (D⁻¹ u))_i, and its transpose is Bᵀ = 1 + α D⁻¹ Mᵀ D⁻¹.

    Multiplying by the diagonal matrix D⁻¹ scales the j-th coordinate by e_j⁻¹, so distributing B u = u + α D⁻¹ M (D⁻¹ u) yields the coordinate formula. Transposition distributes over addition, scalar multiplication, and products; since diagonal matrices are symmetric, (D⁻¹ M D⁻¹)ᵀ = D⁻¹ Mᵀ D⁻¹.

    lines 46–53

    uses Matrix.mulVec_diagonal, Matrix.add_mulVec, Matrix.smul_mulVec, Matrix.transpose_add, Matrix.transpose_smul, Matrix.transpose_mul, Matrix.mul_assoc

      have hd : ∀ v : Fin n → ℝ, (Matrix.diagonal fun j => (e j)⁻¹).mulVec v = fun j => (e j)⁻¹ * v j := by
        intro v; funext j; simp [Matrix.mulVec_diagonal]
      simp [Matrix.add_mulVec, Matrix.smul_mulVec, ← Matrix.mulVec_mulVec, hd]
    
    theorem pstar_tr_B_transpose {n : ℕ} (M : Matrix (Fin n) (Fin n) ℝ) (e : Fin n → ℝ) (α : ℝ) :
        (1 + α • (Matrix.diagonal (fun j => (e j)⁻¹) * M * Matrix.diagonal (fun j => (e j)⁻¹))).transpose
          = 1 + α • (Matrix.diagonal (fun j => (e j)⁻¹) * M.transpose * Matrix.diagonal (fun j => (e j)⁻¹)) := by
      simp [Matrix.transpose_add, Matrix.transpose_smul, Matrix.transpose_mul, Matrix.mul_assoc]
  4. Setting x = D⁻¹ u, the quadratic form of B satisfies the identity ‖B u‖² - (1 - α²)‖u‖² = 2α ∑_i (x_i (M x)_i + (α / 2) (e_i² x_i² + (M x)_i² / e_i²)).

    Expanding each coordinate (B u)_i² = (u_i + α e_i⁻¹ (M x)_i)² and subtracting (1 - α²) u_i² leaves 2α u_i e_i⁻¹ (M x)_i + α² (u_i² + e_i⁻² (M x)_i²). Substituting u_i = e_i x_i and factoring out 2α matches the summand on the right-hand side; the sum simplifies identically term by term.

    lines 64–68

    uses pstar_tr_B_mulVec, Finset.mul_sum, Finset.sum_congr

      simp only [dotProduct, pstar_tr_B_mulVec, Finset.mul_sum, ← Finset.sum_sub_distrib]
      refine Finset.sum_congr rfl (fun i _ => ?_)
      have hei : e i ≠ 0 := (he i).ne'
      field_simp
      ring
  5. If 0 < α < 1 and the diagonally weighted sum W_e(M, x) ≥ 0 holds for all x, then the transpose also satisfies W_e(Mᵀ, x) ≥ 0 for all x.

    With c = 1 - α² > 0, the hypothesis W_e(M, x) ≥ 0 and the norm identity mean ‖B u‖² ≥ (1 - α²)‖u‖² for all u. By the singular value transfer theorem, the transpose satisfies ‖Bᵀ v‖² ≥ (1 - α²)‖v‖² for all v. Since Bᵀ is the scaled matrix for Mᵀ, applying the norm identity to Mᵀ at v = D x reveals that 2α W_e(Mᵀ, x) = ‖Bᵀ v‖² - (1 - α²)‖v‖² ≥ 0, which gives W_e(Mᵀ, x) ≥ 0 since α > 0.

    lines 77–93

    uses pstar_tr_sigma_min, pstar_tr_identity, pstar_tr_B_transpose

      have hc : 0 < 1 - α ^ 2 := by nlinarith
      have hB := pstar_tr_sigma_min
        (1 + α • (Matrix.diagonal (fun j => (e j)⁻¹) * M * Matrix.diagonal (fun j => (e j)⁻¹)))
        (1 - α ^ 2) hc (fun u => by
          have h1 := pstar_tr_identity M e he α u
          have h2 := hW (fun j => (e j)⁻¹ * u j)
          nlinarith)
      rw [pstar_tr_B_transpose] at hB
      intro x
      have h1 := pstar_tr_identity M.transpose e he α (fun j => e j * x j)
      have hx : (fun j => (e j)⁻¹ * (e j * x j)) = x := by
        funext j; field_simp [(he j).ne']
      rw [hx] at h1
      have h2 := hB (fun j => e j * x j)
      by_contra hneg
      push Not at hneg
      nlinarith
  6. For α ≥ 0, if the unweighted sum ∑ (x_i (M x)_i + α |x_i (M x)_i|) ≥ 0 holds for all x, then every diagonally weighted form satisfies W_e(M, x) ≥ 0.

    Applying the arithmetic mean–geometric mean inequality in the form 2 a b ≤ a² + b² to a = e_i |x_i| and b = |(M x)_i| / e_i yields 2 |x_i (M x)_i| ≤ e_i² x_i² + (M x)_i² / e_i². Multiplying by α / 2 ≥ 0 and summing over i shows that the unweighted sum is bounded above by W_e(M, x), so nonnegativity of the former implies nonnegativity of the latter.

    lines 101–113

    uses two_mul_le_add_sq, abs_mul, mul_pow, sq_abs, div_pow, Finset.sum_le_sum, le_trans

      intro x
      refine le_trans (hS x) (Finset.sum_le_sum (fun i _ => ?_))
      have hei : e i ≠ 0 := (he i).ne'
      set p := x i
      set q := Matrix.mulVec M x i
      have key : 2 * |p * q| ≤ (e i) ^ 2 * p ^ 2 + q ^ 2 / (e i) ^ 2 := by
        have h := two_mul_le_add_sq (e i * |p|) (|q| / e i)
        have hab : e i * |p| * (|q| / e i) = |p * q| := by rw [abs_mul]; field_simp
        have ha : (e i * |p|) ^ 2 = (e i) ^ 2 * p ^ 2 := by rw [mul_pow, sq_abs]
        have hb : (|q| / e i) ^ 2 = q ^ 2 / (e i) ^ 2 := by rw [div_pow, sq_abs]
        rw [mul_assoc, hab, ha, hb] at h
        exact h
      nlinarith
  7. If the diagonally weighted condition W_e(N, x) ≥ 0 holds for all positive weight vectors e, then the unweighted condition ∑ (x_i (N x)_i + α |x_i (N x)_i|) ≥ 0 holds.

    Let G be the unweighted sum and C = (α / 2) ∑ (|x_i| + |(N x)_i|). For any parameter t > 0, choosing the weights e_i = √((|(N x)_i| + t) / (|x_i| + t)) gives an upper bound W_e(N, x) ≤ G + t C, so 0 ≤ G + t C for all t > 0. Assuming for contradiction that G < 0, evaluating at t = -G / (2 (C + 1)) > 0 forces G + t C ≤ G / 2 < 0, a contradiction. Hence G ≥ 0.

    lines 120–157

    uses mul_nonneg, Real.sq_sqrt, div_mul_eq_mul_div, div_le_iff₀, div_pos, div_le_div_iff₀

      intro x
      set G := ∑ i, (x i * Matrix.mulVec N x i + α * |x i * Matrix.mulVec N x i|)
      set C := α / 2 * ∑ i, (|x i| + |Matrix.mulVec N x i|)
      have hC : 0 ≤ C := by
        apply mul_nonneg (by linarith)
        exact Finset.sum_nonneg (fun i _ => by positivity)
      have ht : ∀ t : ℝ, 0 < t → 0 ≤ G + t * C := by
        intro t ht
        have h := hW (fun i => Real.sqrt ((|Matrix.mulVec N x i| + t) / (|x i| + t)))
          (fun i => Real.sqrt_pos.mpr (by positivity)) x
        refine le_trans h ?_
        simp only [G, C, Finset.mul_sum, ← Finset.sum_add_distrib]
        refine Finset.sum_le_sum (fun i _ => ?_)
        set p := x i
        set q := Matrix.mulVec N x i
        have hd : (Real.sqrt ((|q| + t) / (|p| + t))) ^ 2 = (|q| + t) / (|p| + t) :=
          Real.sq_sqrt (by positivity)
        rw [hd]
        have hp : 0 < |p| + t := by positivity
        have hq : 0 < |q| + t := by positivity
        have h1 : (|q| + t) / (|p| + t) * p ^ 2 ≤ |p| * (|q| + t) := by
          rw [div_mul_eq_mul_div, div_le_iff₀ hp, ← sq_abs p]
          nlinarith [mul_nonneg (mul_nonneg (abs_nonneg p) hq.le) ht.le]
        have h2 : q ^ 2 / ((|q| + t) / (|p| + t)) ≤ |q| * (|p| + t) := by
          rw [div_div_eq_mul_div, div_le_iff₀ hq, ← sq_abs q]
          nlinarith [mul_nonneg (mul_nonneg (abs_nonneg q) hp.le) ht.le]
        have h3 : (|q| + t) / (|p| + t) * p ^ 2 + q ^ 2 / ((|q| + t) / (|p| + t))
            ≤ 2 * |p * q| + t * (|p| + |q|) := by
          rw [abs_mul]; nlinarith
        have h4 := mul_le_mul_of_nonneg_left h3 (show 0 ≤ α / 2 by linarith)
        nlinarith
      by_contra hneg
      push Not at hneg
      have h := ht (-G / (2 * (C + 1))) (div_pos (by linarith) (by linarith))
      have hle : -G / (2 * (C + 1)) * C ≤ -G / 2 := by
        rw [div_mul_eq_mul_div, div_le_div_iff₀ (by linarith) (by norm_num)]
        nlinarith
      linarith
  8. For κ ≥ 0, the P*(κ) condition is equivalent to the unweighted condition ∑ (x_i (M x)_i + α |x_i (M x)_i|) ≥ 0 for all x, with α = 2κ / (1 + 2κ).

    Let p_i = x_i (M x)_i. By trichotomy, p_i + α |p_i| equals ((1 + 4κ) / (1 + 2κ)) p_i when p_i > 0, equals (1 / (1 + 2κ)) p_i when p_i < 0, and equals 0 when p_i = 0. Multiplying through by the strictly positive factor 1 + 2κ shows that the unweighted sum is nonnegative if and only if the original P*(κ) expression (1 + 4κ) ∑_{p_i > 0} p_i + ∑_{p_i < 0} p_i is nonnegative.

    lines 163–197

    uses Finset.sum_filter, lt_trichotomy, if_neg, if_pos, abs_of_neg, abs_of_pos

      unfold is_p_star_kappa
      constructor
      · rintro ⟨hκ, h⟩
        refine ⟨hκ, fun x => ?_⟩
        have hx := h x
        have hk : 0 < 1 + 2 * κ := by linarith
        have heq : (1 + 4 * κ) * (∑ i ∈ Finset.univ.filter (fun i => 0 < x i * (Matrix.mulVec M x) i), x i * (Matrix.mulVec M x) i) +
          (∑ i ∈ Finset.univ.filter (fun i => x i * (Matrix.mulVec M x) i < 0), x i * (Matrix.mulVec M x) i)
          = (1 + 2 * κ) * ∑ i, (x i * Matrix.mulVec M x i + 2 * κ / (1 + 2 * κ) * |x i * Matrix.mulVec M x i|) := by
          rw [Finset.sum_filter, Finset.sum_filter, Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib]
          refine Finset.sum_congr rfl (fun i _ => ?_)
          set p := x i * Matrix.mulVec M x i
          rcases lt_trichotomy p 0 with hp | hp | hp
          · rw [if_neg (by linarith), if_pos hp, abs_of_neg hp]; field_simp; ring
          · rw [hp]; simp
          · rw [if_pos hp, if_neg (by linarith), abs_of_pos hp]; field_simp; ring
        rw [heq] at hx
        exact (mul_nonneg_iff_of_pos_left hk).mp hx
      · rintro ⟨hκ, h⟩
        refine ⟨hκ, fun x => ?_⟩
        have hx := h x
        have hk : 0 < 1 + 2 * κ := by linarith
        have heq : (1 + 4 * κ) * (∑ i ∈ Finset.univ.filter (fun i => 0 < x i * (Matrix.mulVec M x) i), x i * (Matrix.mulVec M x) i) +
          (∑ i ∈ Finset.univ.filter (fun i => x i * (Matrix.mulVec M x) i < 0), x i * (Matrix.mulVec M x) i)
          = (1 + 2 * κ) * ∑ i, (x i * Matrix.mulVec M x i + 2 * κ / (1 + 2 * κ) * |x i * Matrix.mulVec M x i|) := by
          rw [Finset.sum_filter, Finset.sum_filter, Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib]
          refine Finset.sum_congr rfl (fun i _ => ?_)
          set p := x i * Matrix.mulVec M x i
          rcases lt_trichotomy p 0 with hp | hp | hp
          · rw [if_neg (by linarith), if_pos hp, abs_of_neg hp]; field_simp; ring
          · rw [hp]; simp
          · rw [if_pos hp, if_neg (by linarith), abs_of_pos hp]; field_simp; ring
        rw [heq]
        exact mul_nonneg hk.le hx
    
  9. If M belongs to P*(κ), then its transpose Mᵀ also belongs to P*(κ).

    If κ = 0, then α = 0, and the condition is positive semi-definiteness x ⬝ M x ≥ 0, which is identical for M and Mᵀ because x ⬝ Mᵀ x = x ⬝ M x. If κ > 0, then 0 < α < 1. The AM-GM step shows that M satisfies W_e(M, x) ≥ 0 for all positive e; the transfer theorem shows that Mᵀ satisfies W_e(Mᵀ, x) ≥ 0; and the limit step shows that Mᵀ satisfies the unweighted condition with parameter α, so Mᵀ belongs to P*(κ).

    lines 201–217

    uses pstar_tr_kappa_iff, pstar_tr_limit, pstar_tr_weighted, pstar_tr_amgm, dotProduct_comm

      obtain ⟨hκ, hS⟩ := h
      refine ⟨hκ, ?_⟩
      have hk : 0 < 1 + 2 * κ := by linarith
      rcases hκ.lt_or_eq with hκ' | hκ'
      · have hα0 : 0 < 2 * κ / (1 + 2 * κ) := by positivity
        have hα1 : 2 * κ / (1 + 2 * κ) < 1 := by rw [div_lt_one hk]; linarith
        exact pstar_tr_limit M.transpose _ hα0.le (fun e he =>
          pstar_tr_weighted M e he _ hα0 hα1 (pstar_tr_amgm M _ hα0.le hS e he))
      · subst hκ'
        intro x
        have hx := hS x
        have hsym : ∑ i, x i * Matrix.mulVec M.transpose x i = ∑ i, x i * Matrix.mulVec M x i := by
          have : dotProduct x (Matrix.mulVec M.transpose x) = dotProduct x (Matrix.mulVec M x) := by
            rw [Matrix.dotProduct_mulVec, Matrix.vecMul_transpose, dotProduct_comm]
          simpa [dotProduct] using this
        simp only [mul_zero, zero_div, zero_mul, add_zero] at hx ⊢
        rw [hsym]; exact hx
  10. The matrix Mᵀ belongs to P*, and the handicap numbers of M and Mᵀ are equal.

    Applying the transposition implication to both M and Mᵀ = (Mᵀ)ᵀ shows that {κ : ℝ | is_p_star_kappa n Mᵀ κ} = {κ : ℝ | is_p_star_kappa n M κ}. If M ∈ P*, there exists some κ ≥ 0 such that M ∈ P*(κ), so Mᵀ ∈ P*(κ) and Mᵀ ∈ P*. Since the handicap number is the infimum of this set of κ, the handicap numbers of M and Mᵀ coincide.

    lines 222–233

    uses pstar_tr_kappa_transpose

      have hset : {κ : ℝ | is_p_star_kappa n M.transpose κ} = {κ : ℝ | is_p_star_kappa n M κ} := by
        ext κ
        constructor
        · intro h
          have := pstar_tr_kappa_transpose M.transpose κ h
          simpa using this
        · exact pstar_tr_kappa_transpose M κ
      refine ⟨?_, ?_⟩
      · obtain ⟨κ, hκ, h⟩ := hM
        exact ⟨κ, hκ, pstar_tr_kappa_transpose M κ h⟩
      · unfold handicap_number
        rw [hset]
abs_mul
The absolute value of a product equals the product of the absolute values: |a * b| = |a| * |b|.
abs_of_neg
If a is negative, its absolute value is -a.
abs_of_pos
If a is positive, its absolute value is a.
div_div_eq_mul_div
Dividing fractions satisfies a / (b / c) = (a * c) / b.
div_le_div_iff₀
For positive denominators, a / b ≤ c / d is equivalent to a * d ≤ c * b.
div_le_iff₀
For positive c, b / c ≤ a is equivalent to b ≤ a * c.
div_mul_eq_mul_div
Dividing and multiplying satisfies (a / b) * c = (a * c) / b.
div_pos
The quotient of two positive numbers is positive.
div_pow
The power of a quotient is the quotient of the powers: (a / b)^n = a^n / b^n.
dotProduct_comm
The inner product of two vectors is commutative: u ⬝ v = v ⬝ u.
dotProduct_self_eq_zero
The inner product of a vector with itself is zero if and only if the vector is the zero vector.
Finset.mul_sum
A scalar factors through a finite sum: a * ∑ f_i = ∑ (a * f_i).
Finset.sum_congr
Two finite sums are equal if their index sets coincide and their summands are equal at every index.
Finset.sum_filter
A sum with a filter predicate can be expressed as a sum of if-then-else expressions over the whole set.
Finset.sum_le_sum
If f_i ≤ g_i for all indices i in a finite set, then ∑ f_i ≤ ∑ g_i.
Finset.sum_mul_sq_le_sq_mul_sq
The Cauchy–Schwarz inequality for finite sums: (∑ f_i * g_i)² ≤ (∑ f_i²) * (∑ g_i²).
Finset.sum_nonneg
A finite sum of nonnegative numbers is nonnegative.
if_neg
An if-then-else expression evaluates to the else branch when its condition is false.
if_pos
An if-then-else expression evaluates to the then branch when its condition is true.
le_trans
Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
lt_trichotomy
For any real numbers a and b, exactly one of a < b, a = b, or b < a holds.
Matrix.add_mulVec
Matrix-vector multiplication distributes over matrix addition: (A + B) u = A u + B u.
Matrix.dotProduct_mulVec
The inner product satisfies v ⬝ (A w) = (v A) ⬝ w.
Matrix.mul_assoc
Matrix multiplication is associative: (A * B) * C = A * (B * C).
Matrix.mulVec_diagonal
Multiplying a vector by a diagonal matrix scales each coordinate: (D v)_i = D_ii * v_i.
Matrix.mulVec_sub
Matrix-vector multiplication distributes over vector subtraction: A (u - v) = A u - A v.
Matrix.mulVec_transpose
Multiplying a vector by the transpose matrix satisfies Aᵀ u = u A.
Matrix.smul_mulVec
Matrix-vector multiplication commutes with scalar multiplication: (c • A) u = c • (A u).
Matrix.transpose_add
The transpose of a sum is the sum of the transposes: (A + B)ᵀ = Aᵀ + Bᵀ.
Matrix.transpose_mul
The transpose of a matrix product reverses the order: (A * B)ᵀ = Bᵀ * Aᵀ.
Matrix.transpose_smul
The transpose commutes with scalar multiplication: (c • A)ᵀ = c • Aᵀ.
mul_nonneg
The product of two nonnegative numbers is nonnegative.
mul_pow
The power of a product is the product of the powers: (a * b)^n = a^n * b^n.
mul_self_nonneg
The square of any real number is nonnegative: 0 ≤ a * a.
pstar_tr_amgm
The unweighted P*(κ) condition implies the diagonally weighted condition W_e(M, x) ≥ 0 for all positive weight vectors e.
pstar_tr_B_mulVec
Coordinate-wise action of the diagonally scaled matrix B = 1 + α D⁻¹ M D⁻¹ on a vector.
pstar_tr_B_transpose
The transpose of 1 + α D⁻¹ M D⁻¹ equals 1 + α D⁻¹ Mᵀ D⁻¹.
pstar_tr_identity
Exact norm identity relating ‖B u‖² - (1 - α²)‖u‖² to the diagonally weighted sum 2α W_e(M, D⁻¹ u).
pstar_tr_kappa_iff
A matrix belongs to P*(κ) if and only if κ ≥ 0 and ∑ (x_i (M x)_i + α |x_i (M x)_i|) ≥ 0 for all x, where α = 2κ / (1 + 2κ).
pstar_tr_kappa_transpose
If M belongs to P*(κ), then its transpose Mᵀ also belongs to P*(κ).
pstar_tr_limit
The unweighted condition ∑ (x_i (N x)_i + α |x_i (N x)_i|) ≥ 0 is recovered from the family of weighted conditions W_e(N, x) ≥ 0 for all positive e.
pstar_tr_sigma_min
A positive lower bound c ‖u‖² ≤ ‖B u‖² on a square matrix carries over to its transpose Bᵀ.
pstar_tr_weighted
The diagonally weighted condition W_e(M, x) ≥ 0 for all x passes to the transpose: W_e(Mᵀ, x) ≥ 0 for all x.
Real.sq_sqrt
The square of the square root of a nonnegative number x is x: (√x)² = x.
sq_abs
The square of the absolute value equals the square: |a|² = a².
two_mul_le_add_sq
For any real numbers a and b, 2 * a * b ≤ a² + b².

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

/-- A lower bound `c ‖u‖² ≤ ‖B u‖²` (c > 0) passes from a square matrix to its transpose. -/theorem pstar_tr_sigma_min {n : ℕ} (B : Matrix (Fin n) (Fin n) ℝ) (c : ℝ) (hc : 0 < c)    (h : ∀ u : Fin n → ℝ, c * dotProduct u u ≤ dotProduct (Matrix.mulVec B u) (Matrix.mulVec B u)) :    ∀ v : Fin n → ℝ, c * dotProduct v v ≤      dotProduct (Matrix.mulVec B.transpose v) (Matrix.mulVec B.transpose v) := by  have hinj : Function.Injective (Matrix.mulVec B) := by    intro a b hab    have h0 := h (a - b)    rw [Matrix.mulVec_sub, hab, sub_self, dotProduct_zero] at h0    have h1 : 0 ≤ dotProduct (a - b) (a - b) := by      unfold dotProduct; exact Finset.sum_nonneg (fun i _ => mul_self_nonneg _)    have h2 : dotProduct (a - b) (a - b) = 0 := by nlinarith    rw [dotProduct_self_eq_zero] at h2    exact sub_eq_zero.mp h2  have hsurj : Function.Surjective (Matrix.mulVec B) :=    Matrix.mulVec_surjective_iff_isUnit.mpr (Matrix.mulVec_injective_iff_isUnit.mp hinj)  intro v  obtain ⟨u, rfl⟩ := hsurj v  set w := Matrix.mulVec B.transpose (Matrix.mulVec B u) with hw  have hdual : dotProduct w u = dotProduct (Matrix.mulVec B u) (Matrix.mulVec B u) := by    rw [hw, Matrix.mulVec_transpose, ← Matrix.dotProduct_mulVec]  have hcs : (dotProduct w u) ^ 2 ≤ dotProduct w w * dotProduct u u := by    have := Finset.sum_mul_sq_le_sq_mul_sq Finset.univ w u    simpa [dotProduct, sq] using this  set a := dotProduct (Matrix.mulVec B u) (Matrix.mulVec B u)  set b := dotProduct w w  set s := dotProduct u u  have ha : 0 ≤ a := by    simp only [a, dotProduct]; exact Finset.sum_nonneg (fun i _ => mul_self_nonneg _)  have hb : 0 ≤ b := by    simp only [b, dotProduct]; exact Finset.sum_nonneg (fun i _ => mul_self_nonneg _)  have hs : 0 ≤ s := by    simp only [s, dotProduct]; exact Finset.sum_nonneg (fun i _ => mul_self_nonneg _)  have hcsa : c * s ≤ a := h u  rw [hdual] at hcs  rcases ha.lt_or_eq with ha' | ha'  · have : c * a * a ≤ b * a := by nlinarith    nlinarith  · rw [← ha']; simpa using hb/-- The scaled matrix `1 + α D⁻¹ M D⁻¹` applied to a vector. -/theorem pstar_tr_B_mulVec {n : ℕ} (M : Matrix (Fin n) (Fin n) ℝ) (e : Fin n → ℝ) (α : ℝ)    (u : Fin n → ℝ) (i : Fin n) :    Matrix.mulVec (1 + α • (Matrix.diagonal (fun j => (e j)⁻¹) * M * Matrix.diagonal (fun j => (e j)⁻¹))) u i      = u i + α * ((e i)⁻¹ * Matrix.mulVec M (fun j => (e j)⁻¹ * u j) i) := by  have hd : ∀ v : Fin n → ℝ, (Matrix.diagonal fun j => (e j)⁻¹).mulVec v = fun j => (e j)⁻¹ * v j := by    intro v; funext j; simp [Matrix.mulVec_diagonal]  simp [Matrix.add_mulVec, Matrix.smul_mulVec, ← Matrix.mulVec_mulVec, hd]theorem pstar_tr_B_transpose {n : ℕ} (M : Matrix (Fin n) (Fin n) ℝ) (e : Fin n → ℝ) (α : ℝ) :    (1 + α • (Matrix.diagonal (fun j => (e j)⁻¹) * M * Matrix.diagonal (fun j => (e j)⁻¹))).transpose      = 1 + α • (Matrix.diagonal (fun j => (e j)⁻¹) * M.transpose * Matrix.diagonal (fun j => (e j)⁻¹)) := by  simp [Matrix.transpose_add, Matrix.transpose_smul, Matrix.transpose_mul, Matrix.mul_assoc]/-- The norm identity behind the scaling: `‖B u‖² - (1-α²)‖u‖² = 2α W(x)` with `x = D⁻¹ u`. -/theorem pstar_tr_identity {n : ℕ} (M : Matrix (Fin n) (Fin n) ℝ) (e : Fin n → ℝ) (he : ∀ i, 0 < e i)    (α : ℝ) (u : Fin n → ℝ) :    dotProduct (Matrix.mulVec (1 + α • (Matrix.diagonal (fun j => (e j)⁻¹) * M * Matrix.diagonal (fun j => (e j)⁻¹))) u)      (Matrix.mulVec (1 + α • (Matrix.diagonal (fun j => (e j)⁻¹) * M * Matrix.diagonal (fun j => (e j)⁻¹))) u)      - (1 - α ^ 2) * dotProduct u u      = 2 * α * ∑ i, ((fun j => (e j)⁻¹ * u j) i * Matrix.mulVec M (fun j => (e j)⁻¹ * u j) i          + α / 2 * ((e i) ^ 2 * ((fun j => (e j)⁻¹ * u j) i) ^ 2            + (Matrix.mulVec M (fun j => (e j)⁻¹ * u j) i) ^ 2 / (e i) ^ 2)) := by  simp only [dotProduct, pstar_tr_B_mulVec, Finset.mul_sum, ← Finset.sum_sub_distrib]  refine Finset.sum_congr rfl (fun i _ => ?_)  have hei : e i ≠ 0 := (he i).ne'  field_simp  ring/-- Diagonally weighted form `W_e(N, x)`. -/theorem pstar_tr_weighted {n : ℕ} (M : Matrix (Fin n) (Fin n) ℝ) (e : Fin n → ℝ) (he : ∀ i, 0 < e i)    (α : ℝ) (hα0 : 0 < α) (hα1 : α < 1)    (hW : ∀ x : Fin n → ℝ, 0 ≤ ∑ i, (x i * Matrix.mulVec M x i      + α / 2 * ((e i) ^ 2 * (x i) ^ 2 + (Matrix.mulVec M x i) ^ 2 / (e i) ^ 2))) :    ∀ x : Fin n → ℝ, 0 ≤ ∑ i, (x i * Matrix.mulVec M.transpose x i      + α / 2 * ((e i) ^ 2 * (x i) ^ 2 + (Matrix.mulVec M.transpose x i) ^ 2 / (e i) ^ 2)) := by  have hc : 0 < 1 - α ^ 2 := by nlinarith  have hB := pstar_tr_sigma_min    (1 + α • (Matrix.diagonal (fun j => (e j)⁻¹) * M * Matrix.diagonal (fun j => (e j)⁻¹)))    (1 - α ^ 2) hc (fun u => by      have h1 := pstar_tr_identity M e he α u      have h2 := hW (fun j => (e j)⁻¹ * u j)      nlinarith)  rw [pstar_tr_B_transpose] at hB  intro x  have h1 := pstar_tr_identity M.transpose e he α (fun j => e j * x j)  have hx : (fun j => (e j)⁻¹ * (e j * x j)) = x := by    funext j; field_simp [(he j).ne']  rw [hx] at h1  have h2 := hB (fun j => e j * x j)  by_contra hneg  push Not at hneg  nlinarith/-- AM-GM: the plain condition gives every weighted one. -/theorem pstar_tr_amgm {n : ℕ} (M : Matrix (Fin n) (Fin n) ℝ) (α : ℝ) (hα : 0 ≤ α)    (hS : ∀ x : Fin n → ℝ, 0 ≤ ∑ i, (x i * Matrix.mulVec M x i + α * |x i * Matrix.mulVec M x i|))    (e : Fin n → ℝ) (he : ∀ i, 0 < e i) :    ∀ x : Fin n → ℝ, 0 ≤ ∑ i, (x i * Matrix.mulVec M x i      + α / 2 * ((e i) ^ 2 * (x i) ^ 2 + (Matrix.mulVec M x i) ^ 2 / (e i) ^ 2)) := by  intro x  refine le_trans (hS x) (Finset.sum_le_sum (fun i _ => ?_))  have hei : e i ≠ 0 := (he i).ne'  set p := x i  set q := Matrix.mulVec M x i  have key : 2 * |p * q| ≤ (e i) ^ 2 * p ^ 2 + q ^ 2 / (e i) ^ 2 := by    have h := two_mul_le_add_sq (e i * |p|) (|q| / e i)    have hab : e i * |p| * (|q| / e i) = |p * q| := by rw [abs_mul]; field_simp    have ha : (e i * |p|) ^ 2 = (e i) ^ 2 * p ^ 2 := by rw [mul_pow, sq_abs]    have hb : (|q| / e i) ^ 2 = q ^ 2 / (e i) ^ 2 := by rw [div_pow, sq_abs]    rw [mul_assoc, hab, ha, hb] at h    exact h  nlinarith/-- Taking the weights to the limit recovers the plain condition. -/theorem pstar_tr_limit {n : ℕ} (N : Matrix (Fin n) (Fin n) ℝ) (α : ℝ) (hα : 0 ≤ α)    (hW : ∀ e : Fin n → ℝ, (∀ i, 0 < e i) → ∀ x : Fin n → ℝ, 0 ≤ ∑ i, (x i * Matrix.mulVec N x i      + α / 2 * ((e i) ^ 2 * (x i) ^ 2 + (Matrix.mulVec N x i) ^ 2 / (e i) ^ 2))) :    ∀ x : Fin n → ℝ, 0 ≤ ∑ i, (x i * Matrix.mulVec N x i + α * |x i * Matrix.mulVec N x i|) := by  intro x  set G := ∑ i, (x i * Matrix.mulVec N x i + α * |x i * Matrix.mulVec N x i|)  set C := α / 2 * ∑ i, (|x i| + |Matrix.mulVec N x i|)  have hC : 0 ≤ C := by    apply mul_nonneg (by linarith)    exact Finset.sum_nonneg (fun i _ => by positivity)  have ht : ∀ t : ℝ, 0 < t → 0 ≤ G + t * C := by    intro t ht    have h := hW (fun i => Real.sqrt ((|Matrix.mulVec N x i| + t) / (|x i| + t)))      (fun i => Real.sqrt_pos.mpr (by positivity)) x    refine le_trans h ?_    simp only [G, C, Finset.mul_sum, ← Finset.sum_add_distrib]    refine Finset.sum_le_sum (fun i _ => ?_)    set p := x i    set q := Matrix.mulVec N x i    have hd : (Real.sqrt ((|q| + t) / (|p| + t))) ^ 2 = (|q| + t) / (|p| + t) :=      Real.sq_sqrt (by positivity)    rw [hd]    have hp : 0 < |p| + t := by positivity    have hq : 0 < |q| + t := by positivity    have h1 : (|q| + t) / (|p| + t) * p ^ 2 ≤ |p| * (|q| + t) := by      rw [div_mul_eq_mul_div, div_le_iff₀ hp, ← sq_abs p]      nlinarith [mul_nonneg (mul_nonneg (abs_nonneg p) hq.le) ht.le]    have h2 : q ^ 2 / ((|q| + t) / (|p| + t)) ≤ |q| * (|p| + t) := by      rw [div_div_eq_mul_div, div_le_iff₀ hq, ← sq_abs q]      nlinarith [mul_nonneg (mul_nonneg (abs_nonneg q) hp.le) ht.le]    have h3 : (|q| + t) / (|p| + t) * p ^ 2 + q ^ 2 / ((|q| + t) / (|p| + t))        ≤ 2 * |p * q| + t * (|p| + |q|) := by      rw [abs_mul]; nlinarith    have h4 := mul_le_mul_of_nonneg_left h3 (show 0 ≤ α / 2 by linarith)    nlinarith  by_contra hneg  push Not at hneg  have h := ht (-G / (2 * (C + 1))) (div_pos (by linarith) (by linarith))  have hle : -G / (2 * (C + 1)) * C ≤ -G / 2 := by    rw [div_mul_eq_mul_div, div_le_div_iff₀ (by linarith) (by norm_num)]    nlinarith  linarith/-- The P*(κ) condition in the form `Σ (p + α|p|) ≥ 0`, `α = 2κ/(1+2κ)`. -/theorem pstar_tr_kappa_iff {n : ℕ} (M : Matrix (Fin n) (Fin n) ℝ) (κ : ℝ) :    is_p_star_kappa n M κ ↔ 0 ≤ κ ∧ ∀ x : Fin n → ℝ,      0 ≤ ∑ i, (x i * Matrix.mulVec M x i + 2 * κ / (1 + 2 * κ) * |x i * Matrix.mulVec M x i|) := by  unfold is_p_star_kappa  constructor  · rintro ⟨hκ, h⟩    refine ⟨hκ, fun x => ?_⟩    have hx := h x    have hk : 0 < 1 + 2 * κ := by linarith    have heq : (1 + 4 * κ) * (∑ i ∈ Finset.univ.filter (fun i => 0 < x i * (Matrix.mulVec M x) i), x i * (Matrix.mulVec M x) i) +      (∑ i ∈ Finset.univ.filter (fun i => x i * (Matrix.mulVec M x) i < 0), x i * (Matrix.mulVec M x) i)      = (1 + 2 * κ) * ∑ i, (x i * Matrix.mulVec M x i + 2 * κ / (1 + 2 * κ) * |x i * Matrix.mulVec M x i|) := by      rw [Finset.sum_filter, Finset.sum_filter, Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib]      refine Finset.sum_congr rfl (fun i _ => ?_)      set p := x i * Matrix.mulVec M x i      rcases lt_trichotomy p 0 with hp | hp | hp      · rw [if_neg (by linarith), if_pos hp, abs_of_neg hp]; field_simp; ring      · rw [hp]; simp      · rw [if_pos hp, if_neg (by linarith), abs_of_pos hp]; field_simp; ring    rw [heq] at hx    exact (mul_nonneg_iff_of_pos_left hk).mp hx  · rintro ⟨hκ, h⟩    refine ⟨hκ, fun x => ?_⟩    have hx := h x    have hk : 0 < 1 + 2 * κ := by linarith    have heq : (1 + 4 * κ) * (∑ i ∈ Finset.univ.filter (fun i => 0 < x i * (Matrix.mulVec M x) i), x i * (Matrix.mulVec M x) i) +      (∑ i ∈ Finset.univ.filter (fun i => x i * (Matrix.mulVec M x) i < 0), x i * (Matrix.mulVec M x) i)      = (1 + 2 * κ) * ∑ i, (x i * Matrix.mulVec M x i + 2 * κ / (1 + 2 * κ) * |x i * Matrix.mulVec M x i|) := by      rw [Finset.sum_filter, Finset.sum_filter, Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib]      refine Finset.sum_congr rfl (fun i _ => ?_)      set p := x i * Matrix.mulVec M x i      rcases lt_trichotomy p 0 with hp | hp | hp      · rw [if_neg (by linarith), if_pos hp, abs_of_neg hp]; field_simp; ring      · rw [hp]; simp      · rw [if_pos hp, if_neg (by linarith), abs_of_pos hp]; field_simp; ring    rw [heq]    exact mul_nonneg hk.le hxtheorem pstar_tr_kappa_transpose {n : ℕ} (M : Matrix (Fin n) (Fin n) ℝ) (κ : ℝ)    (h : is_p_star_kappa n M κ) : is_p_star_kappa n M.transpose κ := by  rw [pstar_tr_kappa_iff] at h ⊢  obtain ⟨hκ, hS⟩ := h  refine ⟨hκ, ?_⟩  have hk : 0 < 1 + 2 * κ := by linarith  rcases hκ.lt_or_eq with hκ' | hκ'  · have hα0 : 0 < 2 * κ / (1 + 2 * κ) := by positivity    have hα1 : 2 * κ / (1 + 2 * κ) < 1 := by rw [div_lt_one hk]; linarith    exact pstar_tr_limit M.transpose _ hα0.le (fun e he =>      pstar_tr_weighted M e he _ hα0 hα1 (pstar_tr_amgm M _ hα0.le hS e he))  · subst hκ'    intro x    have hx := hS x    have hsym : ∑ i, x i * Matrix.mulVec M.transpose x i = ∑ i, x i * Matrix.mulVec M x i := by      have : dotProduct x (Matrix.mulVec M.transpose x) = dotProduct x (Matrix.mulVec M x) := by        rw [Matrix.dotProduct_mulVec, Matrix.vecMul_transpose, dotProduct_comm]      simpa [dotProduct] using this    simp only [mul_zero, zero_div, zero_mul, add_zero] at hx ⊢    rw [hsym]; exact hx/-- Transposition invariance of the class P* and the handicap number. -/theorem p_star_transpose_handicap_invariance (n : ℕ) (M : Matrix (Fin n) (Fin n) ℝ) (hM : is_p_star n M) :    is_p_star n M.transpose ∧ handicap_number n M.transpose = handicap_number n M := by  have hset : {κ : ℝ | is_p_star_kappa n M.transpose κ} = {κ : ℝ | is_p_star_kappa n M κ} := by    ext κ    constructor    · intro h      have := pstar_tr_kappa_transpose M.transpose κ h      simpa using this    · exact pstar_tr_kappa_transpose M κ  refine ⟨?_, ?_⟩  · obtain ⟨κ, hκ, h⟩ := hM    exact ⟨κ, hκ, pstar_tr_kappa_transpose M κ h⟩  · unfold handicap_number    rw [hset]
See it in the graphDiscuss this resultChallenge it