petrial_leaf_zero_pivot
For a graph with a leaf v and unique neighbor u, if v is absent from the perturbation then its matrix rank is two plus the rank on the graph obtained by deleting u and v, with the perturbation restricted.
Statement
theorem petrial_leaf_zero_pivot {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v u : V) (F : Finset V) (hF : v ∉ F) (hu : G.Adj v u) (huniq : ∀ w, G.Adj v w → w = u) : (petrial_matrix G F).rank = 2 + (petrial_matrix (G.induce ({u, v}ᶜ : Set V)) (petrial_leaf_restriction v u F)).rank
- Source
- Helper for the partial Petrial leaf recurrence and OP-1239.
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- petrial_leaf_restrictionRestrict a finite vertex subset to the complement of vertices u and v.
- petrial_matrixGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset F : Finset V,…
- petrial_rank_schur_invertibleFor square finite block matrices over a field, if the upper-left block is invertible, the rank of the whole block matrix is the size of…
- Used by 2
- petrial_nullity_poly_leaf_recFor a finite graph G with a degree-one vertex v whose neighbour is u, the nullity generating polynomial of G equals the nullity generating…
- op_1239_candidate36_petrial_coefficientsThe partial Petrial coefficients of op_1239_candidate36 in ranks 27, 28, and 29 are respectively 256, 32640, and 4666944.
The proof, explained
The proof decomposes the petrial matrix into a 2 × 2 block structure corresponding to the pair {v, u} and the remaining vertices {u, v}ᶜ. Because v is not in the perturbation F and has u as its unique neighbor, the 2 × 2 pivot block A is invertible over ℤ/2ℤ with (A⁻¹)₁₁ = 0, while the off-diagonal blocks vanish along the index corresponding to v. Consequently, the Schur complement correction term M₂₁ A⁻¹ M₁₂ is identically zero, so by the Schur complement formula the matrix rank is 2 plus the rank on the induced subgraph on {u, v}ᶜ.
The vertex set V decomposes as {v, u} ⊕ {u, v}ᶜ, giving a block matrix representation M of the petrial matrix.
Because v and u are adjacent, v ≠ u. We define a bijection from Fin 2 to {u, v} sending 0 to v and 1 to u, which together with the complement {u, v}ᶜ yields an equivalence Fin 2 ⊕ {u, v}ᶜ ≃ V. Reindexing the petrial matrix by this equivalence gives the block matrix M.
uses
Subtype.ext,Equiv.ofBijective,Equiv.sumCongr,Equiv.refl,Equiv.Set.sumComplclassical have hvu : v ≠ u := G.ne_of_adj hu let P : Set V := {u, v} let f : Fin 2 → P := fun i => if i = 0 then ⟨v, by simp [P]⟩ else ⟨u, by simp [P]⟩ have hf : Function.Bijective f := by constructor · intro i j h fin_cases i <;> fin_cases j <;> simp_all [f, Subtype.ext_iff] · intro x have hx : (x : V) = u ∨ (x : V) = v := x.2 rcases hx with hx | hx · refine ⟨1, ?_⟩; apply Subtype.ext; simpa [f] using hx.symm · refine ⟨0, ?_⟩; apply Subtype.ext; simpa [f] using hx.symm let pe : Fin 2 ≃ P := Equiv.ofBijective f hf let e : Fin 2 ⊕ (Pᶜ : Set V) ≃ V := (Equiv.sumCongr pe (Equiv.refl _)).trans (Equiv.Set.sumCompl P) let M := (petrial_matrix G F).submatrix e e
The top-left 2 × 2 block of M is A = !![0, 1; 1, d], where d = 1 if u ∈ F and 0 otherwise.
By checking all four index pairs of Fin 2: the (v, v) entry is 0 because simple graphs have no self-loops and v ∉ F; the off-diagonal entries (v, u) and (u, v) are 1 because v and u are adjacent; and the (u, u) entry is d by definition of the perturbation.
uses
Matrix.diagonal_apply,Ne.symmlet d : ZMod 2 := if u ∈ F then 1 else 0 let A : Matrix (Fin 2) (Fin 2) (ZMod 2) := !![0, 1; 1, d] have hA : M.toBlocks₁₁ = A := by ext i j change (petrial_matrix G F) (pe i).1 (pe j).1 = A i j fin_cases i <;> fin_cases j <;> simp [pe, f, A, d, petrial_matrix, Matrix.diagonal_apply, hF, hu, hu.symm, hvu, Ne.symm hvu]
The matrix A is invertible with determinant 1, and the (1, 1) entry of its inverse is zero: (⅟A) 1 1 = 0.
The determinant of A is 0 · d - 1 · 1 = -1 ≡ 1 (mod 2), which is a unit, so A is invertible. Looking at the (0, 1) entry of A · ⅟A = I, the product formula gives A 0 0 * (⅟A) 0 1 + A 0 1 * (⅟A) 1 1 = 0 + 1 * (⅟A) 1 1 = (⅟A) 1 1. Since the identity matrix has 0 in entry (0, 1), we conclude (⅟A) 1 1 = 0.
uses
Matrix.det_fin_two,isUnit_one,Matrix.invertibleOfIsUnitDet,congrArg,mul_invOf_self,Matrix.mul_apply,Fin.sum_univ_twohave hdet : IsUnit A.det := by have hd : A.det = 1 := by simp [A, Matrix.det_fin_two] rw [hd] exact isUnit_one letI : Invertible A := Matrix.invertibleOfIsUnitDet A hdet have hinv : (⅟A) 1 1 = 0 := by have h := congrArg (fun (X : Matrix (Fin 2) (Fin 2) (ZMod 2)) => X 0 1) (mul_invOf_self A) simpa [Matrix.mul_apply, Fin.sum_univ_two, A] using h
The first column of the off-diagonal block M₂₁ and the first row of M₁₂ are both zero.
Any vertex w in the complement {u, v}ᶜ satisfies w ≠ u and w ≠ v. Since u is the unique neighbor of v, w cannot be adjacent to v, nor can it equal v on the diagonal. Thus the (w, v) and (v, w) entries of the petrial matrix vanish.
uses
Matrix.diagonal_apply,Ne.symmhave hcol (i : (Pᶜ : Set V)) : M.toBlocks₂₁ i 0 = 0 := by change (petrial_matrix G F) i.1 v = 0 have hiu : (i : V) ≠ u := by intro h have hi : (i : V) ∉ P := i.2 apply hi simp [P, h] have hiv : (i : V) ≠ v := by intro h have hi : (i : V) ∉ P := i.2 apply hi simp [P, h] have hadj : ¬ G.Adj (i : V) v := fun h => hiu (huniq _ h.symm) simp [petrial_matrix, Matrix.diagonal_apply, hadj, hiv] have hrow (j : (Pᶜ : Set V)) : M.toBlocks₁₂ 0 j = 0 := by change (petrial_matrix G F) v j.1 = 0 have hju : (j : V) ≠ u := by intro h have hj : (j : V) ∉ P := j.2 apply hj simp [P, h] have hjv : (j : V) ≠ v := by intro h have hj : (j : V) ∉ P := j.2 apply hj simp [P, h] have hadj : ¬ G.Adj v (j : V) := fun h => hju (huniq _ h) simp [petrial_matrix, Matrix.diagonal_apply, hadj, Ne.symm hjv]
The Schur complement correction term vanishes: M₂₁ * ⅟A * M₁₂ = 0.
Expanding the matrix product entrywise, the sum over intermediate indices in Fin 2 × Fin 2 vanishes: terms with first index 0 vanish because column 0 of M₂₁ is zero; terms with second index 0 vanish because row 0 of M₁₂ is zero; and the (1, 1) term vanishes because (⅟A) 1 1 = 0.
uses
Matrix.mul_apply,Fin.sum_univ_two,zero_mul,mul_zero,zero_add,add_zero,Matrix.zero_applyhave hprod : M.toBlocks₂₁ * ⅟A * M.toBlocks₁₂ = 0 := by ext i j simp only [Matrix.mul_apply, Fin.sum_univ_two, hcol, hrow, hinv, zero_mul, mul_zero, zero_add, add_zero, Matrix.zero_apply]
The bottom-right block M₂₂ is the petrial matrix of the induced subgraph on {u, v}ᶜ with the restricted perturbation.
For pairs of vertices in {u, v}ᶜ, adjacency in the induced subgraph is identical to adjacency in G, and the diagonal perturbation matches the filtered subset of F on {u, v}ᶜ.
uses
Matrix.diagonal_apply,SimpleGraph.adjMatrix_apply,Subtype.ext_iffhave hD : M.toBlocks₂₂ = petrial_matrix (G.induce ({u, v}ᶜ : Set V)) (petrial_leaf_restriction v u F) := by ext i j change (petrial_matrix G F) i.1 j.1 = _ simp [petrial_matrix, petrial_leaf_restriction, Matrix.diagonal_apply, SimpleGraph.adjMatrix_apply, Subtype.ext_iff]
The rank of the petrial matrix is 2 plus the rank of the petrial matrix of the induced subgraph on {u, v}ᶜ.
Reindexing by an equivalence preserves matrix rank. By the Schur complement rank formula for the 2 × 2 invertible pivot A, the rank is 2 + rank(M₂₂ - M₂₁ * ⅟A * M₁₂). Since the correction term is zero, this simplifies to 2 + rank(M₂₂), which is the desired formula.
uses
petrial_rank_schur_invertible,Matrix.rank_submatrix,sub_zerohave hschur := petrial_rank_schur_invertible A M.toBlocks₁₂ M.toBlocks₂₁ M.toBlocks₂₂ have hrank : M.rank = (Matrix.fromBlocks A M.toBlocks₁₂ M.toBlocks₂₁ M.toBlocks₂₂).rank := by conv_lhs => rw [← M.fromBlocks_toBlocks] rw [hA] rw [← Matrix.rank_submatrix (petrial_matrix G F) e e, ← show M.rank = _ from rfl, hrank, hschur] rw [hprod, sub_zero, hD] simp
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
Subtype.ext_iff- Two elements of a subtype are equal if and only if their underlying values are equal.
Equiv.ofBijective- A bijective function between types induces an equivalence (bijection).
Equiv.sumCongr- Combines two equivalences into an equivalence between their direct sums.
Equiv.refl- The identity equivalence from any type to itself.
Equiv.Set.sumCompl- The sum of a subset and its complement is equivalent to the full type.
Matrix.diagonal_apply- The (i, j) entry of a diagonal matrix is d(i) if i = j and 0 otherwise.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Matrix.det_fin_two- The determinant of a 2 × 2 matrix is ad - bc.
isUnit_one- The element 1 in a monoid is a unit (invertible).
Matrix.invertibleOfIsUnitDet- A square matrix over a commutative ring is invertible if its determinant is a unit.
congrArg- Applying a function to equal arguments yields equal results.
mul_invOf_self- Multiplying an invertible element by its inverse yields 1.
Matrix.mul_apply- The (i, k) entry of the product of two matrices is the sum of products of corresponding entries.
Fin.sum_univ_two- A sum over Fin 2 equals the value at 0 plus the value at 1.
zero_mul- Zero multiplied on the left by any element is zero.
mul_zero- Zero multiplied on the right by any element is zero.
zero_add- Adding zero on the left leaves an element unchanged.
add_zero- Adding zero on the right leaves an element unchanged.
Matrix.zero_apply- Every entry of the zero matrix is zero.
SimpleGraph.adjMatrix_apply- The (v, w) entry of the adjacency matrix is 1 if v and w are adjacent, and 0 otherwise.
petrial_rank_schur_invertible- For a block matrix with invertible top-left block A, its rank is the number of rows of A plus the rank of its Schur complement D - C A⁻¹ B.
Matrix.rank_submatrix- Permuting the rows and columns of a matrix by equivalences preserves its rank.
sub_zero- Subtracting zero leaves an element unchanged.
- In the final step (line 83), `simp` evaluates the cardinality of the index set `Fin 2` to 2 to complete the rank calculation from `petrial_rank_schur_invertible`.
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.
theorem petrial_leaf_zero_pivot {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v u : V) (F : Finset V) (hF : v ∉ F) (hu : G.Adj v u) (huniq : ∀ w, G.Adj v w → w = u) : (petrial_matrix G F).rank = 2 + (petrial_matrix (G.induce ({u, v}ᶜ : Set V)) (petrial_leaf_restriction v u F)).rank := by classical have hvu : v ≠ u := G.ne_of_adj hu let P : Set V := {u, v} let f : Fin 2 → P := fun i => if i = 0 then ⟨v, by simp [P]⟩ else ⟨u, by simp [P]⟩ have hf : Function.Bijective f := by constructor · intro i j h fin_cases i <;> fin_cases j <;> simp_all [f, Subtype.ext_iff] · intro x have hx : (x : V) = u ∨ (x : V) = v := x.2 rcases hx with hx | hx · refine ⟨1, ?_⟩; apply Subtype.ext; simpa [f] using hx.symm · refine ⟨0, ?_⟩; apply Subtype.ext; simpa [f] using hx.symm let pe : Fin 2 ≃ P := Equiv.ofBijective f hf let e : Fin 2 ⊕ (Pᶜ : Set V) ≃ V := (Equiv.sumCongr pe (Equiv.refl _)).trans (Equiv.Set.sumCompl P) let M := (petrial_matrix G F).submatrix e e let d : ZMod 2 := if u ∈ F then 1 else 0 let A : Matrix (Fin 2) (Fin 2) (ZMod 2) := !![0, 1; 1, d] have hA : M.toBlocks₁₁ = A := by ext i j change (petrial_matrix G F) (pe i).1 (pe j).1 = A i j fin_cases i <;> fin_cases j <;> simp [pe, f, A, d, petrial_matrix, Matrix.diagonal_apply, hF, hu, hu.symm, hvu, Ne.symm hvu] have hdet : IsUnit A.det := by have hd : A.det = 1 := by simp [A, Matrix.det_fin_two] rw [hd] exact isUnit_one letI : Invertible A := Matrix.invertibleOfIsUnitDet A hdet have hinv : (⅟A) 1 1 = 0 := by have h := congrArg (fun (X : Matrix (Fin 2) (Fin 2) (ZMod 2)) => X 0 1) (mul_invOf_self A) simpa [Matrix.mul_apply, Fin.sum_univ_two, A] using h have hcol (i : (Pᶜ : Set V)) : M.toBlocks₂₁ i 0 = 0 := by change (petrial_matrix G F) i.1 v = 0 have hiu : (i : V) ≠ u := by intro h have hi : (i : V) ∉ P := i.2 apply hi simp [P, h] have hiv : (i : V) ≠ v := by intro h have hi : (i : V) ∉ P := i.2 apply hi simp [P, h] have hadj : ¬ G.Adj (i : V) v := fun h => hiu (huniq _ h.symm) simp [petrial_matrix, Matrix.diagonal_apply, hadj, hiv] have hrow (j : (Pᶜ : Set V)) : M.toBlocks₁₂ 0 j = 0 := by change (petrial_matrix G F) v j.1 = 0 have hju : (j : V) ≠ u := by intro h have hj : (j : V) ∉ P := j.2 apply hj simp [P, h] have hjv : (j : V) ≠ v := by intro h have hj : (j : V) ∉ P := j.2 apply hj simp [P, h] have hadj : ¬ G.Adj v (j : V) := fun h => hju (huniq _ h) simp [petrial_matrix, Matrix.diagonal_apply, hadj, Ne.symm hjv] have hprod : M.toBlocks₂₁ * ⅟A * M.toBlocks₁₂ = 0 := by ext i j simp only [Matrix.mul_apply, Fin.sum_univ_two, hcol, hrow, hinv, zero_mul, mul_zero, zero_add, add_zero, Matrix.zero_apply] have hD : M.toBlocks₂₂ = petrial_matrix (G.induce ({u, v}ᶜ : Set V)) (petrial_leaf_restriction v u F) := by ext i j change (petrial_matrix G F) i.1 j.1 = _ simp [petrial_matrix, petrial_leaf_restriction, Matrix.diagonal_apply, SimpleGraph.adjMatrix_apply, Subtype.ext_iff] have hschur := petrial_rank_schur_invertible A M.toBlocks₁₂ M.toBlocks₂₁ M.toBlocks₂₂ have hrank : M.rank = (Matrix.fromBlocks A M.toBlocks₁₂ M.toBlocks₂₁ M.toBlocks₂₂).rank := by conv_lhs => rw [← M.fromBlocks_toBlocks] rw [hA] rw [← Matrix.rank_submatrix (petrial_matrix G F) e e, ← show M.rank = _ from rfl, hrank, hschur] rw [hprod, sub_zero, hD] simp