AFTD Auto-Formalizing Theoretical Domains

balanced_blowup_matrix_row_sum

theoremverified

For natural numbers m and d with 1 ≤ d, and an m x m real matrix L on Fin m with zero row sums, each row of the balanced blow-up matrix balanced_blowup_matrix m d L sums to zero.

Statement

theorem balanced_blowup_matrix_row_sum (m d : ℕ) (hd : 1 ≤ d) (L : Matrix (Fin m) (Fin m) ℝ)
    (hL : ∀ i : Fin m, ∑ j : Fin m, L i j = 0) (i : Fin m) (s : Fin d) :
    ∑ j : Fin m, ∑ t : Fin d, 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 all natural numbers $m$ and $d$ with $1 \le d$, and any $m \times m$ real matrix $L$ such that every row of $L$ sums to 0 (i.e., for every row index $i$, $\sum_{j=0}^{m-1} L_{i,j} = 0$), and for any row indices $i \in \mathrm{Fin}(m)$ and $s \in \mathrm{Fin}(d)$, the sum over all $j \in \mathrm{Fin}(m)$ and $t \in \mathrm{Fin}(d)$ of the $((i, s), (j, t))$ entry of the balanced blowup matrix of $L$ is equal to 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 row sum of the balanced blow-up matrix splits by linearity into the sum over the diagonal Kronecker block D ⊗ I_d minus the sum over the scaled off-diagonal Kronecker block (1 / d) • (A ⊗ J_d). The first sum collapses to L i i because only the single diagonal entry where j = i and t = s is non-zero. The second sum is independent of the index t, producing a factor of d that cancels the scalar 1 / d; the remaining sum over the off-diagonal entries equals L i i because the rows of L sum to zero. Subtracting the two sums leaves L i i - L i i = 0.

  1. d ≠ 0 when coerced to the real numbers.

    Since 1 ≤ d by assumption, d is strictly positive and therefore non-zero, which is verified by linear integer arithmetic after casting to ℝ.

    lines 5–7

      have hd_pos : (d : ℝ) ≠ 0 := by
        norm_cast
        omega
  2. The ((i, s), (j, t))-th entry of the balanced blow-up matrix is given by (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).

    Unfolding the definition of the balanced blow-up matrix B = D ⊗ I_d - (1 / d) • (A ⊗ J_d), where D is the diagonal part of L, I_d is the identity matrix, A is the off-diagonal part of -L, and J_d is the all-ones matrix. Evaluating the entries of the Kronecker products using Matrix.one_apply and Matrix.diagonal_apply yields this explicit formula.

    lines 8–13

    uses Matrix.one_apply, Matrix.diagonal_apply

      have h_entry (j : Fin m) (t : Fin d) :
          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]
  3. The total row sum decomposes into the difference of two double sums: the sum over the diagonal term minus the sum over the scaled off-diagonal term.

    Rewriting the summand using the entry formula h_entry and distributing the summation over subtraction using Finset.sum_sub_distrib.

    line 14

    uses Finset.sum_sub_distrib

      simp_rw [h_entry, Finset.sum_sub_distrib]
  4. The first double sum ∑ j, ∑ t, (if i = j then L i i else 0) * (if s = t then 1 else 0) equals L i i.

    In the double sum over j and t, only the single index pair j = i and t = s satisfies both conditions and yields a non-zero term, which evaluates to L i i * 1 = L i i.

    lines 15–16

      have h1 : (∑ j : Fin m, ∑ t : Fin d, (if i = j then L i i else 0) * (if s = t then 1 else 0 : ℝ)) = L i i := by
        simp
  5. The second double sum ∑ j, ∑ t, (1 / d) * (if i = j then 0 else -L i j) equals L i i.

    Because the summand does not depend on t, summing over Fin d multiplies the term by d (Finset.sum_const, Finset.card_univ, Fintype.card_fin). The factor of d cancels 1 / d (nsmul_eq_mul, mul_assoc, mul_one_div_cancel, one_mul). Next, the conditional expression for the off-diagonal entry is rewritten algebraically as (if i = j then L i i else 0) - L i j by case analysis on whether i = j. Distributing the sum over subtraction (Finset.sum_sub_distrib), the sum ∑ j, L i j vanishes by the zero row-sum hypothesis hL, leaving only the indicator sum which equals L i i.

    lines 17–27

    uses Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul, mul_assoc, mul_one_div_cancel, one_mul, Finset.sum_sub_distrib

      have h2 : (∑ j : Fin m, ∑ _t : Fin d, (1 / (d : ℝ)) * (if i = j then 0 else - L i j)) = L i i := by
        simp_rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin]
        have hd_mul (x : ℝ) : d • (1 / (d : ℝ) * x) = x := by
          rw [nsmul_eq_mul, ← mul_assoc, mul_one_div_cancel hd_pos, one_mul]
        simp_rw [hd_mul]
        have h (j : Fin m) : (if i = j then (0 : ℝ) else - L i j) = (if i = j then L i i else 0) - L i j := by
          split_ifs with hij
          · subst hij; ring
          · ring
        simp_rw [h, Finset.sum_sub_distrib]
        simp [hL i]
  6. The row sum of the balanced blow-up matrix is zero.

    Substituting the computed values L i i from h1 and h2 for the two double sums reduces the row sum to L i i - L i i, which equals 0 by sub_self.

    line 28

    uses sub_self

      rw [h1, h2, sub_self]
