p_star_transpose_handicap_invariance
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*(κ).
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.
uses
Matrix.mulVec_sub,Finset.sum_nonneg,mul_self_nonneg,dotProduct_self_eq_zerohave 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)
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.
uses
Matrix.mulVec_transpose,Matrix.dotProduct_mulVec,Finset.sum_mul_sq_le_sq_mul_sqintro 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 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⁻¹.
uses
Matrix.mulVec_diagonal,Matrix.add_mulVec,Matrix.smul_mulVec,Matrix.transpose_add,Matrix.transpose_smul,Matrix.transpose_mul,Matrix.mul_assochave 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]
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.
uses
pstar_tr_B_mulVec,Finset.mul_sum,Finset.sum_congrsimp 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
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.
uses
pstar_tr_sigma_min,pstar_tr_identity,pstar_tr_B_transposehave 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
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.
uses
two_mul_le_add_sq,abs_mul,mul_pow,sq_abs,div_pow,Finset.sum_le_sum,le_transintro 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
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.
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
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.
uses
Finset.sum_filter,lt_trichotomy,if_neg,if_pos,abs_of_neg,abs_of_posunfold 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
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*(κ).
uses
pstar_tr_kappa_iff,pstar_tr_limit,pstar_tr_weighted,pstar_tr_amgm,dotProduct_commobtain ⟨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
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.
uses
pstar_tr_kappa_transposehave 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².
- The limiting argument in `pstar_tr_limit` uses an algebraic contradiction rather than an analytic limit: by evaluating the inequality at the specific parameter t = -G / (2 * (C + 1)) > 0 when assuming G < 0, it derives a contradiction directly without needing topology or convergence lemmas.
- Unresolved check: no step explains line(s) 200 -- every tactic of the proof has to belong to some step
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.
/-- 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]