root_lattice_form_pos_def
The k×k matrix H = I_k − 11ᵀ/(k+1) is positive definite.
Statement
theorem root_lattice_form_pos_def (k : ℕ) : (1 - (1 / ((k : ℝ) + 1)) • Matrix.of (fun _ _ : Fin k => (1 : ℝ))).PosDef
- Source
- arXiv:2610.26970 (Gaussian Lower Bounds for Distinct Subset Sums in Higher Dimensions), Proposition 3.2: the positive-definiteness claim
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- magic_square_winning_op_zero_leftFor any dimensions dA and dB and any Bob matrix effects B : Fin 3 → (Fin 3 → Bool) → Matrix (Fin dB) (Fin dB) ℂ, if Alice's matrix effects…
The proof, explained
To show that the matrix H = I_k − (1/(k+1)) 11ᵀ is positive definite, we first observe that H is real symmetric (Hermitian), reducing the goal to showing that xᵀ H x > 0 for all non-zero x. Evaluating the quadratic form yields xᵀ H x = ∑_i x_i² − (1/(k+1)) (∑_i x_i)². By the Cauchy–Schwarz inequality, (∑_i x_i)² ≤ k ∑_i x_i², so the quadratic form is bounded below by (1 − k/(k+1)) ∑_i x_i² = (1/(k+1)) ∑_i x_i². Since x is non-zero, its sum of squares is strictly positive, which ensures that xᵀ H x > 0.
The matrix H = I_k − (1/(k+1)) 11ᵀ is Hermitian, so it suffices to show that its quadratic form xᵀ H x is strictly positive for every non-zero vector x.
By Matrix.PosDef.of_dotProduct_mulVec_pos, positive definiteness reduces to checking that H is Hermitian and that the quadratic form star(x) ⬝ᵥ (H x) is strictly positive whenever x ≠ 0. Since the (i, j)-th entry is δ_{ij} − 1/(k+1), which is symmetric in i and j and real-valued, H is Hermitian.
uses
Matrix.PosDef.of_dotProduct_mulVec_pos,Matrix.IsHermitian.ext,Matrix.sub_apply,Matrix.one_apply,Matrix.of_apply,eq_commapply Matrix.PosDef.of_dotProduct_mulVec_pos · apply Matrix.IsHermitian.ext intro i j simp [Matrix.sub_apply, Matrix.one_apply, Matrix.of_apply, eq_comm]
We may assume that k ≠ 0.
We introduce a non-zero vector x. If k = 0, the indexing type Fin 0 is empty, so x is identically zero, which contradicts the hypothesis x ≠ 0. Hence k cannot be 0.
· intro x hx by_cases hk : k = 0 · subst k exfalso apply hx funext i exact i.elim0
The matrix-vector product H x has components (H x)_i = x_i − (1/(k+1)) ∑_j x_j.
Unfolding matrix-vector multiplication, the identity matrix contributes x_i and the all-ones matrix contributes the sum of all components ∑_j x_j scaled by 1/(k+1).
uses
Matrix.mulVec,dotProduct,Matrix.sub_apply,Matrix.one_apply,Matrix.of_apply,Matrix.smul_apply,smul_eq_mul,sub_mul,Finset.sum_sub_distrib,Finset.mul_sum· have hMx : Matrix.mulVec (1 - (1 / ((k : ℝ) + 1)) • Matrix.of (fun _ _ : Fin k => (1 : ℝ))) x = fun i => x i - (1 / ((k : ℝ) + 1)) * (∑ j, x j) := by funext i simp only [Matrix.mulVec, dotProduct, Matrix.sub_apply, Matrix.one_apply, Matrix.of_apply, Matrix.smul_apply, smul_eq_mul, sub_mul] rw [Finset.sum_sub_distrib] congr 1 · simp · rw [← Finset.mul_sum] ring
The quadratic form evaluates to star(x) ⬝ᵥ (H x) = ∑_i x_i² − (1/(k+1)) (∑_i x_i)².
Taking the inner product of x with H x gives ∑_i x_i (x_i − (1/(k+1)) ∑_j x_j). Distributing the sum yields the sum of squares ∑_i x_i² minus (1/(k+1)) times the product (∑_i x_i)(∑_j x_j) = (∑_i x_i)². Rewriting with this identity transforms the goal into showing that this expression is strictly positive.
uses
dotProduct,star_trivial,mul_sub,Finset.sum_sub_distrib,pow_two,Finset.sum_mulhave hQ : dotProduct (star x) (fun i => x i - (1 / ((k : ℝ) + 1)) * (∑ j, x j)) = (∑ i, x i ^ 2) - (1 / ((k : ℝ) + 1)) * (∑ i, x i)^2 := by simp only [dotProduct, star_trivial] simp only [mul_sub] rw [Finset.sum_sub_distrib] congr 1 · simp [pow_two] · rw [← Finset.sum_mul] ring rw [hMx, hQ]
By the Cauchy–Schwarz inequality, (∑_i x_i)² ≤ k ∑_i x_i².
Applying sq_sum_le_card_mul_sum_sq to the vector x over the k-element universe Finset.univ gives the standard Cauchy–Schwarz bound (∑_i x_i)² ≤ k ∑_i x_i².
uses
sq_sum_le_card_mul_sum_sq,Finset.univhave hcs : (∑ i, x i)^2 ≤ (k : ℝ) * ∑ i, x i^2 := by simpa using (sq_sum_le_card_mul_sum_sq (s := (Finset.univ : Finset (Fin k))) (f := x))
The sum of squares ∑_i x_i² is strictly positive.
Since x ≠ 0, there is at least one coordinate i with x_i ≠ 0. The square x_i² is strictly positive and all other squares are non-negative, so their sum over all coordinates is strictly positive.
uses
Finset.sum_pos',sq_nonneg,Finset.mem_univ,sq_pos_of_ne_zerohave hApos : 0 < ∑ i, x i ^ 2 := by have hne : ∃ i : Fin k, x i ≠ 0 := by by_contra h apply hx funext i by_contra hi exact h ⟨i, hi⟩ obtain ⟨i, hi⟩ := hne exact Finset.sum_pos' (fun j _ => sq_nonneg (x j)) ⟨i, Finset.mem_univ i, sq_pos_of_ne_zero hi⟩
The subtracted term satisfies (1/(k+1)) (∑_i x_i)² ≤ (k/(k+1)) ∑_i x_i².
Because k ≥ 0, the factor 1/(k+1) is non-negative. Multiplying the Cauchy–Schwarz inequality by 1/(k+1) preserves the inequality.
uses
mul_le_mul_of_nonneg_lefthave hbound : (1 / ((k : ℝ) + 1)) * (∑ i, x i)^2 ≤ ((k : ℝ) / ((k : ℝ) + 1)) * (∑ i, x i ^ 2) := by have hc : 0 ≤ 1 / ((k : ℝ) + 1) := by positivity calc (1 / ((k : ℝ) + 1)) * (∑ i, x i)^2 ≤ (1 / ((k : ℝ) + 1)) * ((k : ℝ) * (∑ i, x i ^ 2)) := mul_le_mul_of_nonneg_left hcs hc _ = ((k : ℝ) / ((k : ℝ) + 1)) * (∑ i, x i ^ 2) := by ring
The coefficient 1 − k/(k+1) is equal to 1/(k+1) and is strictly positive.
Putting 1 − k/(k+1) over a common denominator yields (k+1 − k)/(k+1) = 1/(k+1), which is strictly positive because k ≥ 0.
have hcoef : 0 < (1 : ℝ) - (k : ℝ) / ((k : ℝ) + 1) := by have h : (1 : ℝ) - (k : ℝ) / ((k : ℝ) + 1) = 1 / ((k : ℝ) + 1) := by field_simp ring rw [h] positivity
The quadratic form is strictly positive: ∑_i x_i² − (1/(k+1)) (∑_i x_i)² > 0. automation
The quadratic form is bounded below by (1 − k/(k+1)) ∑_i x_i² = (1/(k+1)) ∑_i x_i². Since both the coefficient and the sum of squares are strictly positive, their product is strictly positive, and nlinarith deduces that the quadratic form is strictly positive.
uses
mul_posnlinarith [mul_pos hcoef hApos]
Matrix.PosDef.of_dotProduct_mulVec_pos- A matrix M is positive definite if it is Hermitian and star(x) ⬝ᵥ (M.mulVec x) > 0 for all non-zero vectors x.
Matrix.IsHermitian.ext- A matrix A is Hermitian if star(A j i) = A i j for all indices i and j.
Matrix.sub_apply- The (i, j)-th entry of a difference of matrices A - B is A i j - B i j.
Matrix.one_apply- The (i, j)-th entry of the identity matrix is 1 if i = j and 0 otherwise.
Matrix.of_apply- The (i, j)-th entry of the matrix formed from a function f is f i j.
eq_comm- Equality is symmetric: a = b if and only if b = a.
Matrix.mulVec- Matrix-vector multiplication: (M.mulVec x) i is the dot product of the i-th row of M with x.
dotProduct- The dot product of two vectors is the sum over all indices of their pointwise product.
Matrix.smul_apply- The (i, j)-th entry of the scalar multiple r • A is r • (A i j).
smul_eq_mul- Scalar multiplication of real numbers is standard multiplication: a • b = a * b.
sub_mul- Distributivity of subtraction on the right: (a - b) * c = a * c - b * c.
Finset.sum_sub_distrib- The sum of differences is the difference of sums: ∑ (f x - g x) = ∑ f x - ∑ g x.
Finset.mul_sum- Factoring a scalar out of a sum on the left: a * ∑ f i = ∑ a * f i.
star_trivial- For real numbers, the star operation is the identity: star r = r.
mul_sub- Distributivity of multiplication on the left: a * (b - c) = a * b - a * c.
pow_two- The square of an element is its product with itself: a ^ 2 = a * a.
Finset.sum_mul- Factoring a scalar out of a sum on the right: (∑ f i) * a = ∑ f i * a.
sq_sum_le_card_mul_sum_sq- The Cauchy–Schwarz inequality for sums: (∑_{i ∈ s} f i)^2 ≤ |s| * ∑_{i ∈ s} (f i)^2.
Finset.univ- The universal finset containing all elements of a finite type.
Finset.sum_pos'- A sum of non-negative terms is strictly positive if at least one term is strictly positive.
sq_nonneg- The square of any real number is non-negative: 0 ≤ a ^ 2.
Finset.mem_univ- Every element of a finite type belongs to Finset.univ.
sq_pos_of_ne_zero- The square of a non-zero real number is strictly positive: a ≠ 0 → 0 < a ^ 2.
mul_le_mul_of_nonneg_left- Multiplying an inequality b ≤ c on the left by a non-negative number a ≥ 0 yields a * b ≤ a * c.
mul_pos- The product of two strictly positive real numbers is strictly positive: 0 < a → 0 < b → 0 < a * b.
- The case k = 0 is a formal edge case where the vector space of dimension 0 has no non-zero vectors, making the condition vacuously true.
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.
theorem root_lattice_form_pos_def (k : ℕ) : (1 - (1 / ((k : ℝ) + 1)) • Matrix.of (fun _ _ : Fin k => (1 : ℝ))).PosDef := by apply Matrix.PosDef.of_dotProduct_mulVec_pos · apply Matrix.IsHermitian.ext intro i j simp [Matrix.sub_apply, Matrix.one_apply, Matrix.of_apply, eq_comm] · intro x hx by_cases hk : k = 0 · subst k exfalso apply hx funext i exact i.elim0 · have hMx : Matrix.mulVec (1 - (1 / ((k : ℝ) + 1)) • Matrix.of (fun _ _ : Fin k => (1 : ℝ))) x = fun i => x i - (1 / ((k : ℝ) + 1)) * (∑ j, x j) := by funext i simp only [Matrix.mulVec, dotProduct, Matrix.sub_apply, Matrix.one_apply, Matrix.of_apply, Matrix.smul_apply, smul_eq_mul, sub_mul] rw [Finset.sum_sub_distrib] congr 1 · simp · rw [← Finset.mul_sum] ring have hQ : dotProduct (star x) (fun i => x i - (1 / ((k : ℝ) + 1)) * (∑ j, x j)) = (∑ i, x i ^ 2) - (1 / ((k : ℝ) + 1)) * (∑ i, x i)^2 := by simp only [dotProduct, star_trivial] simp only [mul_sub] rw [Finset.sum_sub_distrib] congr 1 · simp [pow_two] · rw [← Finset.sum_mul] ring rw [hMx, hQ] have hcs : (∑ i, x i)^2 ≤ (k : ℝ) * ∑ i, x i^2 := by simpa using (sq_sum_le_card_mul_sum_sq (s := (Finset.univ : Finset (Fin k))) (f := x)) have hApos : 0 < ∑ i, x i ^ 2 := by have hne : ∃ i : Fin k, x i ≠ 0 := by by_contra h apply hx funext i by_contra hi exact h ⟨i, hi⟩ obtain ⟨i, hi⟩ := hne exact Finset.sum_pos' (fun j _ => sq_nonneg (x j)) ⟨i, Finset.mem_univ i, sq_pos_of_ne_zero hi⟩ have hbound : (1 / ((k : ℝ) + 1)) * (∑ i, x i)^2 ≤ ((k : ℝ) / ((k : ℝ) + 1)) * (∑ i, x i ^ 2) := by have hc : 0 ≤ 1 / ((k : ℝ) + 1) := by positivity calc (1 / ((k : ℝ) + 1)) * (∑ i, x i)^2 ≤ (1 / ((k : ℝ) + 1)) * ((k : ℝ) * (∑ i, x i ^ 2)) := mul_le_mul_of_nonneg_left hcs hc _ = ((k : ℝ) / ((k : ℝ) + 1)) * (∑ i, x i ^ 2) := by ring have hcoef : 0 < (1 : ℝ) - (k : ℝ) / ((k : ℝ) + 1) := by have h : (1 : ℝ) - (k : ℝ) / ((k : ℝ) + 1) = 1 / ((k : ℝ) + 1) := by field_simp ring rw [h] positivity nlinarith [mul_pos hcoef hApos]