AFTD Auto-Formalizing Theoretical Domains

op223_zmatrix_posdef_of_positive_vector

theoremverified

A real symmetric matrix with nonpositive off-diagonal entries is positive definite if it maps some strictly positive vector to a strictly positive vector.

Statement

theorem op223_zmatrix_posdef_of_positive_vector {ι : Type*} [Fintype ι] [DecidableEq ι]
    (M : Matrix ι ι ℝ) (v : ι → ℝ) (hsym : M.IsSymm)
    (hoff : ∀ i j, i ≠ j → M i j ≤ 0)
    (hv : ∀ i, 0 < v i) (hMv : ∀ i, 0 < (M.mulVec v) i) : M.PosDef
Source
Standard strict diagonal dominance after a positive diagonal scaling.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To show that the real symmetric matrix $M$ is positive definite, it suffices to prove that the quadratic form $x^\\top M x > 0$ for all non-zero real vectors $x$. Introducing the substitution $x_i = v_i w_i$ and the diagonally scaled symmetric matrix $A_{ij} = v_i M_{ij} v_j$, the quadratic form transforms into $\\sum_{i,j} A_{ij} w_i w_j$. Because $A$ has nonpositive off-diagonal entries, expanding $(w_i - w_j)^2 \\ge 0$ yields a key inequality bounding the quadratic form below by the row-sum form $\\sum_i (\\sum_j A_{ij}) w_i^2$. Finally, each row sum $\\sum_j A_{ij}$ equals $v_i (M v)_i > 0$, so this lower bound is a sum of nonnegative terms with at least one strictly positive term, ensuring $x^\\top M x > 0$.

  1. For all $i$ and $j$, $A_{ij} w_i^2 + A_{ij} w_j^2 \\le 2 A_{ij} w_i w_j$.

    We split into cases on whether $i = j$. If $i = j$, both sides simplify to $2 A_{ii} w_i^2$, so equality holds. If $i \\ne j$, the off-diagonal hypothesis gives $A_{ij} \\le 0$, while $(w_i - w_j)^2 \\ge 0$. The product of a nonpositive number and a nonnegative number is nonpositive, so $A_{ij}(w_i - w_j)^2 \\le 0$. Expanding this product yields $A_{ij} w_i^2 - 2 A_{ij} w_i w_j + A_{ij} w_j^2 \\le 0$, which rearranges to the claim.

    lines 5–13

    uses le_rfl, sq_nonneg, mul_nonpos_of_nonpos_of_nonneg

      have hpair : ∀ i j, A i j * (w i)^2 + A i j * (w j)^2 ≤ 2 * (A i j * w i * w j) := by
        intro i j
        by_cases hij : i = j
        · subst j
          ring_nf
          exact le_rfl
        · have hfactor : 0 ≤ (w i - w j)^2 := sq_nonneg _
          have h1 : A i j * (w i - w j)^2 ≤ 0 := mul_nonpos_of_nonpos_of_nonneg (hA i j hij) hfactor
          nlinarith
  2. Summing the pairwise inequality over all $i$ and $j$ yields $\\sum_{i,j} (A_{ij} w_i^2 + A_{ij} w_j^2) \\le \\sum_{i,j} 2 A_{ij} w_i w_j$.

    We sum the inequality from the previous step over all pairs $(i, j)$ using the monotonicity of finite sums.

    lines 14–20

    uses Finset.sum_le_sum

      have hsum : ∑ i, ∑ j, (A i j * (w i)^2 + A i j * (w j)^2)
          ≤ ∑ i, ∑ j, 2 * (A i j * w i * w j) := by
        apply Finset.sum_le_sum
        intro i hi
        apply Finset.sum_le_sum
        intro j hj
        exact hpair i j
  3. Each of the double sums $\\sum_{i, j} A_{ij} w_i^2$ and $\\sum_{i, j} A_{ij} w_j^2$ is equal to $\\sum_i (\\sum_j A_{ij}) w_i^2$.

    For the first sum, factoring $w_i^2$ out of the inner sum over $j$ gives $\\sum_i (\\sum_j A_{ij}) w_i^2$. For the second sum, exchanging the order of summation and renaming indices gives $\\sum_j (\\sum_i A_{ij}) w_j^2$; using the symmetry $A_{ij} = A_{ji}$, this is also $\\sum_i (\\sum_j A_{ij}) w_i^2$.

    lines 21–33

    uses Finset.sum_congr, Finset.sum_mul, Finset.sum_comm

      have hfirst : ∑ i, ∑ j, A i j * (w i)^2 = ∑ i, (∑ j, A i j) * (w i)^2 := by
        apply Finset.sum_congr rfl
        intro i hi
        rw [Finset.sum_mul]
      have hsecond : ∑ i, ∑ j, A i j * (w j)^2 = ∑ i, (∑ j, A i j) * (w i)^2 := by
        rw [Finset.sum_comm]
        apply Finset.sum_congr rfl
        intro k hk
        rw [← Finset.sum_mul]
        congr 1
        apply Finset.sum_congr rfl
        intro i hi
        exact (hsym i k).symm
  4. The row-sum weighted squares are bounded by the quadratic sum: $\\sum_i (\\sum_j A_{ij}) w_i^2 \\le \\sum_{i, j} A_{ij} w_i w_j$.

    Splitting the sum of sums on the left-hand side of the summed inequality into two sums gives $2 \\sum_i (\\sum_j A_{ij}) w_i^2$. Factoring the scalar 2 out of the right-hand side gives $2 \\sum_{i, j} A_{ij} w_i w_j$. Dividing both sides of the inequality by 2 gives the result.

    lines 34–50

    uses Finset.sum_add_distrib, Finset.sum_congr, Finset.mul_sum

      have hL : ∑ i, ∑ j, (A i j * (w i)^2 + A i j * (w j)^2)
          = 2 * (∑ i, (∑ j, A i j) * (w i)^2) := by
        calc
          ∑ i, ∑ j, (A i j * (w i)^2 + A i j * (w j)^2)
              = (∑ i, ∑ j, A i j * (w i)^2) + (∑ i, ∑ j, A i j * (w j)^2) := by
                  simp_rw [Finset.sum_add_distrib]
          _ = (∑ i, (∑ j, A i j) * (w i)^2) + (∑ i, (∑ j, A i j) * (w i)^2) := by
                  rw [hfirst, hsecond]
          _ = 2 * (∑ i, (∑ j, A i j) * (w i)^2) := by ring
      have hR : ∑ i, ∑ j, 2 * (A i j * w i * w j)
          = 2 * (∑ i, ∑ j, A i j * w i * w j) := by
        rw [Finset.mul_sum]
        apply Finset.sum_congr rfl
        intro i hi
        rw [Finset.mul_sum]
      rw [hL, hR] at hsum
      linarith
  5. The matrix $M$ is Hermitian, and to show it is positive definite it suffices to show $x^\\top M x > 0$ for all non-zero real vectors $x$.

    Because $M$ is real and symmetric, it is Hermitian. By definition, a Hermitian matrix is positive definite if the quadratic form $\\langle x, M x\\rangle$ is strictly positive for every non-zero vector $x$. Over $\\mathbb{R}$, complex conjugation is the identity, so $\\operatorname{star} x = x$.

    lines 56–59

    uses Matrix.isHermitian_iff_isSymm.mpr, Matrix.PosDef.of_dotProduct_mulVec_pos

      have hHerm : M.IsHermitian := Matrix.isHermitian_iff_isSymm.mpr hsym
      refine Matrix.PosDef.of_dotProduct_mulVec_pos hHerm ?_
      intro x hx
      rw [show star x = x from funext (fun i => by simp)]
  6. Defining $w_i = x_i / v_i$ implies $v_i w_i = x_i$ for all $i$.

    Since each component $v_i$ is strictly positive, it is non-zero, so clearing the denominator in $w_i = x_i / v_i$ yields $v_i w_i = x_i$.

    lines 60–64

    uses ne_of_gt

      let w : ι → ℝ := fun i => x i / v i
      have hw : ∀ i, v i * w i = x i := by
        intro i
        dsimp [w]
        field_simp [ne_of_gt (hv i)]
  7. The diagonally scaled matrix $A_{ij} = v_i M_{ij} v_j$ is symmetric with nonpositive off-diagonal entries, and satisfies $\\sum_i (\\sum_j A_{ij}) w_i^2 \\le \\sum_{i, j} A_{ij} w_i w_j$.

    Symmetry of $M$ implies $A_{ji} = v_j M_{ji} v_i = v_i M_{ij} v_j = A_{ij}$. Since $v_i, v_j > 0$ and $M_{ij} \\le 0$ for $i \\ne j$, the product $A_{ij} = v_i M_{ij} v_j$ is nonpositive off the diagonal. Applying the helper lemma to $A$ and $w$ yields the inequality.

    lines 65–76

    uses mul_nonpos_of_nonneg_of_nonpos, mul_nonpos_of_nonpos_of_nonneg, op223_zmatrix_posdef_of_positive_vector_sum_ineq

      let A : ι → ι → ℝ := fun i j => v i * M i j * v j
      have hAsym : ∀ i j, A j i = A i j := by
        intro i j
        dsimp [A]
        rw [hsym.apply i j]
        ring
      have hAoff : ∀ i j, i ≠ j → A i j ≤ 0 := by
        intro i j hij
        dsimp [A]
        have h1 : v i * M i j ≤ 0 := mul_nonpos_of_nonneg_of_nonpos (hv i).le (hoff i j hij)
        exact mul_nonpos_of_nonpos_of_nonneg h1 (hv j).le
      have hineq := op223_zmatrix_posdef_of_positive_vector_sum_ineq A hAsym hAoff w
  8. For each row $i$, the sum $\\sum_j A_{ij}$ equals $v_i (M v)_i$.

    Substituting the definition of $A_{ij}$ into the sum gives $\\sum_j v_i M_{ij} v_j$. Factoring out $v_i$ leaves $\\sum_j M_{ij} v_j$, which is the $i$-th entry of the matrix-vector product $M v$.

    lines 77–85

    uses Matrix.mulVec_apply, Matrix.row_apply, Finset.mul_sum, Finset.sum_congr

      have hrow : ∀ i, (∑ j, A i j) = v i * (M.mulVec v) i := by
        intro i
        dsimp [A]
        rw [Matrix.mulVec_apply]
        simp only [dotProduct, Matrix.row_apply]
        rw [Finset.mul_sum]
        apply Finset.sum_congr rfl
        intro j hj
        ring
  9. The row-sum weighted square sum $\\sum_i (\\sum_j A_{ij}) w_i^2$ is strictly positive.

    Rewriting each $\\sum_j A_{ij}$ as $v_i (M v)_i$, every term $v_i (M v)_i w_i^2$ is nonnegative since $v_i > 0$, $(M v)_i > 0$, and squares are nonnegative. Since $x \\ne 0$, there is some coordinate $k$ where $x_k \\ne 0$, which implies $w_k = x_k / v_k \\ne 0$ and hence $w_k^2 > 0$. Thus the $k$-th term is strictly positive, making the entire sum strictly positive.

    lines 86–94

    uses Finset.sum_pos', mul_nonneg, mul_pos, sq_nonneg, Function.ne_iff.mp, Finset.mem_univ, sq_pos_of_ne_zero, div_ne_zero, ne_of_gt

      have hSpos : 0 < ∑ i, (∑ j, A i j) * (w i)^2 := by
        simp_rw [hrow]
        apply Finset.sum_pos'
        · intro i hi
          exact mul_nonneg (mul_pos (hv i) (hMv i)).le (sq_nonneg (w i))
        · obtain ⟨k, hk⟩ := Function.ne_iff.mp hx
          refine ⟨k, Finset.mem_univ k, ?_⟩
          exact mul_pos (mul_pos (hv k) (hMv k))
            (sq_pos_of_ne_zero (div_ne_zero hk (ne_of_gt (hv k))))
  10. The quadratic form $x^\\top M x$ equals $\\sum_{i, j} A_{ij} w_i w_j$.

    Expanding the dot product and matrix-vector product expresses $x^\\top M x$ as $\\sum_{i, j} M_{ij} x_i x_j$. Substituting $x_i = v_i w_i$ and $x_j = v_j w_j$ converts this to $\\sum_{i, j} (v_i M_{ij} v_j) w_i w_j = \\sum_{i, j} A_{ij} w_i w_j$.

    lines 95–106

    uses Finset.sum_congr, Matrix.mulVec_apply, Matrix.row_apply, Finset.mul_sum

      have hquad : x ⬝ᵥ M.mulVec x = ∑ i, ∑ j, A i j * w i * w j := by
        simp only [dotProduct]
        apply Finset.sum_congr rfl
        intro i hi
        rw [Matrix.mulVec_apply]
        simp only [dotProduct, Matrix.row_apply]
        rw [Finset.mul_sum]
        apply Finset.sum_congr rfl
        intro j hj
        rw [← hw i, ← hw j]
        dsimp [A]
        ring
  11. The quadratic form $x^\\top M x$ is strictly positive, completing the proof.

    Chaining the strict inequality and the two relations gives $0 < \\sum_i (\\sum_j A_{ij}) w_i^2 \\le \\sum_{i, j} A_{ij} w_i w_j = x^\\top M x$.

    lines 107–110

      calc
        0 < ∑ i, (∑ j, A i j) * (w i)^2 := hSpos
        _ ≤ ∑ i, ∑ j, A i j * w i * w j := hineq
        _ = x ⬝ᵥ M.mulVec x := hquad.symm
