AFTD Auto-Formalizing Theoretical Domains

regular_bipartite_adj_charpoly_roots_contain_pm_degree

theoremverified

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

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.

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

    lines 8–15

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

    lines 16–20

    uses SimpleGraph.adjMatrix_apply, if_neg

      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')]
  3. 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$.

    lines 21–25

    uses SimpleGraph.adjMatrix_mulVec_const_apply_of_regular, Matrix.mulVec, Function.const_apply, mul_one

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

    lines 26–27

    uses Fintype.card_pos_iff

      obtain ⟨v0⟩ : Nonempty V := by
        rw [← Fintype.card_pos_iff]; omega
  5. 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.

    lines 28–36

    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_diagonal

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

    lines 37–41

    uses Matrix.mulVec, mul_one, Pi.smul_apply, smul_eq_mul

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

    lines 42–51

    uses Fintype.sum_sum_type, Finset.sum_const_zero, zero_add, add_zero, Matrix.mulVec

      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']
  8. 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\}$.

    lines 52–68

    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_singleton

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

    lines 69–80

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

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