balanced_blowup_spectrum_subset
For natural numbers m and d with 1 ≤ d, and an m x m real matrix L on Fin m, the complex spectrum of L is a subset of the complex spectrum of its balanced blow-up matrix balanced_blowup_matrix m d L.
Statement
theorem balanced_blowup_spectrum_subset (m d : ℕ) (hd : 1 ≤ d) (L : Matrix (Fin m) (Fin m) ℝ) :
spectrum ℂ (L.map Complex.ofReal) ⊆
spectrum ℂ ((balanced_blowup_matrix m d L).map Complex.ofReal)- 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$ such that $1 \le d$, and for every $m \times m$ real matrix $L$, the spectrum over $\mathbb{C}$ of $L$ (embedded into the complex numbers) is a subset of the spectrum over $\mathbb{C}$ of the $(m \cdot d) \times (m \cdot d)$ real matrix balanced_blowup_matrix m d L (embedded into the complex numbers).
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
To prove that any eigenvalue r in the complex spectrum of L is also in the spectrum of its balanced blow-up matrix B, the proof lifts an eigenvector v ≠ 0 of L (with L v = r v) to a vector w on Fin m × Fin d by setting w(i, s) = v_i. The crucial structural property of the blow-up matrix is that summing the entries in any row of block (i, s) across the d columns of block j yields exactly L_{i, j}. Consequently, multiplying B by w computes (L v)_i = r v_i = r w(i, s) in every component, demonstrating that w is a non-zero eigenvector of B with eigenvalue r.
Assume r is in the spectrum of L, and rule out the empty matrix case m = 0.
Let r be an element of the complex spectrum of L. If m = 0, the matrix has empty index type Fin 0, so det(r I - L) = 1 ≠ 0, which means r I - L is invertible. But membership in the spectrum implies r I - L is not invertible, which would force 1 = 0. Hence m = 0 is impossible.
uses
spectrum.mem_iff,Matrix.isUnit_iff_isUnit_det,isUnit_iff_ne_zero,Classical.not_not,Matrix.det_isEmpty,False.elim,one_ne_zerointro r hr by_cases hm : m = 0 · subst hm rw [spectrum.mem_iff, Matrix.isUnit_iff_isUnit_det, isUnit_iff_ne_zero, Classical.not_not] at hr rw [Matrix.det_isEmpty] at hr exact False.elim (one_ne_zero hr)
The blow-up factor d is non-zero as a real number.
From the hypothesis 1 ≤ d, integer arithmetic (via norm_cast and omega) implies that d ≠ 0 in ℝ.
have hd_pos : (d : ℝ) ≠ 0 := by norm_cast omega
Derive the explicit formula for the entries of the balanced blow-up matrix B.
Unfolding the definition of balanced_blowup_matrix m d L, which is (D ⊗ I_d) - (1/d) · (A ⊗ J_d) where D is the diagonal part of L and A is the off-diagonal part with negated entries, the entry at index ((i, s), (j, t)) simplifies to (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).
uses
Matrix.one_apply,Matrix.diagonal_applyhave h_entry (i j : Fin m) (s : Fin d) (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]
For any row index (i, s) and column block j, the sum of the entries of the blow-up matrix across the d columns t ∈ Fin d equals L i j (in both ℝ and ℂ).
Summing the entry formula over t ∈ Fin d: if i = j, the second term vanishes and the first term has s = t for exactly one t, yielding L i i; if i ≠ j, the first term vanishes and the second term sums d identical copies of (1/d) * L i j, which simplifies to L i j. Applying the ring homomorphism Complex.ofRealHom to the sum over Fin d gives the same identity for the complexified matrices.
uses
Finset.sum_sub_distrib,nsmul_eq_mul,mul_assoc,mul_one_div_cancel,one_mul,Finset.sum_const,Finset.card_univ,Fintype.card_fin,Complex.ofRealHom,map_sumhave sum_blowup_eq (i j : Fin m) (s : Fin d) : ∑ t : Fin d, ((balanced_blowup_matrix m d L).map Complex.ofReal) (i, s) (j, t) = (L.map Complex.ofReal) i j := by have h_sum : ∑ t : Fin d, balanced_blowup_matrix m d L (i, s) (j, t) = L i j := by simp_rw [h_entry, Finset.sum_sub_distrib] have h1 : (∑ t : Fin d, (if i = j then L i i else 0) * (if s = t then 1 else 0 : ℝ)) = (if i = j then L i i else 0) := by simp have hd_mul (x : ℝ) : d • (1 / (d : ℝ) * x) = x := by rw [nsmul_eq_mul, ← mul_assoc, mul_one_div_cancel hd_pos, one_mul] have h2 : (∑ _t : Fin d, (1 / (d : ℝ)) * (if i = j then 0 else - L i j)) = (if i = j then 0 else - L i j) := by rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, hd_mul] rw [h1, h2] split_ifs with hij · subst hij; ring · ring change ∑ t : Fin d, (Complex.ofRealHom (balanced_blowup_matrix m d L (i, s) (j, t))) = Complex.ofRealHom (L i j) rw [← map_sum Complex.ofRealHom, h_sum]
There exists a non-zero eigenvector v ∈ ℂᵐ of L with eigenvalue r, so L v = r • v.
Since r is in the spectrum of L, r I - L is not invertible, meaning its determinant is 0. A square matrix over ℂ with zero determinant has a non-trivial kernel, providing a non-zero vector v with (r I - L) v = 0. Expanding this relation componentwise gives (L v) i = r * v i for every i.
uses
spectrum.mem_iff,Matrix.isUnit_iff_isUnit_det,isUnit_iff_ne_zero,Classical.not_not,Matrix.exists_mulVec_eq_zero_iff,congr_fun,Matrix.sub_mulVec,Pi.sub_apply,sub_eq_zero,Matrix.diagonal_apply,Matrix.algebraMap_eq_diagonal,Pi.smul_apply,smul_eq_mulhave has_eigen : ∃ v : Fin m → ℂ, v ≠ 0 ∧ Matrix.mulVec (L.map Complex.ofReal) v = r • v := by rw [spectrum.mem_iff, Matrix.isUnit_iff_isUnit_det, isUnit_iff_ne_zero, Classical.not_not] at hr rw [← Matrix.exists_mulVec_eq_zero_iff] at hr obtain ⟨v, hv, h0⟩ := hr refine ⟨v, hv, ?_⟩ ext i have hi : (Matrix.mulVec (algebraMap ℂ (Matrix (Fin m) (Fin m) ℂ) r - L.map Complex.ofReal) v) i = 0 := congr_fun h0 i rw [Matrix.sub_mulVec] at hi simp only [Pi.sub_apply, sub_eq_zero] at hi have hdiag : (Matrix.mulVec (Matrix.diagonal ((algebraMap ℂ (Fin m → ℂ)) r)) v) i = r * v i := by simp [Matrix.mulVec, dotProduct, Matrix.diagonal_apply] rw [Matrix.algebraMap_eq_diagonal, hdiag] at hi simp [Pi.smul_apply, smul_eq_mul, hi] obtain ⟨v, hv, hLv⟩ := has_eigen
Define the lifted vector w ∈ ℂᵐˣᵈ by w(i, s) = v(i), and show w ≠ 0.
We extend v across each blow-up block by repeating its values: w(i, s) = v(i). Because 1 ≤ d, the index 0 is valid in Fin d. If w were 0, then v(i) = w(i, 0) = 0 for all i, contradicting v ≠ 0.
uses
congr_funlet w : Fin m × Fin d → ℂ := fun p => v p.1 have hw : w ≠ 0 := by intro hw0 apply hv ext i have hd0 : 0 < d := by omega have hwi := congr_fun hw0 (i, ⟨0, hd0⟩) exact hwi
The vector w is an eigenvector of the balanced blow-up matrix B with eigenvalue r, i.e., B w = r • w.
At coordinate (i, s), the matrix-vector product (B w)(i, s) equals ∑_{j, t} B_{(i, s), (j, t)} v_j = ∑_j (∑_t B_{(i, s), (j, t)}) v_j. By the block row-sum property, the inner sum over t equals L_{i, j}. Thus the product evaluates to ∑_j L_{i, j} v_j = (L v)_i = r * v_i = r * w(i, s).
uses
Pi.smul_apply,smul_eq_mul,Fintype.sum_prod_type,Finset.sum_mul,congr_funhave hBw : Matrix.mulVec ((balanced_blowup_matrix m d L).map Complex.ofReal) w = r • w := by ext ⟨i, s⟩ simp only [Matrix.mulVec, dotProduct, Pi.smul_apply, smul_eq_mul, w] rw [Fintype.sum_prod_type] have h_inner (j : Fin m) : (∑ t : Fin d, ((balanced_blowup_matrix m d L).map Complex.ofReal) (i, s) (j, t) * v j) = (L.map Complex.ofReal) i j * v j := by rw [← Finset.sum_mul, sum_blowup_eq i j s] simp_rw [h_inner] have h_vi : (Matrix.mulVec (L.map Complex.ofReal) v) i = (r • v) i := congr_fun hLv i simp only [Matrix.mulVec, dotProduct, Pi.smul_apply, smul_eq_mul] at h_vi exact h_vi
Conclude that r is in the spectrum of the balanced blow-up matrix B.
Since w ≠ 0 satisfies B w = r • w, the matrix (r I - B) has a non-trivial kernel vector w. This implies det(r I - B) = 0, so r I - B is not invertible (not a unit). By the characterization of the matrix spectrum, r belongs to the spectrum of B.
uses
spectrum.mem_iff,Matrix.isUnit_iff_isUnit_det,isUnit_iff_ne_zero,Classical.not_not,Matrix.exists_mulVec_eq_zero_iff,Matrix.sub_mulVec,Pi.sub_apply,Pi.zero_apply,sub_eq_zero,Matrix.diagonal_apply,Matrix.algebraMap_eq_diagonal,congr_fun,Pi.smul_apply,smul_eq_mulrw [spectrum.mem_iff, Matrix.isUnit_iff_isUnit_det, isUnit_iff_ne_zero, Classical.not_not] rw [← Matrix.exists_mulVec_eq_zero_iff] refine ⟨w, hw, ?_⟩ ext ⟨i, s⟩ rw [Matrix.sub_mulVec] simp only [Pi.sub_apply, Pi.zero_apply, sub_eq_zero] have hdiag : (Matrix.mulVec (Matrix.diagonal ((algebraMap ℂ (Fin m × Fin d → ℂ)) r)) w) (i, s) = r * w (i, s) := by simp [Matrix.mulVec, dotProduct, Matrix.diagonal_apply] rw [Matrix.algebraMap_eq_diagonal, hdiag] have hi : (Matrix.mulVec ((balanced_blowup_matrix m d L).map Complex.ofReal) w) (i, s) = (r • w) (i, s) := congr_fun hBw (i, s) simp only [Pi.smul_apply, smul_eq_mul] at hi exact hi.symm
Classical.not_not- Double negation elimination: ¬¬a is equivalent to a.
Complex.ofRealHom- The canonical inclusion of real numbers into complex numbers as a ring homomorphism.
False.elim- Ex falso quodlibet: False implies any proposition.
Fintype.card_fin- The cardinality of Fin n is n.
Fintype.sum_prod_type- A sum over the product type α × β can be written as an iterated double sum.
Finset.card_univ- The cardinality of the universal finset on a finite type equals the cardinality of the type.
Finset.sum_const- Summing a constant over a finset equals the size of the finset times the constant.
Finset.sum_mul- Right-multiplication distributes over finite sums: (∑ i, f i) * a = ∑ i, f i * a.
Finset.sum_sub_distrib- The sum of a difference is the difference of the sums.
Matrix.algebraMap_eq_diagonal- The scalar matrix r · I is equal to the diagonal matrix with r along the diagonal.
Matrix.det_isEmpty- The determinant of an empty (0-by-0) matrix is 1.
Matrix.diagonal_apply- The (i, j) entry of a diagonal matrix is d(i) if i = j and 0 otherwise.
Matrix.exists_mulVec_eq_zero_iff- A square matrix over an integral domain has zero determinant if and only if there exists a non-zero vector in its kernel.
Matrix.isUnit_iff_isUnit_det- A square matrix over a commutative ring is invertible if and only if its determinant is a unit.
Matrix.one_apply- The (i, j) entry of the identity matrix is 1 if i = j and 0 otherwise.
Matrix.sub_mulVec- Matrix-vector multiplication distributes over matrix subtraction: (A - B) x = A x - B x.
Pi.sub_apply- The difference of two functions evaluated at i equals the difference of their values at i.
Pi.smul_apply- Scalar multiplication of a function evaluated at i equals the scalar times the function value at i.
Pi.zero_apply- The zero function evaluated at any index i gives 0.
congr_fun- Equal functions have equal values at every input.
isUnit_iff_ne_zero- In a group with zero (such as a field), an element is a unit if and only if it is non-zero.
map_sum- An additive monoid homomorphism commutes with finite sums.
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
mul_one_div_cancel- Any non-zero element times its reciprocal is 1.
nsmul_eq_mul- Natural scalar multiplication n • a equals (n : α) * a.
one_mul- Multiplication by 1 on the left is the identity: 1 * a = a.
one_ne_zero- The multiplicative identity 1 is not equal to 0.
smul_eq_mul- Scalar multiplication in an algebra over a field agrees with standard ring multiplication.
spectrum.mem_iff- An element r is in the spectrum of a if and only if r · 1 - a is not invertible.
sub_eq_zero- The difference a - b is 0 if and only if a = b.
- The edge case m = 0 is handled formally: a 0-by-0 matrix has determinant 1 and empty spectrum. On paper, one usually assumes m ≥ 1 implicitly.
- The balanced blow-up matrix is defined via Kronecker products; the proof immediately simplifies this to an entry-by-entry formula via h_entry.
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 spectrum of L is contained in the spectrum of its balanced blow-up matrix. -/theorem balanced_blowup_spectrum_subset (m d : ℕ) (hd : 1 ≤ d) (L : Matrix (Fin m) (Fin m) ℝ) : spectrum ℂ (L.map Complex.ofReal) ⊆ spectrum ℂ ((balanced_blowup_matrix m d L).map Complex.ofReal) := by intro r hr by_cases hm : m = 0 · subst hm rw [spectrum.mem_iff, Matrix.isUnit_iff_isUnit_det, isUnit_iff_ne_zero, Classical.not_not] at hr rw [Matrix.det_isEmpty] at hr exact False.elim (one_ne_zero hr) have hd_pos : (d : ℝ) ≠ 0 := by norm_cast omega have h_entry (i j : Fin m) (s : Fin d) (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] have sum_blowup_eq (i j : Fin m) (s : Fin d) : ∑ t : Fin d, ((balanced_blowup_matrix m d L).map Complex.ofReal) (i, s) (j, t) = (L.map Complex.ofReal) i j := by have h_sum : ∑ t : Fin d, balanced_blowup_matrix m d L (i, s) (j, t) = L i j := by simp_rw [h_entry, Finset.sum_sub_distrib] have h1 : (∑ t : Fin d, (if i = j then L i i else 0) * (if s = t then 1 else 0 : ℝ)) = (if i = j then L i i else 0) := by simp have hd_mul (x : ℝ) : d • (1 / (d : ℝ) * x) = x := by rw [nsmul_eq_mul, ← mul_assoc, mul_one_div_cancel hd_pos, one_mul] have h2 : (∑ _t : Fin d, (1 / (d : ℝ)) * (if i = j then 0 else - L i j)) = (if i = j then 0 else - L i j) := by rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, hd_mul] rw [h1, h2] split_ifs with hij · subst hij; ring · ring change ∑ t : Fin d, (Complex.ofRealHom (balanced_blowup_matrix m d L (i, s) (j, t))) = Complex.ofRealHom (L i j) rw [← map_sum Complex.ofRealHom, h_sum] have has_eigen : ∃ v : Fin m → ℂ, v ≠ 0 ∧ Matrix.mulVec (L.map Complex.ofReal) v = r • v := by rw [spectrum.mem_iff, Matrix.isUnit_iff_isUnit_det, isUnit_iff_ne_zero, Classical.not_not] at hr rw [← Matrix.exists_mulVec_eq_zero_iff] at hr obtain ⟨v, hv, h0⟩ := hr refine ⟨v, hv, ?_⟩ ext i have hi : (Matrix.mulVec (algebraMap ℂ (Matrix (Fin m) (Fin m) ℂ) r - L.map Complex.ofReal) v) i = 0 := congr_fun h0 i rw [Matrix.sub_mulVec] at hi simp only [Pi.sub_apply, sub_eq_zero] at hi have hdiag : (Matrix.mulVec (Matrix.diagonal ((algebraMap ℂ (Fin m → ℂ)) r)) v) i = r * v i := by simp [Matrix.mulVec, dotProduct, Matrix.diagonal_apply] rw [Matrix.algebraMap_eq_diagonal, hdiag] at hi simp [Pi.smul_apply, smul_eq_mul, hi] obtain ⟨v, hv, hLv⟩ := has_eigen let w : Fin m × Fin d → ℂ := fun p => v p.1 have hw : w ≠ 0 := by intro hw0 apply hv ext i have hd0 : 0 < d := by omega have hwi := congr_fun hw0 (i, ⟨0, hd0⟩) exact hwi have hBw : Matrix.mulVec ((balanced_blowup_matrix m d L).map Complex.ofReal) w = r • w := by ext ⟨i, s⟩ simp only [Matrix.mulVec, dotProduct, Pi.smul_apply, smul_eq_mul, w] rw [Fintype.sum_prod_type] have h_inner (j : Fin m) : (∑ t : Fin d, ((balanced_blowup_matrix m d L).map Complex.ofReal) (i, s) (j, t) * v j) = (L.map Complex.ofReal) i j * v j := by rw [← Finset.sum_mul, sum_blowup_eq i j s] simp_rw [h_inner] have h_vi : (Matrix.mulVec (L.map Complex.ofReal) v) i = (r • v) i := congr_fun hLv i simp only [Matrix.mulVec, dotProduct, Pi.smul_apply, smul_eq_mul] at h_vi exact h_vi rw [spectrum.mem_iff, Matrix.isUnit_iff_isUnit_det, isUnit_iff_ne_zero, Classical.not_not] rw [← Matrix.exists_mulVec_eq_zero_iff] refine ⟨w, hw, ?_⟩ ext ⟨i, s⟩ rw [Matrix.sub_mulVec] simp only [Pi.sub_apply, Pi.zero_apply, sub_eq_zero] have hdiag : (Matrix.mulVec (Matrix.diagonal ((algebraMap ℂ (Fin m × Fin d → ℂ)) r)) w) (i, s) = r * w (i, s) := by simp [Matrix.mulVec, dotProduct, Matrix.diagonal_apply] rw [Matrix.algebraMap_eq_diagonal, hdiag] have hi : (Matrix.mulVec ((balanced_blowup_matrix m d L).map Complex.ofReal) w) (i, s) = (r • w) (i, s) := congr_fun hBw (i, s) simp only [Pi.smul_apply, smul_eq_mul] at hi exact hi.symm