balanced_blowup_matrix_row_sum
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
- 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 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.
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 ℝ.
have hd_pos : (d : ℝ) ≠ 0 := by norm_cast omega
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.
uses
Matrix.one_apply,Matrix.diagonal_applyhave 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]
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.
uses
Finset.sum_sub_distribsimp_rw [h_entry, Finset.sum_sub_distrib]
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.
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
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.
uses
Finset.sum_const,Finset.card_univ,Fintype.card_fin,nsmul_eq_mul,mul_assoc,mul_one_div_cancel,one_mul,Finset.sum_sub_distribhave 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]
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.
uses
sub_selfrw [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
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.
/-- 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]