AFTD Auto-Formalizing Theoretical Domains

bipartite_complement_adj_charpoly_mul

theoremverified

Let H be an s-regular graph contained in the complete bipartite graph on parts V, W of size m, and G = K_{V,W} minus H. Then charpoly(A_G)·(X² − s²) = charpoly(A_H)·(X² − (m − s)²) for the real adjacency matrices.

Statement

open scoped Classical in
theorem bipartite_complement_adj_charpoly_mul
    {V W : Type*} [Fintype V] [Fintype W]
    (m s : ℕ) (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) :
    ((completeBipartiteGraph V W \ H).adjMatrix ℝ).charpoly *
        (Polynomial.X ^ 2 - Polynomial.C ((s : ℝ) ^ 2)) =
      (H.adjMatrix ℝ).charpoly * (Polynomial.X ^ 2 - Polynomial.C (((m : ℝ) - s) ^ 2))
Source
arXiv:2611.00591, Lemma 4.1 (step of its proof)
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • three_token_k2n_domination_number_four_geThe domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is at least 4.
  • FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via ZMod.
Used by 1

The proof, explained

To relate the characteristic polynomials of the complement G = K_{V,W} \\ H and the s-regular bipartite subgraph H on equal parts of size m, we express the adjacency matrix of G as A_G = EF - A_H, where EF is the adjacency matrix of K_{V,W} formed from indicator matrices E and F. Conjugating xI - A_G by the signature matrix D = diag(I_V, -I_W) negates the off-diagonal blocks, showing that charpoly(A_G)(x) = det(xI - A_H + EF). Applying the Weinstein-Aronszajn determinant identity det(1 + AB) = det(1 + BA) alongside the intertwining relation (xI - A_H)E = E !![x, -s; -s, x] reduces the determinant of this rank-2 perturbation to a 2 × 2 determinant, yielding charpoly(A_G)(x) · (x² - s²) = charpoly(A_H)(x) · (x² - (m - s)²) whenever det(xI - A_H) ≠ 0 and x² ≠ s². Because this relation holds at infinitely many points, the identity holds for the polynomials themselves.

  1. The product of the indicator matrices F and E is !![0, m; m, 0]. automation

    Evaluating each of the four entries of the product FE, the sum over V ⊕ W splits into the sum over V and the sum over W. The off-diagonal entries sum the indicator of a single part of size m, yielding m, while the diagonal entries sum identically zero terms.

    lines 13–15

    uses bipc_E, bipc_F, Matrix.mul_apply, Fintype.sum_sum_type

      ext c d
      fin_cases c <;> fin_cases d <;>
        simp [bipc_E, bipc_F, Matrix.mul_apply, Fintype.sum_sum_type, hV, hW]
  2. The matrix (xI - A) intertwines with E via (xI - A)E = E !![x, -s; -s, x].

    For any row index i and column index c, expanding the left-hand side yields x E_{i,c} - (AE)_{i,c}. Since A has row sums s and zero diagonal blocks, the sum of entries of A in row i across the other part is s. Checking the cases c = 0 and c = 1 for i ∈ V and i ∈ W matches the corresponding entries of E !![x, -s; -s, x].

    lines 21–33

    uses Matrix.sub_mul, Matrix.sub_apply, Matrix.scalar_apply, Matrix.diagonal_mul, Fintype.sum_sum_type, Finset.sum_const_zero, zero_add, bipc_E, Matrix.mul_apply, Matrix.diagonal_apply, add_zero

      ext i c
      rw [Matrix.sub_mul, Matrix.sub_apply, Matrix.scalar_apply, Matrix.diagonal_mul]
      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'
        fin_cases c <;>
          simp [bipc_E, Matrix.mul_apply, Fintype.sum_sum_type, Matrix.sub_apply, hll, hrow',
            Matrix.scalar_apply, Matrix.diagonal_apply]
      · simp only [hrr, Finset.sum_const_zero, add_zero] at hrow'
        fin_cases c <;>
          simp [bipc_E, Matrix.mul_apply, Fintype.sum_sum_type, Matrix.sub_apply, hrr, hrow',
            Matrix.scalar_apply, Matrix.diagonal_apply]
  3. Setting N = xI - A and T = !![x, -s; -s, x], both matrices are invertible when their determinants are nonzero, with det(T) = x² - s², and N⁻¹ E = E T⁻¹.

    The determinant of the 2 × 2 matrix T is computed directly as x² - s². Since det(N) ≠ 0 and det(T) ≠ 0, both N and T are units in the matrix ring. From the intertwining relation NE = ET, multiplying by N⁻¹ on the left and by T⁻¹ on the right gives N⁻¹ E = E T⁻¹.

    lines 43–57

    uses bipc_E, bipc_F, Matrix.det_fin_two_of, bipc_AE, Matrix.mul_assoc, Matrix.nonsing_inv_mul, Matrix.one_mul, Matrix.mul_nonsing_inv, Matrix.mul_one

      set N := Matrix.scalar (V ⊕ W) x - A with hNdef
      set E := bipc_E V W
      set F := bipc_F V W
      set T : Matrix (Fin 2) (Fin 2) ℝ := !![x, -s; -s, x] with hT
      have hTdet : T.det = x ^ 2 - s ^ 2 := by
        rw [hT, Matrix.det_fin_two_of]; ring
      have hNE : N * E = E * T := bipc_AE A s hll hrr hrow x
      have hNu : IsUnit N.det := isUnit_iff_ne_zero.mpr hN
      have hTu : IsUnit T.det := isUnit_iff_ne_zero.mpr (by rw [hTdet]; exact hxs)
      have hinvE : N⁻¹ * E = E * T⁻¹ := by
        have h1 : N⁻¹ * (E * T) = E := by
          rw [← hNE, ← Matrix.mul_assoc, Matrix.nonsing_inv_mul _ hNu, Matrix.one_mul]
        calc N⁻¹ * E = N⁻¹ * E * (T * T⁻¹) := by rw [Matrix.mul_nonsing_inv _ hTu, Matrix.mul_one]
          _ = N⁻¹ * (E * T) * T⁻¹ := by simp only [Matrix.mul_assoc]
          _ = E * T⁻¹ := by rw [h1]
  4. The perturbation N + EF factors as N(1 + (N⁻¹E)F), and (1 + F(ET⁻¹))T = T + FE has determinant x² - (m - s)².

    Factoring out N on the left gives N + EF = N(1 + (N⁻¹E)F). Right-multiplying 1 + F(ET⁻¹) by T yields T + FE. Since FE = !![0, m; m, 0], we have T + FE = !![x, m - s; m - s, x], whose determinant is x² - (m - s)².

    lines 58–69

    uses Matrix.mul_add, Matrix.mul_one, Matrix.mul_assoc, Matrix.mul_nonsing_inv, Matrix.one_mul, Matrix.add_mul, Matrix.nonsing_inv_mul, bipc_FE, Matrix.det_fin_two_of

      have hsplit : N + E * F = N * (1 + (N⁻¹ * E) * F) := by
        rw [Matrix.mul_add, Matrix.mul_one, ← Matrix.mul_assoc, ← Matrix.mul_assoc,
          Matrix.mul_nonsing_inv _ hNu, Matrix.one_mul]
      have h2 : (1 + F * (E * T⁻¹)) * T = T + F * E := by
        rw [Matrix.add_mul, Matrix.one_mul, Matrix.mul_assoc, Matrix.mul_assoc,
          Matrix.nonsing_inv_mul _ hTu, Matrix.mul_one]
      have hTFE : (T + F * E).det = x ^ 2 - ((m : ℝ) - s) ^ 2 := by
        rw [bipc_FE m hV hW, hT]
        rw [show (!![x, -s; -s, x] + !![0, (m : ℝ); (m : ℝ), 0] : Matrix (Fin 2) (Fin 2) ℝ) =
          !![x, m - s; m - s, x] by
            ext i j; fin_cases i <;> fin_cases j <;> simp <;> ring]
        rw [Matrix.det_fin_two_of]; ring
  5. The determinant identity det(N + EF) (x² - s²) = det(N) (x² - (m - s)²) holds.

    Taking determinants of the factorization N + EF = N(1 + (N⁻¹E)F) and applying the Weinstein-Aronszajn identity det(1 + (N⁻¹E)F) = det(1 + F(N⁻¹E)) replaces N⁻¹E with ET⁻¹. Multiplying by det(T) = x² - s² combines the factors into det(T + FE) = x² - (m - s)², completing the identity.

    lines 70–71

    uses Matrix.det_mul, Matrix.det_one_add_mul_comm, mul_assoc

      rw [hsplit, Matrix.det_mul, Matrix.det_one_add_mul_comm, hinvE, ← hTdet, mul_assoc,
        ← Matrix.det_mul, h2, hTFE]
  6. The adjacency matrix A of H vanishes on V × V and W × W, and every row sum of A is s.

    Because H is a subgraph of the complete bipartite graph K_{V,W}, no two vertices in V and no two vertices in W are adjacent, so the diagonal blocks of A vanish. Since H is s-regular, multiplying A by the all-ones vector gives s times the all-ones vector, meaning each row sum is s.

    lines 82–108

    uses SimpleGraph.adjMatrix_apply, if_neg, SimpleGraph.adjMatrix_mulVec_const_apply_of_regular, mul_one

      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
      set Ag := (completeBipartiteGraph V W \ H).adjMatrix ℝ with hAg
      have hll : ∀ v v', A (Sum.inl v) (Sum.inl v') = 0 := by
        intro v v'
        rw [hA, SimpleGraph.adjMatrix_apply, if_neg]
        intro h
        have := hH_sub h
        simp at this
      have hrr : ∀ w w', A (Sum.inr w) (Sum.inr w') = 0 := by
        intro w w'
        rw [hA, SimpleGraph.adjMatrix_apply, if_neg]
        intro h
        have := hH_sub h
        simp at this
      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
  7. The diagonal matrix D with +1 on V and -1 on W satisfies D² = 1 and det(D)² = 1.

    Since 1² = 1 and (-1)² = 1, multiplying D by itself gives the identity matrix. By multiplicativity of the determinant, det(D)² = det(D²) = det(1) = 1.

    lines 109–116

    uses Matrix.diagonal, Matrix.diagonal_mul_diagonal, Matrix.diagonal_one, Matrix.det_mul, Matrix.det_one

      set D : Matrix (V ⊕ W) (V ⊕ W) ℝ := Matrix.diagonal (Sum.elim (fun _ => 1) (fun _ => -1))
        with hDdef
      have hD2 : D * D = 1 := by
        rw [hDdef, Matrix.diagonal_mul_diagonal, ← Matrix.diagonal_one]
        congr 1
        ext i
        cases i <;> simp
      have hDD : D.det * D.det = 1 := by rw [← Matrix.det_mul, hD2, Matrix.det_one]
  8. Conjugating xI - A_G by D gives xI - A + EF.

    Conjugation by D negates the off-diagonal blocks of any matrix while preserving its diagonal blocks. Since A_G is bipartite, D A_G D = -A_G. Because G is the bipartite complement K_{V,W} \\ H, its adjacency matrix is A_G = EF - A, so -A_G = A - EF. Hence D(xI - A_G)D = xI - (-A_G) = xI - A + EF, which is verified entrywise across the four blocks.

    lines 117–142

    uses bipc_E, bipc_F, Matrix.mul_diagonal, Matrix.diagonal_mul, Matrix.scalar_apply, Matrix.diagonal_apply, Matrix.mul_apply, Fin.sum_univ_two, SimpleGraph.adjMatrix_apply, Matrix.add_apply, Matrix.sub_apply, SimpleGraph.sdiff_adj, completeBipartiteGraph_adj

      have hconj : ∀ x : ℝ, D * (Matrix.scalar (V ⊕ W) x - Ag) * D =
          Matrix.scalar (V ⊕ W) x - A + bipc_E V W * bipc_F V W := by
        intro x
        ext i j
        rw [hDdef, Matrix.mul_diagonal, Matrix.diagonal_mul]
        rcases i with v | w <;> rcases j with v' | w'
        · have := hll v v'
          simp only [hA] at this
          simp [Matrix.scalar_apply, Matrix.diagonal_apply, bipc_E, bipc_F, Matrix.mul_apply,
            Fin.sum_univ_two, hAg, hA, this, SimpleGraph.adjMatrix_apply, hnl, hnr]
          try (split_ifs <;> simp)
        · simp only [Matrix.add_apply, Matrix.sub_apply, Matrix.scalar_apply, Matrix.diagonal_apply,
            bipc_E, bipc_F, Matrix.mul_apply, Fin.sum_univ_two, hAg, hA, SimpleGraph.adjMatrix_apply,
            SimpleGraph.sdiff_adj, completeBipartiteGraph_adj]
          simp
          split_ifs <;> simp
        · simp only [Matrix.add_apply, Matrix.sub_apply, Matrix.scalar_apply, Matrix.diagonal_apply,
            bipc_E, bipc_F, Matrix.mul_apply, Fin.sum_univ_two, hAg, hA, SimpleGraph.adjMatrix_apply,
            SimpleGraph.sdiff_adj, completeBipartiteGraph_adj]
          simp
          split_ifs <;> simp
        · have := hrr w w'
          simp only [hA] at this
          simp [Matrix.scalar_apply, Matrix.diagonal_apply, bipc_E, bipc_F, Matrix.mul_apply,
            Fin.sum_univ_two, hAg, hA, this, SimpleGraph.adjMatrix_apply, hnl, hnr]
          try (split_ifs <;> simp)
  9. For all real x, the characteristic polynomial of A_G evaluates to det(xI - A + EF).

    The characteristic polynomial evaluation charpoly(A_G)(x) is det(xI - A_G). Using det(D)² = 1 and multiplicativity of determinants, this equals det(D(xI - A_G)D), which by the conjugation identity is det(xI - A + EF).

    lines 143–149

    uses bipc_E, bipc_F, Matrix.eval_charpoly, Matrix.det_mul, one_mul

      have heval : ∀ x : ℝ, Ag.charpoly.eval x =
          (Matrix.scalar (V ⊕ W) x - A + bipc_E V W * bipc_F V W).det := by
        intro x
        rw [Matrix.eval_charpoly, ← hconj x, Matrix.det_mul, Matrix.det_mul]
        calc (Matrix.scalar (V ⊕ W) x - Ag).det
            = (D.det * D.det) * (Matrix.scalar (V ⊕ W) x - Ag).det := by rw [hDD, one_mul]
          _ = _ := by ring
  10. The characteristic polynomial identity charpoly(A_G) · (X² - s²) = charpoly(A_H) · (X² - (m - s)²) holds.

    The polynomial charpoly(A_H) · (X² - s²) is a product of monic polynomials, hence monic and nonzero, so it has only finitely many real roots. For any x that is not a root, det(xI - A_H) ≠ 0 and x² - s² ≠ 0, so the determinant identity bipc_det_identity applies to equate charpoly(A_G)(x) · (x² - s²) with charpoly(A_H)(x) · (x² - (m - s)²). Because two real polynomials that agree on an infinite set must be identical, the equality of polynomials follows.

    lines 150–160

    uses Matrix.charpoly_monic, Polynomial.monic_X_pow_sub_C, Polynomial.eq_of_infinite_eval_eq, Set.Infinite.mono, Polynomial.eval_mul, Polynomial.eval_sub, Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_C, mul_ne_zero_iff, Matrix.eval_charpoly, bipc_det_identity

      have hp : A.charpoly * (Polynomial.X ^ 2 - Polynomial.C ((s : ℝ) ^ 2)) ≠ 0 :=
        ((Matrix.charpoly_monic A).mul (Polynomial.monic_X_pow_sub_C _ (by norm_num))).ne_zero
      apply Polynomial.eq_of_infinite_eval_eq
      refine Set.Infinite.mono ?_ (Polynomial.finite_setOfPred_isRoot hp).infinite_compl
      intro x hx
      simp only [Set.mem_compl_iff, Set.mem_ofPred_eq, Polynomial.IsRoot, Polynomial.eval_mul,
        Polynomial.eval_sub, Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_C] at hx ⊢
      rcases mul_ne_zero_iff.mp hx with ⟨h1, h2⟩
      rw [Matrix.eval_charpoly] at h1
      rw [heval x, Matrix.eval_charpoly]
      exact bipc_det_identity m hV hW A s hll hrr hrow x h1 h2