Matrix.one_apply
The entries of the identity matrix are 1 on the diagonal and 0 elsewhere.
Matrix.diagonal_apply
The (i, j)-th entry of a diagonal matrix is d(i) if i = j and 0 elsewhere.
Finset.sum_sub_distrib
The sum of a difference of functions over a finite set equals the difference of their sums.
Finset.sum_const
Summing a constant value over a finite set multiplies the constant by the cardinality of the set.
Finset.card_univ
The cardinality of the universal finset univ of a finite type is the cardinality of the type.
Fintype.card_fin
The cardinality of Fin n is n.
nsmul_eq_mul
Scalar multiplication of a ring element by a natural number n equals multiplication by the coercion of n.
mul_assoc
Multiplication is associative: (a * b) * c = a * (b * c).
mul_one_div_cancel
Multiplying a non-zero element by its reciprocal gives 1.
one_mul
Multiplication by 1 on the left is the identity: 1 * a = a.
sub_self
Subtracting an element from itself gives 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

/-- Each row of the balanced blow-up matrix sums to zero if L has zero row sums. -/theorem balanced_blowup_matrix_row_sum (m d : ℕ) (hd : 1 ≤ d) (L : Matrix (Fin m) (Fin m) ℝ)    (hL : ∀ i : Fin m, ∑ j : Fin m, L i j = 0) (i : Fin m) (s : Fin d) :    ∑ j : Fin m, ∑ t : Fin d, balanced_blowup_matrix m d L (i, s) (j, t) = 0 := by  have hd_pos : (d : ℝ) ≠ 0 := by    norm_cast    omega  have h_entry (j : Fin m) (t : Fin d) :      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]  simp_rw [h_entry, Finset.sum_sub_distrib]  have h1 : (∑ j : Fin m, ∑ t : Fin d, (if i = j then L i i else 0) * (if s = t then 1 else 0 : ℝ)) = L i i := by    simp  have h2 : (∑ j : Fin m, ∑ _t : Fin d, (1 / (d : ℝ)) * (if i = j then 0 else - L i j)) = L i i := by    simp_rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin]    have hd_mul (x : ℝ) : d • (1 / (d : ℝ) * x) = x := by      rw [nsmul_eq_mul, ← mul_assoc, mul_one_div_cancel hd_pos, one_mul]    simp_rw [hd_mul]    have h (j : Fin m) : (if i = j then (0 : ℝ) else - L i j) = (if i = j then L i i else 0) - L i j := by      split_ifs with hij      · subst hij; ring      · ring    simp_rw [h, Finset.sum_sub_distrib]    simp [hL i]  rw [h1, h2, sub_self]
See it in the graphDiscuss this resultChallenge it