standardized_laplacian_spectra_subset_of_dvd
Let 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 subset of the set of eigenvalues of standardized Laplacian matrices of order n.
Statement
theorem standardized_laplacian_spectra_subset_of_dvd (m n : ℕ) (hm : 2 ≤ m) (hn : 2 ≤ n)
(hdvd : m ∣ n) :
standardized_laplacian_spectra m ⊆ standardized_laplacian_spectra n- Formalizes
- scout/2610-14100-digraph-laplacian-spectra-the-2005-polygon-conjecture-fails.md:1044
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- is_standardized_laplacianA standardized Laplacian matrix of order n is a real n x n matrix with zero row sums and off-diagonal entries in [-1/n, 0].
- standardized_laplacian_spectraThe set Lambda_n of all complex eigenvalues of standardized Laplacian matrices of order n.
- 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…
- balanced_blowup_matrix_row_sumFor 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_off_diagFor 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…
- balanced_blowup_spectrum_subsetFor 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…
Read back from the Lean
For any natural numbers m and n, if 2 ≤ m, 2 ≤ n, and m ∣ n, then the set of standardized Laplacian spectra of order m is a subset of the set of standardized Laplacian spectra of order n.
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 show that every eigenvalue of an m × m standardized Laplacian matrix is also an eigenvalue of an n × n standardized Laplacian when m divides n, we set d = n / m and construct the balanced blowup matrix L' of size (m · d) × (m · d). By the spectral inclusion theorem for balanced blowups, L' retains the spectrum of L. Reindexing L' along a bijection Fin m × Fin d ≃ Fin n produces an n × n matrix M whose row sums and off-diagonal bounds satisfy the standardized Laplacian axioms. Finally, because reindexing is an algebra isomorphism, it preserves the spectrum, showing that the eigenvalue belongs to the standardized Laplacian spectrum of order n.
Let z be an eigenvalue of some standardized Laplacian matrix L of order m.
We take an arbitrary element z in the standardized Laplacian spectrum of order m. By definition, there exists a matrix L of size m × m with zero row sums and off-diagonal entries in [-1/m, 0] such that z is in the spectrum of L.
intro z hz simp only [standardized_laplacian_spectra] at hz ⊢ rcases hz with ⟨L, hL, hzL⟩ rcases hL with ⟨hL_row, hL_off⟩
The blowup factor d = n / m is at least 1, satisfies m * d = n, and the balanced blowup matrix L' retains the eigenvalue z.
Since m divides n and both are at least 2, d = n / m is a positive natural number satisfying m * d = n. We construct the balanced blowup matrix L' of L of block size d. By balanced_blowup_spectrum_subset, the spectrum of L' contains that of L, so z is in the spectrum of L'.
uses
Nat.div_pos,Nat.le_of_dvd,Nat.mul_div_cancel',balanced_blowup_spectrum_subsetset d := n / m with hd_def have hm1 : 1 ≤ m := by omega have hd : 1 ≤ d := Nat.div_pos (Nat.le_of_dvd (by omega) hdvd) (by omega) have h_mul : m * d = n := Nat.mul_div_cancel' hdvd set L' := balanced_blowup_matrix m d L with hL'_def have hzL' : z ∈ spectrum ℂ (L'.map Complex.ofReal) := balanced_blowup_spectrum_subset m d hd L hzL
Reindexing L' via the bijection Fin m × Fin d ≃ Fin n yields an n × n matrix M, proposed as the standardized Laplacian witness.
Using the arithmetic identity m * d = n, we compose the product equivalence Fin m × Fin d ≃ Fin (m * d) with finCongr to get a bijection e : Fin m × Fin d ≃ Fin n. Reindexing L' by e gives an n × n matrix M, which we propose as the witness for z being in the standardized Laplacian spectrum of order n.
uses
finCongrlet e : Fin m × Fin d ≃ Fin n := finProdFinEquiv.trans (finCongr h_mul) set M := Matrix.reindex e e L' with hM_def use M refine ⟨⟨?_, ?_⟩, ?_⟩
Every row sum of M is zero.
For each row index i, rewriting the sum over j : Fin n using the equivalence e converts it into a double sum over Fin m × Fin d. Evaluating at the pre-image e⁻¹(i) = (i₁, s₁), the sum vanishes by balanced_blowup_matrix_row_sum.
uses
Equiv.sum_comp,Matrix.reindex_apply,Matrix.submatrix_apply,Equiv.symm_apply_apply,Fintype.sum_prod_type,balanced_blowup_matrix_row_sum· intro i change ∑ j : Fin n, Matrix.reindex e e L' i j = 0 rw [← Equiv.sum_comp e (fun j => Matrix.reindex e e L' i j)] simp only [Matrix.reindex_apply, Matrix.submatrix_apply, Equiv.symm_apply_apply] rcases e.symm i with ⟨i₁, s₁⟩ rw [Fintype.sum_prod_type] exact balanced_blowup_matrix_row_sum m d hd L hL_row i₁ s₁
For distinct indices i ≠ j, the off-diagonal entry M i j lies in [-1/n, 0].
Because e⁻¹ is injective, i ≠ j implies e⁻¹(i) ≠ e⁻¹(j). The entry M i j corresponds to an off-diagonal entry of L', which by balanced_blowup_matrix_off_diag lies in [-1/(m * d), 0]. Substituting m * d = n yields the required bound [-1/n, 0].
uses
Matrix.reindex_apply,Matrix.submatrix_apply,balanced_blowup_matrix_off_diag· intro i j hij change -(1 : ℝ) / (n : ℝ) ≤ Matrix.reindex e e L' i j ∧ Matrix.reindex e e L' i j ≤ 0 simp only [Matrix.reindex_apply, Matrix.submatrix_apply] have hne : e.symm i ≠ e.symm j := by intro h apply hij exact e.symm.injective h have h_off := balanced_blowup_matrix_off_diag m d hm1 hd L hL_off (e.symm i).1 (e.symm j).1 (e.symm i).2 (e.symm j).2 hne have h_cast : (n : ℝ) = (m * d : ℝ) := by rw [← h_mul]; push_cast; rfl rw [h_cast] exact h_off
The complex eigenvalue z belongs to the spectrum of M.
Reindexing along e induces an algebra isomorphism Matrix.reindexAlgEquiv between the matrix algebras. By AlgEquiv.spectrum_eq, an algebra isomorphism preserves spectra, so the spectrum of M matches that of L', which contains z.
uses
Matrix.coe_reindexAlgEquiv,AlgEquiv.spectrum_eq· have h_map : M.map Complex.ofReal = Matrix.reindexAlgEquiv ℂ ℂ e (L'.map Complex.ofReal) := by rw [hM_def] ext i j simp [Matrix.coe_reindexAlgEquiv] rw [h_map] rw [AlgEquiv.spectrum_eq (Matrix.reindexAlgEquiv ℂ ℂ e) (L'.map Complex.ofReal)] exact hzL'
Nat.le_of_dvd- If a natural number m divides n and n > 0, then m ≤ n.
Nat.div_pos- For natural numbers a and b, if b ≤ a and b > 0, then a / b > 0.
Nat.mul_div_cancel'- If n divides m, then n * (m / n) = m.
balanced_blowup_spectrum_subset- Every eigenvalue of a matrix L is also an eigenvalue of its balanced blowup matrix.
finCongr- An equality of natural numbers n = m induces an equivalence between Fin n and Fin m.
Equiv.sum_comp- Summing over a finite set is invariant under reindexing the terms by an equivalence.
Matrix.reindex_apply- Reindexing a matrix by row and column equivalences corresponds to taking the submatrix via their inverses.
Matrix.submatrix_apply- The (i, j)-th entry of a submatrix formed by index maps r and c is the (r i, c j)-th entry of the original matrix.
Equiv.symm_apply_apply- Applying an equivalence and then its inverse is the identity.
Fintype.sum_prod_type- A sum over a Cartesian product of finite types equals the iterated sum over each component.
balanced_blowup_matrix_row_sum- If the row sums of L are zero, then the row sums of its balanced blowup matrix are also zero.
balanced_blowup_matrix_off_diag- If the off-diagonal entries of L lie in [-1/m, 0], then the off-diagonal entries of its balanced blowup matrix lie in [-1/(m * d), 0].
Matrix.coe_reindexAlgEquiv- The underlying map of the matrix algebra equivalence induced by an index equivalence is given by Matrix.reindex.
AlgEquiv.spectrum_eq- An algebra equivalence preserves the spectrum of an element.
- The balanced blowup matrix is naturally indexed by pairs in Fin m × Fin d, whereas the definition of a standardized Laplacian of order n requires matrices indexed by Fin n. The proof explicitly constructs a bijection Fin m × Fin d ≃ Fin n and transports the matrix and its spectrum across this bijection using the matrix algebra isomorphism Matrix.reindexAlgEquiv.
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.
/-- If m divides n for integers m, n >= 2, then Lambda_m is a subset of Lambda_n. -/theorem standardized_laplacian_spectra_subset_of_dvd (m n : ℕ) (hm : 2 ≤ m) (hn : 2 ≤ n) (hdvd : m ∣ n) : standardized_laplacian_spectra m ⊆ standardized_laplacian_spectra n := by intro z hz simp only [standardized_laplacian_spectra] at hz ⊢ rcases hz with ⟨L, hL, hzL⟩ rcases hL with ⟨hL_row, hL_off⟩ set d := n / m with hd_def have hm1 : 1 ≤ m := by omega have hd : 1 ≤ d := Nat.div_pos (Nat.le_of_dvd (by omega) hdvd) (by omega) have h_mul : m * d = n := Nat.mul_div_cancel' hdvd set L' := balanced_blowup_matrix m d L with hL'_def have hzL' : z ∈ spectrum ℂ (L'.map Complex.ofReal) := balanced_blowup_spectrum_subset m d hd L hzL let e : Fin m × Fin d ≃ Fin n := finProdFinEquiv.trans (finCongr h_mul) set M := Matrix.reindex e e L' with hM_def use M refine ⟨⟨?_, ?_⟩, ?_⟩ · intro i change ∑ j : Fin n, Matrix.reindex e e L' i j = 0 rw [← Equiv.sum_comp e (fun j => Matrix.reindex e e L' i j)] simp only [Matrix.reindex_apply, Matrix.submatrix_apply, Equiv.symm_apply_apply] rcases e.symm i with ⟨i₁, s₁⟩ rw [Fintype.sum_prod_type] exact balanced_blowup_matrix_row_sum m d hd L hL_row i₁ s₁ · intro i j hij change -(1 : ℝ) / (n : ℝ) ≤ Matrix.reindex e e L' i j ∧ Matrix.reindex e e L' i j ≤ 0 simp only [Matrix.reindex_apply, Matrix.submatrix_apply] have hne : e.symm i ≠ e.symm j := by intro h apply hij exact e.symm.injective h have h_off := balanced_blowup_matrix_off_diag m d hm1 hd L hL_off (e.symm i).1 (e.symm j).1 (e.symm i).2 (e.symm j).2 hne have h_cast : (n : ℝ) = (m * d : ℝ) := by rw [← h_mul]; push_cast; rfl rw [h_cast] exact h_off · have h_map : M.map Complex.ofReal = Matrix.reindexAlgEquiv ℂ ℂ e (L'.map Complex.ofReal) := by rw [hM_def] ext i j simp [Matrix.coe_reindexAlgEquiv] rw [h_map] rw [AlgEquiv.spectrum_eq (Matrix.reindexAlgEquiv ℂ ℂ e) (L'.map Complex.ofReal)] exact hzL'