AFTD Auto-Formalizing Theoretical Domains

balanced_blowup_matrix_off_diag

theoremverified

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

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.

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

    lines 8–14

    uses Matrix.one_apply, Matrix.diagonal_apply

      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]
  2. 0 < d as a real number. automation

    From the hypothesis 1 ≤ d, the positivity tactic determines that d is strictly positive in ℝ.

    line 15

      have hd_pos : 0 < (d : ℝ) := by positivity
  3. 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.

    lines 16–23

    uses div_nonpos_of_nonpos_of_nonneg

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

    lines 24–26

    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
  5. -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`.

    lines 27–30

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

    lines 31–33

    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

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