bipartite_complement_adj_charpoly_mul
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
- 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
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.
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.
uses
bipc_E,bipc_F,Matrix.mul_apply,Fintype.sum_sum_typeext c d fin_cases c <;> fin_cases d <;> simp [bipc_E, bipc_F, Matrix.mul_apply, Fintype.sum_sum_type, hV, hW]
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].
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_zeroext 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]
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⁻¹.
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_oneset 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]
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)².
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_ofhave 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
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.
uses
Matrix.det_mul,Matrix.det_one_add_mul_comm,mul_assocrw [hsplit, Matrix.det_mul, Matrix.det_one_add_mul_comm, hinvE, ← hTdet, mul_assoc, ← Matrix.det_mul, h2, hTFE]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.
uses
SimpleGraph.adjMatrix_apply,if_neg,SimpleGraph.adjMatrix_mulVec_const_apply_of_regular,mul_onehave 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
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.
uses
Matrix.diagonal,Matrix.diagonal_mul_diagonal,Matrix.diagonal_one,Matrix.det_mul,Matrix.det_oneset 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]
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.
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_adjhave 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)
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).
uses
bipc_E,bipc_F,Matrix.eval_charpoly,Matrix.det_mul,one_mulhave 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
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.
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_identityhave 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
- The entrywise matrix identities (such as the product of indicator matrices bipc_FE and the conjugation identity hconj) are verified mechanically by case-splitting on the two bipartite parts and the two indicator columns.
- The passage from the determinant identity at infinitely many points to the polynomial equality relies on Mathlib's Polynomial.eq_of_infinite_eval_eq, using the fact that the product of monic polynomials is nonzero and therefore has only finitely many roots.
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.
/-- 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