op223_zmatrix_posdef_of_positive_vector
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$.
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.
uses
le_rfl,sq_nonneg,mul_nonpos_of_nonpos_of_nonneghave 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
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.
uses
Finset.sum_le_sumhave 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
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$.
uses
Finset.sum_congr,Finset.sum_mul,Finset.sum_commhave 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
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.
uses
Finset.sum_add_distrib,Finset.sum_congr,Finset.mul_sumhave 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
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$.
uses
Matrix.isHermitian_iff_isSymm.mpr,Matrix.PosDef.of_dotProduct_mulVec_poshave 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)]
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$.
uses
ne_of_gtlet 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)]
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.
uses
mul_nonpos_of_nonneg_of_nonpos,mul_nonpos_of_nonpos_of_nonneg,op223_zmatrix_posdef_of_positive_vector_sum_ineqlet 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
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$.
uses
Matrix.mulVec_apply,Matrix.row_apply,Finset.mul_sum,Finset.sum_congrhave 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
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.
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_gthave 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))))
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$.
uses
Finset.sum_congr,Matrix.mulVec_apply,Matrix.row_apply,Finset.mul_sumhave 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
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$.
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
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.
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