standardized_laplacian_order_four_diagonal_lt_one
Every diagonal entry of an order-four standardized Laplacian is less than one.
Statement
theorem standardized_laplacian_order_four_diagonal_lt_one (L : Matrix (Fin 4) (Fin 4) ℝ)
(hL : is_standardized_laplacian 4 L) (i : Fin 4) : L i i < 1- Source
- Sector-bound formalization for IN-166; arXiv:math/0508176, Theorem 5.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_standardized_laplacianA standardized Laplacian matrix of order n is a real n x n matrix with zero row sums and off-diagonal entries in [-1/n, 0].
- Used by 1
- standardized_laplacian_order_four_perturbation_stationaryEvery positive centered scalar shift of an order-four standardized Laplacian has a strictly positive left null vector.
The proof, explained
The proof uses the two defining conditions of an order-four standardized Laplacian: the row sums are zero, and every off-diagonal entry is at least $-1/4$. Summing this lower bound across the three off-diagonal entries in row $i$ shows that their sum is at least $3 \times (-1/4) = -3/4$. Because the diagonal entry $L_{i, i}$ plus the off-diagonal entries sum to zero, $L_{i, i} \le 3/4$, which is strictly less than $1$.
The $i$-th row sums to 0, and splits into the diagonal entry $L_{i, i}$ and the sum of the off-diagonal entries $\sum_{j \ne i} L_{i, j}$.
By the definition of a standardized Laplacian, the sum of all entries in row $i$ is zero. Using `Finset.add_sum_erase` and `Finset.mem_univ`, the full row sum is separated into the diagonal term $L_{i, i}$ and the sum over all remaining indices $j \in \mathrm{univ} \setminus \{i\}$.
uses
Finset.add_sum_erase,Finset.mem_univhave hrow := hL.1 i have hsplit := Finset.add_sum_erase Finset.univ (fun j => L i j) (Finset.mem_univ i)
Every off-diagonal entry $L_{i, j}$ with $j \ne i$ is at least $-1/4$.
For any index $j \in \mathrm{univ} \setminus \{i\}$, `Finset.ne_of_mem_erase` ensures $j \ne i$, so $i \ne j$. The second defining condition of an order-four standardized Laplacian then provides the lower bound $-(1/4) \le L_{i, j}$.
uses
Finset.ne_of_mem_erasehave hbound : ∀ j ∈ Finset.univ.erase i, -(1 : ℝ) / 4 ≤ L i j := by intro j hj exact (hL.2 i j (Finset.ne_of_mem_erase hj).symm).1
The sum of the constant lower bounds $-1/4$ is at most the sum of the off-diagonal entries $\sum_{j \ne i} L_{i, j}$.
Summing the pointwise inequality $-(1/4) \le L_{i, j}$ over all off-diagonal indices using `Finset.sum_le_sum` yields $\sum_{j \ne i} (-1/4) \le \sum_{j \ne i} L_{i, j}$.
uses
Finset.sum_le_sumhave hsum := Finset.sum_le_sum hboundThe sum of the off-diagonal entries is at least $-3/4$.
Erasing one index from the 4-element universe leaves a set of cardinality 3. Rewriting the constant sum using `Finset.sum_const` and `nsmul_eq_mul` gives $3 \cdot (-1/4)$, which evaluates to $-3/4$ via `norm_num`. Substituting this constant sum into the off-diagonal inequality yields $-3/4 \le \sum_{j \ne i} L_{i, j}$.
uses
Finset.sum_const,nsmul_eq_mulhave hcard : (Finset.univ.erase i).card = 3 := by simp have hconst : (∑ _j ∈ Finset.univ.erase i, -(1 : ℝ) / 4) = -(3 : ℝ) / 4 := by rw [Finset.sum_const, hcard, nsmul_eq_mul] norm_num rw [hconst] at hsum
The diagonal entry $L_{i, i}$ is strictly less than 1. automation
Since $L_{i, i} + \sum_{j \ne i} L_{i, j} = 0$ and $\sum_{j \ne i} L_{i, j} \ge -3/4$, it follows that $L_{i, i} \le 3/4 < 1$. Linear arithmetic (`linarith`) combines these inequalities to close the goal.
linarith
Finset.add_sum_erase- For a finite set $s$ and an element $a \in s$, the sum of a function $f$ over $s$ equals $f(a)$ plus the sum of $f$ over $s \setminus \{a\}$.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set `Finset.univ`.
Finset.ne_of_mem_erase- An element belonging to a set with $a$ erased is not equal to $a$.
Finset.sum_le_sum- If $f(x) \le g(x)$ for all $x \in s$, then the sum of $f$ over $s$ is at most the sum of $g$ over $s$.
Finset.sum_const- Summing a constant value $b$ over a finite set $s$ is equivalent to multiplying $b$ by the cardinality of $s$.
nsmul_eq_mul- Natural number scalar multiplication $n \bullet a$ equals the ring product $(\uparrow n) \cdot a$.
- The cardinality of the set of off-diagonal indices is computed automatically by `simp` from the size of `Fin 4`, and the final inequality is deduced via linear arithmetic automation (`linarith`).
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 standardized_laplacian_order_four_diagonal_lt_one (L : Matrix (Fin 4) (Fin 4) ℝ) (hL : is_standardized_laplacian 4 L) (i : Fin 4) : L i i < 1 := by have hrow := hL.1 i have hsplit := Finset.add_sum_erase Finset.univ (fun j => L i j) (Finset.mem_univ i) have hbound : ∀ j ∈ Finset.univ.erase i, -(1 : ℝ) / 4 ≤ L i j := by intro j hj exact (hL.2 i j (Finset.ne_of_mem_erase hj).symm).1 have hsum := Finset.sum_le_sum hbound have hcard : (Finset.univ.erase i).card = 3 := by simp have hconst : (∑ _j ∈ Finset.univ.erase i, -(1 : ℝ) / 4) = -(3 : ℝ) / 4 := by rw [Finset.sum_const, hcard, nsmul_eq_mul] norm_num rw [hconst] at hsum linarith