bipc_E
The indicator matrix of shape (V ⊕ W) × 2 whose two columns are the indicator vectors of the parts V and W
bipc_F
The indicator matrix of shape 2 × (V ⊕ W) whose two rows are the indicator vectors of W and V
Matrix.mul_apply
The (i, j)-entry of a matrix product AB is the sum ∑_k A_{i,k} B_{k,j}
Fintype.sum_sum_type
A sum over the sum type V ⊕ W splits into the sum over V plus the sum over W
Matrix.sub_mul
Right multiplication of matrices distributes over subtraction: (M - M') N = MN - M'N
Matrix.sub_apply
The (i, j)-entry of the difference A - B is A_{i,j} - B_{i,j}
Matrix.scalar_apply
A scalar matrix xI is a diagonal matrix whose diagonal entries all equal x
Matrix.diagonal_mul
Left multiplying a matrix by a diagonal matrix scales row i by the i-th diagonal entry
Finset.sum_const_zero
The sum of zeros over any finite set is zero
zero_add
Adding zero on the left leaves an element unchanged: 0 + a = a
Matrix.diagonal_apply
The (i, j)-entry of a diagonal matrix is its diagonal entry when i = j and 0 otherwise
add_zero
Adding zero on the right leaves an element unchanged: a + 0 = a
Matrix.det_fin_two_of
The determinant of a 2 × 2 matrix with entries a, b, c, d is ad - bc
bipc_AE
For any s-regular bipartite matrix A, (xI - A) E = E !![x, -s; -s, x]
Matrix.mul_assoc
Matrix multiplication is associative: (LM)N = L(MN)
Matrix.nonsing_inv_mul
For an invertible matrix A, A⁻¹ A = 1
Matrix.one_mul
Left multiplying by the identity matrix leaves a matrix unchanged: 1 · M = M
Matrix.mul_nonsing_inv
For an invertible matrix A, A A⁻¹ = 1
Matrix.mul_one
Right multiplying by the identity matrix leaves a matrix unchanged: M · 1 = M
Matrix.mul_add
Left multiplication of matrices distributes over addition: L(M + N) = LM + LN
Matrix.add_mul
Right multiplication of matrices distributes over addition: (L + M)N = LN + MN
bipc_FE
The product of the indicator matrices satisfies FE = !![0, m; m, 0]
Matrix.det_mul
The determinant of a product of square matrices is the product of their determinants: det(MN) = det(M) det(N)
Matrix.det_one_add_mul_comm
The Weinstein-Aronszajn determinant identity det(1 + AB) = det(1 + BA) for rectangular matrices
mul_assoc
Multiplication in a semigroup is associative: (ab)c = a(bc)
SimpleGraph.adjMatrix_apply
The (v, w)-entry of the adjacency matrix is 1 if v and w are adjacent and 0 otherwise
if_neg
An if-then-else expression reduces to its else branch when the condition is false
SimpleGraph.adjMatrix_mulVec_const_apply_of_regular
Multiplying the adjacency matrix of a d-regular graph by the constant vector a gives d · a at each vertex
mul_one
Multiplying an element on the right by 1 leaves it unchanged: a · 1 = a
Matrix.diagonal
The diagonal matrix formed from a given diagonal vector
Matrix.diagonal_mul_diagonal
The product of two diagonal matrices is the diagonal matrix of their pointwise product
Matrix.diagonal_one
The diagonal matrix with all diagonal entries 1 is the identity matrix
Matrix.det_one
The determinant of the identity matrix is 1
Matrix.mul_diagonal
Right multiplying a matrix by a diagonal matrix scales column j by the j-th diagonal entry
Fin.sum_univ_two
A sum over the two-element type Fin 2 equals f(0) + f(1)
Matrix.add_apply
The (i, j)-entry of a sum of matrices A + B is A_{i,j} + B_{i,j}
SimpleGraph.sdiff_adj
Two vertices are adjacent in G \\ H iff they are adjacent in G and not adjacent in H
completeBipartiteGraph_adj
Two vertices in V ⊕ W are adjacent in K_{V,W} iff one belongs to V and the other to W
Matrix.eval_charpoly
The characteristic polynomial of M evaluated at t is det(tI - M)
one_mul
Multiplying an element on the left by 1 leaves it unchanged: 1 · a = a
Matrix.charpoly_monic
The characteristic polynomial of any square matrix is monic
Polynomial.monic_X_pow_sub_C
For n > 0, the polynomial X^n - c is monic
Polynomial.eq_of_infinite_eval_eq
Two polynomials over an integral domain that agree on an infinite set are identical
Set.Infinite.mono
Any set containing an infinite subset is itself infinite
Polynomial.eval_mul
Polynomial evaluation distributes over multiplication: (pq)(x) = p(x) q(x)
Polynomial.eval_sub
Polynomial evaluation distributes over subtraction: (p - q)(x) = p(x) - q(x)
Polynomial.eval_pow
Polynomial evaluation distributes over powers: (p^n)(x) = (p(x))^n
Polynomial.eval_X
The indeterminate polynomial X evaluates at x to x
Polynomial.eval_C
The constant polynomial C(c) evaluates at any point to c
mul_ne_zero_iff
In an integral domain, ab ≠ 0 if and only if a ≠ 0 and b ≠ 0
bipc_det_identity
The determinant identity det(xI - A + EF) (x² - s²) = det(xI - A) (x² - (m - s)²) for an s-regular bipartite matrix 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

/-- the two part indicator columns -/noncomputable def bipc_E (V W : Type*) : Matrix (V ⊕ W) (Fin 2) ℝ :=  Matrix.of fun i c => Sum.elim (fun _ => if c = 0 then (1 : ℝ) else 0)    (fun _ => if c = 1 then (1 : ℝ) else 0) inoncomputable def bipc_F (V W : Type*) : Matrix (Fin 2) (V ⊕ W) ℝ :=  Matrix.of fun c j => Sum.elim (fun _ => if c = 1 then (1 : ℝ) else 0)    (fun _ => if c = 0 then (1 : ℝ) else 0) jtheorem bipc_FE {V W : Type*} [Fintype V] [Fintype W] (m : ℕ)    (hV : Fintype.card V = m) (hW : Fintype.card W = m) :    bipc_F V W * bipc_E V W = !![0, (m : ℝ); (m : ℝ), 0] := by  ext c d  fin_cases c <;> fin_cases d <;>    simp [bipc_E, bipc_F, Matrix.mul_apply, Fintype.sum_sum_type, hV, hW]theorem bipc_AE {V W : Type*} [Fintype V] [Fintype W] [DecidableEq (V ⊕ W)] (A : Matrix (V ⊕ W) (V ⊕ W) ℝ) (s : ℝ)    (hll : ∀ v v', A (Sum.inl v) (Sum.inl v') = 0) (hrr : ∀ w w', A (Sum.inr w) (Sum.inr w') = 0)    (hrow : ∀ i, ∑ j, A i j = s) (x : ℝ) :    (Matrix.scalar (V ⊕ W) x - A) * bipc_E V W = bipc_E V W * !![x, -s; -s, x] := by  ext i c  rw [Matrix.sub_mul, Matrix.sub_apply, Matrix.scalar_apply, Matrix.diagonal_mul]  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'    fin_cases c <;>      simp [bipc_E, Matrix.mul_apply, Fintype.sum_sum_type, Matrix.sub_apply, hll, hrow',        Matrix.scalar_apply, Matrix.diagonal_apply]  · simp only [hrr, Finset.sum_const_zero, add_zero] at hrow'    fin_cases c <;>      simp [bipc_E, Matrix.mul_apply, Fintype.sum_sum_type, Matrix.sub_apply, hrr, hrow',        Matrix.scalar_apply, Matrix.diagonal_apply]theorem bipc_det_identity {V W : Type*} [Fintype V] [Fintype W] [DecidableEq (V ⊕ W)]    (m : ℕ) (hV : Fintype.card V = m) (hW : Fintype.card W = m)    (A : Matrix (V ⊕ W) (V ⊕ W) ℝ) (s : ℝ)    (hll : ∀ v v', A (Sum.inl v) (Sum.inl v') = 0) (hrr : ∀ w w', A (Sum.inr w) (Sum.inr w') = 0)    (hrow : ∀ i, ∑ j, A i j = s) (x : ℝ)    (hN : (Matrix.scalar (V ⊕ W) x - A).det ≠ 0) (hxs : x ^ 2 - s ^ 2 ≠ 0) :    (Matrix.scalar (V ⊕ W) x - A + bipc_E V W * bipc_F V W).det * (x ^ 2 - s ^ 2) =      (Matrix.scalar (V ⊕ W) x - A).det * (x ^ 2 - ((m : ℝ) - s) ^ 2) := by  set N := Matrix.scalar (V ⊕ W) x - A with hNdef  set E := bipc_E V W  set F := bipc_F V W  set T : Matrix (Fin 2) (Fin 2) ℝ := !![x, -s; -s, x] with hT  have hTdet : T.det = x ^ 2 - s ^ 2 := by    rw [hT, Matrix.det_fin_two_of]; ring  have hNE : N * E = E * T := bipc_AE A s hll hrr hrow x  have hNu : IsUnit N.det := isUnit_iff_ne_zero.mpr hN  have hTu : IsUnit T.det := isUnit_iff_ne_zero.mpr (by rw [hTdet]; exact hxs)  have hinvE : N⁻¹ * E = E * T⁻¹ := by    have h1 : N⁻¹ * (E * T) = E := by      rw [← hNE, ← Matrix.mul_assoc, Matrix.nonsing_inv_mul _ hNu, Matrix.one_mul]    calc N⁻¹ * E = N⁻¹ * E * (T * T⁻¹) := by rw [Matrix.mul_nonsing_inv _ hTu, Matrix.mul_one]      _ = N⁻¹ * (E * T) * T⁻¹ := by simp only [Matrix.mul_assoc]      _ = E * T⁻¹ := by rw [h1]  have hsplit : N + E * F = N * (1 + (N⁻¹ * E) * F) := by    rw [Matrix.mul_add, Matrix.mul_one, ← Matrix.mul_assoc, ← Matrix.mul_assoc,      Matrix.mul_nonsing_inv _ hNu, Matrix.one_mul]  have h2 : (1 + F * (E * T⁻¹)) * T = T + F * E := by    rw [Matrix.add_mul, Matrix.one_mul, Matrix.mul_assoc, Matrix.mul_assoc,      Matrix.nonsing_inv_mul _ hTu, Matrix.mul_one]  have hTFE : (T + F * E).det = x ^ 2 - ((m : ℝ) - s) ^ 2 := by    rw [bipc_FE m hV hW, hT]    rw [show (!![x, -s; -s, x] + !![0, (m : ℝ); (m : ℝ), 0] : Matrix (Fin 2) (Fin 2) ℝ) =      !![x, m - s; m - s, x] by        ext i j; fin_cases i <;> fin_cases j <;> simp <;> ring]    rw [Matrix.det_fin_two_of]; ring  rw [hsplit, Matrix.det_mul, Matrix.det_one_add_mul_comm, hinvE, ← hTdet, mul_assoc,    ← Matrix.det_mul, h2, hTFE]open scoped Classical intheorem bipartite_complement_adj_charpoly_mul    {V W : Type*} [Fintype V] [Fintype W]    (m s : ℕ) (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) :    ((completeBipartiteGraph V W \ H).adjMatrix ℝ).charpoly *        (Polynomial.X ^ 2 - Polynomial.C ((s : ℝ) ^ 2)) =      (H.adjMatrix ℝ).charpoly * (Polynomial.X ^ 2 - Polynomial.C (((m : ℝ) - s) ^ 2)) := 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  set Ag := (completeBipartiteGraph V W \ H).adjMatrix ℝ with hAg  have hll : ∀ v v', A (Sum.inl v) (Sum.inl v') = 0 := by    intro v v'    rw [hA, SimpleGraph.adjMatrix_apply, if_neg]    intro h    have := hH_sub h    simp at this  have hrr : ∀ w w', A (Sum.inr w) (Sum.inr w') = 0 := by    intro w w'    rw [hA, SimpleGraph.adjMatrix_apply, if_neg]    intro h    have := hH_sub h    simp at this  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  set D : Matrix (V ⊕ W) (V ⊕ W) ℝ := Matrix.diagonal (Sum.elim (fun _ => 1) (fun _ => -1))    with hDdef  have hD2 : D * D = 1 := by    rw [hDdef, Matrix.diagonal_mul_diagonal, ← Matrix.diagonal_one]    congr 1    ext i    cases i <;> simp  have hDD : D.det * D.det = 1 := by rw [← Matrix.det_mul, hD2, Matrix.det_one]  have hconj : ∀ x : ℝ, D * (Matrix.scalar (V ⊕ W) x - Ag) * D =      Matrix.scalar (V ⊕ W) x - A + bipc_E V W * bipc_F V W := by    intro x    ext i j    rw [hDdef, Matrix.mul_diagonal, Matrix.diagonal_mul]    rcases i with v | w <;> rcases j with v' | w'    · have := hll v v'      simp only [hA] at this      simp [Matrix.scalar_apply, Matrix.diagonal_apply, bipc_E, bipc_F, Matrix.mul_apply,        Fin.sum_univ_two, hAg, hA, this, SimpleGraph.adjMatrix_apply, hnl, hnr]      try (split_ifs <;> simp)    · simp only [Matrix.add_apply, Matrix.sub_apply, Matrix.scalar_apply, Matrix.diagonal_apply,        bipc_E, bipc_F, Matrix.mul_apply, Fin.sum_univ_two, hAg, hA, SimpleGraph.adjMatrix_apply,        SimpleGraph.sdiff_adj, completeBipartiteGraph_adj]      simp      split_ifs <;> simp    · simp only [Matrix.add_apply, Matrix.sub_apply, Matrix.scalar_apply, Matrix.diagonal_apply,        bipc_E, bipc_F, Matrix.mul_apply, Fin.sum_univ_two, hAg, hA, SimpleGraph.adjMatrix_apply,        SimpleGraph.sdiff_adj, completeBipartiteGraph_adj]      simp      split_ifs <;> simp    · have := hrr w w'      simp only [hA] at this      simp [Matrix.scalar_apply, Matrix.diagonal_apply, bipc_E, bipc_F, Matrix.mul_apply,        Fin.sum_univ_two, hAg, hA, this, SimpleGraph.adjMatrix_apply, hnl, hnr]      try (split_ifs <;> simp)  have heval : ∀ x : ℝ, Ag.charpoly.eval x =      (Matrix.scalar (V ⊕ W) x - A + bipc_E V W * bipc_F V W).det := by    intro x    rw [Matrix.eval_charpoly, ← hconj x, Matrix.det_mul, Matrix.det_mul]    calc (Matrix.scalar (V ⊕ W) x - Ag).det        = (D.det * D.det) * (Matrix.scalar (V ⊕ W) x - Ag).det := by rw [hDD, one_mul]      _ = _ := by ring  have hp : A.charpoly * (Polynomial.X ^ 2 - Polynomial.C ((s : ℝ) ^ 2)) ≠ 0 :=    ((Matrix.charpoly_monic A).mul (Polynomial.monic_X_pow_sub_C _ (by norm_num))).ne_zero  apply Polynomial.eq_of_infinite_eval_eq  refine Set.Infinite.mono ?_ (Polynomial.finite_setOfPred_isRoot hp).infinite_compl  intro x hx  simp only [Set.mem_compl_iff, Set.mem_ofPred_eq, Polynomial.IsRoot, Polynomial.eval_mul,    Polynomial.eval_sub, Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_C] at hx ⊢  rcases mul_ne_zero_iff.mp hx with ⟨h1, h2⟩  rw [Matrix.eval_charpoly] at h1  rw [heval x, Matrix.eval_charpoly]  exact bipc_det_identity m hV hW A s hll hrr hrow x h1 h2
See it in the graphDiscuss this resultChallenge it