AFTD Auto-Formalizing Theoretical Domains

regular_adj_charpoly_root_abs_le

theoremverified

For an s-regular simple graph G on a finite vertex set, every root μ of the characteristic polynomial of its real adjacency matrix satisfies |μ| ≤ s.

Statement

open scoped Classical in
theorem regular_adj_charpoly_root_abs_le
    {V : Type*} [Fintype V] (G : SimpleGraph V) (s : ℕ) (hG : G.IsRegularOfDegree s)
    (μ : ℝ) (hμ : μ ∈ (G.adjMatrix ℝ).charpoly.roots) : |μ| ≤ s
Source
arXiv:2611.00591, Lemma 4.1 (step of its proof)
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The theorem is proved by applying Gershgorin's circle theorem to the real adjacency matrix of the graph. Because a simple graph has no self-loops, all diagonal entries of its adjacency matrix are zero, meaning every eigenvalue μ satisfies |μ| ≤ ∑_{j ≠ k} |A_{kj}| for some vertex k. Since each entry of the adjacency matrix is 0 or 1, this row sum is simply the degree of vertex k. In an s-regular graph, every vertex has degree s, which immediately yields |μ| ≤ s.

  1. The root μ of the characteristic polynomial of the adjacency matrix is an eigenvalue of the linear map induced by that matrix.

    From the assumption that μ is a root of the characteristic polynomial of the adjacency matrix (using Polynomial.mem_roots'.mp), we view the matrix as a linear endomorphism on ℝ^V via Matrix.toLin'. Because the characteristic polynomial of this endomorphism coincides with that of the matrix (Matrix.charpoly_toLin'), μ is an eigenvalue of the endomorphism by Module.End.hasEigenvalue_iff_isRoot_charpoly.

    lines 5–8

    uses Polynomial.mem_roots'.mp, Module.End.hasEigenvalue_iff_isRoot_charpoly, Matrix.charpoly_toLin'

      have hroot : (G.adjMatrix ℝ).charpoly.IsRoot μ := (Polynomial.mem_roots'.mp hμ).2
      have hev : Module.End.HasEigenvalue (Matrix.toLin' (G.adjMatrix ℝ)) μ := by
        rw [Module.End.hasEigenvalue_iff_isRoot_charpoly, Matrix.charpoly_toLin']
        exact hroot
  2. There exists a vertex k such that |μ| ≤ ∑_{j ≠ k} ‖A_{kj}‖, where A is the adjacency matrix.

    By Gershgorin's circle theorem (eigenvalue_mem_ball), the eigenvalue μ lies in a closed ball centered at some diagonal entry A_{kk} whose radius is the sum of the norms of the off-diagonal entries in row k. Expressing membership in the closed ball as a distance inequality (Metric.mem_closedBall) and using the real distance formula (Real.dist_eq), the condition becomes |μ - A_{kk}| ≤ ∑_{j ≠ k} ‖A_{kj}‖. Because G is a simple graph with no self-loops (SimpleGraph.irrefl), the diagonal entry A_{kk} is 0 (by SimpleGraph.adjMatrix_apply, if_false, and sub_zero), simplifying the inequality to |μ| ≤ ∑_{j ≠ k} ‖A_{kj}‖.

    lines 9–11

    uses eigenvalue_mem_ball, Metric.mem_closedBall, Real.dist_eq, SimpleGraph.adjMatrix_apply, SimpleGraph.irrefl, if_false, sub_zero

      obtain ⟨k, hk⟩ := eigenvalue_mem_ball hev
      rw [Metric.mem_closedBall, Real.dist_eq, SimpleGraph.adjMatrix_apply] at hk
      simp only [SimpleGraph.irrefl, if_false, sub_zero] at hk
  3. The sum of the norms of the off-diagonal entries in row k equals s.

    We evaluate the sum ∑_{j ≠ k} ‖A_{kj}‖ in three steps. First, because the diagonal entry A_{kk} is 0, adding it does not change the total, so the off-diagonal sum equals the full row sum ∑_j ‖A_{kj}‖ (lines 13–17, using Finset.sum_erase_add, Finset.mem_univ, and SimpleGraph.adjMatrix_apply). Second, since every entry of an adjacency matrix is either 0 or 1, each norm satisfies ‖A_{kj}‖ = A_{kj} (lines 18–22). Third, multiplying the adjacency matrix by the all-ones vector evaluates the row sum ∑_j A_{kj}, which equals the degree of vertex k (lines 23–25, using SimpleGraph.adjMatrix_mulVec_const_apply). Finally, since G is s-regular, the degree of vertex k is s, so the row sum equals s (line 26).

    lines 12–26

    uses Finset.sum_erase_add, Finset.mem_univ, SimpleGraph.adjMatrix_apply, SimpleGraph.adjMatrix_mulVec_const_apply

      have hsum : (∑ j ∈ Finset.univ.erase k, ‖G.adjMatrix ℝ k j‖) = (s : ℝ) := by
        have h1 : (∑ j ∈ Finset.univ.erase k, ‖G.adjMatrix ℝ k j‖) =
            ∑ j, ‖G.adjMatrix ℝ k j‖ := by
          rw [← Finset.sum_erase_add _ _ (Finset.mem_univ k)]
          simp [SimpleGraph.adjMatrix_apply]
        rw [h1]
        have h2 : ∀ j, ‖G.adjMatrix ℝ k j‖ = G.adjMatrix ℝ k j := by
          intro j
          simp only [SimpleGraph.adjMatrix_apply]
          split_ifs <;> simp
        simp only [h2]
        have h4 : (∑ j, G.adjMatrix ℝ k j) = (G.degree k : ℝ) := by
          have := SimpleGraph.adjMatrix_mulVec_const_apply (α := ℝ) (G := G) (a := (1 : ℝ)) (v := k)
          simpa [Matrix.mulVec, dotProduct] using this
        rw [h4, hG k]
  4. |μ| ≤ s.

    Linear arithmetic combines the Gershgorin bound |μ| ≤ ∑_{j ≠ k} ‖A_{kj}‖ with the row-sum evaluation ∑_{j ≠ k} ‖A_{kj}‖ = s to conclude that |μ| ≤ s.

    line 27

      linarith [hk, hsum.le]
Polynomial.mem_roots'.mp
An element belonging to the multiset of roots of a polynomial is a root of that polynomial.
Module.End.hasEigenvalue_iff_isRoot_charpoly
A scalar μ is an eigenvalue of an endomorphism if and only if μ is a root of its characteristic polynomial.
Matrix.charpoly_toLin'
The characteristic polynomial of the linear map induced by a square matrix equals the characteristic polynomial of the matrix.
eigenvalue_mem_ball
Gershgorin's circle theorem: every eigenvalue of a matrix lies in the closed ball centered at some diagonal entry A_{kk} with radius equal to the sum of the norms of the off-diagonal entries in row k.
Metric.mem_closedBall
A point y lies in the closed ball centered at x with radius ε if and only if the distance between y and x is at most ε.
Real.dist_eq
The metric distance between two real numbers x and y is |x - y|.
SimpleGraph.adjMatrix_apply
The (v, w) entry of the adjacency matrix of a simple graph is 1 if v and w are adjacent, and 0 otherwise.
SimpleGraph.irrefl
In a simple graph, no vertex is adjacent to itself (there are no self-loops).
if_false
An if-then-else expression whose condition is False evaluates to its else branch.
sub_zero
Subtracting zero leaves an element unchanged (a - 0 = a).
Finset.sum_erase_add
For any element a in a finite set s, the sum of a function over s equals the sum over s without a plus the value at a.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
SimpleGraph.adjMatrix_mulVec_const_apply
Multiplying the adjacency matrix by the constant vector with entry a yields, at each vertex v, the degree of v multiplied by a.

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

open scoped Classical intheorem regular_adj_charpoly_root_abs_le    {V : Type*} [Fintype V] (G : SimpleGraph V) (s : ℕ) (hG : G.IsRegularOfDegree s)    (μ : ℝ) (hμ : μ ∈ (G.adjMatrix ℝ).charpoly.roots) : |μ| ≤ s := by  have hroot : (G.adjMatrix ℝ).charpoly.IsRoot μ := (Polynomial.mem_roots'.mp hμ).2  have hev : Module.End.HasEigenvalue (Matrix.toLin' (G.adjMatrix ℝ)) μ := by    rw [Module.End.hasEigenvalue_iff_isRoot_charpoly, Matrix.charpoly_toLin']    exact hroot  obtain ⟨k, hk⟩ := eigenvalue_mem_ball hev  rw [Metric.mem_closedBall, Real.dist_eq, SimpleGraph.adjMatrix_apply] at hk  simp only [SimpleGraph.irrefl, if_false, sub_zero] at hk  have hsum : (∑ j ∈ Finset.univ.erase k, ‖G.adjMatrix ℝ k j‖) = (s : ℝ) := by    have h1 : (∑ j ∈ Finset.univ.erase k, ‖G.adjMatrix ℝ k j‖) =        ∑ j, ‖G.adjMatrix ℝ k j‖ := by      rw [← Finset.sum_erase_add _ _ (Finset.mem_univ k)]      simp [SimpleGraph.adjMatrix_apply]    rw [h1]    have h2 : ∀ j, ‖G.adjMatrix ℝ k j‖ = G.adjMatrix ℝ k j := by      intro j      simp only [SimpleGraph.adjMatrix_apply]      split_ifs <;> simp    simp only [h2]    have h4 : (∑ j, G.adjMatrix ℝ k j) = (G.degree k : ℝ) := by      have := SimpleGraph.adjMatrix_mulVec_const_apply (α := ℝ) (G := G) (a := (1 : ℝ)) (v := k)      simpa [Matrix.mulVec, dotProduct] using this    rw [h4, hG k]  linarith [hk, hsum.le]
See it in the graphDiscuss this resultChallenge it