AFTD Auto-Formalizing Theoretical Domains

balanced_blowup_spectrum_subset

theoremverified

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

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.

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

    lines 5–10

    uses spectrum.mem_iff, Matrix.isUnit_iff_isUnit_det, isUnit_iff_ne_zero, Classical.not_not, Matrix.det_isEmpty, False.elim, one_ne_zero

      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)
  2. 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 ℝ.

    lines 11–13

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

    lines 14–19

    uses Matrix.one_apply, Matrix.diagonal_apply

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

    lines 20–39

    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_sum

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

    lines 40–54

    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_mul

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

    lines 55–62

    uses congr_fun

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

    lines 63–74

    uses Pi.smul_apply, smul_eq_mul, Fintype.sum_prod_type, Finset.sum_mul, congr_fun

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

    lines 75–87

    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_mul

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

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