regular_bipartite_adj_charpoly_roots_contain_pm_degree
Let H be an s-regular graph contained in the complete bipartite graph on parts V, W of size m ≥ 1. Then s and −s are roots of the characteristic polynomial of the real adjacency matrix of H, with the multiset {s, −s} contained in its roots (so 0 has multiplicity at least 2 when s = 0).
Statement
open scoped Classical in theorem regular_bipartite_adj_charpoly_roots_contain_pm_degree {V W : Type*} [Fintype V] [Fintype W] (m s : ℕ) (hm : 1 ≤ m) (hV : Fintype.card V = m) (hW : Fintype.card W = m) (H : SimpleGraph (V ⊕ W)) (hH_sub : H ≤ completeBipartiteGraph V W) (hH_reg : H.IsRegularOfDegree s) : ({(s : ℝ), -(s : ℝ)} : Multiset ℝ) ≤ (H.adjMatrix ℝ).charpoly.roots
- 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 proof constructs explicit eigenvectors for $s$ and $-s$: the all-ones vector has eigenvalue $s$ because row sums of the adjacency matrix equal the degree $s$, while the vector taking value $+1$ on $V$ and $-1$ on $W$ has eigenvalue $-s$ by the bipartite structure. To conclude that the multiset $\{s, -s\}$ is contained in the roots of the characteristic polynomial, the argument splits on $s = 0$. If $s \ne 0$, the roots $s$ and $-s$ are distinct, so multiset containment reduces to set inclusion; if $s = 0$, the adjacency matrix is identically zero of order $2m \ge 2$, so 0 has algebraic multiplicity at least 2.
$H$ has no edges between two vertices of $V$, nor between two vertices of $W$.
Because $H$ is a subgraph of the complete bipartite graph between $V$ and $W$, every edge in $H$ must connect a vertex of $V$ to a vertex of $W$. Consequently, no two vertices in $V$ (or in $W$) can be adjacent.
have hnl : ∀ v v', ¬ H.Adj (Sum.inl v) (Sum.inl v') := by intro v v' h have := hH_sub h simp at this have hnr : ∀ w w', ¬ H.Adj (Sum.inr w) (Sum.inr w') := by intro w w' h have := hH_sub h simp at this
The diagonal blocks of the adjacency matrix $A$ of $H$ are identically zero: $A(v, v') = 0$ for all $v, v' \in V$ and $A(w, w') = 0$ for all $w, w' \in W$.
The adjacency matrix entries are defined by checking adjacency (1 if adjacent, 0 otherwise). Since there are no edges within $V$ or within $W$, all entries in those blocks evaluate to 0.
uses
SimpleGraph.adjMatrix_apply,if_negset A := H.adjMatrix ℝ with hA have hll : ∀ v v', A (Sum.inl v) (Sum.inl v') = 0 := by intro v v'; rw [hA, SimpleGraph.adjMatrix_apply, if_neg (hnl v v')] have hrr : ∀ w w', A (Sum.inr w) (Sum.inr w') = 0 := by intro w w'; rw [hA, SimpleGraph.adjMatrix_apply, if_neg (hnr w w')]
Every row of $A$ sums to $s$: for every vertex $i \in V \oplus W$, $\sum_j A(i, j) = s$.
Because $H$ is $s$-regular, multiplying $A$ by the all-ones vector produces $s$ times the all-ones vector. Expanding the matrix-vector product as row sums shows that every row sum equals $s$.
uses
SimpleGraph.adjMatrix_mulVec_const_apply_of_regular,Matrix.mulVec,Function.const_apply,mul_onehave hrow : ∀ i, ∑ j, A i j = s := by intro i have := SimpleGraph.adjMatrix_mulVec_const_apply_of_regular (α := ℝ) hH_reg (a := 1) (v := i) simp only [Matrix.mulVec, dotProduct, Function.const_apply, mul_one] at this exact this
The vertex set $V$ is nonempty, so there exists a vertex $v_0 \in V$.
The cardinality of $V$ is $m \ge 1 > 0$, which is equivalent to $V$ being inhabited.
uses
Fintype.card_pos_iffobtain ⟨v0⟩ : Nonempty V := by rw [← Fintype.card_pos_iff]; omega
Any scalar $\mu \in \mathbb{R}$ having an eigenvector $u$ with $u(v_0) \ne 0$ is a root of the characteristic polynomial of $A$.
Since $u(v_0) \ne 0$, the vector $u$ is nonzero. The eigenvalue equation $A u = \mu u$ gives $(\mu I - A) u = 0$, so $\mu I - A$ has a nontrivial nullspace and therefore determinant zero. Thus $\det(\mu I - A) = 0$, meaning $\mu$ is a root of the characteristic polynomial.
uses
Polynomial.mem_roots,Matrix.charpoly_monic,Polynomial.IsRoot,Matrix.eval_charpoly,Matrix.exists_mulVec_eq_zero_iff,Matrix.sub_mulVec,Matrix.scalar_apply,Matrix.mulVec_diagonalhave hroot : ∀ μ : ℝ, ∀ u : V ⊕ W → ℝ, u (Sum.inl v0) ≠ 0 → A.mulVec u = μ • u → μ ∈ A.charpoly.roots := by intro μ u hu h rw [Polynomial.mem_roots (Matrix.charpoly_monic A).ne_zero, Polynomial.IsRoot, Matrix.eval_charpoly, ← Matrix.exists_mulVec_eq_zero_iff] refine ⟨u, fun h0 => hu (by rw [h0]; rfl), ?_⟩ rw [Matrix.sub_mulVec, h] ext i simp [Matrix.scalar_apply, Matrix.mulVec_diagonal]
$s$ is a root of the characteristic polynomial of $A$.
The all-ones vector $\mathbf{1}$ has value $1 \ne 0$ at $v_0$. Multiplying $A$ by $\mathbf{1}$ gives $(A \mathbf{1})_i = \sum_j A(i, j) = s = s \cdot \mathbf{1}_i$ at every vertex $i$, so $\mathbf{1}$ is an eigenvector with eigenvalue $s$.
uses
Matrix.mulVec,mul_one,Pi.smul_apply,smul_eq_mulhave hplus : (s : ℝ) ∈ A.charpoly.roots := by refine hroot s (fun _ => 1) (by norm_num) ?_ ext i simp only [Matrix.mulVec, dotProduct, mul_one, Pi.smul_apply, smul_eq_mul] rw [hrow i]
$-s$ is a root of the characteristic polynomial of $A$.
Consider the vector $u$ equal to $+1$ on $V$ and $-1$ on $W$, which is nonzero at $v_0 \in V$. For $v \in V$, the $V$-block of row $v$ is zero, so $(A u)(v) = \sum_{w \in W} A(v, w)(-1) = -\sum_j A(v, j) = -s = -s \cdot u(v)$. Similarly, for $w \in W$, the $W$-block is zero, so $(A u)(w) = \sum_{v \in V} A(w, v)(+1) = \sum_j A(w, j) = s = -s \cdot (-1) = -s \cdot u(w)$. Thus $A u = -s u$, making $-s$ an eigenvalue.
uses
Fintype.sum_sum_type,Finset.sum_const_zero,zero_add,add_zero,Matrix.mulVechave hminus : -(s : ℝ) ∈ A.charpoly.roots := by refine hroot (-s) (Sum.elim (fun _ => 1) (fun _ => -1)) (by simp) ?_ ext i have hrow' := hrow i rw [Fintype.sum_sum_type] at hrow' rcases i with v | w · simp only [hll, Finset.sum_const_zero, zero_add] at hrow' simp [Matrix.mulVec, dotProduct, Fintype.sum_sum_type, hll, hrow'] · simp only [hrr, Finset.sum_const_zero, add_zero] at hrow' simp [Matrix.mulVec, dotProduct, Fintype.sum_sum_type, hrr, hrow']
If $s = 0$, the multiset $\{0, -0\} = \{0, 0\}$ is bounded by the roots of the characteristic polynomial of $A$.
When $s = 0$, every vertex has degree 0, so the graph has no edges and $A = 0$. The characteristic polynomial of the zero matrix of size $2m$ is $X^{2m}$, whose roots multiset is $2m$ copies of 0. Since $m \ge 1$, $2m \ge 2$, so the multiplicity of 0 in the polynomial roots is at least 2, dominating $\{0, 0\}$.
uses
SimpleGraph.adjMatrix_apply,if_neg,SimpleGraph.mem_neighborFinset,Finset.card_eq_zero,Matrix.charpoly_zero,Polynomial.roots_X_pow,Multiset.le_iff_count,Fintype.card_sum,Multiset.count_nsmul,Nat.cast_zero,neg_zero,Multiset.insert_eq_cons,Multiset.count_cons,Multiset.count_singletonby_cases hs : s = 0 · subst hs have hA0 : A = 0 := by ext i j rw [hA, SimpleGraph.adjMatrix_apply, if_neg] · rfl intro h have h1 : j ∈ H.neighborFinset i := (SimpleGraph.mem_neighborFinset _ _ _).mpr h have h2 : (H.neighborFinset i).card = 0 := hH_reg i rw [Finset.card_eq_zero] at h2 rw [h2] at h1 simp at h1 rw [hA0, Matrix.charpoly_zero, Polynomial.roots_X_pow, Multiset.le_iff_count] intro a simp only [Fintype.card_sum, hV, hW, Multiset.count_nsmul, Nat.cast_zero, neg_zero, Multiset.insert_eq_cons, Multiset.count_cons, Multiset.count_singleton] split_ifs <;> omega
If $s \ne 0$, the multiset $\{s, -s\}$ is contained in the roots of the characteristic polynomial of $A$.
When $s \ne 0$, $s \ne -s$, so the multiset $\{s, -s\}$ has no repeated elements. For duplicate-free multisets, multiset inequality is equivalent to subset inclusion, and both $s$ and $-s$ were shown to be roots.
uses
Multiset.le_iff_subset,Multiset.insert_eq_cons,Multiset.mem_cons,Multiset.mem_singleton,Multiset.nodup_cons,Multiset.nodup_singleton· have hne : (s : ℝ) ≠ -(s : ℝ) := by intro h have : (s : ℝ) = 0 := by linarith exact hs (by exact_mod_cast this) rw [Multiset.le_iff_subset] · intro x hx simp only [Multiset.insert_eq_cons, Multiset.mem_cons, Multiset.mem_singleton] at hx rcases hx with rfl | rfl · exact hplus · exact hminus · rw [Multiset.insert_eq_cons, Multiset.nodup_cons] exact ⟨by simpa using hne, Multiset.nodup_singleton _⟩
add_zero- Adding zero on the right leaves an element unchanged: $a + 0 = a$.
Finset.card_eq_zero- A finite set has cardinality zero if and only if it is the empty set.
Finset.sum_const_zero- The sum of zeros over any finite set is zero.
Fintype.card_pos_iff- A finite type is nonempty if and only if its cardinality is strictly positive.
Fintype.card_sum- The cardinality of a disjoint sum type $V \oplus W$ is $|V| + |W|$.
Fintype.sum_sum_type- The sum of a function over a disjoint sum $V \oplus W$ equals the sum over $V$ plus the sum over $W$.
Function.const_apply- The constant function evaluated at any input returns that constant value.
if_neg- An if-then-else expression evaluates to its second branch when the condition is false.
Matrix.charpoly_monic- The characteristic polynomial of any square matrix is monic.
Matrix.charpoly_zero- The characteristic polynomial of the $n \times n$ zero matrix is $X^n$.
Matrix.eval_charpoly- Evaluating the characteristic polynomial of a matrix $M$ at $t$ equals $\det(t I - M)$.
Matrix.exists_mulVec_eq_zero_iff- A square matrix has determinant zero if and only if it has a nonzero vector in its nullspace.
Matrix.mulVec- Matrix-vector multiplication computes the dot product of each matrix row with the vector.
Matrix.mulVec_diagonal- Multiplying a diagonal matrix by a vector scales each component by the corresponding diagonal entry.
Matrix.scalar_apply- The scalar matrix $a I$ is the diagonal matrix with all diagonal entries equal to $a$.
Matrix.sub_mulVec- Matrix-vector multiplication distributes over matrix subtraction: $(A - B) u = A u - B u$.
mul_one- Multiplying an element by 1 leaves it unchanged: $a \cdot 1 = a$.
Multiset.count_cons- The count of $a$ in $b ::ₘ s$ is its count in $s$, plus 1 if $a = b$.
Multiset.count_nsmul- The count of an element in $n \bullet s$ is $n$ times its count in $s$.
Multiset.count_singleton- The count of $a$ in the singleton multiset $\{b\}$ is 1 if $a = b$ and 0 otherwise.
Multiset.insert_eq_cons- Inserting an element into a multiset prepends it: $\operatorname{insert} a\ s = a ::ₘ s$.
Multiset.le_iff_count- Multiset inequality $s \le t$ holds if and only if every element's multiplicity in $s$ is at most its multiplicity in $t$.
Multiset.le_iff_subset- For a duplicate-free multiset $s$, multiset inequality $s \le t$ is equivalent to subset inclusion $s \subseteq t$.
Multiset.mem_cons- An element belongs to $b ::ₘ s$ if and only if it equals $b$ or belongs to $s$.
Multiset.mem_singleton- An element belongs to the singleton multiset $\{a\}$ if and only if it equals $a$.
Multiset.nodup_cons- The multiset $a ::ₘ s$ has no duplicates if and only if $a \notin s$ and $s$ has no duplicates.
Multiset.nodup_singleton- A singleton multiset $\{a\}$ has no duplicate elements.
Nat.cast_zero- The canonical coercion of natural number 0 into a ring is 0.
neg_zero- The negation of zero is zero: $-0 = 0$.
Pi.smul_apply- Scalar multiplication of a function or vector is defined pointwise.
Polynomial.IsRoot- A scalar $a$ is a root of polynomial $p$ if evaluating $p$ at $a$ yields zero.
Polynomial.mem_roots- For a nonzero polynomial $p$, an element $a$ belongs to the multiset of roots of $p$ if and only if $p(a) = 0$.
Polynomial.roots_X_pow- The roots of $X^n$ are $n$ copies of 0 as a multiset.
SimpleGraph.adjMatrix_apply- The entry of the adjacency matrix at $(v, w)$ is 1 if $v$ and $w$ are adjacent and 0 otherwise.
SimpleGraph.adjMatrix_mulVec_const_apply_of_regular- In a $d$-regular graph, multiplying the adjacency matrix by the constant vector $a$ gives $d \cdot a$ at each vertex.
SimpleGraph.mem_neighborFinset- A vertex $w$ is in the neighbor finset of $v$ if and only if $v$ and $w$ are adjacent.
smul_eq_mul- Scalar multiplication in a ring agrees with standard multiplication: $a \bullet b = a \cdot b$.
zero_add- Adding zero on the left leaves an element unchanged: $0 + a = a$.
- When $s = 0$, the multiset $\{s, -s\}$ is $\{0, 0\}$, requiring $0$ to have algebraic multiplicity at least 2. This is handled by a separate case showing the adjacency matrix is identically zero and its dimension $2m$ is at least 2.
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_bipartite_adj_charpoly_roots_contain_pm_degree {V W : Type*} [Fintype V] [Fintype W] (m s : ℕ) (hm : 1 ≤ m) (hV : Fintype.card V = m) (hW : Fintype.card W = m) (H : SimpleGraph (V ⊕ W)) (hH_sub : H ≤ completeBipartiteGraph V W) (hH_reg : H.IsRegularOfDegree s) : ({(s : ℝ), -(s : ℝ)} : Multiset ℝ) ≤ (H.adjMatrix ℝ).charpoly.roots := by have hnl : ∀ v v', ¬ H.Adj (Sum.inl v) (Sum.inl v') := by intro v v' h have := hH_sub h simp at this have hnr : ∀ w w', ¬ H.Adj (Sum.inr w) (Sum.inr w') := by intro w w' h have := hH_sub h simp at this set A := H.adjMatrix ℝ with hA have hll : ∀ v v', A (Sum.inl v) (Sum.inl v') = 0 := by intro v v'; rw [hA, SimpleGraph.adjMatrix_apply, if_neg (hnl v v')] have hrr : ∀ w w', A (Sum.inr w) (Sum.inr w') = 0 := by intro w w'; rw [hA, SimpleGraph.adjMatrix_apply, if_neg (hnr w w')] have hrow : ∀ i, ∑ j, A i j = s := by intro i have := SimpleGraph.adjMatrix_mulVec_const_apply_of_regular (α := ℝ) hH_reg (a := 1) (v := i) simp only [Matrix.mulVec, dotProduct, Function.const_apply, mul_one] at this exact this obtain ⟨v0⟩ : Nonempty V := by rw [← Fintype.card_pos_iff]; omega have hroot : ∀ μ : ℝ, ∀ u : V ⊕ W → ℝ, u (Sum.inl v0) ≠ 0 → A.mulVec u = μ • u → μ ∈ A.charpoly.roots := by intro μ u hu h rw [Polynomial.mem_roots (Matrix.charpoly_monic A).ne_zero, Polynomial.IsRoot, Matrix.eval_charpoly, ← Matrix.exists_mulVec_eq_zero_iff] refine ⟨u, fun h0 => hu (by rw [h0]; rfl), ?_⟩ rw [Matrix.sub_mulVec, h] ext i simp [Matrix.scalar_apply, Matrix.mulVec_diagonal] have hplus : (s : ℝ) ∈ A.charpoly.roots := by refine hroot s (fun _ => 1) (by norm_num) ?_ ext i simp only [Matrix.mulVec, dotProduct, mul_one, Pi.smul_apply, smul_eq_mul] rw [hrow i] have hminus : -(s : ℝ) ∈ A.charpoly.roots := by refine hroot (-s) (Sum.elim (fun _ => 1) (fun _ => -1)) (by simp) ?_ ext i have hrow' := hrow i rw [Fintype.sum_sum_type] at hrow' rcases i with v | w · simp only [hll, Finset.sum_const_zero, zero_add] at hrow' simp [Matrix.mulVec, dotProduct, Fintype.sum_sum_type, hll, hrow'] · simp only [hrr, Finset.sum_const_zero, add_zero] at hrow' simp [Matrix.mulVec, dotProduct, Fintype.sum_sum_type, hrr, hrow'] by_cases hs : s = 0 · subst hs have hA0 : A = 0 := by ext i j rw [hA, SimpleGraph.adjMatrix_apply, if_neg] · rfl intro h have h1 : j ∈ H.neighborFinset i := (SimpleGraph.mem_neighborFinset _ _ _).mpr h have h2 : (H.neighborFinset i).card = 0 := hH_reg i rw [Finset.card_eq_zero] at h2 rw [h2] at h1 simp at h1 rw [hA0, Matrix.charpoly_zero, Polynomial.roots_X_pow, Multiset.le_iff_count] intro a simp only [Fintype.card_sum, hV, hW, Multiset.count_nsmul, Nat.cast_zero, neg_zero, Multiset.insert_eq_cons, Multiset.count_cons, Multiset.count_singleton] split_ifs <;> omega · have hne : (s : ℝ) ≠ -(s : ℝ) := by intro h have : (s : ℝ) = 0 := by linarith exact hs (by exact_mod_cast this) rw [Multiset.le_iff_subset] · intro x hx simp only [Multiset.insert_eq_cons, Multiset.mem_cons, Multiset.mem_singleton] at hx rcases hx with rfl | rfl · exact hplus · exact hminus · rw [Multiset.insert_eq_cons, Multiset.nodup_cons] exact ⟨by simpa using hne, Multiset.nodup_singleton _⟩