adjacency_lambda2_eq_of_charpoly_roots
For a simple graph G on a finite vertex set, if the roots of the characteristic polynomial of its real adjacency matrix are a, x and a multiset M with x ≤ a and every element of M at most x, then the second largest adjacency eigenvalue adjacency_lambda2 G equals x.
Statement
open scoped Classical in theorem adjacency_lambda2_eq_of_charpoly_roots {V : Type*} [Fintype V] (G : SimpleGraph V) (a x : ℝ) (M : Multiset ℝ) (hroots : (G.adjMatrix ℝ).charpoly.roots = a ::ₘ x ::ₘ M) (hxa : x ≤ a) (hM : ∀ y ∈ M, y ≤ x) : adjacency_lambda2 G = x
- Source
- arXiv:2611.00591, Lemma 4.1 (step of its proof)
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- adjacency_lambda2For any finite vertex type V and any simple graph G on V, the eigenvalue at index 1 of the real adjacency matrix (G.isHermitian_adjMatrix…
- 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 adjacency matrix of a simple graph is real symmetric, so its eigenvalues in descending order coincide with the roots of its characteristic polynomial sorted in non-increasing order. Given that the roots are a, x, and a multiset M with x ≤ a and all elements of M at most x, the sorted list of eigenvalues begins with a followed by x. Since this list has length at least 2, the second eigenvalue adjacency_lambda2 G is well-defined and equals the entry at index 1, which is x.
The list of eigenvalues of the adjacency matrix sorted in descending order equals a :: x :: M.sort (≥).
The real adjacency matrix of a simple graph is symmetric (Hermitian), so by the spectral theorem (sort_roots_charpoly_eq_eigenvalues₀), its eigenvalues sorted in descending order coincide with the roots of its characteristic polynomial sorted in descending order. Since the roots are real, taking their real parts via RCLike.re is the identity function (using Multiset.map_id). Substituting the known roots a ::ₘ x ::ₘ M and applying Multiset.sort_cons twice pulls a and x to the front, yielding a :: x :: M.sort (≥).
uses
Multiset.map_id,Multiset.sort_conshave hA := G.isHermitian_adjMatrix ℝ have hsort := hA.sort_roots_charpoly_eq_eigenvalues₀ have hre : (G.adjMatrix ℝ).charpoly.roots.map RCLike.re = (G.adjMatrix ℝ).charpoly.roots := by conv_rhs => rw [← Multiset.map_id (G.adjMatrix ℝ).charpoly.roots] rfl rw [hre, hroots, Multiset.sort_cons, Multiset.sort_cons] at hsort
The vertex set of G has cardinality at least 2 (2 ≤ |V|).
Applying List.length to both sides of the sorted eigenvalue equality via congrArg shows that the list of eigenvalues has length |V| (by List.length_ofFn), while the list a :: x :: M.sort (≥) has length |M| + 2 (by List.length_cons). Linear arithmetic (omega) immediately yields 2 ≤ |V|.
uses
congrArg,List.length_cons,List.length_ofFn· have hlen := congrArg List.length hsort simp only [List.length_cons, List.length_ofFn] at hlen have hn : 2 ≤ Fintype.card V := by omega
adjacency_lambda2 G = x
Unfolding the definition of adjacency_lambda2 G, the condition 2 ≤ |V| holds, so dif_pos reduces the expression to the eigenvalue at index 1 (the second eigenvalue). Evaluating both sides of the sorted list equality at index 1 via congrArg, the second entry of a :: x :: M.sort (≥) is x (by List.getElem?_cons_succ and List.getElem?_cons_zero), which matches the second eigenvalue (by List.getElem?_ofFn).
uses
dif_pos,congrArg,List.getElem?_cons_succ,List.getElem?_cons_zero,List.getElem?_ofFnunfold adjacency_lambda2 rw [dif_pos hn] have := congrArg (fun l => l[1]?) hsort simp only [List.getElem?_cons_succ, List.getElem?_cons_zero, List.getElem?_ofFn] at this simp at this obtain ⟨_, hx⟩ := this exact hx.symm
Every element of M is at most x (∀ b ∈ M, x ≥ b).
This is directly the hypothesis hM, discharging the first sorting condition needed to pull x to the front of M.sort (≥).
· exact fun b hb => hM b hb
Every element of x ::ₘ M is at most a (∀ b ∈ x ::ₘ M, a ≥ b).
Any element b in x ::ₘ M either equals x or belongs to M (by Multiset.mem_cons.mp). If b = x, then b ≤ a by hypothesis hxa. If b ∈ M, then b ≤ x ≤ a by hypothesis hM and transitivity with hxa. This discharges the second sorting condition needed to pull a to the front.
uses
Multiset.mem_cons.mp· intro b hb rcases Multiset.mem_cons.mp hb with rfl | hb · exact hxa · exact (hM b hb).trans hxa
Multiset.map_id- Mapping the identity function over any multiset leaves the multiset unchanged.
Multiset.sort_cons- If an element a satisfies r a b for all b in a multiset s, then sorting the multiset a ::ₘ s by r yields a prepended to the sorted list of s.
congrArg- Applying a function to both sides of an equality preserves the equality: if a₁ = a₂, then f(a₁) = f(a₂).
List.length_cons- Prepending an element to a list increases its length by 1.
List.length_ofFn- The length of the list generated from a function with domain Fin n is n.
dif_pos- A dependent if-then-else evaluates to its 'then' branch when the condition is satisfied.
List.getElem?_cons_succ- The element at index i + 1 in a list a :: l is the element at index i in the tail l.
List.getElem?_cons_zero- The element at index 0 in a list a :: l is the head element a.
List.getElem?_ofFn- The element at index i of a list formed by List.ofFn f of size n is some (f i) if i < n, and none otherwise.
Multiset.mem_cons.mp- An element belongs to a ::ₘ s if and only if it equals a or belongs to s.
- In Lean, the general spectral theorem for Hermitian matrices uses the real-part map `RCLike.re` on roots of the characteristic polynomial; because the adjacency matrix here is real, an explicit rewrite `Multiset.map_id` is used to identify these real parts with the roots themselves.
- The definition of `adjacency_lambda2 G` contains a case split checking `2 ≤ Fintype.card V` (defaulting to 0 when the graph has fewer than 2 vertices), requiring an auxiliary arithmetic deduction that the vertex set has size at least 2 before evaluating the eigenvalue.
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 adjacency_lambda2_eq_of_charpoly_roots {V : Type*} [Fintype V] (G : SimpleGraph V) (a x : ℝ) (M : Multiset ℝ) (hroots : (G.adjMatrix ℝ).charpoly.roots = a ::ₘ x ::ₘ M) (hxa : x ≤ a) (hM : ∀ y ∈ M, y ≤ x) : adjacency_lambda2 G = x := by have hA := G.isHermitian_adjMatrix ℝ have hsort := hA.sort_roots_charpoly_eq_eigenvalues₀ have hre : (G.adjMatrix ℝ).charpoly.roots.map RCLike.re = (G.adjMatrix ℝ).charpoly.roots := by conv_rhs => rw [← Multiset.map_id (G.adjMatrix ℝ).charpoly.roots] rfl rw [hre, hroots, Multiset.sort_cons, Multiset.sort_cons] at hsort · have hlen := congrArg List.length hsort simp only [List.length_cons, List.length_ofFn] at hlen have hn : 2 ≤ Fintype.card V := by omega unfold adjacency_lambda2 rw [dif_pos hn] have := congrArg (fun l => l[1]?) hsort simp only [List.getElem?_cons_succ, List.getElem?_cons_zero, List.getElem?_ofFn] at this simp at this obtain ⟨_, hx⟩ := this exact hx.symm · exact fun b hb => hM b hb · intro b hb rcases Multiset.mem_cons.mp hb with rfl | hb · exact hxa · exact (hM b hb).trans hxa