regular_adj_charpoly_root_abs_le
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
- bipartite_complement_adj_spectrum_and_lambda2Let H be an s-regular bipartite simple graph whose two parts V and W each have size m ≥ 2, and let G = K_{V,W} \ E(H) be its bipartite…
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.
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.
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
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}‖.
uses
eigenvalue_mem_ball,Metric.mem_closedBall,Real.dist_eq,SimpleGraph.adjMatrix_apply,SimpleGraph.irrefl,if_false,sub_zeroobtain ⟨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
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).
uses
Finset.sum_erase_add,Finset.mem_univ,SimpleGraph.adjMatrix_apply,SimpleGraph.adjMatrix_mulVec_const_applyhave 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]
|μ| ≤ 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.
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
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.
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]