le_rfl
In any preorder, every element is less than or equal to itself ($a \\le a$).
sq_nonneg
The square of any element in an ordered semiring is nonnegative ($a^2 \\ge 0$).
mul_nonpos_of_nonpos_of_nonneg
The product of a nonpositive number and a nonnegative number is nonpositive.
Finset.sum_le_sum
If $f(i) \\le g(i)$ for all $i$ in a finite set $s$, then $\\sum_{i \\in s} f(i) \\le \\sum_{i \\in s} g(i)$.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on all elements.
Finset.sum_mul
Right multiplication distributes over finite sums: $(\\sum_{i \\in s} f(i)) \\cdot a = \\sum_{i \\in s} (f(i) \\cdot a)$.
Finset.sum_comm
Finite double sums can be evaluated in either order: $\\sum_{x \\in s} \\sum_{y \\in t} f(x, y) = \\sum_{y \\in t} \\sum_{x \\in s} f(x, y)$.
Finset.sum_add_distrib
The sum of a sum of functions over a finite set equals the sum of their individual sums: $\\sum_{x \\in s} (f(x) + g(x)) = \\sum_{x \\in s} f(x) + \\sum_{x \\in s} g(x)$.
Finset.mul_sum
Left multiplication distributes over finite sums: $a \\cdot \\sum_{i \\in s} f(i) = \\sum_{i \\in s} (a \\cdot f(i))$.
Matrix.isHermitian_iff_isSymm.mpr
A real matrix is Hermitian if it is symmetric.
Matrix.PosDef.of_dotProduct_mulVec_pos
A Hermitian matrix $M$ is positive definite if $x^* M x > 0$ for every non-zero vector $x$.
ne_of_gt
If $b < a$, then $a \\ne b$.
mul_nonpos_of_nonneg_of_nonpos
The product of a nonnegative number and a nonpositive number is nonpositive.
op223_zmatrix_posdef_of_positive_vector_sum_ineq
For any real symmetric matrix $A$ with nonpositive off-diagonal entries and any vector $w$, $\\sum_i (\\sum_j A_{ij}) w_i^2 \\le \\sum_{i, j} A_{ij} w_i w_j$.
Matrix.mulVec_apply
The $i$-th entry of the matrix-vector product $M v$ is the dot product of the $i$-th row of $M$ with $v$.
Matrix.row_apply
The $j$-th component of the $i$-th row of $A$ is the matrix entry $A_{ij}$.
Finset.sum_pos'
A finite sum of nonnegative terms is strictly positive if at least one term is strictly positive.
mul_nonneg
The product of two nonnegative numbers is nonnegative.
mul_pos
The product of two strictly positive numbers is strictly positive.
Function.ne_iff.mp
If two functions are not equal, there exists an input at which they differ.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `univ`.
sq_pos_of_ne_zero
The square of any non-zero element in a strictly ordered ring is strictly positive.
div_ne_zero
If $a \\ne 0$ and $b \\ne 0$, then $a / b \\ne 0$.

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

