distinct_subset_sums_root_matrix_pos_def
For any natural number k ≥ 1, the root lattice matrix distinct_subset_sums_root_matrix k is positive definite.
Statement
theorem distinct_subset_sums_root_matrix_pos_def (k : ℕ) (hk : 1 ≤ k) :
Matrix.PosDef (distinct_subset_sums_root_matrix k)- Source
- arXiv:2610.26970 Proposition 3.2
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- distinct_subset_sums_root_matrixFor a natural number k, distinct_subset_sums_root_matrix k is the real k × k matrix H whose (i, j)-th entry is (if i = j then (1 : ℝ) else…
Read back from the Lean
For every natural number $k$ such that $1 \le k$, the $k \times k$ real matrix distinct_subset_sums_root_matrix k is positive definite (in the sense of Matrix.PosDef).
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 root lattice matrix distinct_subset_sums_root_matrix k is given by I_k - (1 / (k + 1)) J_k, where J_k is the all-ones matrix. To prove it is positive definite, the argument first checks that the matrix is Hermitian by entrywise symmetry. It then evaluates the quadratic form xᵀ M x as ∑ x_i² - (1 / (k + 1)) (∑ x_i)², bounds (∑ x_i)² ≤ k ∑ x_i² using the Cauchy–Schwarz inequality, and concludes that the quadratic form is strictly positive since k / (k + 1) < 1 and ∑ x_i² > 0 for x ≠ 0.
To prove that the matrix is positive definite, it suffices to show that it is Hermitian and that its quadratic form is strictly positive for every non-zero vector.
By `PosDef.of_dotProduct_mulVec_pos`, positive definiteness of a matrix M reduces to verifying two conditions: M is Hermitian (equal to its conjugate transpose), and for any vector x ≠ 0, the real quadratic form x* ⬝ᵥ (M *ᵥ x) is strictly positive.
uses
PosDef.of_dotProduct_mulVec_posopen Matrix Finset in refine PosDef.of_dotProduct_mulVec_pos ?_ ?_
The matrix distinct_subset_sums_root_matrix k is Hermitian.
Because the entries are real, conjugation is trivial via `star_trivial`. By definition, the (i, j) entry is δ_{ij} - 1/(k + 1). Comparing this with the (j, i) entry, we split into cases: if i = j, the diagonal entry trivially equals itself; if i ≠ j, then j ≠ i by `Ne.symm`, so both Kronecker delta terms vanish, leaving -1/(k + 1) on both sides.
uses
conjTranspose_apply,star_trivial,distinct_subset_sums_root_matrix,Ne.symm· ext i j simp only [conjTranspose_apply, star_trivial, distinct_subset_sums_root_matrix] by_cases h : i = j · subst h; rfl · have h' : j ≠ i := Ne.symm h simp [h, h']
For any non-zero vector x, the quadratic form evaluates to ∑ i, (x i)^2 - (1 / (k + 1)) * (∑ i, x i)^2.
Expanding the matrix-vector product coordinate-wise gives (M *ᵥ x)_i = x i - (1 / (k + 1)) * ∑ j, x j. Taking the inner product with x and distributing the multiplication and sum yields ∑ i, (x i)^2 - (1 / (k + 1)) * (∑ i, x i)^2. Rewriting the goal with this identity transforms the positive definiteness condition into proving this scalar expression is strictly positive.
uses
distinct_subset_sums_root_matrix,sub_mul,sum_sub_distrib,mul_sub,sq· intro x hx have h_dot : star x ⬝ᵥ (distinct_subset_sums_root_matrix k *ᵥ x) = ∑ i, (x i) ^ 2 - (1 / ((k : ℝ) + 1)) * (∑ i, x i) ^ 2 := by simp only [dotProduct, mulVec, star_trivial, distinct_subset_sums_root_matrix] have h (i : Fin k) : (∑ j, ((if i = j then (1 : ℝ) else 0) - 1 / ((k : ℝ) + 1)) * x j) = x i - (1 / ((k : ℝ) + 1)) * ∑ j, x j := by simp [sub_mul, sum_sub_distrib, ← mul_sum] simp_rw [h] simp only [mul_sub, sum_sub_distrib, ← sum_mul, sq] ring rw [h_dot]
There exists an index i such that x i ≠ 0.
By contraposition from the hypothesis that x ≠ 0, if x i = 0 for every index i, then x would be the zero vector, a contradiction. Thus there must be some coordinate i where x i ≠ 0.
have hne : ∃ i, x i ≠ 0 := by contrapose! hx ext i exact hx i obtain ⟨i, hi⟩ := hne
The sum of squares S = ∑ j, (x j)^2 is strictly positive.
Since x i ≠ 0, its square (x i)^2 is strictly positive by `sq_pos_of_ne_zero`. Each term in the sum is non-negative by `sq_nonneg`, so the single term (x i)^2 is bounded by the total sum via `single_le_sum`. Since (x i)^2 > 0, the sum of squares is strictly positive.
uses
sq_pos_of_ne_zero,single_le_sum,sq_nonneg,mem_univhave hS : 0 < ∑ j, (x j) ^ 2 := by have hi_pos : 0 < (x i) ^ 2 := sq_pos_of_ne_zero hi have hle : (x i) ^ 2 ≤ ∑ j, (x j) ^ 2 := single_le_sum (fun j _ => sq_nonneg (x j)) (mem_univ i) linarith
By Cauchy–Schwarz, (∑ i, x i)^2 ≤ k * ∑ i, (x i)^2.
Applying the Cauchy–Schwarz inequality (`sum_mul_sq_le_sq_mul_sq`) to the vector x and the constant vector 1 on the index set Fin k gives (∑ i, x i * 1)^2 ≤ (∑ i, (x i)^2) * ∑ i, 1^2. The second sum simplifies to the cardinality of Fin k, which is k, establishing (∑ i, x i)^2 ≤ k * ∑ i, (x i)^2.
uses
sum_mul_sq_le_sq_mul_sq,univ,mul_one,one_pow,sum_const,card_univ,Fintype.card_fin,nsmul_eq_mulhave hCS : (∑ i, x i) ^ 2 ≤ (k : ℝ) * ∑ i, (x i) ^ 2 := by have := sum_mul_sq_le_sq_mul_sq (univ : Finset (Fin k)) x (fun _ => (1 : ℝ)) simp only [mul_one, one_pow, sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul] at this linarith
The quadratic form S - (1 / (k + 1)) * C is strictly positive, completing the proof.
Let S = ∑ i, (x i)^2 and C = (∑ i, x i)^2. Since k ≥ 1, the denominator k + 1 is strictly positive. Dividing the Cauchy–Schwarz bound C ≤ k * S by k + 1 gives C / (k + 1) ≤ (k * S) / (k + 1). Because S > 0, we have k * S < S * (k + 1) = k * S + S, so (k * S) / (k + 1) < S. By transitivity, C / (k + 1) < S, which implies S - (1 / (k + 1)) * C > 0.
uses
div_le_div_of_nonneg_right,le_of_lt,div_lt_iff₀set S := ∑ i, (x i) ^ 2 set C := (∑ i, x i) ^ 2 have hk_real : (1 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk have hk1 : 0 < (k : ℝ) + 1 := by linarith have h1 : C / ((k : ℝ) + 1) ≤ ((k : ℝ) * S) / ((k : ℝ) + 1) := div_le_div_of_nonneg_right hCS (le_of_lt hk1) have h2 : (1 / ((k : ℝ) + 1)) * C = C / ((k : ℝ) + 1) := by ring rw [h2] have h3 : ((k : ℝ) * S) / ((k : ℝ) + 1) < S := by rw [div_lt_iff₀ hk1] nlinarith linarith
card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type: |univ| = card(α).
conjTranspose_apply- The (j, i) entry of the conjugate transpose Mᴴ is the conjugate of the (i, j) entry of M.
div_lt_iff₀- For c > 0, b / c < a holds if and only if b < a * c.
div_le_div_of_nonneg_right- If a ≤ b and c ≥ 0, then a / c ≤ b / c.
distinct_subset_sums_root_matrix- The k × k matrix whose (i, j) entry is δ_{ij} - 1/(k + 1).
Fintype.card_fin- The cardinality of the standard finite type Fin n is n.
le_of_lt- Strict inequality implies non-strict inequality: a < b implies a ≤ b.
mem_univ- Every element of a finite type belongs to the universal finset univ.
mul_one- Multiplying by 1 on the right leaves an element unchanged: a * 1 = a.
mul_sub- Multiplication distributes over subtraction on the left: a * (b - c) = a * b - a * c.
Ne.symm- Disequality is symmetric: if a ≠ b, then b ≠ a.
nsmul_eq_mul- Natural number scalar multiplication equals multiplication by the coerced natural number: n • a = ↑n * a.
one_pow- Any power of 1 is 1: 1^n = 1.
PosDef.of_dotProduct_mulVec_pos- A matrix M is positive definite if M is Hermitian and x* ⬝ᵥ (M *ᵥ x) > 0 for all non-zero vectors x.
single_le_sum- A single non-negative term is bounded by the sum over the finset: if each f(x) ≥ 0 and a ∈ s, then f(a) ≤ ∑ x ∈ s, f(x).
sq- The square of an element is its product with itself: a^2 = a * a.
sq_nonneg- In an ordered ring, the square of any element is non-negative: 0 ≤ a^2.
sq_pos_of_ne_zero- If an element is non-zero, its square is strictly positive: a ≠ 0 implies 0 < a^2.
star_trivial- On the real numbers (or any trivial star ring), the star operation is the identity: star r = r.
sub_mul- Multiplication distributes over subtraction on the right: (a - b) * c = a * c - b * c.
sum_const- Summing a constant b over a finset s equals |s| • b.
sum_mul_sq_le_sq_mul_sq- The Cauchy–Schwarz inequality for sums: (∑ i ∈ s, f(i) * g(i))^2 ≤ (∑ i ∈ s, f(i)^2) * ∑ i ∈ s, g(i)^2.
sum_sub_distrib- The sum of a difference of functions equals the difference of their sums.
univ- The finset of all elements of a finite type.
- Routine algebraic manipulations and linear arithmetic inequalities are handled by the `ring`, `linarith`, and `nlinarith` tactics.
- Type casting between natural numbers and real numbers is handled via `exact_mod_cast`.
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.
/-- The root lattice matrix H is positive definite for every k ≥ 1. -/theorem distinct_subset_sums_root_matrix_pos_def (k : ℕ) (hk : 1 ≤ k) : Matrix.PosDef (distinct_subset_sums_root_matrix k) := by open Matrix Finset in refine PosDef.of_dotProduct_mulVec_pos ?_ ?_ · ext i j simp only [conjTranspose_apply, star_trivial, distinct_subset_sums_root_matrix] by_cases h : i = j · subst h; rfl · have h' : j ≠ i := Ne.symm h simp [h, h'] · intro x hx have h_dot : star x ⬝ᵥ (distinct_subset_sums_root_matrix k *ᵥ x) = ∑ i, (x i) ^ 2 - (1 / ((k : ℝ) + 1)) * (∑ i, x i) ^ 2 := by simp only [dotProduct, mulVec, star_trivial, distinct_subset_sums_root_matrix] have h (i : Fin k) : (∑ j, ((if i = j then (1 : ℝ) else 0) - 1 / ((k : ℝ) + 1)) * x j) = x i - (1 / ((k : ℝ) + 1)) * ∑ j, x j := by simp [sub_mul, sum_sub_distrib, ← mul_sum] simp_rw [h] simp only [mul_sub, sum_sub_distrib, ← sum_mul, sq] ring rw [h_dot] have hne : ∃ i, x i ≠ 0 := by contrapose! hx ext i exact hx i obtain ⟨i, hi⟩ := hne have hS : 0 < ∑ j, (x j) ^ 2 := by have hi_pos : 0 < (x i) ^ 2 := sq_pos_of_ne_zero hi have hle : (x i) ^ 2 ≤ ∑ j, (x j) ^ 2 := single_le_sum (fun j _ => sq_nonneg (x j)) (mem_univ i) linarith have hCS : (∑ i, x i) ^ 2 ≤ (k : ℝ) * ∑ i, (x i) ^ 2 := by have := sum_mul_sq_le_sq_mul_sq (univ : Finset (Fin k)) x (fun _ => (1 : ℝ)) simp only [mul_one, one_pow, sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul] at this linarith set S := ∑ i, (x i) ^ 2 set C := (∑ i, x i) ^ 2 have hk_real : (1 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk have hk1 : 0 < (k : ℝ) + 1 := by linarith have h1 : C / ((k : ℝ) + 1) ≤ ((k : ℝ) * S) / ((k : ℝ) + 1) := div_le_div_of_nonneg_right hCS (le_of_lt hk1) have h2 : (1 / ((k : ℝ) + 1)) * C = C / ((k : ℝ) + 1) := by ring rw [h2] have h3 : ((k : ℝ) * S) / ((k : ℝ) + 1) < S := by rw [div_lt_iff₀ hk1] nlinarith linarith