balanced_blowup_matrix_off_diag
For natural numbers m and d with 1 ≤ m and 1 ≤ d, and an m x m real matrix L on Fin m with off-diagonal entries in [-1/m, 0], all off-diagonal entries of balanced_blowup_matrix m d L lie in [-1/(m*d), 0].
Statement
theorem balanced_blowup_matrix_off_diag (m d : ℕ) (hm : 1 ≤ m) (hd : 1 ≤ d)
(L : Matrix (Fin m) (Fin m) ℝ)
(hL : ∀ i j : Fin m, i ≠ j → -(1 : ℝ) / m ≤ L i j ∧ L i j ≤ 0)
(i j : Fin m) (s t : Fin d) (hne : (i, s) ≠ (j, t)) :
-(1 : ℝ) / (m * d) ≤ balanced_blowup_matrix m d L (i, s) (j, t) ∧
balanced_blowup_matrix m d L (i, s) (j, t) ≤ 0- Source
- scout/2610-14100-digraph-laplacian-spectra-the-2005-polygon-conjecture-fails.md:1049
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- balanced_blowup_matrixFor natural numbers m and d, and an m x m real matrix L on Fin m, balanced_blowup_matrix m d L is the real matrix on Fin m × Fin d defined…
- Used by 1
- standardized_laplacian_spectra_subset_of_dvdLet m, n ≥ 2 be natural numbers such that m divides n. Then the set of eigenvalues of standardized Laplacian matrices of order m is a…
Read back from the Lean
For any natural numbers $m, d \ge 1$, any $m \times m$ real matrix $L$ such that all off-diagonal entries satisfy $-\frac{1}{m} \le L_{i,j} \le 0$ (for all $i \neq j$ in $\mathrm{Fin}(m)$), and any two pairs of indices $(i, s) \neq (j, t)$ in $\mathrm{Fin}(m) \times \mathrm{Fin}(d)$, the $((i, s), (j, t))$ entry of $\mathrm{balanced\_blowup\_matrix}(m, d, L)$ satisfies $$-\frac{1}{m \cdot d} \le \mathrm{balanced\_blowup\_matrix}(m, d, L)_{(i, s), (j, t)} \le 0.$$
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 proof computes the entry of the balanced blow-up matrix at ((i, s), (j, t)) from its definition as a difference of Kronecker products, and splits into cases on whether i = j or i ≠ j. When i = j, the off-diagonal condition (i, s) ≠ (j, t) forces s ≠ t, causing both terms to vanish and the entry to be 0, which trivially falls in [-1/(m*d), 0]. When i ≠ j, the entry simplifies to (1/d) * L i j; dividing the assumed bounds -1/m ≤ L i j ≤ 0 by d > 0 then yields the required bounds -1/(m*d) ≤ (1/d) * L i j ≤ 0.
The entry of the balanced blow-up matrix at index ((i, s), (j, t)) is explicitly (if i = j then L i i else 0) * (if s = t then 1 else 0) - (1 / d) * (if i = j then 0 else -L i j), reducing the goal to bounding this expression in [-1/(m*d), 0].
Unfolding the definition of `balanced_blowup_matrix` expresses it as the Kronecker product D ⊗ I minus (1 / d) • (A ⊗ J), where D is the diagonal part of L, I is the identity matrix, A contains the negated off-diagonal entries of L, and J is the all-ones matrix. Evaluating the entries using the characterizations of the identity matrix (`Matrix.one_apply`) and diagonal matrices (`Matrix.diagonal_apply`) establishes this explicit formula (`h_entry`), which is then substituted into the goal.
uses
Matrix.one_apply,Matrix.diagonal_applyhave h_entry : balanced_blowup_matrix m d L (i, s) (j, t) = (if i = j then L i i else 0) * (if s = t then 1 else 0) - (1 / (d : ℝ)) * (if i = j then 0 else - L i j) := by unfold balanced_blowup_matrix simp [Matrix.one_apply, Matrix.diagonal_apply] rw [h_entry]
0 < d as a real number. automation
From the hypothesis 1 ≤ d, the positivity tactic determines that d is strictly positive in ℝ.
have hd_pos : 0 < (d : ℝ) := by positivity
The matrix entry lies in [-1/(m*d), 0] in the case where i = j.
We split into cases on whether i = j. When i = j, the condition (i, s) ≠ (j, t) implies s ≠ t. Substituting i = j and s ≠ t into the entry formula makes both terms vanish: the identity factor is 0 because s ≠ t, and the off-diagonal factor is 0 because i = j. Hence the matrix entry simplifies to 0, which trivially satisfies 0 ≤ 0. The lower bound -1/(m*d) ≤ 0 then follows via `div_nonpos_of_nonpos_of_nonneg` since -1 ≤ 0 and m * d ≥ 0.
uses
div_nonpos_of_nonpos_of_nonnegby_cases hij : i = j · subst hij have hst : s ≠ t := by intro h apply hne rw [h] simp [hst] exact div_nonpos_of_nonpos_of_nonneg (by linarith) (by positivity)
In the case where i ≠ j, the matrix entry simplifies to (1 / d) * L i j, and it suffices to show -1/(m*d) ≤ (1 / d) * L i j and (1 / d) * L i j ≤ 0.
When i ≠ j, the diagonal term vanishes and the subtracted term simplifies from 0 - (1 / d) * (-L i j) to (1 / d) * L i j. The hypothesis hL on off-diagonal entries guarantees -1/m ≤ L i j ≤ 0. Splitting the goal with `constructor` leaves two inequalities to verify: the lower bound and the upper bound.
uses
MulZeroClass.zero_mul,zero_sub,mul_neg,neg_neg· simp only [hij, ↓reduceIte, MulZeroClass.zero_mul, zero_sub, mul_neg, neg_neg] have hL_ij := hL i j hij constructor
-1/(m*d) ≤ (1 / d) * L i j.
Using `div_div`, the left-hand side -1/(m*d) is rewritten as (-1/m)/d. After rewriting (1 / d) * L i j as L i j / d, the inequality (-1/m)/d ≤ L i j / d follows from the known bound -1/m ≤ L i j by dividing by d ≥ 0 using `div_le_div_of_nonneg_right` and `le_of_lt`.
uses
div_div,div_le_div_of_nonneg_right,le_of_lt· rw [← div_div] have : 1 / (d : ℝ) * L i j = L i j / d := by ring rw [this] exact div_le_div_of_nonneg_right hL_ij.1 (le_of_lt hd_pos)
(1 / d) * L i j ≤ 0.
Rewriting (1 / d) * L i j as L i j / d, the non-positivity follows directly from L i j ≤ 0 and d ≥ 0 via `div_nonpos_of_nonpos_of_nonneg` and `le_of_lt`.
uses
div_nonpos_of_nonpos_of_nonneg,le_of_lt· have : 1 / (d : ℝ) * L i j = L i j / d := by ring rw [this] exact div_nonpos_of_nonpos_of_nonneg hL_ij.2 (le_of_lt hd_pos)
Matrix.one_apply- An entry of the identity matrix is 1 on the diagonal (i = j) and 0 off the diagonal (i ≠ j).
Matrix.diagonal_apply- An entry of a diagonal matrix is given by the diagonal function when the row and column indices match, and 0 otherwise.
div_nonpos_of_nonpos_of_nonneg- Dividing a non-positive number by a non-negative number yields a non-positive number.
MulZeroClass.zero_mul- Zero multiplied by any element is zero.
zero_sub- Subtracting an element from zero gives its negation.
mul_neg- Multiplying an element by the negation of another gives the negation of the product.
neg_neg- The negation of the negation of an element is the element itself.
div_div- Dividing by b and then by c is equivalent to dividing by the product b * c.
div_le_div_of_nonneg_right- Dividing both sides of an inequality a ≤ b by a non-negative number c preserves the inequality: a / c ≤ b / c.
le_of_lt- A strict inequality a < b implies the non-strict inequality 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
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 off-diagonal entries of the balanced blow-up matrix lie in [-1/(m*d), 0]. -/theorem balanced_blowup_matrix_off_diag (m d : ℕ) (hm : 1 ≤ m) (hd : 1 ≤ d) (L : Matrix (Fin m) (Fin m) ℝ) (hL : ∀ i j : Fin m, i ≠ j → -(1 : ℝ) / m ≤ L i j ∧ L i j ≤ 0) (i j : Fin m) (s t : Fin d) (hne : (i, s) ≠ (j, t)) : -(1 : ℝ) / (m * d) ≤ balanced_blowup_matrix m d L (i, s) (j, t) ∧ balanced_blowup_matrix m d L (i, s) (j, t) ≤ 0 := by have h_entry : balanced_blowup_matrix m d L (i, s) (j, t) = (if i = j then L i i else 0) * (if s = t then 1 else 0) - (1 / (d : ℝ)) * (if i = j then 0 else - L i j) := by unfold balanced_blowup_matrix simp [Matrix.one_apply, Matrix.diagonal_apply] rw [h_entry] have hd_pos : 0 < (d : ℝ) := by positivity by_cases hij : i = j · subst hij have hst : s ≠ t := by intro h apply hne rw [h] simp [hst] exact div_nonpos_of_nonpos_of_nonneg (by linarith) (by positivity) · simp only [hij, ↓reduceIte, MulZeroClass.zero_mul, zero_sub, mul_neg, neg_neg] have hL_ij := hL i j hij constructor · rw [← div_div] have : 1 / (d : ℝ) * L i j = L i j / d := by ring rw [this] exact div_le_div_of_nonneg_right hL_ij.1 (le_of_lt hd_pos) · have : 1 / (d : ℝ) * L i j = L i j / d := by ring rw [this] exact div_nonpos_of_nonpos_of_nonneg hL_ij.2 (le_of_lt hd_pos)