private lemma op223_zmatrix_posdef_of_positive_vector_sum_ineq {ι : Type*} [Fintype ι]    (A : ι → ι → ℝ) (hsym : ∀ i j, A j i = A i j)    (hA : ∀ i j, i ≠ j → A i j ≤ 0) (w : ι → ℝ) :    ∑ i, (∑ j, A i j) * (w i)^2 ≤ ∑ i, ∑ j, A i j * w i * w j := by  have hpair : ∀ i j, A i j * (w i)^2 + A i j * (w j)^2 ≤ 2 * (A i j * w i * w j) := by    intro i j    by_cases hij : i = j    · subst j      ring_nf      exact le_rfl    · have hfactor : 0 ≤ (w i - w j)^2 := sq_nonneg _      have h1 : A i j * (w i - w j)^2 ≤ 0 := mul_nonpos_of_nonpos_of_nonneg (hA i j hij) hfactor      nlinarith  have hsum : ∑ i, ∑ j, (A i j * (w i)^2 + A i j * (w j)^2)      ≤ ∑ i, ∑ j, 2 * (A i j * w i * w j) := by    apply Finset.sum_le_sum    intro i hi    apply Finset.sum_le_sum    intro j hj    exact hpair i j  have hfirst : ∑ i, ∑ j, A i j * (w i)^2 = ∑ i, (∑ j, A i j) * (w i)^2 := by    apply Finset.sum_congr rfl    intro i hi    rw [Finset.sum_mul]  have hsecond : ∑ i, ∑ j, A i j * (w j)^2 = ∑ i, (∑ j, A i j) * (w i)^2 := by    rw [Finset.sum_comm]    apply Finset.sum_congr rfl    intro k hk    rw [← Finset.sum_mul]    congr 1    apply Finset.sum_congr rfl    intro i hi    exact (hsym i k).symm  have hL : ∑ i, ∑ j, (A i j * (w i)^2 + A i j * (w j)^2)      = 2 * (∑ i, (∑ j, A i j) * (w i)^2) := by    calc      ∑ i, ∑ j, (A i j * (w i)^2 + A i j * (w j)^2)          = (∑ i, ∑ j, A i j * (w i)^2) + (∑ i, ∑ j, A i j * (w j)^2) := by              simp_rw [Finset.sum_add_distrib]      _ = (∑ i, (∑ j, A i j) * (w i)^2) + (∑ i, (∑ j, A i j) * (w i)^2) := by              rw [hfirst, hsecond]      _ = 2 * (∑ i, (∑ j, A i j) * (w i)^2) := by ring  have hR : ∑ i, ∑ j, 2 * (A i j * w i * w j)      = 2 * (∑ i, ∑ j, A i j * w i * w j) := by    rw [Finset.mul_sum]    apply Finset.sum_congr rfl    intro i hi    rw [Finset.mul_sum]  rw [hL, hR] at hsum  linariththeorem op223_zmatrix_posdef_of_positive_vector {ι : Type*} [Fintype ι] [DecidableEq ι]    (M : Matrix ι ι ℝ) (v : ι → ℝ) (hsym : M.IsSymm)    (hoff : ∀ i j, i ≠ j → M i j ≤ 0)    (hv : ∀ i, 0 < v i) (hMv : ∀ i, 0 < (M.mulVec v) i) : M.PosDef := by  have hHerm : M.IsHermitian := Matrix.isHermitian_iff_isSymm.mpr hsym  refine Matrix.PosDef.of_dotProduct_mulVec_pos hHerm ?_  intro x hx  rw [show star x = x from funext (fun i => by simp)]  let w : ι → ℝ := fun i => x i / v i  have hw : ∀ i, v i * w i = x i := by    intro i    dsimp [w]    field_simp [ne_of_gt (hv i)]  let A : ι → ι → ℝ := fun i j => v i * M i j * v j  have hAsym : ∀ i j, A j i = A i j := by    intro i j    dsimp [A]    rw [hsym.apply i j]    ring  have hAoff : ∀ i j, i ≠ j → A i j ≤ 0 := by    intro i j hij    dsimp [A]    have h1 : v i * M i j ≤ 0 := mul_nonpos_of_nonneg_of_nonpos (hv i).le (hoff i j hij)    exact mul_nonpos_of_nonpos_of_nonneg h1 (hv j).le  have hineq := op223_zmatrix_posdef_of_positive_vector_sum_ineq A hAsym hAoff w  have hrow : ∀ i, (∑ j, A i j) = v i * (M.mulVec v) i := by    intro i    dsimp [A]    rw [Matrix.mulVec_apply]    simp only [dotProduct, Matrix.row_apply]    rw [Finset.mul_sum]    apply Finset.sum_congr rfl    intro j hj    ring  have hSpos : 0 < ∑ i, (∑ j, A i j) * (w i)^2 := by    simp_rw [hrow]    apply Finset.sum_pos'    · intro i hi      exact mul_nonneg (mul_pos (hv i) (hMv i)).le (sq_nonneg (w i))    · obtain ⟨k, hk⟩ := Function.ne_iff.mp hx      refine ⟨k, Finset.mem_univ k, ?_⟩      exact mul_pos (mul_pos (hv k) (hMv k))        (sq_pos_of_ne_zero (div_ne_zero hk (ne_of_gt (hv k))))  have hquad : x ⬝ᵥ M.mulVec x = ∑ i, ∑ j, A i j * w i * w j := by    simp only [dotProduct]    apply Finset.sum_congr rfl    intro i hi    rw [Matrix.mulVec_apply]    simp only [dotProduct, Matrix.row_apply]    rw [Finset.mul_sum]    apply Finset.sum_congr rfl    intro j hj    rw [← hw i, ← hw j]    dsimp [A]    ring  calc    0 < ∑ i, (∑ j, A i j) * (w i)^2 := hSpos    _ ≤ ∑ i, ∑ j, A i j * w i * w j := hineq    _ = x ⬝ᵥ M.mulVec x := hquad.symm
See it in the graphDiscuss this resultChallenge it