AFTD Auto-Formalizing Theoretical Domains

root_lattice_form_pos_def

theoremverified

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.

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

    lines 3–6

    uses Matrix.PosDef.of_dotProduct_mulVec_pos, Matrix.IsHermitian.ext, Matrix.sub_apply, Matrix.one_apply, Matrix.of_apply, eq_comm

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

    lines 7–13

      · intro x hx
        by_cases hk : k = 0
        · subst k
          exfalso
          apply hx
          funext i
          exact i.elim0
  3. 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).

    lines 14–24

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

    lines 25–35

    uses dotProduct, star_trivial, mul_sub, Finset.sum_sub_distrib, pow_two, Finset.sum_mul

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

    lines 36–37

    uses sq_sum_le_card_mul_sum_sq, Finset.univ

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

    lines 38–47

    uses Finset.sum_pos', sq_nonneg, Finset.mem_univ, sq_pos_of_ne_zero

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

    lines 48–55

    uses mul_le_mul_of_nonneg_left

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

    lines 56–61

          have hcoef : 0 < (1 : ℝ) - (k : ℝ) / ((k : ℝ) + 1) := by
            have h : (1 : ℝ) - (k : ℝ) / ((k : ℝ) + 1) = 1 / ((k : ℝ) + 1) := by
              field_simp
              ring
            rw [h]
            positivity
  9. 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.

    line 62

    uses mul_pos

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

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

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